Schneller k Mismatch String Matching Algorithmus

10

Ich suche nach einem schnellen k-Mismatch-String-Matching-Algorithmus. Bei einer gegebenen Musterfolge P der Länge m und einer Textzeichenfolge T der Länge n benötige ich einen schnellen (linearen Zeit-) Algorithmus, um alle Positionen zu finden, an denen P mit einer Teilzeichenfolge von T mit höchstens k Fehlpaarungen übereinstimmt. Dies unterscheidet sich vom Problem der k-Unterschiede (Bearbeitungsabstand). Eine Nichtübereinstimmung impliziert, dass der Teilstring und das Muster an höchstens k Positionen einen anderen Buchstaben haben. Ich benötige wirklich nur k = 1 (höchstens 1 Fehlanpassung), daher reicht auch ein schneller Algorithmus für den speziellen Fall von k = 1 aus. Die Alphabetgröße beträgt 26 (Groß- und Kleinschreibung wird nicht berücksichtigt, daher sollte der Platzbedarf mit der Größe des Alphabets nicht zu schnell wachsen (z. B. nimmt der FAAST-Algorithmus, glaube ich, in der Größe des Alphabets exponentiell Platz ein, und so weiter) ist nur für Protein- und Gensequenzen geeignet).

Ein auf dynamischer Programmierung basierender Ansatz ist im schlimmsten Fall O (mn), was zu langsam ist. Ich glaube, dass es dafür Modifikationen des Boyer-Moore-Algorithmus gibt, aber ich bin nicht in der Lage, solche Papiere in die Hände zu bekommen. Ich habe kein Abonnement für den Zugriff auf wissenschaftliche Zeitschriften oder Veröffentlichungen, daher müssen alle Referenzen gemeinfrei sein.

Ich würde mich sehr über Hinweise oder Verweise auf frei verfügbare Dokumente oder den Algorithmus selbst für dieses Problem freuen.

Paresh
quelle
2
Wenn das Muster festgelegt ist (der zu übereinstimmende Text jedoch variiert), können Sie möglicherweise einen endlichen Automaten erstellen und den Text durchlaufen. Es gibt auch Algorithmen, die Suffixbäume verwenden (normalerweise gut, wenn der Text konstant ist und das Muster variiert, aber auch anwendbar, wenn beide variieren). Möglicherweise finden Sie einige Referenzen im Web. (Ich habe noch keine Antwort hinzugefügt, da ich mir der auf Suffixbäumen basierenden Algorithmen nicht sehr sicher bin. Wenn jemand weiß, kann er diesen Kommentar ignorieren.)
Aryabhata
@ Aryabhata Danke! Sowohl das Muster als auch der Text ändern sich. In diesem Zusammenhang wäre der Bau eines endlichen Automaten zu teuer, insbesondere wenn der Spielraum für eine Nichtübereinstimmung berücksichtigt wird. Suffixbäume / Suffix-Arrays habe ich nie verwendet und weiß wenig über sie, hatte aber den Eindruck, dass sie langsam aufgebaut und effizient sind, hauptsächlich für die exakte Übereinstimmung. Aber ich werde diese Option weiter untersuchen. Alle Zeiger in diese oder eine andere Richtung wären am nützlichsten!
Paresh
1
Nein, Suffixbäume können auch für ungefähre Übereinstimmungen verwendet werden. Zumindest behauptet das Wiki so: en.wikipedia.org/wiki/Suffix_tree
Aryabhata

Antworten:

5

Für dieses Problem können Suffix-Arrays verwendet werden. Sie enthalten die Startpositionen jedes Suffixes der Zeichenfolge, sortiert in lexikografischer Reihenfolge. Obwohl sie naiv in -Komplexität konstruiert werden können, gibt es Methoden, um sie in Θ ( n ) -Komplexität zu konstruieren . Siehe zum Beispiel dies und das . Nennen wir dieses Suffix-Array SA.O(nlogn)Θ(n)

Sobald das Suffix-Array erstellt wurde, müssen wir ein LCP-Array (Longest Common Prefix) für das Suffix-Array erstellen. Das LCP-Array speichert die Länge des längsten gemeinsamen Präfixes zwischen zwei aufeinanderfolgenden Präfixen im Suffix-Array (lexikografische aufeinanderfolgende Suffixe). Somit enthält LCP [i] die Länge des längsten gemeinsamen Präfixes zwischen SA [i] und SA [i + 1]. Dieses Array kann auch in linearer Zeit erstellt werden: siehe hier , hier und hier für einige gute Referenzen.

uvu<vminu<=k<=v1LCP[k]LCPO(n)O(nlogn)LCP[u,v]O(1)

iTLCPTiPPT[i]l0TPLCPT[i+l0+1]P[l0+1]kLCPO(1)O(k) LCPiTO(nk)

O(nk+(n+m)log(n+m))O(nk+nlogn)m=O(n)O(nk)

Paresh
quelle
Groß! Ich habe jetzt etwas auf meiner TODO-Liste zu lesen :-)
Aryabhata
Der Link zu siam.org im zweiten Absatz ist defekt, aber der verlinkte Artikel ist
leecbaker
4

O(n+m)kO(nk+m)

Die Idee ähnelt dem Rabin-Karp-Rolling-Hash- Algorithmus für exakte Teilstring-Übereinstimmungen.

m2km/2k2k2k

k

k

Ich gehe davon aus (Vorbehalt: Ich habe es nicht selbst ausprobiert), dass dies in der Praxis wahrscheinlich schneller und möglicherweise einfacher zu codieren / zu warten ist als die Verwendung eines auf Suffixbäumen basierenden Ansatzes.

Aryabhata
quelle
Brauche nur eine Klarstellung. Mit "..separieren Sie jede Zeichenfolge der Länge m in 2k Blöcke mit jeweils m / 2k Größe ..." meinen Sie, dass jeder Teilstring der Länge m in T (mit der Länge n) in 2k Blöcke unterteilt wird. Und dieser Hash kann in O (n) nach der Rolling-Hash-Methode berechnet werden. Dann wird die Musterzeichenfolge auch in 2k-Blöcke unterteilt, und die entsprechenden Hashes werden verglichen, wobei berücksichtigt wird, dass höchstens k Blöcke nicht übereinstimmen. Wenn ja, könnten wir möglicherweise alle Fälle verwerfen, in denen die Anzahl der Fehlpaarungen mehr als k beträgt. Habe ich richtig verstanden
Paresh
kΩ(nk)O(n)
Ich mag diesen Ansatz! Dieser Ansatz ist jedoch im Allgemeinen schnell, verschlechtert sich jedoch zu O (mnk), wenn die Anzahl der Übereinstimmungen hoch ist (O (n) Übereinstimmungen). Vor diesem Hintergrund habe ich zwei rollende Hashes beibehalten, unter der Annahme, dass beide keine Kollision für dieselbe Eingabe haben können (ich habe dies nicht mathematisch gemacht, da ich die Geschwindigkeit sehen wollte). Auf diese Weise müssen wir eine Übereinstimmung nicht char-by-char überprüfen, wenn die beiden Hashes übereinstimmen. Dies ist im Allgemeinen ziemlich schnell, aber auch dies ist langsam, wenn die Anzahl der Übereinstimmungen groß ist. Damit und mit der von Ihnen vorgeschlagenen Art war es für große Spiele langsam.
Paresh
Dies könnte im schlimmsten Fall schneller gemacht werden, wenn wir den Text in teilenmm/2kmO(nkm)
mm/2k2kk+1k+cΩ(nm)mm/2k