In der Informatik suchen der Knuth-Morris-Pratt-Schnur-Suche-Algorithmus (oder KMP Algorithmus) nach Ereignissen eines "Wortes" innerhalb einer "Haupttextschnur" durch die Beschäftigung der Beobachtung, dass, wenn eine Fehlanpassung vorkommt, das Wort selbst genügend Information aufnimmt, um zu bestimmen, wo das folgende Match beginnen konnte, so Nachprüfung vorher verglichener Charaktere umgehend.

Der Algorithmus wurde 1974 von Donald Knuth und Vaughan Pratt, und unabhängig von James H. Morris konzipiert. Die drei haben es gemeinsam 1977 veröffentlicht.

ZEICHEN: Dieser Artikel verwendet Reihe bei Nullpunkteinstellung, um Schnuren zu vertreten; so darin wird angezeigt.

KMP Algorithmus

Bearbeitetes Beispiel des Suchalgorithmus

Um die Details des Algorithmus zu illustrieren, arbeiten wir durch einen (relativ künstlichen) Lauf des Algorithmus. Zu jeder vorgegebenen Zeit ist der Algorithmus in einem Staat, der durch zwei ganze Zahlen bestimmt ist, und, die beziehungsweise die Position anzeigen, innerhalb deren der Anfang eines zukünftigen Matchs für, und der Index in der Bezeichnung des Charakters zurzeit unter der Rücksicht ist. Das wird am Anfang des Laufs wie gezeichnet

1 2

m: 01234567890123456789012

S: ABC ABCDAB ABCDABCDABDE

W: ABCABD

i: 0123456

</Code>

Wir gehen weiter, indem wir aufeinander folgende Charaktere vergleichen, Charakteren dessen "anzupassen", sich von einem bis das folgende bewegend, wenn sie zusammenpassen. Jedoch, im vierten Schritt, kommen wir ist ein Raum und, eine Fehlanpassung. Anstatt zu beginnen, wieder an zu suchen, bemerken wir, dass nicht zwischen Positionen 0 und 3 in außer an 0 vorkommt; folglich, alle jene Charaktere vorher überprüft, wissen wir, dass es keine Chance gibt, den Anfang eines Matchs zu finden, wenn wir sie wieder überprüfen. Deshalb gehen wir zum folgenden Charakter weiter, untergehend und. (M wird zuerst 3 seitdem werden und dann 4 seitdem werden)

1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE

W: ABCDAB

i: 0123456

</Code>

Wir erhalten schnell ein fast ganzes Match, wenn, an , wir wieder eine Diskrepanz haben. Jedoch, gerade vor dem Ende des aktuellen teilweisen Matchs, sind wir gegangen, der der Anfang eines neuen Matchs sein konnte, so müssen wir das berücksichtigen. Da wir bereits wissen, dass diese Charaktere die zwei Charaktere vor der aktuellen Position vergleichen, brauchen wir nicht sie wieder zu überprüfen; wir fassen einfach neu und setzen fort, den aktuellen Charakter zu vergleichen. So nicht nur lassen wir vorher verglichene Charaktere, sondern auch vorher verglichene Charaktere dessen weg.

1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE

W: ABDABD

i: 0123456

</Code>

Diese Suche scheitert sofort jedoch, weil das Muster noch keinen Raum, so als in der ersten Probe enthält, kehren wir zum Anfang dessen zurück und beginnen, am folgenden Charakter zu suchen: Rücksetzen. (M wird zuerst 10 seitdem werden und dann 11 seitdem werden)

1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE

W: ABCDAB

i: 0123456

</Code>

Wieder stoßen wir sofort auf ein Match, aber der folgende Charakter vergleicht das Schlusszeichen des Wortes nicht. Wie zuvor vernünftig urteilend, gehen wir unter, um an der Schnur-Buchstaben zwei anzufangen, die bis zur aktuellen Position führt, unterzugehen und fortzusetzen, von der aktuellen Position zusammenzupassen.

