Verständnis Knuth-Morris-Pratt-Algorithmus

Kann mir das jemand erklären? Ich habe schon darüber zu Lesen und es ist immer noch schwer zu Folgen.

text : ababdbaababa

Muster: Abeba

Tabelle für Abeba -1 0 0 1 2.

Ich glaube, ich verstehe, wie die Tabelle aufgebaut ist, aber ich verstehe nicht, wie zu verschieben, nachdem Konflikt aufgetreten ist. Scheint, wie wir nicht einmal verwenden Sie die Tabelle beim schalten?

Wann verwenden wir die Tabelle?

chekc das aus: jakeboxer.com/blog/2009/12/13/...

InformationsquelleAutor antz | 2012-11-07

16

die Tabelle wird verwendet, wenn Ihr mismatch Auftritt. Jetzt wenden wir das Muster in Ihren text ein:

Starten Sie passenden text mit Muster und testen Sie, ob das Muster lässt sich in text, beginnend an der ersten position. Vergleichen Sie text[1] mit pattern[1] - und das entpuppt sich als ein match. Sie tun das gleiche für text[2], text[3] und text[4].

wenn Sie wollen-match - text[5] mit pattern[5] Sie nicht über eine übereinstimmung (d<>a). Sie wissen dann, dass Ihre Muster nicht beginnen bei der ersten position. Sie könnten dann starten Sie das passende über und über wieder für position 2, aber das ist nicht effizient. Sie können verwenden Sie die Tabelle nun.

Der Fehler aufgetreten bei pattern[5] so dass Sie gehen, um table[5] 2. Das sagt dir, dass Sie beginnen können, Abgleich an der aktuellen position wieder mit 2 bereits erkannten Zeichen. Anstatt start-matching-position 2, können Sie beginnen, an Ihrer bisherigen position (1) + table[5] (2)=3. In der Tat, Wenn wir uns text[3] und text[4] wir sehen, dass es gleich pattern[1] und pattern[2], respectivily.

Die zahlen in der Tabelle sagen Ihnen, wie viele Positionen sind bereits abgestimmt, wenn ein Fehler Auftritt. In diesem Fall werden 2 Zeichen für das nächste Muster wurden bereits abgestimmt. Sie können dann sofort beginnen, für die passende position 3 und skip-position 2 (wie kann das pattern nicht gefunden, beginnend an der position[2]).
- Ja. Ich verstehe den ersten Teil, der. aber wenn Sie halten goin mit es Sie am Ende nur einmal verschieben, bis das Ende, das ist, warum es war verwirrend (scheint sinnlos). ist das normal?
- Also deine Frage ist "warum machen wir diese Tabelle, wenn wir es nur nutzen, wenn?"? Gut, Ihre text-string in der Regel ist viel mehr (wie ein DNA-Sequenz), und Sie dann wird verwenden Sie die Tabelle mehr. Sie tatsächlich nutzen die Tabelle jedes mal, wenn ein text[i] doesn ' T match pattern[j]
- "2 bereits gematchte Zeichen" dies läutete die Glocke, und die Lichter eingeschaltet in meinem Gehirn Jetzt verstehe ich, warum nehmen Sie die maximale Länge die Präfix-und suffix num.. Danke!
InformationsquelleAutor Origin
29

Hier habe ich kurz beschrieben computing die Präfix-Funktion und verschiebt sich durch den text hier.

Weitere Informationen: Knuth–Morris–Pratt-string-such-Algorithmus

Verschiebung durch den text :
```
Text:     ABC ABCDAB ABCDABCDABDE
Pattern : ABCDABD
```
Szenario 1 - Es gibt einige übereinstimmende Zeichen/s in Muster und Text.

e.g 1: hier gibt es 3 passenden Zeichen.

Erhalten Sie den Wert aus der Tabelle für 3 Zeichen. (index 2, ABC) ich.e 0
Also shift = 3 - 0 ich.e 3

e.g 2: hier gibt es 6 passenden Zeichen.

Den Wert aus der Tabelle für 6 Zeichen. (index 5, ABCDAB) ich.e 2
Daher Verschiebung = 6 - 2 ich.e 4

