trouver de longues sous-chaînes répétées dans une chaîne massive

Question

J'ai imaginé naïvement que je pouvais construire un suffixe trie où je garde un compte de visite pour chaque nœud, puis les nœuds les plus profonds avec des nombres supérieurs à un sont le résultat que je cherche pour. J'ai une chaîne vraiment très longue (des centaines de mégaoctets). J'ai environ 1 Go de RAM. C'est pourquoi la construction d'un suffixe trie avec des données de comptage est trop inefficace dans l'espace pour travailler pour moi. Pour citer Wikipedia's Suffix tree:

Le stockage de l'arborescence de suffixes d'une chaîne nécessite généralement beaucoup plus d'espace que le stockage de la chaîne elle-même. La grande quantité d'informations dans chaque arête et nœud rend l'arborescence de suffixes très coûteuse, consommant environ dix à vingt fois la taille de la mémoire du texte source dans de bonnes implémentations. Le tableau des suffixes réduit cette exigence à un facteur de quatre, et les chercheurs ont continué à trouver des structures d'indexation plus petites.

Et c'était les commentaires de wikipedia sur l'arbre, pas trie.

Comment puis-je trouver de longues séquences répétées dans une quantité de données aussi importante et dans un délai raisonnable (par exemple, moins d'une heure sur une machine de bureau moderne)?

(Quelques liens wikipedia pour éviter les gens de les afficher comme la « réponse »: Algorithms on strings et surtout Longest repeated substring problem ;-))

Answer 1

La méthode la plus efficace consiste à créer un index des sous-chaînes et à les trier. C'est une opération O (n lg n).

BWT la compression fait cette étape, donc c'est un problème bien compris et il y a des implémentations de type radix et suffix (revendiquer O (n)) et ainsi de le rendre aussi efficace que possible. Cela prend encore beaucoup de temps, peut-être plusieurs secondes pour les grands textes.

Si vous voulez utiliser le code utilitaire, C++ std::stable_sort() effectue beaucoup mieux questd::sort() pour le langage naturel (et beaucoup plus rapide que C de qsort(), mais pour des raisons différentes).

Ensuite, visiter chaque élément pour voir la longueur de sa sous-chaîne commune avec ses voisins est O (n).

Answer 2

ce texte avec des sauts de mot? Ensuite, je soupçonne que vous voulez une variation de mot-dans-contexte: faire une copie de chaque ligne n fois pour n mots dans une ligne, en cassant chaque ligne à chaque mot; trier alpha de l'ensemble; chercher des reprises.

S'il s'agit d'une seule longue chaîne de caractères, comme des séquences d'ADN bioinformatique, vous voulez construire quelque chose comme votre trie sur le disque; Construire un enregistrement pour chaque personnage avec un décalage de disque pour les prochains-nœuds. J'examinerais le volume 3 de Knuth, section 5.4, «tri externe».

Answer 3

Le moyen le plus simple pourrait être simplement plunk down the $100 pour un tas plus de RAM. Sinon, vous devrez probablement regarder les structures sauvegardées sur le disque pour conserver votre arborescence de suffixes.

Answer 4

Vous pouvez consulter les arborescences de suffixes sur disque. J'ai trouvé ce Suffix tree implementation library à travers Google, plus un tas d'articles qui pourraient aider à l'implémenter vous-même.

Answer 5

Pouvez-vous résoudre votre problème en créant un suffix array à la place? Sinon, vous devrez probablement utiliser l'un des arbres de suffixes sur disque mentionnés dans les autres réponses.

Answer 6

Vous pouvez résoudre ce problème en utilisant la division et la conquête. Je pense que cela devrait être la même complexité algorithmique que l'utilisation d'une structure arborescente, mais peut-être mise en œuvre sage moins efficace

void LongSubstrings(string data, string prefix, IEnumerable<int> positions) 
{ 
    Dictionary<char, DiskBackedBuffer> buffers = new Dictionary<char, DiskBackedBuffer>(); 
    foreach (int position in positions) 
    { 
     char nextChar = data[position]; 
     buffers[nextChar].Add(position+1); 
    } 

    foreach (char c in buffers.Keys) 
    { 
     if (buffers[c].Count > 1) 
      LongSubstrings(data, prefix + c, buffers[c]); 
     else if (buffers[c].Count == 1) 
      Console.WriteLine("Unique sequence: {0}", prefix + c); 
    } 
} 

void LongSubstrings(string data) 
{ 
    LongSubstrings(data, "", Enumerable.Range(0, data.Length)); 
} 

Après cela, vous devez faire une classe qui a mis en œuvre DiskBackedBuffer telle qu'elle était une liste de numéros, et quand le tampon atteignait une certaine taille, il s'écrivait lui-même sur le disque en utilisant un fichier temporaire, et rappelait du disque lorsqu'il était lu.

Answer 7

répondre à ma propre question:

Étant donné qu'une longue correspondance est aussi un match court, vous pouvez échanger des passes multiples pour la RAM d'abord trouver des correspondances plus courts et voir si vous pouvez « pousser » ces matchs.

L'approche littérale à ceci est de construire un trie (avec des comptes dans chaque noeud) de toutes les séquences d'une certaine longueur fixe dans les données. Vous devez ensuite éliminer tous les nœuds qui ne correspondent pas à vos critères (par exemple, la correspondance la plus longue). Ensuite, faites un passage ultérieur à travers les données, en construisant le trie plus loin, mais pas plus large. Répétez jusqu'à ce que vous ayez trouvé la ou les séquences répétées les plus longues.

Un bon ami a suggéré d'utiliser le hachage. En hachant la séquence de caractères de longueur fixe commençant à chaque caractère, vous avez maintenant le problème de trouver des valeurs de hachage en double (et en vérifiant la duplication, car le hachage est avec perte). Si vous allouez un tableau à la longueur des données pour contenir les valeurs de hachage, vous pouvez faire des choses intéressantes, par ex. pour voir si une correspondance est plus longue que votre passe de longueur fixe des données, vous pouvez simplement comparer les séquences de hachages plutôt que de les régénérer. Etc.

Answer 8

Juste une pensée de attardé qui me est venue ...

En fonction de votre système d'exploitation/environnement. Vous pouvez créer un très grand suffixe sur le disque à l'aide de mmap(), puis conserver un sous-ensemble le plus fréquemment accédé de cet arbre dans la mémoire cache (par exemple, pointeurs 64 bits & mmap().) Mémoire.

Answer 9

Qu'en est-il un programme simple comme ceci:

S = "ABAABBCCAAABBCCM" 

def findRepeat(S): 
    n = len(S) 
    #find the maxim lenth of repeated string first 
    msn = int(floor(n/2)) 
    #start with maximum length 
    for i in range(msn,1,-1): 
     substr = findFixedRepeat(S, i) 
     if substr: 
      return substr 
    print 'No repeated string' 
    return 0 

def findFixedRepeat(str, n): 
    l = len(str) 
    i = 0 
    while ((i + n -1) < l): 
     ss = S[i:i+n] 
     bb = S[i+n:] 
     try: 
      ff = bb.index(ss) 
     except: 
      ff = -1 

     if ff >= 0: 
      return ss; 
     i = i+1 
    return 0 
print findRepeat(S)