1 2 m: 01234567890123456789012

S: ABC ABCDAB ABCDE

W: ABCDABD

i: 0123456

</Code>

Dieses Mal sind wir im Stande, das Match zu vollenden, dessen erster Charakter ist.

Beschreibung und Pseudocode für den Suchalgorithmus

Das obengenannte Beispiel enthält alle Elemente des Algorithmus. Im Augenblick nehmen wir die Existenz eines "teilweisen Matchs" Tisch an, der unten beschrieben ist, der anzeigt, wo wir nach dem Anfang eines neuen Matchs suchen müssen, falls der aktuelle in einer Fehlanpassung endet. Die Einträge dessen werden gebaut, so dass, wenn wir ein Match haben, das daran anfängt, scheitert, wenn man sich damit vergleicht, dann wird das folgende mögliche Match am Index in anfangen (d. h. ist der Betrag "des Zurückverfolgens", das wir nach einer Fehlanpassung tun müssen). Das hat zwei Implikationen: Erstens, der anzeigt, dass, wenn eine Fehlanpassung ist, wir nicht denselben Weg zurückverfolgen können und einfach den folgenden Charakter überprüfen müssen; und zweitens, obwohl das folgende mögliche Match am Index, als im Beispiel oben beginnen wird, brauchen wir keinen der Charaktere danach wirklich zu überprüfen, so dass wir fortsetzen, davon zu suchen. Der folgende ist eine Beispielpseudocodedurchführung des KMP-Suchalgorithmus.

Algorithmus kmp_search:

Eingang:

eine Reihe von Charakteren, S (der Text, der zu suchen ist)

eine Reihe von Charakteren, W (das Wort gesucht)

Produktion:

eine ganze Zahl (die Position bei Nullpunkteinstellung in S, an dem W gefunden wird)

definieren Sie Variablen:

eine ganze Zahl, M  0 (der Anfang des aktuellen Matchs in S)

eine ganze Zahl, ich  0 (die Position des aktuellen Charakters in W)

eine Reihe von ganzen Zahlen, T (der Tisch, geschätzt anderswohin)

während m+i weniger ist als die Länge von S, tun Sie:

wenn W [ich] = S [M + ich],

wenn ich (Länge von W)-1, gleich bin

geben Sie M zurück

lassen Sie mich  i + 1

sonst,

lassen Sie M  M + ich - T [ich],

wenn T [ich] größer bin als-1,

lassen Sie mich  T [ich]

sonst

lassen Sie mich  0

(wenn wir hier reichen, haben wir alle S erfolglos gesucht)

geben Sie die Länge von S zurück

Leistungsfähigkeit des Suchalgorithmus

Die vorherige Existenz des Tisches annehmend, hat der Suchteil des Knuth-Morris-Pratt Algorithmus Kompliziertheit O (k), wo die Länge ist und großer-O Notation zu sein. Als abgesehen vom festen oberirdischen, das im Hereingehen und Herausnehmen über die Funktion übernommen ist, wird die ganze Berechnung in der Schleife durchgeführt, wir werden einen gebundenen die Zahl von Wiederholungen dieser Schleife berechnen; um das zu tun, machen wir zuerst eine Schlüsselbeobachtung über die Natur dessen. Definitionsgemäß wird es gebaut, so dass, wenn ein Match, das daran begonnen hatte, scheitert, während es sich mit dann vergleicht, das folgende mögliche Match daran beginnen muss. Insbesondere muss das folgende mögliche Match an einem höheren Index vorkommen als, so dass

