Как называется структура данных для и-или-списков (или-или-деревьев) и где я могу прочитать об этом? - PullRequest
0 голосов
/ 17 декабря 2018

Недавно мне нужно было создать структуру данных, представляющую собой вложенный список вопросов и / или вопросов.Поскольку почти все интересные вещи были обнаружены кем-то ранее, я ищу название этой структуры данных.это выглядит примерно так:

'((abc) (bde) (c (ab) (fa)))

Интерпретация: я хочу найти abc или bde, caf или caaили cbf или cba, и список включает это.На верхнем уровне каждый элемент объединяется или объединяется, а подсписки верхнего уровня объединяются и объединяются, а подсписки подсписков - или снова подсписки - это и делаются, и подспискииз них или до бесконечности.Обратите внимание, что в моем примере все списки имеют одинаковую длину, в моем реальном приложении списки различаются по длине.

Код для обхода такого «дерева» относительно прост, но я предполагаю, чтоэто название для этого типа дерева, и есть кое-что, что я могу о нем прочитать.

Эти списки эквивалентны регулярным выражениям фиксированной длины (которые я видел как "сетевые выражения", но яособенно интересует эта структура данных и ее представление.

Ответы [ 2 ]

0 голосов
/ 17 декабря 2018

Деревья также являются подмножеством DAWGS - направленных ациклических графов слов , и их можно построить таким же образом.

В моем случае у меня есть очень маленький набор, который я построил вручную, и я не беспокоюсь о получении минимального набора, но вместо этого просто хочу что-то, что я могу легко записать, но имею дело с типамипростых вариаций я вижу.По сути, у меня есть разные способы найти, где я храню свои файлы .el, основываясь на разных структурах каталогов различных операционных систем, которые я использую.(Например, когда я работал в Google, каталог / usr / local / emacs / site-lisp был больше похож на /usr/local/Google/emacs/site-lisp.)

Мне не нужнополное регулярное выражение, но есть около десятка вариантов, некоторые из которых имеют довольно длинные списки вложенных подкаталогов (c: \ users \ cfclark \ appData \ roaming \ emacs.emacs.d или некоторые другие ужасные вещи), которые я хотел написатьвниз (а затем попросите emacs выполнить автоматический поиск, чтобы найти тот, который подходит для данной конкретной установки).И каждый раз, когда я иду на новую работу, я могу просто добавить в список описание того, где они находятся в этой настройке.

В любом случае, по мере того, как этот код развивался, я обнаружил, что я занимался (вложенный, или, и, и, и понял, что структура обобщена на случай чередования или / и / или / и / ...).Итак, я предполагаю, что кто-то должен был открыть это раньше.Я сам намекал на это несколько лет назад, но не собирался его реализовывать.Ссылка mpasko256 Disjunctive Normal Form также особенно важна.Я не нормализуюсь до этого уровня, я все еще держу вложенные «а» и «или» вместо «сглаживания до 2», но у меня действительно есть четкая структура, или «сверху», «тогда» и «тогда», «или» ....

0 голосов
/ 17 декабря 2018

В целом (на очень высоком уровне абстракции) это: Контекстно-свободная грамматика -Wiki

Если вы разрешите бесконечно вкладывать его, тогда это не регулярное выражениеиз-за наличия скобок (левые и правые должны совпадать).

Если учесть, что выражения внутри скобок упорядочены.Я имею в виду, что a and b and c эквивалентно (a and b) and c.Вы получите Двоичное дерево выражений -Wiki

Но для вашего конкретного случая , это, вероятно,: Дизъюнктивная нормальная форма -Wiki

Я не уверен, но моя интуиция говорит, что это снова регулярное выражение, потому что у вас есть только 2 уровня вложенности (1-й - для 'or-ed' и 2-й - для частей 'and-ed')

...