Trovare la sottostringa comune più lunga in un set di dati di grandi dimensioni

Question

Negli ultimi giorni ho svolto ricerche approfondite, ho letto tante cose che ora sono più confuso che mai. Come si trova la sottostringa comune più lunga in un set di dati di grandi dimensioni? L'idea è di rimuovere il contenuto duplicato da questo set di dati (di varie lunghezze, quindi l'algo dovrà essere eseguito continuamente). Con set di dati di grandi dimensioni intendo circa 100mb di testo.

Suffix tree? Matrice suffisso? Rabin-Karp? Qual è il modo migliore? E c'è una biblioteca là fuori che può aiutarmi?

Sperando davvero in una buona risposta, mi fa molto male la testa. Grazie! :-)

Answer 1

Ho sempre utilizzato gli array di suffissi. Perché mi è stato detto sempre che questo è il modo più veloce lì.

Se si sta esaurendo la memoria sulla macchina, l'algoritmo è in esecuzione, è sempre possibile salvare l'array in un file sul disco rigido. Rallenterà considerevolmente l'algoritmo ma fornirà il risultato, almeno.

E non credo che una libreria possa fare un lavoro migliore di un buon algoritmo scritto e pulito.

LE: Btw, non è necessario rimuovere alcun dato per trovare la sottostruttura comune più lunga.

Dal 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 

Non è necessario ordinare nulla, hai solo una volta di analizzare i dati 100MB, e buid un n * m array di caratteri per memorizzare il vostro computer. Controllare anche this page

LE: Rabin-Karp è un algoritmo di corrispondenza del modello, non è necessario qui.