Encontrar la subcadena común más larga en un gran conjunto de datos

Question

En los últimos días he investigado esto extensamente, he leído tantas cosas que ahora estoy más confundido que nunca. ¿Cómo se puede encontrar la subcadena común más larga en un gran conjunto de datos? La idea es eliminar el contenido duplicado de este conjunto de datos (de diferentes longitudes, por lo que el algoritmo deberá ejecutarse continuamente). Por gran conjunto de datos me refiero a aproximadamente 100mb de texto.

¿Árbol de sufijos? Sufijo matriz? Rabin-Karp? ¿Cuál es la mejor manera? ¿Y hay una biblioteca por ahí que pueda ayudarme?

Realmente esperando una buena respuesta, me duele mucho la cabeza. ¡Gracias! :-)

Answer 1

Siempre he estado usando matrices de sufijos. Porque me han dicho que esta es la forma más rápida de llegar allí.

Si se está quedando sin memoria en la máquina el algoritmo se está ejecutando, siempre puede guardar su matriz en un archivo en su disco duro. Disminuirá considerablemente el algoritmo, pero proporcionará el resultado, al menos.

Y no creo que una biblioteca haga un mejor trabajo que un buen algoritmo escrito y limpio.

LE: Por cierto, no necesita eliminar ningún dato para encontrar la subcadena común más larga.

Desde el Longest Common Substring Problem:

function LCSubstr(S[1..m], T[1..n]) 
    L := array(1..m, 1..n) 
    z := 0 
    ret := {} 
    for i := 1..m 
     for j := 1..n 
      if S[i] = T[j] 
       if i = 1 or j = 1 
        L[i,j] := 1 
       else 
        L[i,j] := L[i-1,j-1] + 1 
       if L[i,j] > z 
        z := L[i,j] 
        ret := {} 
       if L[i,j] = z 
        ret := ret ∪ {S[i-z+1..i]} 
    return ret 

No es necesario para ordenar nada, sólo tiene que analizar sintácticamente una vez que sus datos de 100 MB, y una BUID n * m conjunto de caracteres para almacenar la informática. También verifique this page

LE: Rabin-Karp es un algoritmo de coincidencia de patrones, no lo necesita aquí.