Алгоритм соответствия дерева?
Я работаю над древовидной библиотекой и частью необходимой функциональности, должен смочь искать узел дочерние узлы, которые соответствуют шаблону.
'Шаблон' является спецификацией (или критерии), который размечает структуру, а также атрибуты узлов в поддереве (поддеревьях), которое будет согласовано.
Например, предположите, что дерево представляет данные относительно конкретного вида птицы. Далее предположите, что узлы такого дерева имеют следующие атрибуты:
- местоположение
- пол
- размах крыла
- вес
- brood_size
Учитывая родительский узел, я хотел бы выпустить поиск без обиняков таким образом:
"Выберите меня все штекерные птицы, которые являются потомками этой птицы, и живой в XXX городах и имеют вес> 100 г. Любая такая найденная птица должна также иметь по крайней мере 2 братьев и одну сестру, и должна самостоятельно иметь по крайней мере одного ребенка"
<примечание>
Просто для уточнения я не ожидаю мочь запросить простой английский язык использования, поскольку я сделал выше. Я только использовал "простой английский запрос" для иллюстрирования типа соответствия, которое я хотел бы выполнить на дереве. Я полностью ожидаю использовать символы для соответствия (в противоположность простому тексту) на практике.
Я думаю о возможном использовании сопоставления с образцом типа regex для соответствия деревьям. Один путь состоял бы в том, чтобы иметь строковое представление каждого узла, таким образом, я мог использовать нормальный regex - но это вероятно из быть довольно неэффективным, поскольку будет много повторных данных - т.е. строковое представление дочерних узлов будет надмножествами их родительского представления, которое будет надмножествами их родителей представительная строка, и так далее, рекурсивно, дерево - это могло очень легко стать громоздким для события, скромно измерил деревья - должен быть лучший путь.
Кто-либо знает об алгоритме, который позволит мне выбирать узлы (поддеревья) в узле, на основе шаблона?
Хотя я попросил общий алгоритм, я реализую это в Python. любые отрывки, которые далее иллюстрируют такой алгоритм (если бы можно действительно быть записаны), были бы очень полезны.
2 ответа
Это зависит от вашего дерева. Если ваше дерево укоренено и упорядочено, вы должны иметь возможность проверить точное совпадение в сублинейном времени, а если нет, вы должны иметь возможность проверить совпадение в линейном времени. Также существует несколько более быстрых алгоритмов приблизительного сопоставления.
Чтобы найти материалы и алгоритмы для подобных тем, Google Scholar станет вашим другом. Поиск совпадения поддерева или чего-то подобного должен привести вас туда.
РЕДАКТИРОВАТЬ: Судя по вашей обновленной записи, я предлагаю вам взглянуть на то, как реализованы XPath и подобные языки запросов. XML - это корневое дерево, и XPath может искать поддеревья в этом дереве с помощью сложных операторов сопоставления, подобных тем, что в вашем примере.
Я также советую вам не реализовывать это самостоятельно, а лучше использовать существующую библиотеку (например, PyLucene или другую поисковую систему, что кажется подходящим с учетом приведенного вами примера).
Что плохого в написании секвенции Lisp с подстановочными знаками для описания совпадения дерева? Круглые скобки группируют узел. Элементы слева направо соответствуют корню, за которым следуют дочерние элементы. Сопоставления поддерева используют вложенные выражения для описания поддерева.
Следующее будет соответствовать дереву с произвольным корневым узлом, первый дочерний элемент является листом A, третий дочерний элемент является поддеревом с корнем X, первый дочерний элемент 1 и третий дочерний элемент A:
(?root A ? (X 1 A))
Эта идея не уникальна для меня; ребята из Лиспа писали такие шаблоны с начала шестидесятых.
Вот сопоставитель шаблонов LISP (в качестве примера, который вам нужен), которому всего 20 лет: http://norvig.com/paip/patmatch.lisp
Однако самому написать код довольно просто. Обычно это домашнее задание для людей, изучающих LISP.