Diskussion:Knuth-Morris-Pratt-Algorithmus

Überarbeitet

So. Ich habe die Seite komplett überarbeitet. Vektorgrafiken sind nicht nötig, das geht auch mit Tabellen. Java-Code ist zu spezifisch und unübersichtlich, dafür gibt's Pseudocode. Laufzeitanalyse ist in Prosa-Form dabei. 77nafets 18:33, 28. Mai 2006 (CEST)

Frühere Diskussion

Rücksprungweite des Rautezeigers muss noch geklärt werden. Conny 10:26, 12. Feb 2005 (CET).

Was gefällt Dir denn an "immer ganz nach links zurrück" nicht? Ich bilde mir ein, daß das so stimmt. --Bodo Thiesen 06:05, 2. Mai 2005 (CEST)

Ich hab mir mal erlaubt, die Einleitung etwas benutzerfreundlicher zu gestalten. Man wurde ja förmlich erschlagen, wenn man die Seite aufgerufen hat. Jetzt wird auch der Fachfremde nicht gleicht abgeschreckt. Ich würde vielleicht den gesamten Text etwas überarbeiten. Da sich der Algorithmus ohnehin sehr schlecht in Worte fassen lässt, würde ich das ganze vielleicht etwas grafischer gestalten. Darf ich? :D --Cerno 18:21, 3. Mai 2005 (CEST)

Hey Cerno,
klingt gut, stell uns die Vektorquellen der Grafiken für eventuelle Korrekturen zur Verfügung. Gespannt auf deine Umsetzung, Grüße, Conny 23:11, 6. Mai 2005 (CEST).

irgendwas stimmt mit dem javacode nicht. die treffer werden in einem container pos gespeichert, wo ist der definiert ? beim aufbau der next-tabelle wird auf j>= 0 geprüft. direkt davor wird j=-1 gesetzt, also wird der while block nie ausgeführt. hm --anon 14.6.2005

Ich denke ebenfalls das der Java Code mit dem Algorithmus drüber entspricht. Der Algorithmus zeigt wie man die Wiederaufsetztpunkte erreicht in dem man das Muster veschiebt. Und Bei dem Java Code steht in der Wiederaufsetztpunk Liste bereits die Tatsächliche Position oder?

Es waehre vielleicht gut wenn man den Text der den Algorithmus beschreibt in Schritt 1, Schritt 2, usw. aufgliedert so, dass man ein Schema bekommt, dass man abarbeiten kann. Den zweiten Algorithmus hab ich mal auf ein Beispiel aus meinem Skript angewandt und da kam was ganz anderes raus. gruss martin (2005-09-18)

Überarbeitung

Der Javaquelltext ist zweifelhaft, die Seite wird komplett neu gesichtet. Als Ziel sollte neben dem Artikel an sich eine gute Metabeschreibung herauskommen, welche auf einen Javaquelltext abbildet. Conny 21:51, 12. Dez 2005 (CET).

Überarbeitung Pseudocode

