Алгоритм сопоставления деревьев?

Question

Я работаю над библиотекой tree , и частью необходимой функциональности является возможность поиска узла для дочерних узлов, которые соответствуют шаблону.

'Шаблон' - это спецификация (или критерии), которая определяет структуру, а также атрибуты узлов в поддереве (ах), которые должны быть сопоставлены.

Например, предположим, что дерево представляет данные, касающиеся определенного вида птиц. Далее предположим, что узлы такого дерева имеют следующие атрибуты:

• место
• пол
• размах крыльев
• вес
• brood_size

Учитывая родительский узел, я хотел бы выполнить поиск на простом английском языке таким образом:

"Принеси мне всех самцов птиц, которые потомки этой птицы и живут в XXX города и имеют вес> 100 г. Любая такая найденная птица также должна иметь как минимум 2 брата и одну сестру и сама должна иметь хотя бы одного ребенка "

Просто чтобы уточнить, я не ожидаю, что смогу делать запросы, используя простой английский, как я делал выше. Я использовал только «простой английский запрос», чтобы проиллюстрировать тип соответствия, которое я хотел бы выполнить в дереве. Я полностью ожидаю использовать символы для сопоставления (в отличие от простого текста) на практике.

Я думаю о возможном использовании сопоставления с типом регулярных выражений для сопоставления деревьев. Одним из способов было бы иметь строковое представление каждого узла, поэтому я мог бы использовать обычное регулярное выражение - но это, вероятно, будет довольно неэффективно, так как будет много повторяющихся данных - то есть строковое представление дочерних узлов будет надмножеством их родительское представление, которое будет надмножеством репрезентативной строки их родителей и т. д., рекурсивно, вверх по дереву - это может очень легко стать громоздким для деревьев со скромными размерами событий - должен быть лучший путь.

Кто-нибудь знает алгоритм, который позволит мне выбирать узлы (поддеревья) в узле на основе шаблона?

Хотя я попросил общий алгоритм, я реализую его на Python. любые фрагменты, которые дополнительно иллюстрируют такой алгоритм (если он действительно может быть написан), были бы чрезвычайно полезны.

Answer 1

Что не так с написанием Lisp Sexpression с символами подстановки для описания соответствия дерева? Скобки группируют узел. Элементы слева направо соответствуют корню, за которым следуют дочерние элементы. Соответствия поддереву используют вложенные выражения для описания поддерева.

Следующее будет соответствовать дереву с произвольным корневым узлом, первый дочерний элемент - лист A, третий дочерний элемент - поддерево с корнем X, первый дочерний элемент 1 и третий дочерний A:

(?root A ? (X 1 A))

Эта идея не уникальна для меня; парни из Lisp пишут такие паттерны с начала шестидесятых.

Вот сопоставитель шаблонов LISP (как пример, который вы хотели), который существует всего 20 лет назад: http://norvig.com/paip/patmatch.lisp

Тем не менее, самостоятельно написать это довольно просто. Обычно это делается как домашнее задание для людей, изучающих LISP.

Answer 2

Это зависит от вашего дерева. Если ваше дерево укоренено и упорядочено, вы должны быть в состоянии проверить точное совпадение в сублинейное время, а если нет, вы сможете проверить совпадение в линейное время. Существует несколько более быстрых алгоритмов для приблизительного сопоставления.

Для поиска материалов и алгоритмов для подобных тем Google Scholar - ваш друг. Поиск подходящего поддерева или аналогичного должен привести вас туда.

РЕДАКТИРОВАТЬ: Судя по вашей обновленной записи, я предлагаю вам взглянуть на то, как реализованы XPath и аналогичные языки запросов. XML является корневым деревом, и XPath может искать в этом дереве поддеревья с помощью сложных операторов сопоставления, подобных тем, что в вашем примере.

Я также советую вам не реализовывать это самостоятельно, а использовать существующую библиотеку (например, PyLucene или какую-либо другую поисковую систему, что представляется целесообразным, учитывая приведенный вами пример).