Diskussion:Knuth-Morris-Pratt-Algorithmus
aus Wikipedia, der freien Enzyklopädie
Inhaltsverzeichnis |
[Bearbeiten] Ü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)
[Bearbeiten] 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)
[Bearbeiten] Ü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).
[Bearbeiten] Laufzeit
Hallo *,
wie siehts denn mit einem Laufzeitvergleich zw. "normaler" Sucher und dem KMP-Alg. aus? Wäre doch sicher interessant!?
GRuß
TOBx2
[Bearbeiten] 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 + " ");
}
}
[Bearbeiten] 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)
