matriz LCP

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

Por ejemplo, si A  := [ab,ab,abaab,b,baab] es una matriz de sufijos, el prefijo común más largo entre A [1] =aby A [2] =abesaque tiene longitud 1, por lo que H [ 2 ] = 1 en la matriz LCP H. Asimismo, el LCP de A [2] =aby A [3] =abaabesab, entonces H [3] = 2.

Aumentar la matriz de sufijos con la matriz LCP permite simular eficientemente 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 el sufijo comprimido árboles. ^[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. Denotemos la subcadena que va desde hasta . Por tanto, es el décimo 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}$

Denotemos la longitud del prefijo común más largo entre dos cadenas y . Entonces la matriz LCP es una matriz entera de tamaño tal que no está definida y es 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 correspondiente matriz de sufijos ordenados  : ${\displaystyle A}$

Matriz de sufijos con los 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}$

Entonces, por ejemplo, la longitud del prefijo común más largo es compartida por los sufijos y . Tenga en cuenta 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 de 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 también calcule 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 mayor inconveniente de su algoritmo es una gran ocupación de espacio de bytes, mientras que la salida original (texto, matriz de sufijos, matriz LCP) sólo ocupa bytes. Por tanto, Manzini (2004) creó una versión refinada del algoritmo de Kasai et al. (2001) (lcp9) y redujo la ocupación del 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 & Ohlebusch (2011) proporcionan dos algoritmos que, aunque teóricamente eran lentos ( ), en la práctica eran 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 actualmente se debe a Fischer (2011), que a su vez se basa en uno de los algoritmos de construcción de matrices de sufijos (SA-IS) más rápidos de Nong, Zhang y Chan (2009). . Fischer & Kurpicz (2017), basado en DivSufSort de Yuta Mori, es aún más rápido.

Aplicaciones

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

• recorrido ascendente 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 sufijos.

Kasai et al. (2001) muestran cómo simular un recorrido ascendente del árbol de sufijos utilizando sólo 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 esta matriz de sufijos mejorada se puede utilizar para simular los tres tipos de recorridos de árboles de sufijos. Fischer y Heun (2007) reducen los requisitos de espacio de la matriz de sufijos mejorada preprocesando la matriz LCP para consultas de rango mínimo . Por lo tanto, todos los problemas que pueden resolverse mediante algoritmos de árbol de sufijos también pueden resolverse 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 adicionalmente la información LCP, este límite se puede mejorar con el tiempo. ^[3] Abouelhoda, Kurtz y Ohlebusch (2004) muestran cómo mejorar aún más este tiempo de carrera para lograr un tiempo óptimo. Por lo tanto, utilizando la información de la matriz de sufijos y la matriz LCP, la consulta de decisión se puede responder tan rápido como usando 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 del árbol 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 subcadena repetida más larga para una cadena de longitud se puede resolver a 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 está almacenado. La subcadena más larga que aparece al menos dos veces viene dada 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 usando el rango. consultas mínimas en la matriz LCP.

Encuentra el número de apariciones de un patrón.

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

• Usamos la búsqueda binaria contra 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 necesarias, comparamos P con la entrada actual de la matriz de sufijos, lo que significa una comparación de cadena completa de hasta m caracteres. Entonces 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 de costumbre, 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 hemos decidido si es lexicográficamente menor o mayor que . Supongamos que el resultado es mayor que . Entonces, en el siguiente paso, consideramos 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'}$

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

El truco ahora es que LCP-LR se calcula previamente de modo que una búsqueda nos indique 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 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 los que M tiene en común con M'. Esto significa que el (k+1)-ésimo carácter de M' es el mismo que el de M, y dado que P es lexicográficamente mayor que M, también debe ser lexicográficamente mayor que M'. Entonces 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 los que tiene en común con . En consecuencia, si comparáramos con , el prefijo común sería menor que , y lexicográficamente sería mayor que , por lo que, sin llegar a hacer 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: . Entonces M y M' son idénticos a los primeros caracteres. Para decidir si continuamos en la mitad izquierda o derecha, basta con comparar empezando por el carácter ésimo. ${\displaystyle k=\mathrm {lcp} (M,M')}$ ${\displaystyle P}$ ${\displaystyle k}$ ${\displaystyle P}$ ${\displaystyle M'}$ ${\displaystyle (k+1)}$
• Seguimos 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. El número total de comparaciones de caracteres está limitado por , por lo que la complejidad total sí lo está . ${\displaystyle P}$ ${\displaystyle m}$ ${\displaystyle O(m+\log N)}$

Todavía necesitamos precalcular 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 proporciona el lcp de entradas consecutivas únicamente, es decir, para cualquiera . Sin embargo, y en la descripción anterior no hay 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 ocurrirán durante la búsqueda binaria: siempre comienza y lo divide en el centro, y luego continúa hacia la izquierda o hacia la derecha y divide esa mitad nuevamente y así sucesivamente. Otra forma de verlo es: cada entrada de la matriz de sufijos ocurre 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. Entonces se trata de valores precalculados distintos, por lo tanto, LCP-LR tiene 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)}$

Para resumir:

• 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 usar dos búsquedas binarias para determinar el extremo izquierdo y derecho del rango de coincidencia para , y la longitud del rango de coincidencia se corresponde con el número de apariciones de P. ${\displaystyle P}$

