array algorithm suffix-tree

algorithm - array - suffix tree c++



muy difícil de entender el árbol de sufijos (3)

En primer lugar, hay muchas formas de construir un árbol de sufijos. Existe el método original O (n) de Weiner (1973), el mejorado de McCreight (1976), el más conocido de Ukkonen (1991/1992) y varias mejoras adicionales, en gran parte relacionadas con la implementación y el almacenamiento. Consideraciones de eficiencia. La más notable entre ellas es quizás la implementación eficiente de árboles de sufijos perezosos por Giegerich y Kurtz.

Además, dado que la construcción directa de matrices de sufijos ha sido posible en O (n) en 2003 (por ejemplo, utilizando el algoritmo Skew , pero también existen otros), y ya que existen métodos bien estudiados para

Arreglos de sufijos son generalmente preferidos a los árboles de sufijos. Por lo tanto, si su intención es construir una implementación altamente optimizada para un propósito específico, es posible que desee estudiar el estudio de los algoritmos de construcción de matrices de sufijos.

Sin embargo, si su interés está en la construcción del árbol de sufijos, y en particular en el algoritmo de Ukkonen, me gustaría sugerirle que analice detenidamente la descripción en esta publicación SO , que ya mencionó, e intentamos mejorar esa descripción juntos. . Sin duda, está lejos de ser una explicación perfectamente intuitiva.

Para responder a la pregunta sobre cómo comparar la cadena de entrada con las etiquetas de borde: por razones de eficiencia durante la construcción y la búsqueda, el carácter inicial de cada etiqueta de borde generalmente se almacena en el nodo. Pero el resto debe consultarse en la cadena de texto principal, como dijo, y de hecho esto puede causar problemas, en particular cuando la cadena es tan grande que no se puede guardar fácilmente en la memoria. Eso (más el hecho de que, como cualquier implementación directa de un árbol, el árbol de sufijos es una estructura de datos que contiene una gran cantidad de punteros, que consumen mucha memoria y hacen que sea difícil mantener la localidad de referencia y beneficiarse del almacenamiento en memoria caché ) es una de las razones principales por las que los árboles de sufijos son mucho más difíciles de manejar que, por ejemplo, los índices invertidos.

He estado buscando tutoriales sobre el árbol de sufijos durante bastante tiempo. En SO, encontré 2 publicaciones sobre la comprensión del árbol de sufijos: 1 , 2 .

Pero no puedo decir que entiendo cómo construir uno, Oops. En el manual de diseño del algoritmo de Skiena, dice:

Como los algoritmos de construcción de árboles de sufijos lineales no son triviales, recomiendo usar una implementación existente.

Bueno, ¿es tan difícil el algoritmo de construcción en línea para el árbol de sufijos? ¿Alguien me puede poner en la dirección correcta para entenderlo?

De todos modos, a la caza, además de la construcción, hay una cosa más que no entiendo sobre el árbol de sufijos. Debido a que los bordes en el árbol de sufijos son solo un par de enteros (¿correcto?) Que especifican la posición inicial y final de la subcadena, entonces, si quiero buscar una cadena x en este árbol de sufijos, ¿cómo debo hacerlo? ¿Desreferir esos enteros en el árbol de sufijos, luego compararlos uno por uno con x ? No podría ser así.

Si combina la matriz de sufijos con una tabla lcp y una tabla secundaria , lo que, por supuesto, debería hacer, esencialmente obtiene un árbol de sufijos. Este punto se explica en el documento: Árboles de sufijo linealizados de Kim, Park y Kim. La tabla lcp permite un recorrido ascendente bastante torpe, y la tabla secundaria permite un recorrido fácil de cualquier tipo. Así que la historia sobre árboles de sufijos que usan punteros que causan problemas de localización de referencia es, en mi opinión, información obsoleta. El árbol de sufijos es, por lo tanto, `` la manera correcta y fácil de seguir '''', siempre y cuando implementes el árbol utilizando una matriz de sufijos subyacente.

El documento de Kim, Park y Kim describe una variante del enfoque en el artículo de título engañoso de Abouelhoda et al: Reemplazo de árboles de sufijos con arreglos de sufijos mejorados . El documento de Kim et al. Aclara que esta es una implementación de árboles de sufijos, y no un reemplazo . Además, los detalles de la construcción de Abouelhoda et al se describen de manera más simple e intuitiva en Kim et al.

,

hay una implementación de la construcción lineal de ukkonen de árboles de sufijos (más matrices de sufijos, matriz lcp) aquí: http://code.google.com/p/text-indexing/ . La visualización provista junto con el sufixtree.js puede ayudar