Ein Beispiel, bei dem der Knuth-Morris-Pratt-Algorithmus schneller ist als Boyer-Moore?

10

Diese Seite über den Knuth-Moriss-Pratt-Algorithmus im Vergleich zu Boyer-Moore beschreibt einen möglichen Fall, in dem der Boyer-Moore-Algorithmus unter einer geringen Sprungdistanz leidet, während KMP eine bessere Leistung erzielen könnte.
Ich suche ein gutes Beispiel (Text, Muster), das diesen Fall klar demonstrieren kann.

algorithms substrings matching Erb
quelle
SO stackoverflow.com/questions/12656160/…
Ciro Santilli 27 病毒 审查 六四 六四 27

Antworten:

3

Es gibt ein Papier, das ein gutes Experiment über diese String-Matching-Algorithmen für verschiedene Muster durchgeführt hat: " Vergleich von String-Matching-Algorithmen: eine Hilfe zur Sicherheit von Informationsinhalten "

Es gibt auch eine Studie dieser String-Matching-Algorithmen für die japanische Sprache: Vergleich und Verbesserung von String-Matching-Algorithmen für japanische Texte

Ich hoffe, diese sind nützlich, um ein Gefühl für die Effizienz von Algorithmen zu bekommen!

Reza
quelle
3

Nun, diese Muster lassen KMP schneller arbeiten:

T = aaaaaaaaaa P = aaaa KMP wird 10 Vergleichsschritte versuchen, während Boyer-Moore 28 Schritte unternehmen wird

Ein anderes Beispiel:

T = aaaaaaaaaa P = abab KMP versucht 8 Vergleichsschritte, wobei BM 12 versucht.

Erb
quelle
Im ersten Beispiel finden beide Algorithmen bei der ersten Schicht sofort eine Übereinstimmung - wie würden sie mehr als 4 Vergleiche durchführen?
BartoszKP