Árbol de sufijos

Un árbol de sufijos es un árbol que contiene todos los sufijos de alguna cadena (y solo ellos). Le permite averiguar si la cadena w está incluida en la cadena original t en tiempo O (|w|) , donde |w| es la longitud de la cadena w .

Definiciones básicas y descripción de la estructura

$\Sigma$ es un conjunto finito no vacío de símbolos, llamado alfabeto. Una secuencia de caracteres (posiblemente vacíos) del alfabeto se denota con las letras r , s y t . es una cadena invertida. Los caracteres individuales se indican con las letras x, y o z. - línea vacía. $t^{{-1}}$ $\varepsilon$
Los símbolos del alfabeto son las letras a, b,… . Mientras que el tamaño del alfabeto se toma constante. |t| denota la longitud de la cadena t . son todas cadenas de longitud m, y . $\Sigma^{m}$ $\Sigma ^{*}=\bigcup \limits _{{i=0}}^({\infty}}\Sigma ^{i}$ $\Sigma ^{+}=\Sigma ^{*}\barra invertida \{\varepsilon \}$

El prefijo w de la cadena t es una cadena tal que wv = t para alguna cadena v (posiblemente vacía). Un prefijo se llama propio si |v| 0. $\neq$

El sufijo w de la cadena t es una cadena tal que vw = t para alguna cadena v (posiblemente vacía). Un sufijo se llama propio si |v| 0. Por ejemplo, para la cadena "subcadena", la subcadena "sub" es su propio prefijo, "anillo" es su propio sufijo. $\neq$

Una subcadena w de una cadena t se denomina rama derecha si t se puede representar como para algunas cadenas y también como letras x y . La rama izquierda se define de manera similar. Por ejemplo, para "eabceeabcd", la subcadena "abc" es la rama derecha, ya que en sus dos ocurrencias en t hay diferentes caracteres a la derecha de la misma, pero la misma subcadena no es una rama izquierda, porque el mismo carácter " mi". $uwxv$ $u'wyv'$ $tu, tu, tu'$ $v'$ $\neq$

$\Sigma^{+}$ -tree T es un árbol enraizado con bordes etiquetados por secuencias de . Para cada carácter a del alfabeto, cada nodo del árbol T tiene como máximo una arista cuya etiqueta comienza con el carácter a . Un borde de t a s con la etiqueta v se denotará por . $\Sigma^{+}$ $t\longrightarrow _{v}s$

Sea k un nodo del -tree T , entonces path(k) es una cadena que es la concatenación de todas las etiquetas de borde desde la raíz hasta k . Llamaremos a la ubicación w para la que path( ) = w . $\Sigma^{+}$ $\sobrelínea {w}$ $\sobrelínea {w}$

Como cada rama es única, si path( t ) = w , podemos designar el nodo t como . El subárbol de un nodo se denota por . Las palabras que están representadas en el -árbol T están dadas por un conjunto, que se denota por palabras ( T ). La palabra w está incluida en el conjunto de palabras ( T ) si y solo si existe una cadena v (posiblemente vacía) tal que sea un nodo del árbol T. $\sobrelínea {w}$ $\sobrelínea {w}$ $T_{{\overline {w))}$ $\Sigma^{+}$ $\sobrelínea {wv}$

Si la cadena w está incluida en las palabras ( T ), w = uv , es un nodo del árbol T , el par se llamará par de enlaces w con respecto al árbol T. Si u es el prefijo más largo, de modo que es un par de enlaces, lo llamaremos par de enlaces canónicos . Luego escribiremos . Se dice que una ubicación es explícita si |v| = 0, e implícito en caso contrario. $\sobrelínea {u}$ $(\sobrelínea {u},v)$ $(\sobrelínea {u},v)$ $(\sobrelínea {u},v)$ $\widehat {w}=(\overline {u},v)$ $\widehat {w}=(\overline {u},v)$

$\Sigma^{+}$ -El árbol T en el que cada arista está etiquetada con un solo símbolo se denomina atómico (por ello cada ubicación es explícita). -tree T en el que cada nodo es una raíz, una hoja o una rama se llama compacto . $\Sigma^{+}$

Un árbol atómico también se llama (haz). Un árbol atómico y uno compacto se definen únicamente por las palabras que contienen. $\Sigma^{+}$ $probar$ $\Sigma^{+}$