Mit dieser Tatsache werden wir zeigen, dass die Schleife in den meisten Malen durchführen kann. Weil in jeder Wiederholung es einen der zwei Zweige in der Schleife durchführt. Der erste Zweig nimmt unveränderlich zu und ändert sich nicht, so dass der Index des zurzeit geprüften Charakters dessen vergrößert wird. Der zweite Zweig trägt zu bei, und wie wir gesehen haben, ist das immer eine positive Zahl. So wird die Position des Anfangs des aktuellen potenziellen Matchs vergrößert. Jetzt endet die Schleife wenn; deshalb kann jeder Zweig der Schleife in den meisten Malen erreicht werden, da sie beziehungsweise zunehmen entweder oder, und: Wenn, dann sicher, so dass, da es durch die Einheitszunahme höchstens zunimmt, wir an einem Punkt in der Vergangenheit, und deshalb jeder Weise gehabt haben müssen, wie wir getan würden.

So führt die Schleife in den meisten Malen durch, zeigend, dass die Zeitkompliziertheit des Suchalgorithmus ist.

Hier ist eine andere Weise, an die Durchlaufzeit zu denken:

Lassen Sie uns sagen, dass wir beginnen, W und S an der Position i und p zu vergleichen, wenn W als eine Teilkette von S an p, dann W [0 durch die M] == S [p durch p+m] besteht.

Auf den Erfolg, d. h. haben das Wort und der Text an den Positionen zusammengepasst (W [ich] == S [p+i]), wir nehmen i um 1 (ich ++) zu.

Nach dem Misserfolg, d. h. dem Wort und dem Text passt an den Positionen nicht zusammen (W [ich]! = S [p+i]), der Textzeigestock wird still behalten, während der Wortzeigestock-Rollen-zurück ein bestimmter Betrag (ich = T [ich], wo T der Sprung-Tisch ist) Und wir versuchen, W [T [ich]] mit S [p+i] zu vergleichen.

Die maximale Zahl von Rollen-zurück von werde mir von mir das heißt, für jeden Misserfolg begrenzt, wir können nur Rollen-zurück so viel, wie wir bis zum Misserfolg fortgeschritten sind.

Dann ist es klar, dass die Durchlaufzeit 2k ist.

"Teilweises Match" Tisch (auch bekannt als "fungiert Misserfolg")

Die Absicht des Tisches ist, dem Algorithmus zu erlauben, jeden Charakter mehr nicht zu vergleichen, als einmal. Die Schlüsselbeobachtung über die Natur einer geradlinigen Suche, die dem erlaubt zu geschehen, besteht darin, dass darin, etwas Segment der Hauptschnur gegen ein anfängliches Segment des Musters überprüft zu haben, wir genau wissen, an der Plätze ein neues potenzielles Match konnte das zur aktuellen Position weitergehen konnte vor der aktuellen Position beginnen. Mit anderen Worten "suchen" wir das Muster selbst "vor" und kompilieren eine Liste aller möglichen Ausweichlösungen, die ein Maximum von hoffnungslosen Charakteren umgehen, während nicht das Opfern jedes Potenzials dabei zusammenpasst.

Wir wollen im Stande sein, für jede Position in, die Länge des längstmöglichen anfänglichen Segmentes der Führung bis zu (aber nicht einschließlich) dass Position, außer dem vollen Segment aufzublicken, das an dieser gerade erfolglos anfängt, um zusammenzupassen; das ist, wie weit wir in der Entdeckung des folgenden Matchs denselben Weg zurückverfolgen müssen. Folglich ist genau die Länge des längstmöglichen richtigen anfänglichen Segmentes, dessen auch ein Segment der Teilkette ist, die daran endet. Wir verwenden die Tagung, dass die leere Schnur Länge 0 hat. Da eine Fehlanpassung am wirklichen Anfang des Musters ein spezieller Fall ist (es gibt keine Möglichkeit des Zurückverfolgens), wir, gehen wie besprochen, oben unter.

Bearbeitetes Beispiel des tabellenbauenden Algorithmus

Wir denken das Beispiel zuerst. Wir werden sehen, dass es ziemlich gleichem Muster als die Hauptsuche folgt, und aus ähnlichen Gründen effizient ist. Wir gehen unter. Um zu finden, müssen wir eine richtige Nachsilbe entdecken, deren auch ein Präfix dessen ist. Aber es gibt keine richtigen Nachsilben dessen, so gehen wir unter. Ebenfalls.

