algoritmo de coincidencia de árbol?

Question

Estoy trabajando en una biblioteca tree, y parte de la funcionalidad requerida, es poder buscar en un nodo nodos secundarios que coincidan con un patrón.

Un 'patrón' es una especificación (o criterio) que establece la estructura, así como los atributos de los nodos en los subárbol (es) que se emparejarán.

Por ejemplo, supongamos que un árbol representa datos sobre una especie de ave en particular. Supongamos además que los nodos de un árbol como tienen los siguientes atributos:

• ubicación
• sexo
• envergadura
• peso
• brood_size

Dado un nodo padre, lo haría gustaría emitir una búsqueda en inglés común así:

"Tráeme todos los pájaros masculinos que son descendientes de esta ave, y viven en ciudad XXX y tienen un peso> 100g. Cualquier ave que se encuentra también debe tener al menos 2 hermanos y una hermana, y debe tener por sí mismo al menos un hijo"

< nota>

Solo para aclarar, no espero ser capaz para consultar utilizando el inglés sencillo como lo hice anteriormente. Solo utilicé la "consulta en inglés simple" para ilustrar el tipo de coincidencia que me gustaría realizar en el árbol. Espero utilizar símbolos para el emparejamiento (en lugar de simple) texto) en la práctica.

</note>

Estoy pensando en posiblemente el uso de un patrón de tipo regex que coincida con los árboles coincidentes. Una forma sería tener una representación de cadena de cada nodo, así que podría usar una expresión regular normal, pero es probable que sea bastante ineficiente, ya que habrá una gran cantidad de datos repetidos, es decir, la representación de cadena de nodos secundarios será superconjuntos de su representación de los padres, que serán superconjuntos de la cadena de representación de sus padres, y así sucesivamente, recíprocamente, en el árbol (esto podría volverse fácilmente difícil de manejar para árboles de tamaño moderado) tiene que haber una mejor manera.

¿Alguien conoce un algoritmo que me permita seleccionar nodos (subárboles) en un nodo, en función de un patrón?

Aunque pedí un algoritmo general, estoy implementando esto en Python. cualquier fragmento que ilustre tal algoritmo (si se puede escribir) sería inmensamente útil.

Answer 1

Esto depende de su árbol. Si su árbol está rooteado y ordenado, debería poder verificar una coincidencia exacta en el tiempo sublineal, y si no, debería poder buscar una coincidencia en tiempo lineal. Varios algoritmos más rápidos también existen para la coincidencia aproximada.

Para encontrar material y algoritmos para temas como este, Google Scholar es tu amigo. Una búsqueda de concordancia de subárbol o similar debería llevarlo allí.

EDIT: A juzgar por su entrada actualizada, le sugiero que consulte cómo se implementan XPath y lenguajes de consulta similares. XML es un árbol enraizado, y XPath puede buscar árboles secundarios en ese árbol con operadores de coincidencia complejos como los de su ejemplo.

También te aconsejo que no implementes esto por tu cuenta, sino que uses una biblioteca existente (como PyLucene o algún otro motor de búsqueda, que parece apropiado dado el ejemplo que sacaste).

Answer 2

¿Qué hay de malo en escribir un Lisp Sexpression con comodines para describir la coincidencia de árbol? Los paréntesis agrupan un nodo. Los elementos de izquierda a derecha coinciden con la raíz seguida por los niños. Las coincidencias de subárbol usan sexpresiones anidadas para describir el subárbol.

La siguiente se correspondería con un árbol con nodo raíz arbitraria, el primer hijo de ser una hoja A, tercer hijo de ser un subárbol enraizado con X, primer hijo 1 y tercer hijo A:

(?root A ? (X 1 A)) 

Esta idea ISN' t único para mí; los chicos de Lisp han estado escribiendo tales patrones desde principios de los años sesenta.

Aquí está un comparador de patrón LISP (como ejemplo que quería) que sólo se remonta 20 años: http://norvig.com/paip/patmatch.lisp

Sin embargo, esto por sí mismo de codificación es bastante fácil. Esto se asigna típicamente como un ejercicio de tarea para las personas que aprenden LISP.