Algoritmos eficientes para buscar una colección de árboles.

9

Tengo un gran conjunto de datos de árboles y me gustaría buscarlo especificando un treelet (subgrafo conectado). La consulta debe devolver todas las ocurrencias del treelet en el conjunto de datos.

¿Hay algoritmos eficientes para hacerlo?

Estaba pensando en algo así como matrices de sufijos, sin embargo, codificar ingenuamente los árboles como cadenas (mediante un orden transversal fijo de sus nodos) no funcionará, ya que el treelet de búsqueda puede tener cualquier forma arbitraria.

ACTUALIZAR:

Algunos detalles sobre las instancias típicas que espero:

El conjunto de datos consistirá en al menos decenas de miles de árboles, cada uno de los cuales constará de veinte a treinta nodos. Los árboles no serán binarios, pero el número típico de niños por nodo será pequeño (generalmente no mayor de cuatro o cinco, aunque en algunos casos degenerados puede llegar a unos treinta). El número de etiquetas estará en las decenas de miles.

Lo necesito para las aplicaciones de PNL: cada árbol será el análisis de dependencia de una oración, cada nodo representará la aparición de una palabra y cada etiqueta será una palabra del diccionario (con algo de decoración).

graph-algorithms ds.data-structures tree graph-isomorphism string-search Antonio Valerio Miceli-Barone
fuente
1
Este volumen presenta una discusión de algoritmos paralelos para el isomorfismo de subárbol.
Anthony Labarre
1
Lo siento, pensé que estabas buscando un subgrafo conectado, que necesariamente será un árbol, que aparecerá en un conjunto de árboles. ¿Podría aclarar en qué aspectos su problema difiere de esta descripción?
Anthony Labarre
1
¿Sabes algo de los árboles de antemano? ¿Binario? ¿Cuántas etiquetas de nodo diferentes espera? ¿Alguna limitación en la eficiencia del espacio? Le pregunto porque si está ejecutando un montón de consultas en el mismo conjunto de datos, una solución podría involucrar algún tipo de indexación agresiva.
Eli
1
¿Está familiarizado con la coincidencia de ramitas XML? Su problema parece ser un caso especial, por lo que simplemente puede usar cualquiera de los algoritmos y software existentes.
Marek Chrobak
2
Supongo que sería mejor ignorar la estructura gráfica. Dada una consulta típica, si descarta la estructura, ¿cuántos árboles anticipa tener todas estas palabras? ¿Sus consultas tienen comodines o son exactas? Si las palabras en una consulta son como "El gato se comió el sombrero", ¿cuántos gráficos tendrán en realidad las palabras "gato" y "sombrero"? Si simplemente indexa cada palabra a un conjunto de árboles, luego se cruza con todos los conjuntos, potencialmente podría buscar ingenuamente el resultado sin incurrir en un costo excesivo.
Eli

Respuestas:

3

Aunque no está específicamente dirigido a árboles (enraizados), creo que la estructura de datos G-trie podría funcionar bastante bien en su entorno. Es una adaptación del trie (para buscar conjuntos de cadenas) a gráficos.

Joshua Grochow
fuente
1

Hace un tiempo escribí el algoritmo de canonización de árboles de Ronald Read y lo puse en wikipedia .

Haría una tabla hash para cada firma de nodo interno y las etiquetaría con una lista de punteros de vuelta a los subárboles de los que provienen. Sin embargo, solo funcionará para las cochinillas con hojas verdaderas.

Chad Brewbaker
fuente