El árbol de sufijos para la cadena t es un árbol tal que las palabras ( T ) = { w | w es una subpalabra de t }. Para una cadena t , el árbol de sufijos atómicos se denota ast( t ), el árbol de sufijos compacto se denota cst( t ). $\Sigma^{+}$

El árbol de prefijos inverso de la cadena t es el árbol de sufijos para la cadena . $t^{{-1}}$

Un sufijo anidado es un sufijo que se incluye en la cadena t en algún otro lugar. El sufijo anidado más largo se llama sufijo activo de la cadena t .

Propiedades de los árboles de sufijos

Lema. La ubicación de w es explícita en un árbol de sufijos compacto si y solo si w es un sufijo no anidado de t o w es una rama derecha.

Prueba. . Si es explícito, entonces puede ser una hoja, un vértice de rama o una raíz (en este caso , w también es un sufijo anidado de t ). $\Flecha correcta$ $\sobrelínea {w}$ $w=\varepsilon$

Si es una hoja, entonces también es un sufijo t . Por lo tanto, no debe ser un sufijo anidado, porque de lo contrario aparecería en otro lugar de la cadena t : v es un sufijo de t tal que w es un prefijo de v . Este nodo no puede ser una hoja. $\sobrelínea {w}$ $\existe$

Si es un nodo de rama, debe haber al menos dos bordes salientes con etiquetas diferentes. Esto significa que hay dos sufijos diferentes u , v , que w es un prefijo de u y w es un prefijo de v , donde v = wxs , u = , x . Por lo tanto , w es una rama derecha. $\sobrelínea {w}$ $\sobrelínea {w}$ $de wx$ $\neq x'$

$\Flecha izquierda$ . Si w es un sufijo no anidado de t , debe ser una hoja. Si w es una rama derecha, entonces hay dos sufijos u y v , u = wxs , v = , x , entonces w es un nodo de rama. El lema está probado . $de wx$ $\neq x'$

Ahora es fácil ver por qué la respuesta a la pregunta de si la palabra w está en la cadena t se puede encontrar en el tiempo O(|w|) : uno solo necesita verificar si w es una ubicación (explícita o implícita) en cst( t ).

Las etiquetas de borde deben ser punteros a la posición en la cadena para que el árbol de sufijos consuma memoria O(n) . La etiqueta de borde (p, q) significa una subcadena o la cadena vacía si p > q. $t_{p}\ldots t_{q}$

Ukkonen introduce el nombre de bordes abiertos para los bordes que terminan en hojas. Las etiquetas de borde abierto se escriben como (p, ) $\infty$ en lugar de (p, |t|) , donde es la longitud, siempre mayor que |t| . $\infty$

Sea T un -árbol. Sea un nodo T , v sea el sufijo w más largo tal que también sea un nodo T . Un borde sin etiqueta de a se llama enlace de sufijo . Si v = w , se llama atómico . $\Sigma^{+}$ $\sobrelínea {aw}$ $\overline {v}$ $\sobrelínea {aw}$ $\overline {v}$

Declaración. En ast( t ) y cst( t$ ), donde $ t , todos los enlaces de sufijos son atómicos. $\no en$

Prueba. El símbolo $ se llama símbolo de guardia . La primera parte (para ast( t )) se deriva de la definición, ya que las ubicaciones son explícitas. Para probar la segunda parte (caso cst( t )) tenemos que demostrar que para todo nodo también hay un nodo cst( t ). Si es un nodo cst( t ), entonces es un nodo hoja o rama. Si es una hoja, entonces aw no es un sufijo anidado de t . Gracias al símbolo de guardia, del lema se deduce que todos los sufijos (incluida la raíz, el sufijo vacío) son explícitos, ya que solo la raíz es un sufijo incrustado. Por tanto , w es una hoja o una raíz. Si es un nodo de rama, entonces aw es una rama derecha, al igual que w . Por lo tanto, la ubicación es explícita por el lema. La afirmación ha sido probada. $\sobrelínea {aw}$ $\sobrelínea {w}$ $\sobrelínea {aw}$ $\sobrelínea {aw}$ $\sobrelínea {w}$

Como se desprende de esta prueba, el símbolo de guardia garantiza la existencia de hojas para todos los sufijos. Con tal carácter, no puede haber sufijos anidados que no sean vacíos. Si omitimos el carácter de guardia, algunos sufijos pueden anidarse y sus ubicaciones quedar implícitas.