Zu weitermachend, bemerken wir, dass es eine Abkürzung zur Überprüfung aller Nachsilben gibt: Lassen Sie uns sagen, dass wir eine richtige Nachsilbe entdeckt haben, die ein richtiges Präfix ist und an mit der Länge 2 (das Maximum möglich) endend; dann ist sein erster Charakter ein richtiges Präfix eines richtigen Präfixes, folglich ein richtiges Präfix selbst, und es endet daran, den wir bereits bestimmt haben, kann im Falle dass T [2] nicht vorkommen. Folglich in jeder Bühne besteht die Abkürzungsregel darin, dass man denken muss, Nachsilben einer gegebenen Größe m+1 nur zu überprüfen, wenn eine gültige Nachsilbe der Größe M in der vorherigen Bühne gefunden wurde (z.B. T [x] =m).

Deshalb brauchen wir uns nicht mit Teilketten sogar zu beschäftigen, die Länge 2 haben, und als im vorherigen Fall scheitert der alleinige mit der Länge 1, so.

Wir gehen zum nachfolgenden. Dieselbe Logik zeigt, dass die längste Teilkette, die wir denken müssen, Länge 1 hat, und obwohl in diesem Fall arbeitet, zurückrufen, dass wir nach Segmenten suchen, die vor dem aktuellen Charakter enden; folglich ebenso.

Jetzt den folgenden Charakter denkend, der ist, üben wir die folgende Logik aus: Wenn wir ein Submuster finden sollten, das vor dem vorherigen Charakter noch beginnt, zum aktuellen weitermachend, dann insbesondere würde es selbst ein richtiges anfängliches Segment haben, das an noch dem Anfang davor endet, der der Tatsache widerspricht, dass wir bereits gefunden haben, dass selbst das frühste Ereignis eines richtigen Segmentes ist, das daran endet. Deshalb brauchen wir nicht vorher zu schauen, um eine Endschnur dafür zu finden. Deshalb.

Schließlich sehen wir, dass der folgende Charakter im andauernden Segment, das daran anfängt, sein würde, und tatsächlich das auch ist. Außerdem dasselbe Argument wie über Shows, für die wir vorher nicht zu schauen brauchen, um ein Segment zu finden, so dass das es ist, und nehmen wir.

Deshalb kompilieren wir den folgenden Tisch:

Anderes Beispiel interessanter und kompliziert:

Beschreibung des Pseudocodes für den tabellenbauenden Algorithmus

Das Beispiel illustriert oben die allgemeine Technik, für den Tisch mit einem Minimum der Aufregung zu sammeln. Der Grundsatz ist der der gesamten Suche: Der grösste Teil der Arbeit wurde bereits im Bekommen zur aktuellen Position getan, so muss sehr wenig im Verlassen davon getan werden. Die einzige geringe Komplikation besteht darin, dass die Logik, die spät in der Schnur falsch richtig ist, nichtrichtige Teilketten am Anfang gibt. Das macht einen Initialisierungscode nötig.

Algorithmus kmp_table:

Eingang:

eine Reihe von Charakteren, W (das Wort, das zu analysieren ist)

eine Reihe von ganzen Zahlen, T (der Tisch, der zu füllen ist)

Produktion:

nichts (aber während der Operation bevölkert es den Tisch)

definieren Sie Variablen:

eine ganze Zahl pos  2 (die aktuelle Position rechnen wir in T)

eine ganze Zahl, cnd  0 (der Index bei Nullpunkteinstellung in W des folgenden Charakters der aktuellen Kandidat-Teilkette)

(die ersten paar Werte werden befestigt, aber davon verschieden, was der Algorithmus andeuten könnte)

lassen Sie T [0] -1, T [1]  0

während pos weniger ist als die Länge von W, tun Sie:

