Trouver la plus longue sous-chaîne commune dans un ensemble de données volumineux

Question

Ces derniers jours, j'ai beaucoup étudié ce sujet, j'ai lu tellement de choses que je suis maintenant plus confus que jamais. Comment trouve-t-on la plus longue sous-chaîne commune dans un grand ensemble de données? L'idée est de supprimer le contenu en double de cet ensemble de données (de différentes longueurs, de sorte que l'algo devra fonctionner en continu). Par grand ensemble de données, je veux dire environ 100mb de texte.

Suffixe? Suffixe tableau? Rabin-Karp? Quelle est la meilleure façon? Et y a-t-il une bibliothèque qui peut m'aider? En espérant vraiment une bonne réponse, j'ai vraiment mal à la tête. Je vous remercie! :-)

Answer 1

J'ai toujours utilisé des tableaux de suffixes. Parce qu'on m'a toujours dit que c'est le moyen le plus rapide.

Si vous manquez de mémoire sur la machine, l'algorithme est en cours d'exécution, vous pouvez toujours enregistrer votre baie dans un fichier sur votre disque dur. Cela va considérablement ralentir l'algorithme mais il fournira le résultat, au moins.

Et je ne pense pas qu'une bibliothèque fera un meilleur travail qu'un bon algorithme écrit et propre. LE: Btw, vous n'avez pas besoin d'enlever des données pour trouver la plus longue sous-chaîne commune.

De l'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 

Vous n'avez pas besoin de trier quoi que ce soit, il suffit d'analyser une fois que vos données de 100 Mo, et un BUID n * m tableau de caractères pour stocker votre calcul. Vérifiez également this page

LE: Rabin-Karp est un algorithme de correspondance de modèles, dont vous n'avez pas besoin ici.