Requisitos de memoria del árbol de sufijos

Declaración. Un árbol de sufijos compacto se puede representar en una forma que requiere memoria O(n) .

Prueba. El árbol de sufijos contiene como máximo una hoja por sufijo (exactamente una con carácter de guardián). Cada nodo interno debe ser un nodo de rama, por lo que un nodo interno tiene al menos dos hijos. Cada rama aumenta el número de hojas en al menos una, por lo que tenemos como máximo n nodos internos y como máximo n hojas.

Para representar cadenas que son etiquetas de borde, usamos la indexación en la cadena de origen, como se describe anteriormente. Cada nodo tiene como máximo un padre y, por lo tanto, el número total de aristas no supera los 2n .

De manera similar, cada nodo tiene como máximo un enlace de sufijo, entonces el número total de enlaces de sufijo también está limitado a 2n . La afirmación ha sido probada.

Como ejemplo de un árbol de sufijos con 2n-1 nodos, considere el árbol de la palabra . El tamaño del árbol de sufijos atómicos para la cadena t es O( ) . ${\ estilo de visualización a^{n}\$}$ $n^{2}$

Construcción de un árbol en tiempo lineal. algoritmo mcc . (Algoritmo de McCreight)

El algoritmo mcc comienza con un árbol vacío y agrega sufijos comenzando desde el más largo. El algoritmo mcc no es un algoritmo en línea, es decir, se requiere toda la línea para su funcionamiento. El correcto funcionamiento requiere que la cadena esté terminada por un carácter especial distinto de los demás, de forma que ningún sufijo sea prefijo de otro sufijo. Cada sufijo en el árbol corresponderá a una hoja. Para el algoritmo, definimos - el sufijo actual (en el paso ), ( cabeza ) - el prefijo más grande del sufijo , que también es el prefijo de otro sufijo , donde . ( cola ) definir como . $suf_{i}$ $i$ $cabeza_{i}$ $suf_{i}$ $suf_{j}$ $j<yo$ $cola_{i}$ $suf_{i}-cabeza_{i}$

La idea clave del algoritmo mcc es la relación entre y . $cabeza_{i}$ $cabeza_{{i-1}}$

Lema. Si donde es una letra del alfabeto, es una cadena (puede estar vacía), entonces es un prefijo . $cabeza_{{i-1}}=aw$ $a$ $w$ $w$ $cabeza_{i}$

Prueba. deja _ Entonces existe , , tal que es a la vez un prefijo de y un prefijo de . Entonces es un prefijo y por lo tanto es un prefijo de la cabeza . El lema está probado. $cabeza_{{i-1}}=aw$ $j$ $j<yo$ $oh$ $suf_{{i-1}}$ $suf_{{j-1}}$ $w$ $suf_{i}$ $suf_{j}$ $w$ $cabeza_{i}$

Conocemos la ubicación de , y si tenemos un enlace de sufijo, podemos saltar rápidamente a la ubicación del prefijo principal sin tener que encontrar la ruta desde la raíz del árbol. Pero es posible que la ubicación no sea explícita (si la ubicación no fue explícita en el paso anterior) y es posible que el enlace del sufijo aún no esté configurado para el nodo . La solución de McCray encuentra un nodo en dos pasos: "volver a escanear" y "escanear". Atravesamos el árbol desde el nodo hasta que encontramos un enlace de sufijo, lo seguimos y luego volvemos a escanear la ruta a la ubicación (que es simple porque sabemos la longitud y la ubicación existe, por lo que no tenemos que leer el borde completo etiquetas moviéndose hacia abajo en el árbol, solo podemos verificar las letras iniciales y la longitud de las palabras). $cabeza_{{i-1}}=aw$ $w$ $cabeza_{i}$ $\sobrelínea {w}$ $\overline {cabeza_{{i-1}}}$ $\overline {cabeza_{{i-1}}}$ $\overline {cabeza_{i}}$ $\overline {cabeza_{{i-1}}}$ $w$ $w$

La figura demuestra esta idea. En lugar de intentar encontrar una ruta desde la raíz hasta el nodo , el algoritmo salta a , sigue el sufijo a , vuelve a escanear la ruta a la ubicación (posiblemente implícita) y se queda para encontrar la ruta a , atravesando carácter por carácter. $F$ $a$ $d$ $mi$ $F$

