Boyer-Morre Algorithmus < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:25 Mi 06.06.2012 | | Autor: | bandchef |
| Aufgabe | | Wenden sie den Boyer-Moore Algo. auf den Text "ALGORITHMEN UND DATENSTRUKTUREN" mit dem Muster DATEN an. |
Hi Leute!
Ich hab Probleme mit diesem Algorithmus:
ALGORITHMEN UND DATENSTRUKTUREN
DATEN
In diesem Schritt wird nun von rechts nach links zweichenweise verglichen: N ergibt mismatch mit R. Es wird nun um die Länge des Muster geschoben.
ALGORITHMEN UND DATENSTRUKTUREN
DATEN
Hier ergibt das N einen mismatch mit E. Wieder um Länge des Zeichens schieben.
ALGORITHMEN UND DATENSTRUKTUREN
DATEN
Das N ergibt einen mismatch mit dem D. Wieder um Länge des Zeichens schieben.
ALGORITHMEN UND DATENSTRUKTUREN
DATEN
Das N ergibt einen mismatch mit dem E. Wieder um Länge des Zeichens schieben.
ALGORITHMEN UND DATENSTRUKTUREN
DATEN
So und nun hat mir der Algo. überlesen...
Was mache ich falsch? Könnt ihr mir helfen?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:13 Do 07.06.2012 | | Autor: | felixf |
Moin!
> Was mache ich falsch? Könnt ihr mir helfen?
Du verwendest nicht den Boyer-Moore-Algorithmus, sondern irgendetwas anderes (was nicht funktioniert).
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:05 Do 07.06.2012 | | Autor: | bandchef |
Ja, das ich irgendetwas anderes verwende als den Boyer-Moore-algo. ist mir auch klar. Deswegen hab ich ja hier nachgefragt!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:48 Fr 08.06.2012 | | Autor: | felixf |
Moin!
> Ja, das ich irgendetwas anderes verwende als den
> Boyer-Moore-algo. ist mir auch klar. Deswegen hab ich ja
> hier nachgefragt!
Dann musst du etwas konkreter fragen. Wie sieht eure Version des Algorithmus aus? Insbesondere: welche Strategien werden verwendet? Warum hast du den Algorithmus nicht ausgefuehrt? Bist du irgendwo haengengeblieben?
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:34 Fr 08.06.2012 | | Autor: | bandchef |
Wir haben zu diesem boyer-morre algo. zwei Heuristiken kennengelernt. Die bad-charakter und good-charakter heuristic.
Ich komme aber mit dem Ablauf des "normalen" (ohne Heuristiken!) Boyer-Moore Algo. schon nicht ganz klar. Ich hab mich dann noch ein bisschen mehr mit dem Algo beschäftigt (die Erklärung auf meinen Unterlagen und im Internet gibt für meinen Geschmack eine viel zu vage Erklärung und lässt für mich noch viel zu viel Interpretationsspielraum!) und dabei auf das hier gekommen:
Man muss ja anscheinend das Muster von rechts nach links durchgehen und dabei die Zeichen des Textes (von links nach rechts oder auch von rechts links?) vergleichen. Sobald eine Ungleichheit eines Zeichens erkannt wird, wird das Muster soweit wie möglich am Text entlang weitergeschoben.
Schrittweite sollte möglichst groß werden:
- Schrittweite gleich der Musterlänge wenn kein einziger Buchstabe des Musters im Text vorkommt.
- Ansonsten geeignete Versetzung.
Das is jetzt mal das was ich mir selber aus meinen Folien und Internet zusammengereimt habe. Wenn ich jetzt nun dieses Schema anwende ergeben sich einige Probleme:
1. Schritt:
ALGORITHMEN_UND_DATENSTRUKTUREN
DATEN
=> R wird mit N verglichen => mismatch => Verschiebung um Musterlänge?
Aber was ist mit den übrigen Zeichen? Ich werde ja wohl alle Zeichen vergleich müssen, oder? Dann fällt nämlich auf einmal auf, dass ja im Muster wie im Textabschnitt ein "A" enthalten ist. Wie berechnet sich dann nun die korrekte Verschiebung?
2. Schritt:
ALGORITHMEN_UND_DATENSTRUKTUREN
DATEN
=> E wird mit N vergleichen => mismatch => Verschiebung um Musterlänge?
Eigentlich muss ich an dieser Stelle nun schon abbrechen, da ich nicht wirklich weiterweiß und somit alles mögliche passieren könnte...
Ich fasse dann mal zusammen, das es für euch/dich einfacher wir mir zu helfen:
Ich habe also quasi Probleme damit, die korrekte Verschiebung in Abhängigkeit des eintretenden Falles zu berechnen. Dementsprechend ist es mir nicht möglich mir selbst einen sehr detaillierten Plan des Algo. aufzuschreiben und mir einzuprägen bzw. anzuwenden. Ich hoffe, ich hab jetzt ausführlich erläutert wie ich meine Probleme damit habe.
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:47 So 10.06.2012 | | Autor: | felixf |
Moin!
> Wir haben zu diesem boyer-morre algo. zwei Heuristiken
> kennengelernt. Die bad-charakter und good-charakter
> heuristic.
Sicher? Normalerweise verwendet man die Bad-Character- und die Good-Suffix-Heuristik.
> Ich komme aber mit dem Ablauf des "normalen" (ohne
> Heuristiken!) Boyer-Moore Algo. schon nicht ganz klar. Ich
Der normale Algorithmus verwendet immer beide Heuristiken.
Oder meinst du eine Abaenderung des Algorithmus, die keine der beiden verwendet? In dem Fall wird der Text immer um ein Zeichen verschoben. Aber das ist dann nicht der Boyer-Moore-Algorithmus, sondern der ![[]](/images/popup.gif) naive Algorithmus.
> hab mich dann noch ein bisschen mehr mit dem Algo
> beschäftigt (die Erklärung auf meinen Unterlagen und im
> Internet gibt für meinen Geschmack eine viel zu vage
> Erklärung und lässt für mich noch viel zu viel
> Interpretationsspielraum!) und dabei auf das hier
> gekommen:
Die Beschreibung in der Wikipedia ist gar nicht so schlecht.
> Man muss ja anscheinend das Muster von rechts nach links
> durchgehen und dabei die Zeichen des Textes (von links nach
> rechts oder auch von rechts links?) vergleichen. Sobald
> eine Ungleichheit eines Zeichens erkannt wird, wird das
> Muster soweit wie möglich am Text entlang weitergeschoben.
Ja. Wie weit verschoben wird, wird durch die Heuristiken berechnet. Das Maximum der beiden Heuristiken nimmt man dann. In jedem Fall wird das Muster um mindestens ein Zeichen verschoben. (Wenn du keine Heuristik verwendest, um genau eins.)
> Schrittweite sollte möglichst groß werden:
> - Schrittweite gleich der Musterlänge wenn kein einziger
> Buchstabe des Musters im Text vorkommt.
Genau. Das ist im Wesentlichen die Bad-Charakter-Heuristik.
> - Ansonsten geeignete Versetzung.
>
>
> Das is jetzt mal das was ich mir selber aus meinen Folien
> und Internet zusammengereimt habe. Wenn ich jetzt nun
> dieses Schema anwende ergeben sich einige Probleme:
>
> 1. Schritt:
> ALGORITHMEN_UND_DATENSTRUKTUREN
> DATEN
>
> => R wird mit N verglichen => mismatch =>
Soweit ok.
> Verschiebung um Musterlänge?
Ja. Das Zeichen $R$ kommt schliesslich nicht im Muster vor.
> Aber was ist mit den übrigen Zeichen? Ich werde ja wohl
> alle Zeichen vergleich müssen, oder? Dann fällt nämlich
> auf einmal auf, dass ja im Muster wie im Textabschnitt ein
> "A" enthalten ist. Wie berechnet sich dann nun die korrekte
> Verschiebung?
Es wird erstmal nur das Zeichen beruecksichtigt, welches sich an der ersten Mismatch-Stelle (von hinten) findet (sowie die Muster-Zeichen). Da das Zeichen, ein R, nicht im Muster vorkommt, wird um die ganze Musterlaenge verschoben.
> 2. Schritt:
| 1: | ALGORITHMEN_UND_DATENSTRUKTUREN
| | 2: | DATEN
|
> => E wird mit N vergleichen => mismatch
Ok.
> => Verschiebung um
> Musterlänge?
Nein.
Das E kommt schliesslich im Muster vor, an vorletzter Stelle. Also wird das Muster soweit verschoben, dass die beiden Es uebereinanderliegen. Als naechstes machst du also mit
| 1: | ALGORITHMEN_UND_DATENSTRUKTUREN
| | 2: | DATEN
|
weiter. Hier ist dann M ungleich T. Da M nicht im Muster vorkommt, verschiebst du um die Musterlaenge und kommst auf
| 1: | ALGORITHMEN_UND_DATENSTRUKTUREN
| | 2: | DATEN
|
Dann wird aus dem gleichen Grund wieder um die Musterlaenge verschoben, und du erhaelst
| 1: | ALGORITHMEN_UND_DATENSTRUKTUREN
| | 2: | DATEN
|
Hier tritt dann ein Match auf und fertig bist du.
LG Felix
|
|
|
| |
|
Zitat: "
> Ich komme aber mit dem Ablauf des "normalen" (ohne
> Heuristiken!) Boyer-Moore Algo. schon nicht ganz klar. Ich
Der normale Algorithmus verwendet immer beide Heuristiken.
Oder meinst du eine Abaenderung des Algorithmus, die keine der beiden verwendet? In dem Fall wird der Text immer um ein Zeichen verschoben. Aber das ist dann nicht der Boyer-Moore-Algorithmus, sondern der []naive Algorithmus."
Den naiven Algorithmus meine ich nicht; den hab ich verstanden  Aber dennoch Danke für die ausführlich Information!
Zitat: "
> Man muss ja anscheinend das Muster von rechts nach links
> durchgehen und dabei die Zeichen des Textes (von links nach
> rechts oder auch von rechts links?) vergleichen. Sobald
> eine Ungleichheit eines Zeichens erkannt wird, wird das
> Muster soweit wie möglich am Text entlang weitergeschoben.
Ja. Wie weit verschoben wird, wird durch die Heuristiken berechnet. Das Maximum der beiden Heuristiken nimmt man dann. In jedem Fall wird das Muster um mindestens ein Zeichen verschoben. (Wenn du keine Heuristik verwendest, um genau eins.)"
Dass man beide Heuristiken berechnet und von den zweien dann den maximalen Wert nimmt wusste ich nicht. Das steht auch nirgends in meinen Unterlagen. Aber gut, jetzt weiß ich es ja
Zitat: "
> Schrittweite sollte möglichst groß werden:
> - Schrittweite gleich der Musterlänge wenn kein einziger
> Buchstabe des Musters im Text vorkommt.
Genau. Das ist im Wesentlichen die Bad-Charakter-Heuristik."
Was ist da dann im Gegensatz dazu die Good-Charakter-Heuristik?
Zitat: "
> 1. Schritt:
> ALGORITHMEN_UND_DATENSTRUKTUREN
> DATEN
>
> => R wird mit N verglichen => mismatch =>
Soweit ok.
> Verschiebung um Musterlänge?
Ja. Das Zeichen $ R $ kommt schliesslich nicht im Muster vor."
Hab ich das richtig verstanden, dass man immer den TEXT mit dem MUSTER vergleicht und NICHT den Muster mit dem Text? Wenn nun das R im Text nicht im Muster vorkommt, könnte aber doch bspw. ein R im Text vorkommen, und so die Verschiebung anders werden! Ist die "Vergleichrichtung" also ein wichtiges Kriterium für den Algorithmus?
Zitat: "
> Aber was ist mit den übrigen Zeichen? Ich werde ja wohl
> alle Zeichen vergleich müssen, oder? Dann fällt nämlich
> auf einmal auf, dass ja im Muster wie im Textabschnitt ein
> "A" enthalten ist. Wie berechnet sich dann nun die korrekte
> Verschiebung?
Es wird erstmal nur das Zeichen beruecksichtigt, welches sich an der ersten Mismatch-Stelle (von hinten) findet (sowie die Muster-Zeichen). Da das Zeichen, ein R, nicht im Muster vorkommt, wird um die ganze Musterlaenge verschoben."
Mit "von hinten" meinst du wohl die Leserichtung von rechts nach links, oder? Kann man das Vorgehen also so formulieren: "Sobald das erste Zeichen des Textes (von rechts gelesen, wobei das "erste Zeichen" durch die Länge des Musters angegeben wird) NICHT mit dem ersten Zeichen (ebenfalls vons rechts gelesen!) Muster übereinstimmt UND auch im übrigen Text kein zeichen vorkommt, dass mit dem Muster übereinstummt, wird um das Muster um die gesamte Länge des Musters verschoben."
Zitat: "
> 2. Schritt:
1: ALGORITHMEN_UND_DATENSTRUKTUREN
2: DATEN
> => E wird mit N vergleichen => mismatch
Ok.
> => Verschiebung um
> Musterlänge?
Nein."
Ok, so einfach ist es also dann doch nicht. Schaun wir weiter unten:
Zitat: "
Das E kommt schliesslich im Muster vor, an vorletzter Stelle. Also wird das Muster soweit verschoben, dass die beiden Es uebereinanderliegen. Als naechstes machst du also mit
1: ALGORITHMEN_UND_DATENSTRUKTUREN
2: DATEN
weiter."
Kann man das dann wiederum so formulieren: "Wenn das erste Zeichen des Textes (von rechts gelesen) nicht mit dem ersten Zeichen des Musters (ebenfalls von rechts gelesen) übereinstimmt, ABER sich im Text ein Zeichen weiter rechts befindet ("weiter rechts" in Bezug auf das erste Zeichen des Textes wobei das erste Zeichen durch die Musterlänge angegeben wird), dass sich innerhalb des Musters befindet, und das wiederum mit dem Muster übereinstimmt, werden diese gleichen Zeichen untereinander ausgerichtet."
Zitat: "
Hier ist dann M ungleich T. Da M nicht im Muster vorkommt, verschiebst du um die Musterlaenge und kommst auf
1: ALGORITHMEN_UND_DATENSTRUKTUREN
2: DATEN
"
M und T sind ungleich, das ist klar. Im Text sieht man aber, dass das letzte Zeichen im Text ein T ist. Das T kommt aber auch im Muster vor. Dies macht aber keinen Sinn, weil ich ja zurückschieben müsste. Stimmts?
Zitat: "
Dann wird aus dem gleichen Grund wieder um die Musterlaenge verschoben, und du erhaelst
1: ALGORITHMEN_UND_DATENSTRUKTUREN
2: DATEN
Hier tritt dann ein Match auf und fertig bist du."
Moment, kann es sein, dass du da jetzt ein bisschen was übersprungen hast?
1: ALGORITHMEN_UND_DATENSTRUKTUREN
2: DATEN
Das Zeichen _ und N sind ungleiche. Es kommt aber im Text wie im Muster noch das D vor. Wäre der nächste Schritt nun nicht der hier:
1: ALGORITHMEN_UND_DATENSTRUKTUREN
2: DATEN
Nun ist T und N unterschiedlich. Man sieht aber, dass im Text wie im Muster ein A vorkommt; also Ausrichtung der beiden A's:
1: ALGORITHMEN_UND_DATENSTRUKTUREN
2: DATEN
Und erst jetzt habe ich den Match! Stimmt das so?
Abschließende Frage: Was ist in diesem Vorgehen nun die Bad bzw. Good-Heurstik? Wo ist diese ersichtlich?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 Mi 13.06.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
