Textsuche < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | | Ich hab hier keine konkrete Aufgabe sondern eher eine Frage zu einem konkreten Beispiel auf der deutschen Wikipedia-Seite. |
Hi Leute!
Text:
| 1: |
| | 2: | HOOLA-HOOLA GIRLS LIKE HOOLIGANS
|
Suchmuster:
Das ist das Beispiel aus der deutschen Wikipedia.
1. Frage an euch: Wenn vom Boyer-Moore-Algorithmus gesprochen wird, sind auch immer diese beiden Heuristiken, als Good-Suffix und Bad-Charakter, gemeint, oder?
2. Ich gehe jetzt den Algorithmus mal durch und will den dann mit Fragen an euch spicken:
| 1: |
| | 2: | HOOLA-HOOLA GIRLS LIKE HOOLIGANS
| | 3: | HOOLIGAN
|
Hier wird das O aus dem Text mit dem N aus dem Muster verglichen -> Mismatch. Das O im Text ist aber im Muster vorhanden. Welche der zwei Heuristiken kommt hier nun zum Tragen? Wenn Ich nun das zweite O (von rechts gesehen!) des Suchmusters unter die Stelle mit dem Mismatch schiebe, habe ich doch die Bad-Charakter Heuristik angewendet oder?
Wie sieht hier nun die Good-Suffix Heuristik aus?
Im Text hat sich hier nun ein Mismatch zwischen dem O und dem N ergeben. Dürfte ich denn nun nicht gleich die beiden H untereinander ausrichten? Denn das HO ergibt doch ein Suffix oder auch Teilwort von HOOLIGAN oder? Außerdem hätte man dann den Text von Haus aus schon um eine weitere Stelle verschoben und laut Wikipedia nimmt der Algorithmus IMMER die höchste Distanz, was ja hier dann die Good-Suffix Heuristik wäre, oder?
Verschiebung mit Bad-Charakter:
| 1: |
| | 2: | HOOLA-HOOLA GIRLS LIKE HOOLIGANS
| | 3: | HOOLIGAN
|
Verschiebung mit Good-Suffix:
| 1: |
| | 2: | HOOLA-HOOLA GIRLS LIKE HOOLIGANS
| | 3: | HOOLIGAN
|
Wie man hier nun sehen kann wäre, die Verschiebung mit der berechneten Länge von Good-Suffix schon um eins weiter. Stimmt das was ich hier berechnet hab (in Bezug auf Good-Suffix)
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:20 Mi 16.01.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