El algoritmo consta de tres partes.

1. Primero, determina la estructura del encabezado anterior, encuentra el siguiente enlace de sufijo disponible y lo sigue.

2. A continuación, vuelve a escanear la parte de la cabeza anterior para la que se conoce la longitud (esta parte se denomina ). $\beta$

3. Finalmente, el algoritmo establece el enlace de sufijo para , escanea el resto (llamado ) y agrega una nueva hoja para . $cabeza_{{i-1}}$ $cabeza_{i}$ $\gama$ $cola_{i}$

Se crea un nodo de rama en la segunda fase de la nueva exploración si no existe ninguna ubicación . En este caso, el escaneo no es necesario, porque si fuera más largo que entonces sería una rama derecha, pero por el lema también es una rama derecha, por lo que el nodo ya debe existir. El nodo se crea en la tercera fase si la ubicación aún no está explícita. $w$ $cabeza_{i}$ $\Alfa Beta$ $\alfa \beta \gamma$ $\Alfa Beta$ $\overline {\alfa \beta}$ $\overline {cabeza_{i}}$

Algoritmo 1 (mcc, McCreight) Entrada: cadena t 1: T : = árbol vacío; 2: cabeza 0 := ;

\epsilon

3: n := longitud(t) ; 4: para i := 1 to n do 5: encuentre , , tal que

\ chi

\alfa

\beta

una. cabeza i-1 = ,

\ chi \ alfa \ beta

b. si el antepasado del nodo principal i-1 no es la raíz ( raíz ), indíquelo , de lo contrario c. y ( | cabeza i-1 |=0)

\overline {\chi \alfa}

|\alfa |=0

|\chi |\leq 1

|\chi |=0\Flecha izquierda-derecha

6: si ( >0) entonces 7: siga el enlace del sufijo desde el nodo hasta ;

|\alfa |

\overline {\chi \alfa}

\overline {\alfa}

8: finaliza si 9: := Reescanear( ) ;

\overline {\alfa \beta}

\overline {\alfa},\beta

10: establezca el enlace de sufijo de a 11: ( , tail i ) := Scan ( , suf i - );

\overline {cabeza_{{i-1}}}

\overline {\alfa \beta}

\overline {cabeza_{{i}}}

\overline {\alfa \beta}

\Alfa Beta

12: agregue una hoja correspondiente a la cola i ; 13: final para

Tenga en cuenta que si entonces y se reconoce con la misma rapidez, como siguiendo el enlace del sufijo de acuerdo con la línea 7 del algoritmo. $|\alfa |=0$ $\overline {\alfa}=raíz$

El procedimiento Volver a escanear busca una ubicación . Si la ubicación aún no es explícita, se agrega un nuevo nodo. Este caso se da cuando la cabecera ( ) se ve en su totalidad: si la cabecera es más larga (y el nodo ya está definido), debe ser un prefijo de más de dos sufijos y además es rama izquierda de . Una ubicación solo puede ser explícita si ese nodo ya es un nodo de rama, y si no había una rama izquierda entonces , debe haber sido más larga porque se encontró un prefijo más largo. $\Alfa Beta$ $\overline {\alfa \beta}$ $cabeza$ $\Alfa Beta$ $t$ $\overline {\alfa \beta}$ $\Alfa Beta$ $cabeza_{{i-1}}$

El procedimiento Scan busca la profundidad del árbol y devuelve la posición.

Procedimiento 1 Reescanear (n, ) Entrada : nodo n , línea 1: i :=1;

\beta

\beta

2: mientras yo | | haz 3: encuentra la arista e=n n' , w 1 = 1 ;

\leq

\beta

{{\stackrel {w}{\longrightarrow}}}

\beta

4: si yo +| w |>| |+1 luego 5: k :=| | -yo +1;

\beta

\beta

6: arista dividida e con nuevo nodo m y aristas n m y m n' ;

{{\stackrel {w_{1}\ldots w_{k}}{\longrightarrow }}}

{{\stackrel {w_{{k+1}}\ldots w_{{|w|}}}{\longrightarrow }}}

7: devuelve m ; 8: termina si 9: i := i +| w |; 10: n := n' ; 11: finaliza mientras 12: regresa n' ; Procedimiento 2 Escaneo (n, ) Entrada : nodo n , línea 1: i :=1;

