Matriz LCP

En informática , la matriz de prefijos comunes más largos ( matriz LCP ) es una estructura de datos auxiliar de la matriz de sufijos . Almacena las longitudes de los prefijos comunes más largos (LCP) entre todos los pares de sufijos consecutivos en una matriz de sufijos ordenada.

Por ejemplo, si A  := [ab,desde,Abaab,b,bebé] es una matriz de sufijos, el prefijo común más largo entre A [1] =aby A [2] =desdeesaque tiene una longitud de 1, por lo que H [2] = 1 en la matriz LCP H . Asimismo, el LCP de A [2] =desdey A [3] =Abaabesdesde, por lo que H [3] = 2.

Aumentar la matriz de sufijos con la matriz LCP permite simular de manera eficiente recorridos de arriba hacia abajo y de abajo hacia arriba del árbol de sufijos , ^{[1] [2]} acelera la coincidencia de patrones en la matriz de sufijos ^[3] y es un requisito previo para los árboles de sufijos comprimidos. ^[4]

Historia

La matriz LCP fue introducida en 1993 por Udi Manber y Gene Myers junto con la matriz de sufijos para mejorar el tiempo de ejecución de su algoritmo de búsqueda de cadenas. ^[3]

Definición

Sea la matriz de sufijos de la cadena de longitud , donde es una letra centinela que es única y lexicográficamente más pequeña que cualquier otro carácter. Sea la subcadena de que va de a . Por lo tanto, es el sufijo más pequeño de . ${\displaystyle A}$ ${\displaystyle S=s_{1},s_{2},\ldots s_{n-1}\$}$ ${\displaystyle n}$ ${\displaystyle \$}$ ${\displaystyle S[i,j]}$ ${\displaystyle S}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle S[A[i],n]}$ ${\displaystyle i}$ ${\displaystyle S}$

Sea la longitud del prefijo común más largo entre dos cadenas y . Entonces, la matriz LCP es una matriz de números enteros de tamaño tal que no está definida y para cada . Por lo tanto, almacena la longitud del prefijo común más largo del sufijo lexicográficamente más pequeño y su predecesor en la matriz de sufijos. ${\displaystyle \operatorname {lcp} (v,w)}$ ${\displaystyle v}$ ${\displaystyle w}$ ${\displaystyle H[1,n]}$ ${\displaystyle n}$ ${\displaystyle H[1]}$ ${\displaystyle H[i]=\operatorname {lcp} (S[A[i-1],n],S[A[i],n])}$ ${\displaystyle 1<i\leq n}$ ${\displaystyle H[i]}$ ${\displaystyle i}$

Diferencia entre matriz LCP y matriz de sufijos:

• Matriz de sufijos: representa el rango lexicográfico de cada sufijo de una matriz.
• Matriz LCP: contiene la coincidencia de prefijo de longitud máxima entre dos sufijos consecutivos, después de ordenarlos lexicográficamente.

Ejemplo

Considere la cadena : ${\displaystyle S={\textrm {banana\$}}}$

y su matriz de sufijos ordenados correspondiente  : ${\displaystyle A}$

Matriz de sufijos con sufijos escritos debajo verticalmente:

Luego, la matriz LCP se construye comparando sufijos lexicográficamente consecutivos para determinar su prefijo común más largo: ${\displaystyle H}$

Por ejemplo, ¿la longitud del prefijo común más largo que comparten los sufijos y es ? Nótese que no está definido, ya que no existe un sufijo lexicográficamente más pequeño. ${\displaystyle H[4]=3}$ ${\displaystyle {\text{ana}}}$ ${\displaystyle A[3]=S[4,7]={\textrm {ana\$}}}$ ${\displaystyle A[4]=S[2,7]={\textrm {anana\$}}}$ ${\displaystyle H[1]}$

Algoritmos de construcción eficientes

Los algoritmos de construcción de matrices LCP se pueden dividir en dos categorías diferentes: algoritmos que calculan la matriz LCP como un subproducto de la matriz de sufijos y algoritmos que utilizan una matriz de sufijos ya construida para calcular los valores LCP.

