Preprocessing Lookup Table String matching

s1mstar
Windoof-User
Windoof-User
Beiträge: 38
Registriert: 18. Apr 2013 14:26

Preprocessing Lookup Table String matching

Beitrag von s1mstar »

Hallo,


wir verstehen nicht ganz wie die Lookup Table durch den Algorithmus im Preprocessing aufgebaut wird. Konkret:

1. Wozu dient die Minimumbildung k = min{m,j+1} bzw. was sagt das Minimum aus, da es ja zusätzlich von der while-Schleife manipuliert wird?
2. Was genau vergleicht die While Schleife bzw warum tut sie das? while(k>0 && (T[1],..,T[k]) != (T[j-k+2],..,T[j],c){ k--; }
Bei dem Versuch die Schleife von Hand durchzurechnen tritt ein Fehler bei T[j-k+2] auf -> StringIndexOutOfBoundsException. Ist dieser Wiki-Eintrag fehlerhaft?
Wie wird das "c" in der obigen Schleifenbedingung verwand? Wird es mit T[j] verknüpft?


Liebe Grüße,
Simon H.

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Preprocessing Lookup Table String matching

Beitrag von JannikV »

Hey.

1) In Schritt 4.1 soll k eigentlich auf den Wert j+1 gesetzt werden. Für j = m macht das für das darauf folgende aber keinen Sinn. Mit dem Minimum soll sichergestellt werden, dass k nicht größer als die Stringlänge m wird. Man könnte das auch bestimmt so umschreiben dass das Minimum nicht gebraucht wird. Aber belassen wir das jetzt mal dabei.
Warum das semantisch sinnvoll ist steht eigentlich bei der Correctness. Und zwar im Satz "According to its intended semantics....." (den ich Aufgrund der Tex Formeln jetzt nicht ganz kopiere..)

2) - das c wird so verwendet, dass es an das davorstehende angehängt wird (Konkatenation).
- kannst du mal ein konkretes Beispiel machen, wo die "Exception" auftreten soll?
- Die while-Schleife ist dazu da um das k zu bestimmen, dass den Zustand angibt in den der Automat gehen soll, wenn wir in Zustand j das Zeichen c lesen. Würden sich Teile des Suchstrings nicht wiederholen, also etwa 'abcde', müsste k ja immer j+1 sein. Da aber auch soetwas wie 'ababab' vorkommen kann, müssen wir zusehen, dass k so gesetzt wird, dass auch solche "verschachtelten" Vorkommen gefunden werden.

-> was mit c gemacht wird ist jetzt beantwortet
-> lass uns das mit der Exception klären
-> dann versuche ein Beispiel zu machen so dass man es vielleicht sieht
-> dabei den Correctness Teil lesen, ist dort ja ein wenig ?! erklärt
-> wenn das nicht hilft -> Sprechstunde aufsuchen und hoffen dass der entsprechende Tutor dazu was sagen kann, denn diese Initialisierung ist allseits unbeliebt ;-)

VG

s1mstar
Windoof-User
Windoof-User
Beiträge: 38
Registriert: 18. Apr 2013 14:26

Re: Preprocessing Lookup Table String matching

Beitrag von s1mstar »

Ich glaube, dass die Exception wegen dem fehlerhaften Wiki-Eintrag (?) den du in deinem 1. Schritt erläutert hast aufgetreten ist.

Ich muss deine Antwort erstmal verdauen und mir das nochmal durch den Kopf gehen lassen. Ich schreibe dann spätestens am Freitag nochmal! (ist bei mir zeitlich gerade etwas eng)

Vielen Dank schon einmal!
Simon

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Preprocessing Lookup Table String matching

Beitrag von JannikV »

Ok.
Wie gesagt, wenn du meinst das ist fehlerhaft würde es sehr helfen wenn du einen konkreten Durchlauf mit dem Problem angeben kannst.
Dann könnte man zusehen dass das behoben wird.

