Was sind die Hauptunterschiede zwischen den Suchalgorithmen von Knuth-Morris-Pratt und Boyer-Moore?

Question

Was sind die Hauptunterschiede zwischen dem Suchalgorithmus Knuth-Morris-Pratt und dem Boyer-Moore Suchalgorithmus?

Ich weiß, KMP sucht nach Y in X, versucht, ein Muster in Y zu definieren, und speichert das Muster in einem Vektor. Ich weiß auch, dass BM besser für kleine Wörter, wie DNA (ACTG) funktioniert.

Was sind die Hauptunterschiede in ihrer Funktionsweise? Welcher ist schneller? Welcher ist weniger computergierig? In welchen Fällen?

Answer 1

Moore's UTexas webpage geht durch beide Algorithmen in einer Schritt-für-Schritt-Mode (er stellt auch verschiedene technische Quellen) :

• Knuth-Morris-Pratt
• Boyer-Moore

Nach dem Mann selbst,

Der klassische Boyer-Moore-Algorithmus aus dem Phänomen leidet, dass es so effizient auf kleine Alphabeten, nicht zu arbeiten wie DNA neigt. Der Abstand Abstand neigt dazu, mit der Musterlänge zu wachsen, weil Teilstrings häufig wieder auftreten. Indem man sich mehr an das erinnert, was bereits erreicht hat, kann man größere Überspringungen durch den Text bekommen. Ein kann sogar "perfekten Speicher" anordnen und somit jedes Zeichen unter am häufigsten betrachten, während der Boyer-Moore-Algorithmus, obwohl linear, ein Zeichen mehrmals aus dem Text untersuchen kann. Diese Idee von erinnert mehr in der Literatur von anderen untersucht worden. Es leidet an der Notwendigkeit für sehr große Tabellen oder Zustandsmaschinen.

Allerdings gab es einige modifications of BM, die kleine Alphabet Suche lebensfähig gemacht haben.

Answer 2

In einer groben Erklärung

Boyer-Moore Ansatz ist zu versuchen, das letzte Zeichen des Musters paßt anstelle des ersten mit der Annahme, dass, wenn es am Ende nicht überein gibt keine Notwendigkeit, zu versuchen, Spiel am Anfang. Dies ermöglicht eine „große Sprünge“ deshalb BM funktioniert besser, wenn das Muster und der Text „natürliche Text“ (dh Englisch)

Knuth-Morris-Pratt sucht nach Vorkommen eines „Wortes“ ähneln suchen W innerhalb einer Haupt "Textzeichenkette" S, indem die Beobachtung verwendet wird, dass, wenn eine Fehlanpassung auftritt, das Wort selbst ausreichende Information verkörpert, um zu bestimmen, wo die nächste Übereinstimmung beginnen könnte, wodurch eine erneute Untersuchung von zuvor übereinstimmenden Zeichen umgangen wird. (Quelle: Wiki)

Das bedeutet KMP ist besser geeignet für kleine Mengen wie DNA (ACTG)

Answer 3

Boyer-Moore-Technik passen die Zeichen von rechts nach links, funktioniert gut auf lange Muster. knuth moris pratt passen die Zeichen von links nach rechts, arbeitet schnell auf kurzen Mustern.