[Frage] Boyer-Moore-Algo - delta-2 Wert

Druckbare Version

08.04.2009, 12:18
MagicMagor

[Frage] Boyer-Moore-Algo - delta-2 Wert

Eigentlich bin ich jemand der lieber erstmal selber versucht ein Problem oder eine Frage zu lösen bevor ich jemand anderen um Hilfe bitte, aber diesmal will ich lieber zu früh fragen als zu spät.

Ich habe in etwa einer Woche (genauer kommenden Dienstag) meine Nachklausur in Informatik3 (Algorithmen und Datenstrukturen) und arbeite mich nun erneut durch das Skript.

Probleme habe ich dabei mit dem Textsuch-Verfahren von Boyer-Moore insbesondere was den delta-2 Wert angeht.
Ich denke ich habe einigermaßen verstanden wie der Algorithmus funktioniert und warum er im Mittel gute Laufzeitergebnisse liefert, aber wie sich der delta-2 und der verbesserte delta-2 Wert berechnet entzieht sich mir noch ein wenig.

Im Skript haben wir also einen Text T der Länge N und ein Muster P mit der Länge M. Verglichen wird jeweils T(i) mit P(j).
Folgendes steht nun im Skript zum delta-2 Wert:

Zitat:

Der sogenannte delta-2-Wert beschreibt, um welchen Wert i maximal erhöht werden kann, wenn an einer Position j im Muster ein Mismatch eintritt.
Genutzt wird dabei die Information, dass auf den Positionen i+1, ..., i+(M-1-j) im Text die gleichen Zeichen stehen, wie im Muster auf den Positionen j, ... , M-1. Wird zusätzlich noch die Information genutzt, dass auf Position i im Text ein anderes Zeichen steht als auf Position j im Muster, dann erhalten wir den verbesserten delta-2 Wert.

Das ist soweit klar, was mir nur nicht klar ist, wie der Wert denn nun genau berechnet wird. (Und genau so eine Aufgabe kam in der ersten Klausur dran - auch wenn ich daher bezweifle, das in der Nachklausur diesselbe Aufgabe noch einmal dran kommt würde ich es gerne verstehen)

Gegeben ist folgendes Beispiel:

Code:

P | = 1 0 0 1 0 1 0 1 0 j | = 0 1 2 3 4 5 6 7 8 delta2(j) | = 15 14 13 7 6 5 4 3 1

Was im Skript vollständig fehlt ist eine mathematische Herleitung des delta2-Wertes oder überhaupt eine Angabe der Berechnung desselbigen. Das Beispiel wird zwar mit vielen Schaubildern verdeutlicht und ich kann insofern nachvollziehen, daß die obigen Werte korrekt sind, aber wie man auf sie kommt kann ich mir nicht herleiten.

Es wäre schön wenn mir hier jemand auf die Sprünge helfen könnte.
08.04.2009, 12:51
drunken monkey

OK, leicht dämliche Antwort, aber hast du's schon mit dem Wikipedia-Artiekl versucht? Da wird's zumindest allgemein recht gut erklärt, und es gibt weiterführende Links.
Aber eine Schritt-für-Schritt-Anleitung, wie man zu den Werten kommt, habe ich jetzt auch nirgends gefunden, sorry. .___.' Kann mich auch nimmer zurückerinnern an damals, wie ich's können musste...*kratz* Vielleicht muss man sich das echt einfach überlegen? .___.''

Wobei, ich könnte eigentlich einfach mal mein altes Skriptum suchen...*kratz*
10.04.2009, 14:00
Brauni90

Wenn ich der Namenskonvention des Skripts folgen kann, dann hilft dir vielleicht folgender Hinweis weiter. Der einfache delta-2 Wert eines Zeichens, dass in P an der hintersten Position i zu finden ist, sollte M - i - 1 betragen, für alle anderen M.
11.04.2009, 15:14
MagicMagor

Zitat:

OK, leicht dämliche Antwort, aber hast du's schon mit dem Wikipedia-Artiekl versucht? Da wird's zumindest allgemein recht gut erklärt, und es gibt weiterführende Links.

Ja, den Wikipedia-Artikel habe ich gelesen, sowohl den englischen als auch den deutschen. Beide haben mir aber nicht weitergeholfen, da ich mit deren Berechnungen auch nicht das von mir gepostete Beispiel aus dem Skript nachvollziehen konnte.
Die Grundidee mag zwar diesselbe sein, aber die Werte, die benutzt werden scheinen einfach nicht mit dem uebereinzustimmen was in meinem Skript der delta2-Wert genannt wird.

Zitat:

Wenn ich der Namenskonvention des Skripts folgen kann, dann hilft dir vielleicht folgender Hinweis weiter. Der einfache delta-2 Wert eines Zeichens, dass in P an der hintersten Position i zu finden ist, sollte M - i - 1 betragen, für alle anderen M.

Wenn mich nicht alles tauescht ist das der delta1-Wert, nämlich die Position wo das Zeichen zum ersten mal im Muster auftaucht von hinten/rechts gelesen.
Der delta2-Wert ist aber nicht spezifisch fürs Zeichen sondern spezifisch für die Position. Welches Zeichen an dieser Position im Muster steht hat zwar sicher eine Auswirkung auf den delta2-Wert aber welche und wie genau entzieht sich immer noch meiner Kentniss.

Mir würde eine einfache mathematische Herleitung der Werte aus meinem obigen Beispiel (es wird dort nur ein Alphabet mit den Zeichen "0" und "1" verwendet) schon reichen. Ansonsten kann ich nur hoffen, daß Boyer-Moore in der Nachklausur nicht vorkommt, da er schon in der Hauptklausur Inhalt einer Aufgabe war.

Dennoch danke für die bisherigen Antworten.