\gama

\gama

2: mientras haya una arista e = n n' , w 1 = i do 3: k :=1;

{{\stackrel {w}{\longrightarrow}}}

\gama

4: mientras que w k = i y k | w | hacer 5: k := k +1;

\gama

\leq

6: yo := yo +1; 7: finaliza while 8: si k >| w | entonces 9: n := n' ; 10: else 11: dividir la arista e con el nuevo nodo m y las aristas n m y m n' ;

{{\stackrel {w_{1}\ldots w_{{k-1}}}{\longrightarrow }}}

{{\stackrel {w_{{k}}\ldots w_{{|w|}}}{\longrightarrow }}}

12: retorno ( m , i ,..., );

\gama

\gamma _{{|\gamma |}}

13: finaliza si 14: finaliza mientras 15: regresa ( n , i ,..., );

\gama

\gamma _{{|\gamma |}}

Construcción de un árbol en tiempo lineal. Algoritmo ukk . (Algoritmo de Ukkonen)

El algoritmo que inventó Esko Ukkonen para construir un árbol de sufijos en tiempo lineal es probablemente el más simple de estos algoritmos. La simplicidad proviene del hecho de que el algoritmo puede considerarse inicialmente como un método simple pero ineficiente que, con algunas implementaciones de "sentido común", alcanza el nivel de los mejores algoritmos en términos de tiempo de ejecución en las peores condiciones. Lo mismo se hace en PDF con figuras .

Explicación detallada del algoritmo y la implementación en C++ : cs.mipt.ru (en ruso) y marknelson.us (en inglés)

Para el algoritmo de Ukkonen necesitamos

1) Árboles de sufijos implícitos 2) Descripción general del algoritmo 3) Optimización de algoritmos

Árboles de sufijos implícitos.

El algoritmo de Ukkonen construye una secuencia de árboles de sufijos implícitos, el último de los cuales se convierte en un árbol de sufijos de cadena real S .

Неявное суффиксное дерево строки S — это дерево, полученное из суффиксного дерева S$ удалением всех вхождений терминального символа $ из меток дуг дерева, удалением после этого дуг без меток и удалением затем вершин, имеющих меньше двух детей. Неявное суффиксное дерево префикса S[l..i] строки S аналогично получается из суффиксного дерева для S[l..i]$ удалением символов $, дуг и вершин, как описано выше.

El árbol de sufijos implícito para cualquier cadena S tendrá menos hojas que el árbol de sufijos para la cadena S$ si y solo si al menos uno de los sufijos de S es un prefijo de otro sufijo. El terminal $ se agregó al final de la S solo para evitar esta situación. Al definir un árbol de sufijos real, este es un punto muy importante. Sin embargo, si S termina con un carácter que no aparece en ningún otro lugar de S, entonces el árbol de sufijos implícito para S tendrá una hoja para cada sufijo y, por lo tanto, es un verdadero árbol de sufijos.

Aunque es posible que el árbol de sufijos implícitos no tenga hojas para todos los sufijos, codifica todos los sufijos S: cada uno se pronuncia mediante los caracteres de algún camino desde la raíz de este árbol de sufijos implícitos. Sin embargo, si este camino no termina con una hoja, no habrá ningún marcador que indique el final del camino. Por lo tanto, los propios árboles de sufijos implícitos son algo menos informativos que los reales. Solo los usaremos como una ayuda para el algoritmo de Ukkonen para obtener un verdadero árbol de sufijos para S.

Descripción general del algoritmo.

Построить дерево T1 for i from 1 to m - 1 do begin {фаза i + 1} for j from 1 to i + 1 begin {продолжение j} найти в текущем дереве конец пути из корня с меткой S[j..i]. Если нужно, продолжить путь, добавив символ S(i + 1), обеспечив появление строки S[j..i + 1] в дереве, end; end;

El algoritmo de Ukkonen construye un árbol implícito de sufijos Ti para cada prefijo S[l..i] de la cadena S, comenzando en T 1 e incrementando i en uno hasta que se construye T m . El árbol de sufijos real para S proviene de T m , y todo el trabajo lleva O(m) tiempo. Explicaremos el algoritmo de Ukkonen presentando primero un método mediante el cual todos los árboles se construyen en un tiempo de O(m³), y luego optimizaremos la implementación de este método para que se logre la velocidad declarada.

