Эффективные алгоритмы поиска по коллекции деревьев

9

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

Существуют ли эффективные алгоритмы для этого?

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

ОБНОВИТЬ:

Некоторые подробности о типичных случаях, которые я ожидаю:

Набор данных будет состоять как минимум из десятков тысяч деревьев, каждое из которых будет содержать от двадцати до тридцати узлов. Деревья не будут не двоичными, но типичное число детей на узел будет небольшим (обычно не больше четырех или пяти, хотя в некоторых вырожденных случаях оно может достигать около тридцати). Количество этикеток составит десятки тысяч.

Мне это нужно для приложений НЛП: каждое дерево будет анализом зависимости предложения, каждый узел представляет слово вхождения, а каждая метка - словарное слово (с некоторым оформлением).

graph-algorithms ds.data-structures tree graph-isomorphism string-search Антонио Валерио Мицели-Бароне
источник
1
В этом томе обсуждаются параллельные алгоритмы изоморфизма поддеревьев.
Энтони Лабарр
1
Извините, я думал, что вы ищете связанный подграф, который обязательно будет деревом, появляющимся в данном наборе деревьев. Не могли бы вы уточнить, в каких аспектах ваша проблема отличается от этого описания?
Энтони Лабарр
1
Вы знаете что-нибудь о деревьях заранее? Binary? Сколько разных меток узлов вы ожидаете? Есть ли ограничения по эффективности использования пространства? Я спрашиваю, потому что, если вы выполняете тонну запросов к одному и тому же набору данных, решение может включать некоторый тип агрессивной индексации.
Эли
1
Вы знакомы с соответствием ветки XML? Ваша проблема, кажется, особый случай, поэтому вы можете просто использовать любой из существующих алгоритмов и программного обеспечения.
Марек Чробак
2
Я думаю, что было бы лучше игнорировать структуру графа. Учитывая типичный запрос, если вы отбросите структуру, сколько деревьев вы ожидаете иметь все эти слова? В ваших запросах есть какие-то символы подстановки или они точные? Если слова в запросе похожи на «Кот съел шляпу», то сколько графиков на самом деле содержат слова «кот» и «шляпа»? Если вы просто индексируете каждое слово для набора деревьев, а затем пересекаете все наборы, потенциально вы можете наивно искать результат, не неся слишком больших затрат.
Эли

Ответы:

3

Несмотря на то, что они не предназначены специально для (укоренившихся) деревьев, я думаю, что структура данных G-trie вполне может работать в ваших условиях. Это адаптация дерева (для поиска наборов строк) к графам.

Джошуа Грохов
источник
1

Некоторое время назад я написал алгоритм канонизации дерева Рональда Рида и поместил его в википедии .

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

Чад Brewbaker
источник