(der erste Fall: Die Teilkette geht weiter)

wenn W [pos - 1] = W [cnd],

lassen Sie cnd  cnd + 1, T [pos]  cnd, pos  pos + 1

(der zweite Fall: Es tut nicht, aber wir können zurückweichen)

sonst, wenn cnd> 0, cnd  T [cnd] lassen Sie

(der dritte Fall: Wir sind an Kandidaten knapp geworden. Bemerken Sie cnd = 0)

lassen Sie sonst T [pos]  0, pos  pos + 1

Leistungsfähigkeit des tabellenbauenden Algorithmus

Die Kompliziertheit des Tabellenalgorithmus ist, wo die Länge dessen ist. Als abgesehen von einer Initialisierung wird die ganze Arbeit in der Schleife getan, es ist genügend zu zeigen, dass diese Schleife rechtzeitig durchführt, der durch das gleichzeitige Überprüfen der Mengen getan wird und. Im ersten Zweig, wird als beide bewahrt und werden gleichzeitig, aber natürlich erhöht, wird vergrößert. Im zweiten Zweig, wird dadurch ersetzt, den wir oben gesehen haben, ist immer ausschließlich weniger als, so zunehmend. Im dritten Zweig, wird erhöht und ist nicht, so beide und Zunahme. Seitdem bedeutet das das in jeder Bühne entweder oder ein für Zunahmen gebundener niedrigerer; deshalb, da der Algorithmus einmal endet, muss er enden danach bei den meisten Wiederholungen der Schleife, seitdem beginnt daran. Deshalb ist die Kompliziertheit des Tabellenalgorithmus.

Leistungsfähigkeit des KMP Algorithmus

Da die zwei Teile des Algorithmus, beziehungsweise, Kompliziertheiten haben, und die Kompliziertheit des gesamten Algorithmus ist.

Diese Kompliziertheiten sind dasselbe, egal wie viele wiederholende Muster in sind oder.

Varianten

Eine Echtzeitversion von KMP kann mit einem getrennten Misserfolg-Funktionstisch für jeden Charakter im Alphabet durchgeführt werden. Wenn eine Fehlanpassung auf dem Charakter im Text vorkommt, wird der Misserfolg-Funktionstisch für den Charakter für den Index im Muster befragt, an dem die Fehlanpassung stattgefunden hat. Das wird die Länge der längsten Teilkette zurückgeben, die beim Zusammenbringen eines Präfixes des Musters mit der zusätzlichen Bedingung endet, dass der Charakter nach dem Präfix ist. Mit dieser Beschränkung braucht der Charakter im Text nicht wieder in der folgenden Phase überprüft zu werden, und so nur eine unveränderliche Zahl von Operationen wird zwischen der Verarbeitung jedes Index des Textes durchgeführt. Das befriedigt die Echtzeitrechenbeschränkung.

Der Kabine-Algorithmus verwendet eine modifizierte Version der KMP Aufbereitungsfunktion, die lexikografisch minimale Schnur-Folge zu finden. Die Misserfolg-Funktion wird progressiv berechnet, als die Schnur rotieren gelassen wird.

Siehe auch

• Schnur von Boyer-Moore sucht Algorithmus
• Schnur von Rabin-Karp sucht Algorithmus
• Aho-Corasick Schnur, die Algorithmus vergleicht

Links

• Schnur, die Applet Zeichentrickfilm Sucht
• Eine Erklärung des Algorithmus und der Probe C ++ codiert durch David Eppstein
• Knuth-Morris-Pratt-Algorithmus-Beschreibung und C codieren durch Christian Charras und Thierry Lecroq
• Erklärung des Algorithmus von Kratzer durch FH Flensburg.
• Das Brechen von Schritten, KMP durch Chu-Cheng Hsieh zu führen.
• http://www.youtube.com/watch?v=Zj_er99KMb8 halten NPTELHRD YouTube Video Vorlesungen