java - ¿Cómo ayuda LCP a encontrar el número de ocurrencias de un patrón?

algorithm data-structures

Question

He leído que el prefijo común más largo (LCP) podría usarse para encontrar el número de apariciones de un patrón en una cadena.

Específicamente, solo necesita crear la matriz de sufijos del texto, ordenarlo y luego, en lugar de hacer una búsqueda binaria para encontrar el rango y poder calcular el número de ocurrencias, simplemente calcula el LCP para cada entrada sucesiva en el matriz de sufijos

Aunque el uso de la búsqueda binaria para encontrar el número de ocurrencias de un patrón es obvio, no puedo entender cómo el LCP ayuda a encontrar el número de ocurrencias aquí.

Por ejemplo, para esta matriz de sufijos para banana :

LCP Suffix entry
N/A a
1 ana
3 anana
0 banana
0 na
2 nana 

¿Cómo me ayuda el LCP a encontrar el número de ocurrencias de una subcadena como "banana" o "na"?

¿Alguna ayuda para descubrir cómo LCP ayuda aquí?

Answer 1

El prefijo común más largo (LCP) es el antepasado común más bajo (LCA) en un árbol de sufijos. Una vez que tenga el ancestro común más bajo, puede contar el número de nodos que se derivan del LCA. Esto le dará el número de apariciones de un patrón en el árbol de sufijos. Esta es la relación entre el LCP y el LCA.

Answer 2

No conozco ninguna forma de utilizar la matriz LCP en lugar de realizar una búsqueda binaria, pero creo que se refiere a la técnica descrita por Udi Manber y Gene Myers en las matrices de sufijos: un nuevo método para la búsqueda de cadenas en línea .

La idea es la siguiente: para encontrar el número de apariciones de una cadena P (longitud m) en un texto T (longitud N),

• Utiliza la búsqueda binaria contra la matriz de sufijos de T (como sugeriste)
• Pero usted lo acelera utilizando la matriz LCP como estructura de datos auxiliar. Más específicamente, genera una versión especial de la matriz LCP (lo llamaré LCP-LR a continuación) y la utiliza.

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 O (log N) que necesita hacer, compara P con la entrada actual de la matriz de sufijos, lo que significa una comparación de cadena completa de arriba a m caracteres. Entonces la complejidad es O (m * log N).

La matriz LCP-LR ayuda a mejorar esto a O (m + log N), de la siguiente manera:

• En cualquier punto durante el algoritmo de búsqueda binario, considera, como de costumbre, un rango (L, ..., R) de la matriz de sufijos y su punto central M, y decide si continúa su búsqueda en el sub-rango izquierdo ( L, ..., M) o en el sub-rango derecho (M, ..., R).
• Para tomar la decisión, compare P con la cadena en M. Si P es idéntico a M, ha terminado, pero si no, habrá comparado los primeros k caracteres de P y luego habrá decidido si P es lexicográficamente más pequeño o mayor que M. Supongamos que el resultado es que P es mayor que M.

• Entonces, en el siguiente paso , consideras (M, ..., R) y un nuevo punto central M ''en el medio:

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

  El truco ahora es que LCP-LR está precomputado de tal manera que una búsqueda O (1) le indica el prefijo común más largo de M y M '', lcp (M, M'').

  Ya sabes (en el paso anterior) que M tiene un prefijo de k caracteres en común con P: lcp (P, M) = k. Ahora hay tres posibilidades:

  • Caso 1: k <lcp (M, M ''), es decir, P tiene menos caracteres de prefijo en común con M que M tiene en común con M''. Esto significa que el (k + 1) -th carácter 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''. Así continuamos en la mitad derecha (M '', ..., R).
  • Caso 2: k> lcp (M, M ''), es decir, P tiene más caracteres de prefijo en común con M que M tiene en común con M''. En consecuencia, si comparáramos P con M '', el prefijo común sería más pequeño que k, y M'' sería lexicográficamente más grande que P, entonces, sin hacer la comparación , continuamos en la mitad izquierda (M, .. .,METRO'').
  • Caso 3: k == lcp (M, M ''). Entonces, M y M ''son idénticos a P en los primeros k caracteres. Para decidir si continuamos en la mitad izquierda o derecha, es suficiente comparar P con M ''a partir del carácter (k + 1) -th .

• Seguimos recursivamente.

El efecto general es que ningún carácter de P 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 m, por lo que la complejidad total es O (m + log N).

Obviamente, la pregunta clave que queda es ¿cómo calculamos LCP-LR para que nos diga en O (1) el tiempo del lcp entre dos entradas de la matriz de sufijos? Como dijo, la matriz LCP estándar le indica el lcp de entradas consecutivas solamente, es decir, lcp (x-1, x) para cualquier x. Pero M y M ''en la descripción anterior no son necesariamente entradas consecutivas, entonces, ¿cómo se hace eso?

La clave para esto es darse cuenta de que solo se producirán ciertos rangos (L, ..., R) durante la búsqueda binaria: siempre comienza con (0, ..., N) y se divide en el centro, y luego continúa hacia la izquierda o hacia la derecha y divide esa mitad de nuevo y así sucesivamente. Si lo piensa: cada entrada de la matriz de sufijos aparece como un punto central de exactamente un rango posible durante la búsqueda binaria. Por lo tanto, hay exactamente N intervalos distintos (L ... M ... R) que posiblemente pueden desempeñar un papel durante la búsqueda binaria, y basta con calcular previamente lcp (L, M) y lcp (M, R) para esos N posibles rangos Entonces, eso es 2 * N valores precomputados distintos, por lo tanto, LCP-LR es O (N) en tamaño.

Además, hay un algoritmo recursivo directo para calcular los valores 2 * N de LCP-LR en tiempo O (N) desde la matriz de LCP estándar; sugeriría publicar una pregunta por separado si necesita una descripción detallada de eso.

Para resumir:

• Es posible calcular LCP-LR en tiempo O (N) y espacio O (2 * N) = O (N) de LCP
• El uso de LCP-LR durante la búsqueda binaria ayuda a acelerar el procedimiento de búsqueda de O (M * log N) a O (M + log N)
• Como sugirió, puede usar dos búsquedas binarias para determinar el extremo izquierdo y derecho del rango de coincidencia para P, y la longitud del rango de coincidencia se corresponde con el número de ocurrencias para P.