Wann würdest du KMP über BOYER-MOORE verwenden?

Question

Ich lerne gerade über Mustervergleichsalgorithmen und bin auf diese beiden Algorithmen gestoßen. Ich habe folgende allgemeine Ideen:

KMP

• Vergleicht Text von links nach rechts
• einen Fehler Array Verwendet zu verschieben intelligent
• nimmt O (m), wobei m die Länge ist das Muster, Versagen Array
• nimmt O (m), Raum
• nimmt O (n), die Zeit zu berechnen, eine Zeichenfolge

zu suchen, 0

BM

• Vergleichen Muster von den letzten Charakter
• Verwenden schlechter Charakter springt und guter Suffix springt
• O (m + Größe des Alphabets) nimmt Tabellen
• nimmt O (m + Größe zu berechnen des Alphabets), Raum
• nimmt O (n), aber in der Regel besser

stieß ich auf die folgende qu suchen estion, die diese Frage ausgelöst (Wahr oder Falsch):

Die Knuth-Morris-Pratt (KMP) Algorithmus ist eine gute Wahl, wenn wir Suche nach dem gleichen Muster wiederholt in vielen verschiedenen Texten wollen.

Deshalb glaube ich, die Antwort nur wahr ist, weil die Annahme ist, dass jedes Mal, wenn der Algorithmus auf verschiedenen Text laufen die Vorverarbeitung nur O (n), wobei für BM ist es O (n + Größe des Alphabets). Ich bin jedoch nicht sicher, ob ich die korrekte Annahme mache, dass jedes Mal, wenn der Algorithmus erneut ausgeführt wird, eine neue Tabelle neu berechnet wird. Denn der Text fällt immer ins englische Alphabet. Ich müsste die Tabelle nur einmal berechnen und die Tabelle einfach wiederverwenden. So am Ende des Tages, würde die Antwort auf diese Frage auf der Tatsache abhängen, dass die Algorithmen sind alle auf Text ausgeführt werden, die in das gleichen Alphabet enthalten ist, oder gibt es einen anderen Faktor, die es beeinflussen können?

Answer 1

In der Theorie werden beide Algorithmen "ähnliche" Leistung haben; KMP wird in der Suche Phase etwa 2n Vergleiche tun und Boyer-Moore über 3n Vergleiche in der Suchphase im schlimmsten Fall tun werden. In beiden Fällen müssen Sie die Vorverarbeitung nicht wiederholen, wenn Sie einen neuen Text erhalten.

Aber die wirkliche Antwort ist, dass Sie keines in der Praxis verwenden sollten.

Der lineare Hilfsspeicher, der von beiden Algorithmen benötigt wird, führt aufgrund der zusätzlichen Speicherzugriffe zu einer erheblich gröberen Leistung auf modernen Architekturen. Die Ideen hinter Boyer-Moore und KMP untermauern die meisten schnellen String-Matching-Algorithmen.So etwas wie KMPs "failure function" Idee wird von jedem mir bekannten, praktisch effektiven String Matching Algorithmus benutzt; Es stellt sich heraus, dass Sie eine nicht optimale "Fehlerfunktion" für ein Muster im Flug berechnen können, das Ihnen immer noch lineare Zeitanpassung bietet, während Sie nur konstanten zusätzlichen Platz benötigen. Boyer-Moore ist schneller als linear im "durchschnittlichen Fall" der Anpassung eines festen Musters an zufälliges Rauschen, was sich in vielen praktischen Situationen auswirkt.