Wie findet man den längsten gemeinsamen Teilstring mehrerer Strings?

Question

Ich schreibe ein Python-Skript, wo ich mehrere Zeichenfolgen habe.

Zum Beispiel:

x = "brownasdfoersjumps" 
y = "foxsxzxasis12sa[[#brown" 
z = "thissasbrownxc-34a@s;" 

In all diesen drei Saiten, haben sie eine Unter Zeichenfolge gemeinsam die brown ist. Ich möchte es in einer Art und Weise suchen, die ich ein Wörterbuch erstellen möchten:

dict = {[commonly occuring substring] => 
      [total number of occurrences in the strings provided]} 

Was ist die beste Art und Weise zu tun, dass sein würde? Bedenkt man, dass ich jedes Mal mehr als 200 Saiten haben werde, was wäre ein einfacher/effizienter Weg?

Answer 1

Dies ist ein relativ optimierter naive Algorithmus. Sie transformieren zuerst jede Sequenz in eine Menge all ihrer Ngramme. Dann schneiden Sie alle Mengen und finden das längste Ngram in der Kreuzung.

from functools import partial, reduce 
from itertools import chain 
from typing import Iterator 


def ngram(seq: str, n: int) -> Iterator[str]: 
    return (seq[i: i+n] for i in range(0, len(seq)-n+1)) 


def allngram(seq: str) -> Iterator[str]: 
    lengths = range(len(seq)) 
    ngrams = map(partial(ngram, seq), lengths) 
    return set(chain.from_iterable(ngrams)) 


sequences = ["brownasdfoersjumps", 
      "foxsxzxasis12sa[[#brown", 
      "thissasbrownxc-34a@s;"] 

seqs_ngrams = map(allngram, sequences) 
intersection = reduce(set.intersection, seqs_ngrams) 
longest = max(intersection, key=len) # -> brown 

Während dies durch kurze Sequenzen führt, ist dieser Algorithmus bei langen Sequenzen äußerst ineffizient. Wenn Ihre Sequenzen lang sind, können Sie eine Heuristik hinzufügen, um die größtmögliche ngram-Länge zu begrenzen (d. H. Die längste mögliche gemeinsame Teilzeichenfolge). Ein offensichtlicher Wert für eine solche Heuristik kann die Länge der kürzesten Sequenz sein.

def allngram(seq: str, minn=1, maxn=None) -> Iterator[str]: 
    lengths = range(minn, maxn) if maxn else range(minn, len(seq)) 
    ngrams = map(partial(ngram, seq), lengths) 
    return set(chain.from_iterable(ngrams)) 


sequences = ["brownasdfoersjumps", 
      "foxsxzxasis12sa[[#brown", 
      "thissasbrownxc-34a@s;"] 

maxn = min(map(len, sequences)) 
seqs_ngrams = map(partial(allngram, maxn=maxn), sequences) 
intersection = reduce(set.intersection, seqs_ngrams) 
longest = max(intersection, key=len) # -> brown 

Dieses noch zu lange dauern kann (oder Ihre Maschine aus RAM laufen lassen), so dass Sie vielleicht einige optimalen Algorithmen (siehe den Link ich links in meinem Kommentar zu Ihrer Frage) lesen über wollen.

aktualisieren

die Anzahl der Saiten zu zählen, wobei jedes ngram

from collections import Counter 
sequences = ["brownasdfoersjumps", 
      "foxsxzxasis12sa[[#brown", 
      "thissasbrownxc-34a@s;"] 

seqs_ngrams = map(allngram, sequences) 
counts = Counter(chain.from_iterable(seqs_ngrams)) 

tritt Counter eine Unterklasse von dict ist, so seine Instanzen ähnliche Schnittstellen haben:

print(counts) 
Counter({'#': 1, 
     '#b': 1, 
     '#br': 1, 
     '#bro': 1, 
     '#brow': 1, 
     '#brown': 1, 
     '-': 1, 
     '-3': 1, 
     '-34': 1, 
     '-34a': 1, 
     '-34a@': 1, 
     '-34a@s': 1, 
     '-34a@s;': 1, 
     ... 

Sie kann die Anzahl filtern, um Teilstrings zu hinterlassen, die mindestens inauftretenStrings: {string: count for string, count in counts.items() if count >= n}