Manber y Myers (1993) proporcionan un algoritmo para calcular la matriz LCP junto con la matriz de sufijos en el tiempo. Kärkkäinen y Sanders (2003) muestran que también es posible modificar su algoritmo de tiempo de modo que calcule también la matriz LCP. Kasai et al. (2001) presentan el primer algoritmo de tiempo (FLAAP) que calcula la matriz LCP dado el texto y la matriz de sufijos. ${\displaystyle O(n\log n)}$ ${\displaystyle O(n)}$ ${\displaystyle O(n)}$

Suponiendo que cada símbolo de texto ocupa un byte y cada entrada del sufijo o matriz LCP ocupa 4 bytes, el principal inconveniente de su algoritmo es una gran ocupación de espacio de bytes, mientras que la salida original (texto, matriz de sufijos, matriz LCP) solo ocupa bytes. Por lo tanto, Manzini (2004) creó una versión refinada del algoritmo de Kasai et al. (2001) (lcp9) y redujo la ocupación de espacio a bytes. Kärkkäinen, Manzini y Puglisi (2009) proporcionan otro refinamiento del algoritmo de Kasai ( -algoritmo) que mejora el tiempo de ejecución. En lugar de la matriz LCP real, este algoritmo construye la matriz LCP permutada (PLCP), en la que los valores aparecen en orden de texto en lugar de orden lexicográfico. ${\displaystyle 13n}$ ${\displaystyle 9n}$ ${\displaystyle 9n}$ ${\displaystyle \Phi }$

Gog y Ohlebusch (2011) proporcionan dos algoritmos que, aunque teóricamente son lentos ( ), en la práctica son más rápidos que los algoritmos mencionados anteriormente. ${\displaystyle O(n^{2})}$

A partir de 2012 ^[actualizar], el algoritmo de construcción de matrices LCP en tiempo lineal más rápido en la actualidad se debe a Fischer (2011), que a su vez se basa en uno de los algoritmos de construcción de matrices de sufijos más rápidos (SA-IS) de Nong, Zhang y Chan (2009). Fischer y Kurpicz (2017) basado en DivSufSort de Yuta Mori es aún más rápido.

Aplicaciones

Como señalan Abouelhoda, Kurtz y Ohlebusch (2004), varios problemas de procesamiento de cadenas se pueden resolver mediante los siguientes tipos de recorridos de árboles :

• Recorrido de abajo hacia arriba del árbol de sufijos completo
• Recorrido de arriba hacia abajo de un subárbol del árbol de sufijos
• recorrido del árbol de sufijos utilizando los enlaces de sufijo.

Kasai et al. (2001) muestran cómo simular un recorrido ascendente del árbol de sufijos utilizando únicamente la matriz de sufijos y la matriz LCP. Abouelhoda, Kurtz y Ohlebusch (2004) mejoran la matriz de sufijos con la matriz LCP y estructuras de datos adicionales y describen cómo se puede utilizar esta matriz de sufijos mejorada para simular los tres tipos de recorridos del árbol de sufijos. Fischer y Heun (2007) reducen los requisitos de espacio de la matriz de sufijos mejorada mediante el preprocesamiento de la matriz LCP para consultas de rango mínimo . Por lo tanto, todos los problemas que se pueden resolver mediante algoritmos de árbol de sufijos también se pueden resolver utilizando la matriz de sufijos mejorada . ^[2]

Decidir si un patrón de longitud es una subcadena de una cadena de longitud lleva tiempo si solo se utiliza la matriz de sufijos. Al utilizar además la información LCP, este límite se puede mejorar en tiempo. ^[3] Abouelhoda, Kurtz y Ohlebusch (2004) muestran cómo mejorar este tiempo de ejecución aún más para lograr un tiempo óptimo. Por lo tanto, utilizando la matriz de sufijos y la información de la matriz LCP, la consulta de decisión se puede responder tan rápido como utilizando el árbol de sufijos . ${\displaystyle P}$ ${\displaystyle m}$ ${\displaystyle S}$ ${\displaystyle n}$ ${\displaystyle O(m\log n)}$ ${\displaystyle O(m+\log n)}$ ${\displaystyle O(m)}$

