Diskussion:Boyer-Moore-Algorithmus
| Auf dieser Seite werden Abschnitte ab Überschriftenebene 2 automatisch archiviert, die seit einem Tag mit dem Baustein {{Erledigt|1=--~~~~}} versehen sind. |
Falsche Komplexitätsangabe bei der Bad-Character-Heuristik?[Quelltext bearbeiten]
Es wird eine Komplexität von O(N+M) angegeben, doch ich glaube, dass eine Worst-Case-Laufzeit von O(NM) herauskommen kann. Kann das jemand bestätigen/ändern? Danke!
--128.131.208.145 13:49, 29. Apr. 2013 (CEST)
- Du hast Recht wenn man nur die Bad-Character-Heuristik verwendet hat man eine Worst-Case-Laufzeit von O(NM) (Beispiel: ). Im Artikel war nich ganz klar auf was sich das O(N+M) bezieht. Habe das mal notdürftig geflickt.
- --Wdvorak (Diskussion) 14:30, 2. Mai 2013 (CEST)
Das Beispiel zur Good-Suffix-Heuristik enthält zu viele Schritte. Bei Schritt 2 steht "Nur der letzte Buchstabe „e“ stimmt überein. Wir können das Muster bis zum nächsten Auftreten von „e“ in supersupe verschieben". Dieses Vorgehen wäre bei der Bad-Character-Heuristik korrekt. Bei Good-Suffix kann um die volle Länge verschoben werden, da die Zeichenfolge „ue“ im Muster nicht vorkommt.
-- 84.56.242.199 17:16, 30. Okt. 2009 (CET)
"Existiert dieser Bad-Character nicht im Muster wird das Muster um seine volle Länge nach rechts verschoben."
Das glaube ich nicht, denn in diesem Fall würde man in vielen Fällen zuviel shiften. Richtig wäre, das Pattern um die Länge des ungematchten Prefix zu verschieben (wie gesagt: nur wenn der Bad-character nicht im Pattern auftritt). (nicht signierter Beitrag von 160.45.118.140 (Diskussion) 12:46, 9. Mär. 2009)
Die C Implementation funktioniert nicht 100%ig korrekt:
char * s = "MENUPOPUPLOCATION"; char * p = "POPUP";
Sollte funktionieren, tuts aber nicht. - nicht in eigenen Programmen verwenden. (nicht signierter Beitrag von Mkrueger (Diskussion | Beiträge) 12:30, 23. Apr. 2009 (CEST))
Diese Zeile ist falsch:
i += skip[(unsigned char)s[i - j]] > next[j] ? skip[(unsigned char)s[i - j]] : next[j];
Richtig ist:
i += skip[(unsigned char)s[i - j]] > next[j] ? skip[(unsigned char)s[i - j]] - j : next[j]; (nicht signierter Beitrag von Masterle (Diskussion | Beiträge) 17:01, 12. Jun. 2011 (CEST))
Hier wird doch verglichen welcher sprung sich mehr lohnt. Sollte dann nicht auch beim Vergleich j abgezogen werden? Also so:
i += skip[(unsigned char)s[i - j]]-j > next[j] ? skip[(unsigned char)s[i - j]] - j : next[j]; (nicht signierter Beitrag von 134.147.40.247 (Diskussion) 12:50, 1. Jul 2011 (CEST))
Was sind m und n?[Quelltext bearbeiten]
In "Bad-Character-Heuristik" müsste zu der Laufzeit noch ergänzt werden, was m und n sind. (nicht signierter Beitrag von 217.232.86.135 (Diskussion) 01:07, 17. Mai 2010 (CEST))
Volle Zustimmung von mir!!! -- 79.211.21.208 22:48, 5. Jan. 2011 (CET)
n = Länge des Textes, m = Länge des Musters. Grad keine Zeit das ordentlich da einzutragen.. (nicht signierter Beitrag von 84.58.208.216 (Diskussion) 12:56, 15. Mär. 2011 (CET))
Würde gerne folgendes Paper als Ergänzung zum Artikel vorschlagen. Boyer Moore Horspool
Es ist an meiner Universität ziemlich beliebt und wurde in den Vorlesungen benutzt. --Umingo 23:45, 25. Okt. 2011 (CEST)
Raus mit dem C-Code, und zwar flott[Quelltext bearbeiten]
Wie auch in jeder Algorithmen-Vorlesung von jedem guten Prof. zu hören ist:
MUSS ein Sprachen-unabhängige Beschreibung des Algorithmus' aufgeführt sein, das Studium der Algorithmen kann sie NICHT mit den Details des Software-Engineerings rumschlagen.
Wer auch nur ein bisschen professionell und objektiv arbeitet wird einsehen, dass in einer Enzyklopädie AUSSCHLIEßLICH Pseudocode angebracht ist. (nicht signierter Beitrag von 81.210.230.125 (Diskussion) 22:44, 22. Dez. 2011 (CET))
- Ich stimme zu und füge hinzu: Die Implementierung ist Spaghetticode! Mit gotos! --213.47.103.60 16:20, 18. Jun. 2012 (CEST)