Tres reglas para la continuación de sufijos.

Para convertir esta descripción general en un algoritmo, debemos especificar exactamente cómo realizar la continuación del sufijo. Sea S[j..i] = β el sufijo de S[1..i]. En la continuación j, cuando el algoritmo encuentra el final β en el árbol actual, continúa β para asegurarse de que el sufijo βS(i + 1) esté presente en el árbol. El algoritmo opera de acuerdo con una de las siguientes tres reglas.

Regla 1. En el árbol actual, el camino β termina en una hoja. Esto significa que el camino desde la raíz etiquetada como β va al final de algún arco de "hoja" (el arco incluido en la hoja). Al cambiar el árbol, agregue el símbolo S (i + 1) al final de la etiqueta de este arco de hojas.

Regla 2. Ningún camino desde el final de la cadena β comienza con S(i + 1), pero hay al menos un camino que comienza desde allí. En este caso, se debe crear un nuevo arco de hojas, comenzando al final de β, etiquetado con el símbolo S(i + 1). En este caso, si β termina dentro del arco, se debe crear un nuevo vértice. A la hoja al final del nuevo arco de hojas se le asigna el número j. Así, en la regla 2, son posibles dos casos.

Regla 3. Algún camino desde el final de la cadena β comienza con el símbolo S(i + 1). En este caso, la cadena βS(i + 1) ya está en el árbol actual, por lo que no es necesario hacer nada (en un árbol de sufijos implícitos, el final del sufijo no necesita marcarse explícitamente).

Buscar en el árbol de sufijos

Deje que se dé el texto y un conjunto de patrones lleguen a la entrada. Después de construir un árbol de sufijos a partir del texto utilizando el algoritmo de Ukkonen, cada patrón se puede buscar de la siguiente manera:

De acuerdo con los símbolos de los patrones entrantes, se realiza un recorrido en el árbol de sufijos construido hasta que se agotan los símbolos del patrón o la siguiente coincidencia se vuelve imposible.
1. Deje que se agoten los símbolos del patrón.
  1. Luego, cada hoja en el subárbol que comienza desde el punto de la última coincidencia tiene como número la posición inicial del patrón en el texto.
  2. Ahora es posible encontrar las k posiciones iniciales del patrón recorriendo el subárbol desde el final de la ruta coincidente en un recorrido lineal, como una búsqueda primero en profundidad o en anchura, y anotando los números de hoja encontrados.
  3. Esto funciona para una línea a partir del número de posiciones, ya que cada vértice interno tiene al menos dos hijos y el número de hojas a lo largo del camino es proporcional al número de arcos recorridos.
2. En el segundo caso, cuando no hay una nueva coincidencia, entonces no hay un patrón en el texto.
3. Si necesita encontrar solo una ocurrencia, entonces necesita cambiar el preprocesamiento, escribiendo en cada vértice el número de la hoja más pequeña en el subárbol.

Árbol de sufijos generalizados

Un árbol de sufijos se puede construir sobre un conjunto de cadenas con o sin concatenación de cadenas. ${\displaystyle S_{1},S_{2},\puntos,S_{n))$

Concatenación de cadenas

Agregamos varios centinelas (caracteres fuera del alfabeto) al final de cada línea.
Vamos a concatenarlos todos en uno.
Construimos un árbol de sufijos en esta línea.
Los números de hoja en este árbol tienen pares de números, donde el primero corresponde a la cadena y el otro a la posición inicial en ella. $Si}$

Este enfoque es problemático debido a la presencia de sufijos sintéticos, pero esto se resuelve reduciendo el segundo índice del par de sufijos en los arcos a los vértices de las hojas.

Sin concatenación de cadenas

No habrá sufijos sintéticos en este algoritmo.

Construyendo un árbol de sufijos para la cadena . ${\ estilo de visualización S_ {1} \ $}$
Estamos buscando las primeras coincidencias de la cadena . $yo$ ${\ estilo de visualización S_{1},S_{2))$
En el árbol de sufijos para , completamos para . $S_{1}$ $S_{2}[l+1\dots n]\$$
Así sucesivamente para las siguientes líneas.

Debe tenerse en cuenta que las etiquetas comprimidas en diferentes arcos pueden hacer referencia a diferentes cadenas, por lo que se deben almacenar tres números en los arcos.