La matriz LCP también es una parte esencial de los árboles de sufijos comprimidos que proporcionan una funcionalidad completa de árboles de sufijos como enlaces de sufijos y consultas de ancestro común más bajo . ^{[5] [6]} Además, se puede utilizar junto con la matriz de sufijos para calcular la factorización Lempel-Ziv LZ77 en el tiempo. ^{[2] [7] [8] [9]} ${\displaystyle O(n)}$

El problema de la subcadena repetida más larga para una cadena de longitud se puede resolver en el tiempo utilizando tanto la matriz de sufijos como la matriz LCP. Es suficiente realizar un escaneo lineal a través de la matriz LCP para encontrar su valor máximo y el índice correspondiente donde se almacena. La subcadena más larga que aparece al menos dos veces se da entonces por . ${\displaystyle S}$ ${\displaystyle n}$ ${\displaystyle \Theta (n)}$ ${\displaystyle A}$ ${\displaystyle v_{max}}$ ${\displaystyle i}$ ${\displaystyle v_{max}}$ ${\displaystyle S[A[i],A[i]+v_{max}-1]}$

El resto de esta sección explica dos aplicaciones de la matriz LCP con más detalle: cómo se pueden usar la matriz de sufijos y la matriz LCP de una cadena para construir el árbol de sufijos correspondiente y cómo es posible responder consultas LCP para sufijos arbitrarios utilizando consultas de rango mínimo en la matriz LCP.

Encuentra el número de ocurrencias de un patrón

Para encontrar el número de ocurrencias de una cadena dada (longitud ) en un texto (longitud ), ^[3] ${\displaystyle P}$ ${\displaystyle m}$ ${\displaystyle T}$ ${\displaystyle N}$

• Utilizamos la búsqueda binaria en la matriz de sufijos de para encontrar la posición inicial y final de todas las apariciones de . ${\displaystyle T}$ ${\displaystyle P}$
• Ahora, para acelerar la búsqueda, utilizamos la matriz LCP, específicamente una versión especial de la matriz LCP (LCP-LR a continuación).

El problema con el uso de la búsqueda binaria estándar (sin la información LCP) es que en cada una de las comparaciones que se deben realizar, comparamos P con la entrada actual de la matriz de sufijos, lo que significa una comparación de cadena completa de hasta m caracteres. Por lo tanto, la complejidad es . ${\displaystyle O(\log N)}$ ${\displaystyle O(m\log N)}$

La matriz LCP-LR ayuda a mejorar esto de la siguiente manera: ${\displaystyle O(m+\log N)}$

En cualquier punto durante el algoritmo de búsqueda binaria, consideramos, como es habitual, un rango de la matriz de sufijos y su punto central , y decidimos si continuamos nuestra búsqueda en el subrango izquierdo o en el subrango derecho . Para tomar la decisión, comparamos con la cadena en . Si es idéntico a , nuestra búsqueda está completa. Pero si no, ya hemos comparado los primeros caracteres de y luego decidimos si es lexicográficamente menor o mayor que . Supongamos que el resultado es que es mayor que . Entonces, en el siguiente paso, consideramos y un nuevo punto central en el medio: ${\displaystyle (L,\dots ,R)}$ ${\displaystyle M}$ ${\displaystyle (L,\dots ,M)}$ ${\displaystyle (M,\dots ,R)}$ ${\displaystyle P}$ ${\displaystyle M}$ ${\displaystyle P}$ ${\displaystyle M}$ ${\displaystyle k}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle M}$ ${\displaystyle P}$ ${\displaystyle M}$ ${\displaystyle (M,\dots ,R)}$ ${\displaystyle M'}$

 Yo ...... Yo ...... R | sabemos: lcp(P,M)==k

El truco ahora es que LCP-LR está precalculado de tal manera que una búsqueda nos indica el prefijo común más largo de y , . ${\displaystyle O(1)}$ ${\displaystyle M}$ ${\displaystyle M'}$ ${\displaystyle \mathrm {lcp} (M,M')}$