Szenario 2 - Wenn es keine übereinstimmende Zeichen dann shift um eins.
- Vielen Dank für die Erklärung mit Bildern!! Ich wünschte, diese Antwort war auserwählt vor allen Antworten. Ich konnte nicht einen einzigen anderen Ressourcen, die erklärte, die Präfix-Tabelle generation so deutlich.
InformationsquelleAutor Rukmal Dias
10

Gut, das ist ein altes Thema, aber hoffentlich jemand, der sucht diese in der Zukunft wird es sehen. Die Antwort oben ist gut, aber ich war durch ein Beispiel selbst zu sehen, was Los ist genau.

Ersten Teil der Ausstellung stammt aus wiki, der Teil, den ich wirklich wollte, um zu erarbeiten, wie das backtracking-array aufgebaut ist.

Hier geht:

wir arbeiten, durch eine (relativ künstliche) ausführen des Algorithmus, wo
```
W = "ABCDABD" and 
S = "ABC ABCDAB ABCDABCDABDE". 
```
Jederzeit der Algorithmus in einem Zustand bestimmt, der durch zwei Ganzzahlen:

m bezeichnet die position in S, das ist der Anfang von einem potenziellen match für W

i den index W bezeichnet den Charakter, die derzeit unter Berücksichtigung.

In jedem Schritt vergleichen wir S[m+i] mit W[i] und Voraus, wenn Sie gleich sind. Dies wird dargestellt, zu Beginn des Laufs, wie
```
              1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W: ABCDABD
i: 0123456
```
Gehen wir durch den Vergleich von aufeinanderfolgenden Zeichen von W auf "parallel" Zeichen des S, sich von einem zum nächsten, wenn Sie übereinstimmen. Jedoch, im vierten Schritt,
wir bekommen S[3] ist ein Raum und W[3] = 'D', ein Missverhältnis. Eher als Anfang für die Suche wieder auf S[1], wir beachten Sie, dass kein 'A' vorkommt, zwischen den Positionen 0 und 3 in S
außer bei 0; folglich haben überprüft, alle diese Zeichen zuvor, wir wissen, es gibt keine chance, den Beginn einer Partie, wenn wir überprüfen Sie Sie erneut.
Deshalb bewegen wir uns auf das nächste Zeichen, Einstellung m = 4 und i = 0.
```
              1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:     ABCDABD
i:     0123456
```
Haben wir schnell erhalten Sie eine fast vollständige übereinstimmung "ABCDAB", wenn Sie bei W[6] (S[10]), haben wir wieder eine Diskrepanz. Jedoch, kurz vor dem Ende der aktuellen partiellen
match, wir übergeben eine "AB" - könnte das der Beginn einer neuen übereinstimmen, so müssen wir dies berücksichtigen. Wie wir bereits wissen, dass diese Zeichen entsprechen
die zwei Zeichen vor der aktuellen position brauchen wir Sie nicht überprüfen Sie Sie wieder, wir einfach zurücksetzen m = 8, i = 2 und weiter, passend zu den aktuellen Charakter. So,
nicht nur, dass wir vorher weglassen übereinstimmenden Zeichen von S, aber auch vorher übereinstimmenden Zeichen von W.
```
              1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:         ABCDABD
i:         0123456
```
Diese Suche nicht sofort, jedoch, als die Muster immer noch nicht die ein Leerzeichen enthalten, so wie in der ersten Studie, die wir zurück an den Anfang von W und beginnen
die Suche auf das nächste Zeichen von S: m = 11, zurückgesetzt i = 0.
```
              1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:            ABCDABD
i:            0123456
```
Wir mal wieder sofort treffen auf ein match "ABCDAB" aber das nächste Zeichen, 'C', entspricht nicht der endgültige Charakter " D " des Wortes W. Argumentation wie zuvor,
wir setzen m = 15, zu Beginn zwei-Zeichen-string "AB" im Vorfeld der aktuellen position i = 2, und weiterhin die passenden von der aktuellen position.
```
              1         2  
m: 01234567890123456789012
S: ABC ABCDAB ABCDABCDABDE
W:                ABCDABD
i:                0123456
```
Dieser Zeit sind wir in der Lage das Spiel, dessen ersten Charakter S[15].