Los sufijos de dos cadenas pueden coincidir, pero al mismo tiempo, ningún sufijo será un prefijo de otro sufijo (debido a centinela). Luego, la hoja apunta a todas las cadenas y posiciones iniciales de ese sufijo.

Comparación con árboles clave

Para resolver el problema de encontrar un conjunto de patrones, existe el algoritmo Aho-Korasik. Encuentra todas las ocurrencias para - la longitud total de los patrones, T - la longitud del texto, k - el número de ocurrencias. $O(P+T+k),P$

Asintóticamente, encontrar todas las ocurrencias en un árbol de sufijos toma la misma cantidad de tiempo. Pero el hecho es que Aho-Korasik usa la memoria para el árbol de claves , el tiempo para construir y el tiempo para buscar . Pero el árbol de sufijos ocupa la memoria , el tiempo , la construcción y la búsqueda. ${\ estilo de visualización O (P)}$ ${\ estilo de visualización O (P)}$ ${\ estilo de visualización O (T)}$ ${\ estilo de visualización O (T)}$ ${\ estilo de visualización O (T)}$ ${\ estilo de visualización O (P)}$

Es decir, si hay muchas muestras y más que el texto, entonces el árbol de sufijos es pequeño, pero lleva mucho tiempo buscar. De lo contrario, Aho-Korasik, cuando los patrones son cortos y el texto es más grande, ocupa menos memoria, pero el árbol de sufijos se busca más rápido.

Así, la elección entre uno u otro depende de la frontera del tiempo o de la memoria.

Véase también

Literatura

Gasfield D. Cadenas, árboles y secuencias en algoritmos: Informática y biología computacional / Per. De inglés. I. V. Romanovsky. - 2ª ed. - San Petersburgo. : Nevsky Dialect, 2003. - 654 p.
Smith B. Métodos y algoritmos para computar en cadenas = Patrones de computación en cadenas. - M. : Williams, 2006. - 496 p. - ISBN 5-8459-1081-1 , 0-201-39839-7.
Okulov S. M. Algoritmos para el procesamiento de cadenas. - M. : Binom, 2013. - 255 p. - ISBN 978-5-9963016-2-1 .

Enlaces

Árbol (estructura de datos)
Árbol de búsqueda binario Árbol (teoría de grafos) estructura de árbol
Árboles binarios	árbol binario árbol en T
Árboles binarios autoequilibrados	árbol AA árbol AVL árbol rojo-negro árbol de juego árbol con multas árbol cartesiano árbol de fibonacci árbol B árbol en T
árboles B	2-3-árbol árbol B⁺ árbol B* B x -árbol árbol de la UB 2-3-4 árbol (a,b)-árbol arbol bailando
árboles de prefijo	árbol de sufijos Árbol de prefijos comprimido Árbol de búsqueda ternario
Partición binaria del espacio	árbol k-dimensional árbol de vicepresidentes
Árboles no binarios	Árbol cuádruple octárbol Octree voxel disperso árbol exponencial árbol PQ
Rompiendo el espacio	R-árbol Árbol R de Hilbert R+-árbol R*-árbol árbol X M-árbol árbol de fenwick Árbol de segmentos
Otros árboles	montón árbol de hachís árbol de los dedos árbol métrico árbol de revestimiento árbol BK Árbol de doble cadena iDistancia Árbol de corte de enlace árbol LSM
Algoritmos	Primera búsqueda en amplitud Primera búsqueda en profundidad algoritmo DSW protocolo de árbol de expansión

Instrumentos de cuerda
Medidas de similitud de cadenas	Distancia de Damerau a Loewenstein distancia Levenstein distancia de hamming Similitud de Jaro-Winkler
Búsqueda de subcadena	Algoritmo de Boyer-Moore Algoritmo de Boyer-Moore-Horspool Algoritmo de Knuth-Morris-Pratt Algoritmo de Rabin-Karp función de prefijo Función Z Algoritmo Aho - Korasik
palíndromos	árbol palíndromo Algoritmo del administrador
Alineación de secuencia	Algoritmo de Needleman-Wunsha Algoritmo de Smith-Waterman
Estructuras de sufijos	Matriz de sufijos sufijo autómata árbol de sufijos árbol de prefijos
Otro	analizando La coincidencia de patrones Mayor subsecuencia común Mayor subcadena común