s1mstar
Windoof-User
Windoof-User
Beiträge: 38
Registriert: 18. Apr 2013 14:26

Re: Preprocessing Lookup Table String matching

Beitrag von s1mstar »

Ich denke der Fehler liegt bei mir!

Ich will mal kurz ein Fazit bilden und bin (wie immer) für Verbesserungsvorschläge und Kritik offen.

Induktionsanfang:
// Ausfüllen der ersten Zeile der LookUp-Table
Schritt 3: FÜR jeden Buchstaben c aus dem Alphabet (von T):
Schritt 3.1.: WENN der erste Buchstabe von Suchstring T (T[1]) == aktuell gelesenem Buchstaben c:
Schritt 3.1.1: DANN Mache einen LookUp-Table Eintrag in der ersten Zeile beim aktuell gelesenen Buchstaben mit 1.
Schritt 3.1.2: ANSONSTEN Mache das Selbe mit 0.

// Ausfüllen der restlichen LookUp-Table -> äußere Schleife bezeichnet die Zeilen der Tabelle (= Zustände) , innere Schleife bezeichnet die Spalten der Tabelle (= Buchstaben im Alphabet)

// Äußere Schleife
Schritt 4.0.1: FÜR aktuellen Zustand j von 1.. <Länge von T gleichzeitig maximaler Zustand>
// Innere Schleife
Schritt 4.0.2: FÜR jedes Zeichen c im Alphabet
Schritt 4.1: Setze den Folgezustand k auf den höchstmöglichen Zustand, der erreicht werden kann (= nächster Zustand, da pro Zeichen ein Zustand)
// Überlegung dahinter: T[1] bis T[k] bezeichnet den Teilstring des Suchstrings der im besten Fall schon mit dem gleichen Teilstring T[j-k+2] bis T[j] (= T[1] bis T[k-1]) übereinstimmt. Es wird nun noch
// überprüft, ob der aktuell gelesene Buchstabe c mit T[k] übereinstimmt. Wenn dies der Fall ist kann die Schleife verlassen werden. Sollte dies nicht der Fall sein wird in der nächsten Iteration probiert ob
// zumindest noch der Vorgängerzustand haltbar (bzw. erreichbar) ist. Die Schleife läuft maximal solange runter bis 0 erreicht ist. D.h. es konnte kein besserer Zustand erreicht werden und es wird der
// Startzustand 0 eingetragen.
Schritt 4.2: SOLANGE Folgezustand noch nicht 0 ist UND Zeichenkette (T[1] bis T[k]) != (T[j-k+2] bis T[j] konkateniert mit c)
Schritt 4.2.1: Dekrementiere k um 1. // Um zu gucken, ob ein Vorgängerzustand noch erreicht werden kann.
Schritt 4.3: Mache LookUp-Table Eintrag bei [aktuellem Zustand, aktuell gelesenes Zeichen c] = k;


Ich hoffe, dass diese Erklärung halbwegs richtig und plausibel ist. Über eine bessere/ verständlichere Erklärung für Schritt 4.2 wäre ich jedoch sehr dankbar.


Liebe Grüße,
Simon H.


PS: Sorry, hat etwas länger gedauert ;)

s1mstar
Windoof-User
Windoof-User
Beiträge: 38
Registriert: 18. Apr 2013 14:26

Re: Preprocessing Lookup Table String matching

Beitrag von s1mstar »

Hallo,

könnte mir jemand ein Feedback dazu geben bzw. ob das so, wie ich es interpretiere korrekt ist?

LG,
Simon

Benutzeravatar
JannikV
Nerd
Nerd
Beiträge: 609
Registriert: 24. Apr 2011 12:42

Re: Preprocessing Lookup Table String matching

Beitrag von JannikV »

Wenn ich nichts übersehen habe sieht das erstmal soweit gut aus.

Antworten

Zurück zu „Archiv“