Matriz de sufijos

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 6 de noviembre de 2021; las comprobaciones requieren 2 ediciones .

La matriz de sufijos es una matriz ordenada lexicográficamente de todos los sufijos de la cadena . Esta estructura de datos fue diseñada por Eugene Myers y Udy Manber como una alternativa más económica al árbol de sufijos en términos de requisitos de memoria. A menudo se usa cuando se necesitan búsquedas rápidas de subcadenas, como en la transformación Burrows-Wheeler (BWT) y como estructura de datos en un índice de búsqueda .

Ejemplo

Considere la cadena "abracadabra" de 11 caracteres de longitud.

abracadabra 1 2 3 4 5 6 7 8 9 10 11

Lista ordenada de sus sufijos:

a Abra abracadabra acadabra adábra sostén bracadabra Cadabra Dabra real academia de bellas artes racadabra

La matriz de sufijos de esta cadena es {11,8,1,4,6,9,2,5,7,10,3}, porque el sufijo "a" comienza con el carácter 11, el sufijo "abra" comienza con el carácter 8. ir, y así sucesivamente, hasta el último sufijo "racadabra", que comienza con el tercer carácter de la palabra original.

Ahora, usando esta matriz, puede encontrar fácilmente todas las subcadenas. Por ejemplo, si necesita encontrar la subcadena "ab", basta con encontrar todos los sufijos que comienzan con "ab". Al ordenar alfabéticamente, están uno al lado del otro. Usando la búsqueda binaria , encontramos los sufijos 2 y 3 "abra" y "abracadabra" que coinciden con el elemento 2 y 3 de la matriz de sufijos (8 y 1). Esto significa que la subcadena buscada "ab" aparece en el primer y octavo carácter de la palabra original.

Edificio

Se puede construir una matriz de sufijos con o sin un árbol de sufijos rellenando una cadena a una longitud cíclica de una potencia de dos y aplicándole un algoritmo específico.

A través del árbol de sufijos

Construimos un árbol de sufijos para la cadena T$. Donde T es texto.
En este árbol de sufijos, ejecutamos una búsqueda en profundidad con la prioridad de elegir bordes mínimos lexigráficamente.
Durante la búsqueda, consideramos que $ (centinela) es el carácter lexicográficamente más pequeño.
Llegada a la hoja alcanzando algún sufijo lexicográficamente más pequeño aún no considerado en ese momento, cuyo valor en la hoja, comenzando con el índice en, debe escribirse en la celda actual de la matriz de sufijos.
Esto da como resultado una matriz de sufijos para todo el texto.

La complejidad de la construcción es , la línea incluye la construcción de un árbol de sufijos y una búsqueda en profundidad. ${\ estilo de visualización O (| T |)}$

Buscar

Se puede realizar una búsqueda en una matriz de sufijos mediante una búsqueda binaria. Su peor calificación . Pero puedes acelerar hasta . ${\ estilo de visualización O (n \ log {m})}$ $O(n+\log _{2}{m})$

Búsqueda binaria ingenua

