Поиск наиболее частых поддеревьев в коллекции деревьев (синтаксический анализ)

Question

У меня есть коллекция деревьев, узлы которых помечены (но не однозначно). В частности, деревья взяты из набора проанализированных предложений (см. http://en.wikipedia.org/wiki/Treebank). Я хочу извлечь наиболее общие поддеревья из коллекции - производительность еще не проблема. Я был бы благодарен за алгоритмы (в идеале Java) или указатели на инструменты, которые делают это для treebanks. Обратите внимание, что порядок дочерних узлов важен.

EDIT @mjv. Мы работаем в ограниченном домене (химии), который имеет стилизованный язык, поэтому разновидность деревьев не огромна - вероятно, подобна детским читателям. Простой древо «кошка сидела на коврике».

<sentence> 
    <nounPhrase> 
    <article/> 
    <noun/> 
    </nounPhrase> 
    <verbPhrase> 
    <verb/> 
    <prepositionPhrase> 
     <preposition/> 
     <nounPhrase> 
     <article/> 
     <noun/> 
     </nounPhrase> 
    </prepositionPhrase> 
    </verbPhrase> 
</sentence> 

Здесь предложение содержит два идентичных частичные из речи поддерев (фактические лексемы «кошки». «Мат» не важны в согласовании). Таким образом, алгоритм должен будет обнаружить это. Обратите внимание, что не все nounPhrases одинаковы - «большая черная кошка» может быть:

 <nounPhrase> 
     <article/> 
     <adjective/> 
     <adjective/> 
     <noun/> 
     </nounPhrase> 

Длина предложений будет больше - от 15 до 30 узлов. Я ожидал получить полезные результаты от 1000 деревьев. Если это не займет больше дня или около того, это приемлемо.

Очевидно, что чем короче дерево, тем чаще происходит nounPhrase.

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

Answer 1

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

Эта проблема не LCS - наиболее распространенная последовательность не связана с самой длинной общей подпоследовательностью. Наиболее частым поддеревом является то, что происходит больше всего.

Это должно быть в худшем случае O (N L^2) для N деревьев длины L (при условии, что тестирование равенства поддерева, содержащего L-узлов, равно O (L)).

Answer 2

Думаю, хотя вы говорите, что производительность еще не проблема, это NP-трудная проблема, так что никогда не будет возможно быстро ее выполнить. Если я правильно понял, вы можете рассмотреть этот вариант проблемы Longest common subsequence; если вы сглаживаете свое дерево в прямую последовательность, например

(nounphrase)(DOWN)(article:the)(adjective:big)(adjective:black)(noun:cat)(UP) 

Тогда ваша проблема становится LCS.

Wikibooks имеет реализацию Java ЛВП here

Answer 3

Это хорошо известная проблема в информатике, для которой существуют эффективные решения.

Вот некоторые соответствующие ссылки:

Kenji Абэ, Синдзи Kawasoe, Тацуя Асаи, Хироки Arimura, Сеий Арикав, оптимизированный Несущая Discovery для Полуструктурированных данных, Proc.6-я Европейская конференция по принципам и практике обнаружения знаний в базах данных (PKDD-2002), LNAI 2431, Springer-Verlag, 1-14 августа 2002 г.

Мохаммед Дж. Заки, эффективно добыча частых деревьев в лесу, 8-й ACM SIGKDD Международная конференция по обнаружение знаний и интеллектуального анализа данных, июль 2002.

Или, если вы просто хотите быстрый код, иди сюда: FREQT (преобразование XML в S-выражений не должно дать вам слишком много проблем, и оставлен как упражнение для читателя)

Answer 4

В этом случае я нашел инструмент, называемый gspan. Его можно скачать бесплатно по адресу http://www.cs.ucsb.edu/~xyan/software/gSpan.htm. Его версия C++ с интерфейсом matlab находится на http://www.nowozin.net/sebastian/gboost/