Ya sabemos (por el paso anterior) que sí tiene un prefijo de caracteres en común con : . Ahora hay tres posibilidades: ${\displaystyle M}$ ${\displaystyle k}$ ${\displaystyle P}$ ${\displaystyle \mathrm {lcp} (P,M)=k}$

• Caso 1: , es decir, tiene menos caracteres de prefijo en común con M que M tiene en común con M'. Esto significa que el carácter (k+1)-ésimo de M' es el mismo que el de M, y como P es lexicográficamente más grande que M, también debe ser lexicográficamente más grande que M'. Por lo tanto, continuamos en la mitad derecha (M',...,R). ${\displaystyle k<\mathrm {lcp} (M,M')}$ ${\displaystyle P}$
• Caso 2: , es decir, tiene más caracteres de prefijo en común con que con . En consecuencia, si comparáramos con , el prefijo común sería menor que , y sería lexicográficamente mayor que , por lo que, sin hacer realmente la comparación, continuamos en la mitad izquierda . ${\displaystyle k>\mathrm {lcp} (M,M')}$ ${\displaystyle P}$ ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle M'}$ ${\displaystyle P}$ ${\displaystyle M'}$ ${\displaystyle k}$ ${\displaystyle M'}$ ${\displaystyle P}$ ${\displaystyle (M,\dots ,M')}$
• Caso 3: . Por lo tanto, M y M' son idénticos a los de los primeros caracteres. Para decidir si continuamos en la mitad izquierda o derecha, basta comparar con el comienzo del carácter n. ${\displaystyle k=\mathrm {lcp} (M,M')}$ ${\displaystyle P}$ ${\displaystyle k}$ ${\displaystyle P}$ ${\displaystyle M'}$ ${\displaystyle (k+1)}$
• Continuamos recursivamente.

El efecto general es que ningún carácter de se compara con ningún carácter del texto más de una vez (para más detalles, consulte ^[3] ). El número total de comparaciones de caracteres está limitado por , por lo que la complejidad total es de hecho . ${\displaystyle P}$ ${\displaystyle m}$ ${\displaystyle O(m+\log N)}$

Aún necesitamos calcular previamente LCP-LR para que pueda decirnos a tiempo el lcp entre dos entradas cualesquiera de la matriz de sufijos. Sabemos que la matriz LCP estándar nos da el lcp de entradas consecutivas solamente, es decir, para cualquier . Sin embargo, y en la descripción anterior no son necesariamente entradas consecutivas. ${\displaystyle O(1)}$ ${\displaystyle \mathrm {lcp} (i-1,i)}$ ${\displaystyle i}$ ${\displaystyle M}$ ${\displaystyle M'}$

La clave para esto es darse cuenta de que solo ciertos rangos aparecerán alguna vez durante la búsqueda binaria: siempre comienza con y divide eso en el centro, y luego continúa hacia la izquierda o la derecha y divide esa mitad nuevamente y así sucesivamente. Otra forma de verlo es: cada entrada de la matriz de sufijos aparece como punto central de exactamente un rango posible durante la búsqueda binaria. Por lo tanto, hay exactamente N rangos distintos que posiblemente puedan desempeñar un papel durante la búsqueda binaria, y basta con precalcular y para esos rangos posibles. Por lo tanto, son valores precalculados distintos, por lo tanto, LCP-LR es de tamaño. ${\displaystyle (L,\dots ,R)}$ ${\displaystyle (0,\dots ,N)}$ ${\displaystyle (L\dots M\dots R)}$ ${\displaystyle \mathrm {lcp} (L,M)}$ ${\displaystyle \mathrm {lcp} (M,R)}$ ${\displaystyle N}$ ${\displaystyle 2N}$ ${\displaystyle O(N)}$

Además, existe un algoritmo recursivo sencillo para calcular los valores de LCP-LR en el tiempo a partir de la matriz LCP estándar. ${\displaystyle 2N}$ ${\displaystyle O(N)}$

En resumen:

• Es posible calcular LCP-LR en tiempo y espacio a partir de LCP. ${\displaystyle O(N)}$ ${\displaystyle O(2N)=O(N)}$
• El uso de LCP-LR durante la búsqueda binaria ayuda a acelerar el procedimiento de búsqueda de a . ${\displaystyle O(M\log N)}$ ${\displaystyle O(M+\log N)}$
• Podemos utilizar dos búsquedas binarias para determinar el extremo izquierdo y derecho del rango de coincidencia para , y la longitud del rango de coincidencia corresponde con el número de ocurrencias de P. ${\displaystyle P}$

Construcción de árboles de sufijos

Dada la matriz de sufijos y la matriz LCP de una cadena de longitud , su árbol de sufijos se puede construir en el tiempo basándose en la siguiente idea: comenzar con el árbol de sufijos parcial para el sufijo lexicográficamente más pequeño e insertar repetidamente los otros sufijos en el orden dado por la matriz de sufijos. ${\displaystyle A}$ ${\displaystyle H}$ ${\displaystyle S=s_{1},s_{2},\ldots s_{n}\$}$ ${\displaystyle n+1}$ ${\displaystyle ST}$ ${\displaystyle O(n)}$

Sea el árbol de sufijos parcial para . Además, sea la longitud de la concatenación de todas las etiquetas de ruta desde la raíz de hasta el nodo . ${\displaystyle ST_{i}}$ ${\displaystyle 0\leq i\leq n}$ ${\displaystyle d(v)}$ ${\displaystyle ST_{i}}$ ${\displaystyle v}$

Caso 1 ( ): Supongamos que los sufijos , y de la cadena ya se han añadido al árbol de sufijos. A continuación, el sufijo se añade al árbol como se muestra en la imagen. La ruta situada más a la derecha se resalta en rojo. ${\displaystyle d(v)=H[i+1]}$ ${\displaystyle a\$}$ ${\displaystyle ana\$}$ ${\displaystyle anana\$}$ ${\displaystyle banana\$}$ ${\displaystyle S=banana\$}$ ${\displaystyle na\$}$

Comience con , el árbol que consta solo de la raíz. Para insertar en , camine hacia arriba por el camino más a la derecha comenzando en la hoja recientemente insertada hasta la raíz, hasta llegar al nodo más profundo con . ${\displaystyle ST_{0}}$ ${\displaystyle A[i+1]}$ ${\displaystyle ST_{i}}$ ${\displaystyle A[i]}$ ${\displaystyle v}$ ${\displaystyle d(v)\leq H[i+1]}$

Es necesario distinguir dos casos:

• ${\displaystyle d(v)=H[i+1]}$: Esto significa que la concatenación de las etiquetas en la ruta de la raíz a la ruta es igual al prefijo común más largo de los sufijos y . En este caso, inserte como una nueva hoja del nodo y etiquete la arista con . Por lo tanto, la etiqueta de la arista consta de los caracteres restantes del sufijo que no están representados por la concatenación de las etiquetas de la ruta de la raíz a la ruta. Esto crea el árbol de sufijos parcial . ${\displaystyle v}$ ${\displaystyle A[i]}$ ${\displaystyle A[i+1]}$
  ${\displaystyle A[i+1]}$ ${\displaystyle x}$ ${\displaystyle v}$ ${\displaystyle (v,x)}$ ${\displaystyle S[A[i+1]+H[i+1],n]}$ ${\displaystyle A[i+1]}$ ${\displaystyle v}$
  ${\displaystyle ST_{i+1}}$

  

  Caso 2 ( ): Para agregar el sufijo , se debe dividir la arista del sufijo insertado previamente . La nueva arista del nuevo nodo interno se etiqueta con el prefijo común más largo de los sufijos y . Las aristas que conectan las dos hojas se etiquetan con los caracteres de sufijo restantes que no forman parte del prefijo. ${\displaystyle d(v)<H[i+1]}$ ${\displaystyle nana\$}$ ${\displaystyle na\$}$ ${\displaystyle na\$}$ ${\displaystyle nana\$}$

• ${\displaystyle d(v)<H[i+1]}$: Esto significa que la concatenación de las etiquetas en la ruta de la raíz a la ruta muestra menos caracteres que el prefijo común más largo de los sufijos y los caracteres faltantes están contenidos en la etiqueta del borde del borde más a la derecha de . Por lo tanto, tenemos que dividir ese borde de la siguiente manera: Sea el hijo de la ruta más a la derecha de . ${\displaystyle v}$ ${\displaystyle A[i]}$ ${\displaystyle A[i+1]}$ ${\displaystyle v}$
  ${\displaystyle w}$ ${\displaystyle v}$ ${\displaystyle ST_{i}}$

1. Eliminar el borde . ${\displaystyle (v,w)}$
2. Agregue un nuevo nodo interno y una nueva arista con la etiqueta . La nueva etiqueta consta de los caracteres faltantes del prefijo común más largo de y . Por lo tanto, la concatenación de las etiquetas de la ruta de la raíz a la ruta ahora muestra el prefijo común más largo de y . ${\displaystyle y}$ ${\displaystyle (v,y)}$ ${\displaystyle S[A[i]+d(v),A[i]+H[i+1]-1]}$ ${\displaystyle A[i]}$ ${\displaystyle A[i+1]}$ ${\displaystyle y}$ ${\displaystyle A[i]}$ ${\displaystyle A[i+1]}$
3. Conéctese al nodo interno recién creado mediante un borde que tenga la etiqueta . La nueva etiqueta consta de los caracteres restantes del borde eliminado que no se usaron como etiqueta del borde . ${\displaystyle w}$ ${\displaystyle y}$ ${\displaystyle (y,w)}$ ${\displaystyle S[A[i]+H[i+1],A[i]+d(w)-1]}$ ${\displaystyle (v,w)}$ ${\displaystyle (v,y)}$
4. Agregue una nueva hoja y conéctela al nuevo nodo interno mediante una arista etiquetada como . Por lo tanto, la etiqueta de la arista consta de los caracteres restantes del sufijo que aún no están representados por la concatenación de las etiquetas de la ruta de la raíz a la raíz. ${\displaystyle A[i+1]}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle (y,x)}$ ${\displaystyle S[A[i+1]+H[i+1],n]}$ ${\displaystyle A[i+1]}$ ${\displaystyle v}$
5. Esto crea el árbol de sufijos parcial . ${\displaystyle ST_{i+1}}$

Un argumento de amortización simple muestra que el tiempo de ejecución de este algoritmo está limitado por : ${\displaystyle O(n)}$

Los nodos que se recorren paso a paso caminando por el camino más a la derecha de (aparte del último nodo ) se eliminan del camino más a la derecha cuando se agrega al árbol como una nueva hoja. Estos nodos nunca se volverán a recorrer en todos los pasos posteriores . Por lo tanto, se recorrerán nodos como máximo en total. ${\displaystyle i}$ ${\displaystyle ST_{i}}$ ${\displaystyle v}$ ${\displaystyle A[i+1]}$ ${\displaystyle j>i}$ ${\displaystyle 2n}$

Consultas LCP para sufijos arbitrarios

La matriz LCP solo contiene la longitud del prefijo común más largo de cada par de sufijos consecutivos en la matriz de sufijos . Sin embargo, con la ayuda de la matriz de sufijos inversa ( , es decir, el sufijo que comienza en la posición en se almacena en la posición en ) y consultas mínimas de rango de tiempo constante en , es posible determinar la longitud del prefijo común más largo de sufijos arbitrarios en el tiempo. ${\displaystyle H}$ ${\displaystyle A}$ ${\displaystyle A^{-1}}$ ${\displaystyle A[i]=j\Leftrightarrow A^{-1}[j]=i}$ ${\displaystyle S[j,n]}$ ${\displaystyle j}$ ${\displaystyle S}$ ${\displaystyle A^{-1}[j]}$ ${\displaystyle A}$ ${\displaystyle H}$ ${\displaystyle O(1)}$

Debido al orden lexicográfico de la matriz de sufijos, cada prefijo común de los sufijos y tiene que ser un prefijo común de todos los sufijos entre la posición de en la matriz de sufijos y la posición de en la matriz de sufijos . Por lo tanto, la longitud del prefijo más largo que comparten todos estos sufijos es el valor mínimo en el intervalo . Este valor se puede encontrar en tiempo constante si se preprocesa para consultas de rango mínimo. ${\displaystyle S[i,n]}$ ${\displaystyle S[j,n]}$ ${\displaystyle i}$ ${\displaystyle A^{-1}[i]}$ ${\displaystyle j}$ ${\displaystyle A^{-1}[j]}$ ${\displaystyle H[A^{-1}[i]+1,A^{-1}[j]]}$ ${\displaystyle H}$

Así, dada una cadena de longitud y dos posiciones arbitrarias en la cadena con , la longitud del prefijo común más largo de los sufijos y se puede calcular de la siguiente manera: . ${\displaystyle S}$ ${\displaystyle n}$ ${\displaystyle i,j}$ ${\displaystyle S}$ ${\displaystyle A^{-1}[i]<A^{-1}[j]}$ ${\displaystyle S[i,n]}$ ${\displaystyle S[j,n]}$ ${\displaystyle \operatorname {LCP} (i,j)=H[\operatorname {RMQ} _{H}(A^{-1}[i]+1,A^{-1}[j])]}$

Notas

1. Kasai y otros 2001.
2. Abouelhoda, Kurtz y Ohlebusch 2004.
3. Manber y Myers 1993.
4. Ohlebusch, Fischer y Gog 2010.
5. Sadakane 2007.
6. Fischer, Mäkinen y Navarro 2009.
7. Crochemore y Ilie 2008.
8. Crochemore, Ilie y Smyth 2008.
9. Chen, Puglisi y Smyth 2008.

Referencias

• Abouelhoda, Mohamed Ibrahim; Kurtz, Stefan; Ohlebusch, Enno (2004). "Reemplazo de árboles de sufijos con matrices de sufijos mejoradas". Journal of Discrete Algorithms . 2 : 53–86. doi : 10.1016/S1570-8667(03)00065-0 .
• Manber, Udi; Myers, Gene (1993). "Matrices de sufijos: un nuevo método para búsquedas de cadenas en línea". Revista SIAM de informática . 22 (5): 935. CiteSeerX  10.1.1.105.6571 . doi :10.1137/0222058. S2CID  5074629.
• Kasai, T.; Lee, G.; Arimura, H.; Arikawa, S.; Park, K. (2001). Cálculo del prefijo común más largo en tiempo lineal en matrices de sufijos y sus aplicaciones . Actas del 12.º Simposio anual sobre correspondencia de patrones combinatorios. Notas de clase en informática. Vol. 2089. págs. 181–192. doi :10.1007/3-540-48194-X_17. ISBN 978-3-540-42271-6.
• Ohlebusch, Enno; Fischer, Johannes; Gog, Simon (2010). CST++ . Procesamiento de cadenas y recuperación de información. Apuntes de clase en informática. Vol. 6393. pág. 322. doi :10.1007/978-3-642-16321-0_34. ISBN 978-3-642-16320-3.
• Kärkkäinen, Juha; Sanders, Peter (2003). Construcción de matrices de sufijos de trabajo lineales simples. Actas de la 30.ª conferencia internacional sobre autómatas, lenguajes y programación. pp. 943–955 . Consultado el 28 de agosto de 2012 .
• Fischer, Johannes (2011). Inducción de la matriz LCP . Algoritmos y estructuras de datos. Apuntes de clase en informática. Vol. 6844. págs. 374–385. arXiv : 1101.3448 . doi :10.1007/978-3-642-22300-6_32. ISBN . 978-3-642-22299-3.
• Manzini, Giovanni (2004). Dos trucos para ahorrar espacio en el cálculo de matrices LCP en tiempo lineal . Algorithm Theory – SWAT 2004. Lecture Notes in Computer Science. Vol. 3111. p. 372. doi :10.1007/978-3-540-27810-8_32. ISBN 978-3-540-22339-9.
• Kärkkäinen, Juha; Manzini, Giovanni; Puglisi, Simon J. (2009). Matriz de prefijo común más largo permutada . Coincidencia de patrones combinatorios. Apuntes de clase en informática. Vol. 5577. pág. 181. doi :10.1007/978-3-642-02441-2_17. ISBN 978-3-642-02440-5.
• Puglisi, Simon J.; Turpin, Andrew (2008). Compensaciones espacio-temporales para el cálculo de matrices con el prefijo común más largo . Algoritmos y computación. Apuntes de clase en informática. Vol. 5369. pág. 124. doi :10.1007/978-3-540-92182-0_14. ISBN 978-3-540-92181-3.
• Gog, Simon; Ohlebusch, Enno (2011). Algoritmos de construcción de matrices LCP rápidos y ligeros (PDF) . Actas del taller sobre ingeniería de algoritmos y experimentos, ALENEX 2011. págs. 25–34 . Consultado el 28 de agosto de 2012 .
• Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009). Construcción de matrices de sufijos lineales mediante ordenamiento inducido casi puro . Conferencia sobre compresión de datos de 2009. pág. 193. doi :10.1109/DCC.2009.42. ISBN 978-0-7695-3592-0.
• Fischer, Johannes; Heun, Volker (2007). Una nueva representación sucinta de la información RMQ y mejoras en la matriz de sufijos mejorada . Combinatoria, algoritmos, metodologías probabilísticas y experimentales. Apuntes de clase en informática. Vol. 4614. pág. 459. doi :10.1007/978-3-540-74450-4_41. ISBN 978-3-540-74449-8.
• Chen, G.; Puglisi, SJ; Smyth, WF (2008). "Factorización Lempel–Ziv usando menos tiempo y espacio". Matemáticas en Ciencias de la Computación . 1 (4): 605. doi :10.1007/s11786-007-0024-4. S2CID  1721891.
• Crochemore, M.; Ilie, L. (2008). "Cálculo del factor anterior más largo en tiempo lineal y aplicaciones". Information Processing Letters . 106 (2): 75. CiteSeerX  10.1.1.70.5720 . doi :10.1016/j.ipl.2007.10.006. S2CID  5492217.
• Crochemore, M.; Ilie, L.; Smyth, WF (2008). Un algoritmo simple para calcular la factorización de Lempel Ziv . Conferencia sobre compresión de datos (dcc 2008). pág. 482. doi :10.1109/DCC.2008.36. hdl : 20.500.11937/5907 . ISBN. 978-0-7695-3121-2.
• Sadakane, K. (2007). "Árboles de sufijos comprimidos con funcionalidad completa". Teoría de sistemas informáticos . 41 (4): 589–607. CiteSeerX  10.1.1.224.4152 . doi :10.1007/s00224-006-1198-x. S2CID  263130.
• Fischer, Johannes; Mäkinen, Veli; Navarro, Gonzalo (2009). "Árboles de sufijos comprimidos más rápidos y limitados por entropía". Ciencias Informáticas Teóricas . 410 (51): 5354. doi : 10.1016/j.tcs.2009.09.012 .
• Fischer, Johannes; Kurpicz, Florian (5 de octubre de 2017). "Desmantelando DivSufSort". Actas de la Conferencia de Cuerdas de Praga de 2017. arXiv : 1710.01896 .

Enlaces externos

• Espejo de la implementación ad-hoc del código descrito en Fischer (2011)
• SDSL: Biblioteca de estructuras de datos sucintas: proporciona varias implementaciones de matrices LCP, estructuras de soporte de consultas mínimas de rango (RMQ) y muchas más estructuras de datos sucintas.
• Recorrido de árbol de sufijos de abajo hacia arriba emulado mediante matriz de sufijos y matriz LCP (Java)
• Proyecto de indexación de texto (construcción en tiempo lineal de árboles de sufijos, matrices de sufijos, matriz LCP y transformada de Burrows-Wheeler)