Construcción de árbol 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: comience con el árbol de sufijos parcial para el sufijo lexicográficamente más pequeño e inserte 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 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 están agregados al árbol de sufijos. Luego se agrega el sufijo al árbol como se muestra en la imagen. El camino más a la derecha está resaltado 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 únicamente de la raíz. Para insertar en , recorra el camino más a la derecha comenzando en la hoja recientemente insertada hasta la raíz, hasta llegar al nodo más profundo . ${\displaystyle ST_{0}}$ ${\displaystyle A[i+1]}$ ${\displaystyle ST_{i}}$ ${\displaystyle A[i]}$ ${\displaystyle v}$ ${\displaystyle d(v)\leq H[i+1]}$

Debemos distinguir dos casos:

• ${\displaystyle d(v)=H[i+1]}$: Esto significa que la concatenación de las etiquetas en la ruta de acceso raíz es igual al prefijo común más largo de sufijos y . En este caso, insértelo como una nueva hoja del nodo y etiquete el borde con . Por lo tanto, la etiqueta de borde 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 raíz a ruta. Esto crea el árbol de sufijos parciales . ${\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 el borde del sufijo previamente insertado . El nuevo borde del nuevo nodo interno está etiquetado con el prefijo común más largo de los sufijos y . Los bordes que conectan las dos hojas están etiquetados 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 acceso raíz muestra menos caracteres que el prefijo común de sufijos más largo y los caracteres faltantes están contenidos en la etiqueta del borde más a la derecha . Por lo tanto, tenemos que dividir ese borde de la siguiente manera: Sea el hijo de on en el camino más a la derecha. ${\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 un nuevo borde con etiqueta . La nueva etiqueta consta de los caracteres que faltan del prefijo común más largo y . Por lo tanto, la concatenación de las etiquetas 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 etiquetado . La nueva etiqueta consta de los caracteres restantes del borde eliminado que no se utilizaron 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. Agréguelo como una nueva hoja y conéctelo al nuevo nodo interno mediante un borde etiquetado . Por lo tanto, la etiqueta de borde 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 raíz a ruta. ${\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 parciales . ${\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 recorriendo el camino más a la derecha (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 serán atravesados ​​nuevamente en todos los pasos posteriores . Por lo tanto, como máximo los nodos se recorrerán 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. a 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 compartido por 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 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 col. 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 e 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". Revista de algoritmos discretos . 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 Computación . 22 (5): 935. CiteSeerX  10.1.1.105.6571 . doi :10.1137/0222058. S2CID  5074629.
• Kasai, T.; Lee, G.; Arimura, H.; Arikawa, S.; Parque, K. (2001). "Cálculo del prefijo común más largo en tiempo lineal en matrices de sufijos y sus aplicaciones ". Actas del duodécimo simposio anual sobre combinación de patrones combinatorios. Apuntes de conferencias sobre 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, Simón (2010). CST++ . Procesamiento de cadenas y recuperación de información. Apuntes de conferencias sobre 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; Lijadoras, Peter (2003). Construcción de matriz de sufijos de trabajo lineal simple. Actas de la 30ª conferencia internacional sobre autómatas, lenguajes y programación. págs. 943–955 . Consultado el 28 de agosto de 2012 .
• Fischer, Johannes (2011). Inducir el LCP-Array . Algoritmos y estructuras de datos. Apuntes de conferencias sobre 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 para el cálculo de matrices LCP en tiempo lineal ". Teoría de algoritmos - SWAT 2004. Apuntes de conferencias sobre informática. vol. 3111. pág. 372. doi :10.1007/978-3-540-27810-8_32. ISBN 978-3-540-22339-9.
• Kärkkäinen, Juha; Manzini, Giovanni; Puglisi, Simón J. (2009). Matriz de prefijo común más largo permutada . Coincidencia de patrones combinatorios. Apuntes de conferencias sobre informática. vol. 5577. pág. 181. doi :10.1007/978-3-642-02441-2_17. ISBN 978-3-642-02440-5.
• Puglisi, Simón J.; Turpin, Andrés (2008). "Compensaciones de espacio-tiempo para el cálculo de la matriz de prefijo común más largo ". Algoritmos y Computación. Apuntes de conferencias sobre informática. vol. 5369. pág. 124. doi :10.1007/978-3-540-92182-0_14. ISBN 978-3-540-92181-3.
• Gog, Simón; Ohlebusch, Enno (2011). Algoritmos de construcción de matrices LCP rápidos y ligeros (PDF) . Actas del taller sobre experimentos e ingeniería de algoritmos, ALENEX 2011. págs . Consultado el 28 de agosto de 2012 .
• Nong, Ge; Zhang, Sen; Chan, Wai Hong (2009). "Construcción de matriz de sufijos lineales mediante clasificación inducida casi pura" . Conferencia sobre compresión de datos de 2009. pag. 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 conferencias sobre 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 de Lempel-Ziv utilizando menos tiempo y espacio". Matemáticas en Informática . 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". Cartas de procesamiento de información . 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). pag. 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 los Sistemas Computacionales . 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 limitados por entropía más rápidos". Informática Teórica . 410 (51): 5354. doi : 10.1016/j.tcs.2009.09.012 .
• Fischer, Johannes; Kurpicz, Florian (5 de octubre de 2017). "Desmantelamiento de DivSufSort". Actas de la Conferencia de Stringología de Praga 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 consulta mínima de rango (RMQ) y muchas más estructuras de datos sucintas.
• Recorrido ascendente del árbol de sufijos emulado utilizando una matriz de sufijos y una matriz LCP (Java)
• Proyecto de indexación de texto (construcción en tiempo lineal de árboles de sufijos, matrices de sufijos, matrices LCP y transformación de Burrows-Wheeler)