¿Cómo acelerar el cálculo de la longitud de la subcadena común más larga?

Question

Tengo dos cuerdas muy grandes y estoy tratando de averiguar su Longest Common Substring.

Una forma es utilizar sufijo árboles (se supone que tienen una muy buena complejidad, aunque una aplicación compleja), y el otro es el método de programación dinámica (ambos son mencionados en la página de Wikipedia vinculado anteriormente).

El uso de programación dinámica

El problema es que el método de programación dinámica tiene un enorme tiempo de ejecución (complejidad es O(n*m), donde n y m son longitudes de las dos cadenas).

Lo que quiero saber (antes de saltar para implementar árboles de sufijos): ¿Es posible acelerar el algoritmo si solo quiero saber la longitud de la subcadena común (y no la subcadena común en sí)?

Answer 1

¿Será más rápido en la práctica? Sí. ¿Será más rápido con respecto a Big-Oh? No. La solución de programación dinámica siempre es O (n * m).

El problema que puede encontrar con los árboles de sufijo es que cambia el escaneo de tiempo lineal del árbol de sufijos por una penalización enorme en el espacio. Los árboles de sufijo generalmente son mucho más grandes que la tabla que necesitaría implementar para una versión de programación dinámica del algoritmo. Dependiendo de la longitud de sus cadenas, es muy posible que la programación dinámica sea más rápida.

Buena suerte :)

Answer 2

Estos hará que se ejecute más rápido, aunque todavía será O(nm).

Una optimización está en el espacio (que se podría ahorrar un poco de tiempo de la asignación) se está dando cuenta de que LCSuff solo depende de la fila anterior - por lo tanto, si sólo se preocupan por la longitud, puede optimizar el espacio O(nm) a O(min(n,m)).

La idea es mantener solo dos filas: la fila actual que está procesando, y la fila anterior que acaba de procesar, y descartar el resto.

Answer 3

Myer's bit vector algorithm lo puede ayudar. Funciona mediante el uso de manipulación de bits y es un enfoque mucho más rápido.

Answer 4

Aquí hay un algoritmo simple que puede terminar en O ((m + n) * log (m + n)), y mucho más fácil de implementar en comparación con el algoritmo de árbol de sufijos que es O (m + n) en tiempo de ejecución.

que comience con la longitud mínima común (minL) = 0, y la longitud común máxima (maxL) = min (m + n) +1.

1. if (minL == maxL - 1), the algorithm finished with common len = minL. 

2. let L = (minL + maxL)/2 

3. hash every substring of length L in S, with key = hash, val = startIndex. 

4. hash every substring of length L in T, with key = hash, val = startIndex. check if any hash collision in to hashes. if yes. check whether whether they are really common substring. 

5. if there're really common substring of length L, set minL = L, otherwise set maxL = L. goto 1. 

El problema restante es cómo hash todas las subcadenas con longitud L en el tiempo O (n). Puede usar una fórmula polinómica de la siguiente manera:

Hash(string s, offset i, length L) = s[i] * p^(L-1) + s[i+1] * p^(L-2) + ... + s[i+L-2] * p + s[i+L-1]; choose any constant prime number p. 

then Hash(s, i+1, L) = Hash(s, i, L) * p - s[i] * p^L + s[i+L];