algorithm - optimo - ¿Cómo hacer coincidir un árbol con un gran conjunto de patrones?
arboles de busqueda tries (2)
Lo que necesita es una máquina de estados finitos que rastree el conjunto de posibles coincidencias que pueda tener.
Básicamente, una máquina así es el resultado de comparar los patrones entre sí y determinar qué parte de las coincidencias individuales comparten. Esto es análogo a cómo los lexers toman conjuntos de expresiones regulares para los tokens y los componen en un FSA grande que puede hacer coincidir cualquiera de las expresiones regulares procesando los caracteres uno a la vez.
Puede encontrar referencias a métodos para hacer esto en sistemas de reescritura a largo plazo .
Tengo un conjunto potencialmente infinito de símbolos: A, B, C, ... También hay un símbolo distintivo de marcador de posición especial ? (su significado se explicará más abajo).
Considere los árboles finitos no vacíos de modo que cada nodo tenga un símbolo unido a él y 0 o más subárboles no vacíos. El orden de los subárboles de un nodo dado es significativo (por lo que, por ejemplo, si hay un nodo con 2 subárboles, podemos distinguir cuál queda y cuál es el correcto). Cualquier símbolo dado puede aparecer en el árbol 0 de más veces asociado a diferentes nodos. El símbolo de marcador de posición ? se puede adjuntar solo a los nodos hoja (es decir, los nodos que no tienen subárboles). De la definición habitual de árbol se desprende que los árboles son acíclicos.
El requisito de finitud significa que el número total de nodos en un árbol es un entero finito positivo. Se deduce que el número total de símbolos adjuntos, la profundidad del árbol y el número total de nodos en cada subárbol son todos finitos.
Los árboles se dan en una notación funcional: un nodo se representa con un símbolo adjunto y, si hay subárboles, va seguido de un paréntesis que contiene una lista de subárboles separados por comas, representados recursivamente de la misma manera. Entonces, por ejemplo, el árbol
A
/ /
? B
/ /
A C
/|/
A C Q
/
?
se representa como A(?,B(A(A,C,Q(?)),C)) .
Tengo un conjunto preestablecido invariable de árboles S que se usará como patrones para que coincidan. El conjunto generalmente tendrá ~ 10 5 árboles, y cada elemento tendrá típicamente ~ 10-30 nodos. Puedo utilizar un montón de tiempo para crear de antemano cualquier representación de S que mejor se adapte a mi problema que se indica a continuación.
Necesito escribir una función que acepte un árbol T (típicamente con ~ 10 2 nodos) y compruebe lo más rápido posible si T contiene como subárbol cualquier elemento de S , siempre que cualquier nodo con símbolo de marcador de posición ? coincide con cualquier subárbol no vacío (tanto cuando aparece en T como en un elemento de S ).
Sugiera una estructura de datos para almacenar el conjunto S y un algoritmo para verificar si hay una coincidencia. Cualquier lenguaje de programación o un pseudo-código está bien.
Este artículo describe una variante del algoritmo de Aho-Corasick , donde en lugar de usar una máquina de estados finitos (que el algoritmo estándar de Aho-Corasick utiliza para la coincidencia de cadenas), el algoritmo utiliza un autómata de inserción para la coincidencia de subárboles. Al igual que el algoritmo de concordancia de cadenas Aho-Corasick, su variante solo requiere una pasada a través del árbol de entrada para coincidir con el diccionario completo de S.
El documento es bastante complejo: puede valer la pena ponerse en contacto con el autor para ver si tiene algún código fuente disponible.