Ich glaube, der Pseudocode ist falsch bei der Präfix-Analyse. Zumindest ist er so ungeschickt, dass ich ihn nicht verstehe, das innere while ist jedenfalls unnötig und schaut auf den ersten blick nach einem Aufwand in O(n^2) aus! :(.

Ich hab die Präfix-Analyse mal hübsch, logisch und funktionierend in PHP implementiert. Kann jemand bitte mal den Pseudocode gegenchecken?

Grüße von Thomas am 12.12.2006

PS: Weiß leider nicht, wie man das als Code formatiert, also klickt auf "bearbeiten"...

<?php
$w=array();
$w[]=a;
$w[]=b;
$w[]=a;
$w[]=b;
$w[]=c;
$w[]=a;
$w[]=b;
$w[]=a;
$w[]=b;

print_r(kmp($w));

function kmp1($w)
{
    $n=count($w);
    $N=array();
    $i=1;
    $j=0;
    $N[0]=-1;
    while ($i<$n)
    {
        if($w[$i]==$w[$j])
        {
            $j++;
        }else
        {
            $j=0;
        }
        $N[$i]=$j;
        $i++;
    }
    return $N;
}

?>

Laufzeit

Hallo *,

wie siehts denn mit einem Laufzeitvergleich zw. "normaler" Sucher und dem KMP-Alg. aus? Wäre doch sicher interessant!?

GRuß

 TOBx2

Verbesserter Java-Code

Hallo!

Da ich zur Zeit an einer Arbeit schreibe und diesen Algorithmus beötige, habe ich Ihn mir mal vorgenommen und verbessert. Die Version in dem Artikel compilliert nicht einmal :-( .

Unten angehängt ist eine lauffähige Java-Klasse mit dem Knuth-Morris-Pratt-Algorithmus. Der Code in dem Artikel ist grundsätzlich schon richtig, nur folgende Zeilen sind falsch oder unvolständig:

- pos.add(""+(charposition-j));

Das sollte wohl dazu dienen die Position der Fundstellen in dem zu durchsuchenden String zu speichern. Leider ist nirgendwo ein Objekt pos definiert ...

- counter++;

Was diese nirgendwo definierte Variable hier soll kann ich auch nicht sagen. Weg damit! Die hat überhaupt keinen Sinn.

Die unten folgende Klasse sollte funktioniern und enthält auch eine Beispielanwendung.

Gruß

Frank

PS: Sorry für den grauenvoll formatierten Code . Ich kann kaum HTML ....

---

import java.util.Vector;

public class KnuthMorrisPratt {

private int[] fullTextSearch(String text, String pattern){

int textLength = text.length();

int patternLength = pattern.length();

/*

* This Vector is used store the positions of the occurrences of pattern

* in text.

*/

Vector<Integer> resultVector = new Vector<Integer>();

/*

* start preprocessing and analyse pattern for equal sequences within

* pattern

*/

int compareNext[] = new int[patternLength+1];

int j = - 1, i = 0;

compareNext[0] = -1;

/*

* - Skip outer loop, if pattern has got a zero length (i.e. ""),

* because there is no need to do preprocessing

* - If pattern is not zero (""), skip inner loop for the first loop

* cylce, because j == -1 and therefore j < 0

* => avoid IndexOutOfBoundsException at pattern.charAt(j)

*

*/

while (i < patternLength){

/*

* this loop is used to determine the length of equal

* char sequences within pattern

*/

while (j >= 0 && pattern.charAt(j)!= pattern.charAt(i)){

j=compareNext[j];

}

j++;

i++;

compareNext[i] = j;

}

/*

* start searching

*/

i = 0; // character Position

j = 0;

while (i < textLength){

while (j >= 0 && pattern.charAt(j) != text.charAt(i)){

j=compareNext[j];

}

i++;

j++;

if(j == patternLength){

// Found pattern at position

resultVector.add(new Integer(i-j));

// continue search with appropriate pattern

j=compareNext[j];

}

}//end while

// convert Vector to integer array

resultVector.trimToSize();

int size = resultVector.size();

if (size <= 0) {

// no occurence found

return null;

}

Integer [] resultObjArray = new Integer[size];

resultVector.toArray(resultObjArray);

int [] result = new int[resultObjArray.length];

for (i = 0; i < resultObjArray.length ; i++)

result[i] = resultObjArray[i].intValue();

return result;

}

public static void main(String[] args) {

String pattern = "abcabd";

String text = "abcabcabdxasdrabcabd dabcabddccftabcabd";

System.out.println("Suche Muster " + pattern + " in dem Text " + text + ".\nGefundene Startpositionen (die Zählung

beginnt bei 0!): ");

for ( int occurence : (new KnuthMorrisPratt()).fullTextSearch(text, pattern))

System.out.print(occurence + " ");

}

}

Fehler in der Implementation?

Hmm, irgendwie scheint die angegebene Implementation nicht richtig zu funktionieren, ich habe sowohl auf dem Blatt als auch in einem geschriebenen Programm für das angegebene Beispiel "a,b,a,b,c,a,b,a,b" immer "-1,0,0,1,2,1,1,2,3,4". Ein Kollege von mir ist auf das gleiche Ergebnis gekommen. Wo liegt hier der Hund begragen? :-D -- SeeYa, P.Soell 20:51, 31. Jul 2006 (CEST)

Laufzeit

Ähm, ist KMP tatsächlich linear? Im angegebenen Beispiel gibt es für jeden Index 1 Vergleich, bei 4 und 7 aber jeweils zwei, also O(n+2). Wäre demnach nicht O(n + Anzahl überprüfter Mismatches) korrekt?

Fehlerhafte Präfix-Analyse

Die Idee von kmp-String-Matching-Algorithmus ist eigendlich, dass man einmal Zeichen für Zeichen auf Übereinstimmung prüft und dabei der Zeichenfolgezeiger nie dekrementieren muss.

Hier im Wikieintrag wird der Zeichenfolgezeiger zwar nie dekrementiert aber die Zeichen müssen mehrmals auf Übereinstimmung geprüft werden.

Wenn man das Beispiel

Zeichenfolge = ababbbaa

Muster = ababaa = -1, 0, 0, 1, 2, 3, 1

anschaut sieht man schnell was ich meine.

Eine genauere Lösung wäre

Zeichenfolge = ababbbaa

Muster = ababaa = -1, 0, -1, 0, -1, 3

Hier die Implementation:

#Präfix-Analyse
i := 0
j := 1
N[0] := -1
while j < m
  while i >= 0 and p[j] <> p[j]
     N[j] := i
     i := N[i]
  done
  N[j] := N[i]
done

#KMP-Suche
i := 0
j := 0
while j < m and i < n
   if i>=0 and a[i] != p[j]
      j := N[j]
   endif
   i := i+1
   j := j+1
done
if i = m
   print i-m
else
   print i
endif

Im Beispiel mit

Zeichenfolge = ababbbaa

Muster = ababaa

macht das bei der Suche eine Laufzeitunterschied von zwei zusätzliche Überprufungen.