Algoritmos eficientes para pesquisar uma coleção de árvores

9

Eu tenho um grande conjunto de dados de árvores e gostaria de pesquisá-lo especificando uma árvore (subgrafo conectado). A consulta deve retornar todas as ocorrências da árvore no conjunto de dados.

Existem algoritmos eficientes para fazer isso?

Eu estava pensando em algo como matrizes de sufixo, no entanto, codificar ingenuamente as árvores, pois as seqüências de caracteres (por uma ordem transversal fixa de seus nós) não funcionarão, pois a árvore de busca pode ter qualquer forma arbitrária.

ATUALIZAR:

Alguns detalhes sobre as instâncias típicas que eu espero:

O conjunto de dados consistirá em pelo menos dezenas de milhares de árvores, cada uma consistindo em cerca de vinte a trinta nós. As árvores não serão binárias, mas o número típico de filhos por nó será pequeno (geralmente não maior que quatro ou cinco, embora em alguns casos degenerados possa chegar a cerca de trinta). O número de etiquetas estará na casa das dezenas de milhares.

Eu preciso disso para aplicativos de PNL: cada árvore será a análise de dependência de uma frase, cada nó representando uma palavra oculta e cada rótulo uma palavra de dicionário (com alguma decoração).

graph-algorithms ds.data-structures tree graph-isomorphism string-search Antonio Valério Miceli-Barone
fonte
11
Este volume apresenta uma discussão de algoritmos paralelos para isomorfismo de subárvore.
Anthony Labarre
11
Desculpe, pensei que você estivesse procurando um subgráfico conectado, que necessariamente será uma árvore, aparecendo em um determinado conjunto de árvores. Você poderia esclarecer em que aspectos seu problema difere desta descrição?
Anthony Labarre
11
Você sabe alguma coisa sobre as árvores com antecedência? Binário? Quantos rótulos de nó diferentes você espera? Alguma limitação na eficiência de espaço? Eu pergunto, porque se você estiver executando uma tonelada de consultas no mesmo conjunto de dados, uma solução pode envolver algum tipo de indexação agressiva.
Eli
11
Você está familiarizado com a correspondência de galhos XML? Seu problema parece ser um caso especial; portanto, você pode simplesmente usar qualquer um dos algoritmos e softwares existentes.
Marek Chrobak
2
Eu acho que seria melhor ignorar a estrutura do gráfico. Dada uma consulta típica, se você descartar a estrutura, quantas árvores você antecipa ter todas essas palavras? Suas consultas têm curingas ou são exatas? Se as palavras em uma consulta forem como "O gato comeu o chapéu", quantos gráficos terão realmente as palavras "gato" e "chapéu" nelas? Se você apenas indexar cada palavra para um conjunto de árvores e cruzar todos os conjuntos, potencialmente poderá pesquisar ingenuamente o resultado sem incorrer em um custo muito alto.
Eli

Respostas:

3

Embora não seja especificamente voltada para árvores (enraizadas), acho que a estrutura de dados do G-trie pode ter um desempenho muito bom em sua configuração. É uma adaptação do trie (para pesquisar conjuntos de strings) a gráficos.

Joshua Grochow
fonte
1

Há um tempo atrás, escrevi o algoritmo de canonização em árvore de Ronald Read e o coloquei na wikipedia .

Eu criaria uma hashtable para cada assinatura de nó interno e as rotularia com uma lista de ponteiros para as subárvores de onde elas vieram. No entanto, ele só funcionará para árvores com folhas verdadeiras.

Chad Brewbaker
fonte