Obigen Beispiel enthält alle Elemente des Algorithmus. Für den moment gehen wir davon aus, die Existenz eines "partial match" T-Tabelle, die nachfolgend beschrieben werden, die
zeigt an, wo wir brauchen, um für den start eines neuen Spiels in dem Fall, dass der aktuelle endet in einem Missverhältnis. Die Einträge von T sind so konstruiert, dass
wenn wir ein match, beginnend bei S[m] nicht, dass beim Vergleich von S[m + - i] W[i], dann die nächste mögliche übereinstimmung wird beginnen bei index m + i - T[i] in S (das ist,
T[i] ist die Menge der "backtracking" wir müssen tun, nach einem mismatch). Dies hat zwei Implikationen: Erstens, T[0] = -1, was bedeutet, dass, falls W[0] ist eine Diskrepanz,
wir können nicht zurück und müssen einfach schauen, dass das nächste Zeichen; und zweitens, obwohl die nächsten möglichen match beginnt bei index m + i - T[i], wie im Beispiel
oben brauchen wir nicht wirklich überprüfen, der T[i] - Zeichen danach, so dass wir weiterhin auf der Suche von W[T[i]].

BACKTRACKING-ARRAY-KONSTRUKTION:

also das backtracking array T[] wir rufen lps[], lasst uns sehen, wie wir das berechnen dieser Kerl
```
lps[i] = the longest proper prefix of pat[0..i] 
            which is also a suffix of pat[0..i].
```
Beispiele:
Für die Muster "AABAACAABAA",
```
lps[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]
```
//so-nur durch diese gehen sehr schnell
```
 lps[0] is just 0 by default
 lps[1] is 1 because it's looking at AA and A is both a prefix and suffix
 lps[2] is 0 because it's looking at AAB and suffix is B but there is no prefix equal to B unless you count B itself which I guess is against the rules
 lps[3] is 1 because it's looking at AABA and first A matches last A
 lps[4] is 2 becuase it's looking at AABAA and first 2 A matches last 2 A
 lps[5] is 0 becuase it's looking at AABAAC and nothing matches C
 ...


 For the pattern “ABCDE”, lps[] is [0, 0, 0, 0, 0]
 For the pattern “AAAAA”, lps[] is [0, 1, 2, 3, 4]
 For the pattern “AAABAAA”, lps[] is [0, 1, 2, 0, 1, 2, 3]
 For the pattern “AAACAAAAAC”, lps[] is [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]
```
- Und das macht Total Sinn, wenn man darüber nachdenkt...wenn Sie nicht übereinstimmen, Sie wollen zurück zu gehen, so weit wie Sie können, natürlich, wie weit zurück Sie gehen (das suffix
Teil) ist im wesentlichen das Präfix, da müssen Sie start-matching aus dem ersten Zeichen wieder durch definition. also, wenn dein string aussieht

aaaaaaaaaaaaaaa..b..aaaaaaaaaaaaaaac und Sie mismatche auf den letzten char c, dann, das Sie wiederverwenden möchten aaaaaaaaaaaaaaa als Ihr neues Kopf, finde es nur durch
- Einfach die besten!!!
InformationsquelleAutor tweaking

-1

Eine Komplette Lösung, die mit Java:

package src.com.recursion;
/*
 * This Expains the Search of pattern in text in O(n)
 */
public class FindPatternInText {
    public int checkIfExists(char[] text, char[] pattern) {
        int index = 0;
        int[] lps = new int[pattern.length];
        createPrefixSuffixArray(pattern, lps);
        int i = 0;
        int j = 0;
        int textLength = text.length;
        while (i < textLength) {
            if (pattern[j] == text[i]) {
                j++;
                i++;
            }
            if (j == pattern.length)
                return i - j;
            else if (i < textLength && pattern[j] != text[i]) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return index;
    }

    private void createPrefixSuffixArray(char[] pattern, int[] lps) {
        lps[0] = 0;
        int index = 0;
        int i = 1;
        while (i < pattern.length) {
            if (pattern[i] == pattern[index]) {
                lps[i] = index;
                i++;
                index++;
            } else {
                if (index != 0) {
                    index = lps[index - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
    }
    public static void main(String args[]) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        System.out.println("Point where the pattern match starts is "
                + new FindPatternInText().checkIfExists(text.toCharArray(), pattern.toCharArray()));
    }
}

InformationsquelleAutor Akhil Gupta

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.