La idea de la búsqueda es que si el patrón ocurre en el texto, todos los sufijos que comienzan con en la matriz de sufijos se ubicarán uno al lado del otro. $PAGS$ $Posición$
Realizamos una búsqueda binaria en la matriz de sufijos y encontramos el índice más pequeño : no comienza con y el índice más grande : no comienza con ninguno de los dos . $PAGS$ $Posición$ $i$ $Posición(i-1)$ $PAGS$ $i'$ $Pos(i'+1)$ $PAGS$
Entonces la muestra viene en posiciones hasta . $Posición(i)$ $Pos(i')$
Si hay muchos prefijos de patrones, la puntuación baja a . ${\ estilo de visualización O (n \ log {m})}$

Aceleración simple

$L$ , — límites del intervalo de búsqueda. Al principio , . $R$ ${\ estilo de visualización L = 1}$ ${\ estilo de visualización R = m}$
Recordamos la longitud de los prefijos , , coincidiendo con el prefijo . $Posición(L)$ $Posición(R)$ ${\ Displaystyle PAG: l, r}$
${\ Displaystyle mlr = min (l, r)}$ .
En la próxima comparación en posición, comenzamos a procesar caracteres no desde la primera posición, sino desde . $M={\frac{L+R}{2))$ ${\displaystylemlr(l,r)+1}$
Por lo general, el tiempo de trabajo , pero el peor tiempo de trabajo sigue siendo . $O(n+\log {m})$ ${\ estilo de visualización O (n \ log {m})}$

Aceleración vía LCP

El prefijo común más grande ( eng. Prefijo común más grande ) - para dos cadenas , - la longitud del prefijo coincidente más grande. $S_{1}$ $S_{2}$ $LCP(S_{1},S_{2})$

En este algoritmo, supondremos que para cualquiera de los dos sufijos se calcula . La función se calcula en la etapa de preprocesamiento al construir un árbol. La siguiente afirmación también es cierta : ${\ estilo de visualización LCP}$ $O(1)$ $LCP(i,j)=min(LCP(k,k+1)),i\leq k<j$

Gracias a esta función, puede optimizar la búsqueda binaria de una matriz de sufijos.

Lema : si los primeros caracteres del sufijo coinciden en los límites izquierdo y derecho ( , respectivamente, los índices de la matriz de sufijos) , entonces el mismo número de caracteres coincidirá para todos los sufijos en el segmento . $L$ $R$ $k$ ${\ estilo de visualización [L, R]}$

${\ estilo de visualización L = 1}$ , , , . Los siguientes casos son posibles ${\ estilo de visualización R = | T |}$ ${\ estilo de visualización l = LCP (P, L)}$ ${\ estilo de visualización r = LCP (P, R)}$
1. ${\ estilo de visualización l = r}$ .
  1. Compara el sufijo in con el patrón en posición . $M={\frac{L+R}{2))$ ${\ estilo de visualización l+1}$
  2. El sufijo es lexicográficamente mayor o igual y ocurrió una discrepancia en la posición del sufijo (si hay una coincidencia lexicográfica y , entonces lo consideramos igual a ), luego cambiamos los límites de búsqueda: . $PAGS$ $i$ $METRO$ $PAGS$ $i$ ${\ estilo de visualización | P | +1}$ $L=M,R=R,l=i-1$
  3. De lo contrario, cambie los bordes de esta manera: . ${\ estilo de visualización L = L, R = M, r = i-1}$
2. ${\ estilo de visualización l> r}$ . Comprobamos _ $LCP(L,M),M={\frac {L+R}{2))$
  1. $LCP(L,M)>l$ . En este caso, después de la posición en el sufijo en la posición , sigue un número de caracteres iguales a los de , que no coinciden con el patrón (si lo hicieran, habría más). Por lo tanto, debe cambiar los límites de la siguiente manera: . $yo$ $METRO$ $L$ $yo$ $L=M,R=R,l=l$
  2. $LCP(L,M)<l$ , esto significa que después de la posición en el sufijo, la posición es seguida por una discrepancia con algunos caracteres del prefijo , y la mayoría de las coincidencias con el patrón están contenidas en el segmento, lo que significa que definitivamente no habrá ocurrencias de el patrón en el segmento. Necesita cambiar los bordes de la siguiente manera: . ${\ Displaystyle LCP (L, M)}$ $METRO$ $L$ $L$ ${\ estilo de visualización [M, R]}$ ${\ estilo de visualización L = L, R = M, r = LCP (L, M)}$
  3. ${\ Displaystyle LCP (L, M) = l}$ , esto significa que en el segmento los primeros caracteres de todos los sufijos coinciden y es imposible saber inmediatamente a qué subsegmento ir. Para resolver esto, es necesario comparar con el patrón los caracteres que siguen a la posición en el sufijo. Si es lexicográficamente menor o igual que y hay una discrepancia en la-ésima posición (si hay una coincidencia lexicográfica y, entonces consideramos igual ), entonces cambiamos los límites de la siguiente manera:, ,; de lo contrario ( lexicográficamente mayor): , ,. ${\ estilo de visualización [L, M]}$ $yo$ $PAGS$ $yo$ $METRO$ $METRO$ $PAGS$ $i$ $METRO$ $PAGS$ $i$ ${\ estilo de visualización | P | +1}$ ${\ estilo de visualización L = M}$ ${\ estilo de visualización R = R}$ ${\ estilo de visualización l = i-1}$ $METRO$ ${\ estilo de visualización R = M}$ ${\ estilo de visualización L = L}$ ${\ estilo de visualización r = i-1}$
3. ${\ estilo de visualización l<r}$ . Verificamos y comparamos con como en el paso anterior, pero cambiamos a y a . $LCP(R,M),M={\frac {L+R}{2))$ $r$ $L$ $R$ $yo$ $r$
El algoritmo funciona hasta y se igualan . Esto significa que hay un segmento de coincidencia. Si no se cumple el invariante , entonces no hay patrón como subcadena en el texto. $yo$ $r$ ${\ estilo de visualización | P |}$ ${\ estilo de visualización L <P <R}$

Tal superaceleración da tiempo , ya que se realizan iteraciones sobre la matriz de sufijos. $O(|P|+\log _{2}{|T|})$ ${\ estilo de visualización \ registro _ {2} {| T |}}$

Algoritmos relacionados

Algoritmo de Kasai para construir una matriz de los prefijos comunes más grandes.

Véase también

árbol de sufijos

Enlaces

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.

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