Nachtrag zum zweiten String Matching Algorithmus

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Nachtrag zum zweiten String Matching Algorithmus

Beitrag von Prof. Karsten Weihe »

Hallo allerseits,

ein paar Teilnehmer haben mich nach der Vorlesung auf folgendes potentielles Missverständnis gestoßen:

Immer wenn ich in den Kritzeleien die verschiedenen Präfixe von T unterhalb von S skizziert habe, sah das Bild mehr oder weniger periodisch aus, das heißt, dass die Längendifferenz zweier aufeinanderfolgender Präfixe immer gleich war,so dass man die linken Enden meiner gezeichneten Präfixe zu einer mehr oder weniger geraden Linie verbinden kann.

Das lag aber nur am fehlenden Platz auf der Zeichenfläche. Die Präfixlängen können beliebig chaotischvon oben nach unten kleiner werden, sie müssen selbstverständlich nicht in konstanten Schritten kleiner werden.

KW

studypad
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 158
Registriert: 30. Mär 2011 11:46

Re: Nachtrag zum zweiten String Matching Algorithmus

Beitrag von studypad »

Ich habe mir die Aufzeichnung mittlerweile nochmal angesehen und auch mal in Büchern geguckt, doch die richtige Vorgehensweise des Algorithmus' habe ich noch nicht verstanden.
Kann man dazu nochmal etwas sagen? Am Dienstag vll noch einmal ein Beispiel anspielen, was man gut selbst nach basteln kann wenn man die ersten ein zwei Schritte versteht?
Danke

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Nachtrag zum zweiten String Matching Algorithmus

Beitrag von Prof. Karsten Weihe »

studypad hat geschrieben:Ich habe mir die Aufzeichnung mittlerweile nochmal angesehen und auch mal in Büchern geguckt, doch die richtige Vorgehensweise des Algorithmus' habe ich noch nicht verstanden.
Kann man dazu nochmal etwas sagen?
Ich antworte gern - auf jede konkrete Frage, an der Ihr Verständnis hakt. Woher soll ich sonst wissen, was ich sinnvoll sagen/schreiben kann? :roll:

studypad hat geschrieben: Am Dienstag vll noch einmal ein Beispiel anspielen
Das Beispiel sollen Sie in der dritten theoretischen Übung basteln. :twisted:

KW

studypad
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 158
Registriert: 30. Mär 2011 11:46

Re: Nachtrag zum zweiten String Matching Algorithmus

Beitrag von studypad »

Das Problem ist: Für den ersten Algorithmus ist ein Beispiel konstruiert, Algorithmus durchgespielt doch beim zweiten Algorithmus ist die Idee einfach nicht zu verstehen gewesen.
Wir merken uns ja lediglich q, doch wenn das Präfix A (angenommen das längste) mit c, also A+c nicht mehr passt, aber hingegen B+c passt, wie wissen wir das? Wir haben die Länge von B uns ja nicht gemerkt, lediglich q?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Nachtrag zum zweiten String Matching Algorithmus

Beitrag von Prof. Karsten Weihe »

studypad hat geschrieben: Die Idee des Arbeitens wird mir nicht klar. Was passiert wenn c beim längsten Präfix passt und ich noch zwei weitere kürzere Präfixe habe die ja wiederum im längsten Präfix als Suffix zu finden sind. Werden diese auch um C erweitert? oder fliegen sie raus?
Wenn Sie davon reden, ob das eine oder andere Präfix 'rausfällt, dann sind Sie beim ersten Algorithmus, nicht beim zweiten. Das Präfix (T[1],...,T[k]) fliegt im ersten Algorithmus 'raus genau in dem Fall, wenn c ungleich T[k+1] ist. Das hat überhaupt nichts zu tun damit, was in dieser Iteration mit einen anderen, simultan verwalteten Präfix (T[1],...,T[k'']) passiert, denn für diesen muss ja eine ganz andere Position in T betrachtet werden (nämlich k'): Ob T[k]=c ist, hat nichts damit zu tun, ob T[k']=c ist. Soweit klar?

Nun zum zweiten Algorithmus: Hier verwalten wir überhaupt keine Präfixe während der Schleife, sondern nur eine einzige natürliche Zahl q, sonst nichts (ok, noch das Resultat R). Der Witz ist, dass diese Zahl q eigentlich die einzige Information ist, die man wirklich braucht - im ersten Algorithmus schleppen wir viel zu viel völlig überflüssige Information mit von Iteration zu Iteration, was viel Laufzeit kostet.

Was ist das q? Das q ist einfach die Länge des längsten Präfixes. Immer wenn q gleich der Länge von T ist, haben wir einen neuen Treffer gefunden. Das passiert in beiden Algorithmen völlig gleich, wobei im ersten Algorithmus die Startadresse des längsten Präfixes und im zweiten Algorithmus die Länge q des längsten Präfixes verwaltet wird.

Warum reicht das q aus? Ich glaube, es ist einsichtsreich, die Frage umkgekehrt zu stellen: Wofür verwalten wir eigentlich sämtliche Präfixe im ersten Algorithmus? Schließlich interessiert uns immer nur das längste Präfix A: Wenn A so lang wie T geworden ist, haben wir einen neuen Treffer gefunden. Mit den anderen Präfixen machen wir überhaupt nichts außer "Mitschleppen".

Warum reicht das q also aus? Antwort: Wir schleppen überhaupt nur deshalb alle Präfixe im ersten Algorithmus mit, weil wir sie alle brauchen in dem Moment, wenn A wegfällt, weil entweder das nächste Zeichen nicht mehr auf A passt oder weil A ein Treffer geworden ist. Dann greifen wir auf das längste Präfix B zurück, an das das Zeichen S passend angehängt werden konnte. Mit anderen Worten: Wir berechnen q neu, denn q war vorher die Länge von A und ist nun die Länge von B (plus 1, da S angehängt ist).

Die Idee hinter dem zweiten Algorithmus, die sicherlich schwierig nachzuvollziehen ist, ist die, dass wir die Liste aller Präfixe gar nicht unbedingt brauchen, sondern dass q bzw. B auch anders gefunden werden kann. Die entscheidende Einsicht dafür ist, dass sämtliche Informationen, die wir aus der Liste aller Präfixe verwenden zur Neuberechnung von q, mit der konkreten Situation während des Algorithmus eigentlich überhaupt nichts zu tun haben. Was wir tatsächlich nur verwenden, ist der alte Wert von q und das Zeichen S. Und eine Berechnungsvorschrift, die unabhängig von der konkreten Situation einen Character c und einen Integer q als Inputs bekommt, um einen anderen Integer zu berechnen, kann auch im Preprocessing - also vor dem Durchlauf von S - einmal für jedes Paar (q,c) berechnet und in der Lookup Table abgelegt werden. Während des Durchlaufs kann das neue q dann einfach aus dem alten q durch Nachschauen bei Delta(q,c) berechnet werden.

Klarer geworden? Ich bin mir sicher, ein Beispiel, das ich Ihnen gebe, hilft nicht wirklich weiter, weil man den Wald vor lauter Bäumen nicht sehen würde.

KW

studypad
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 158
Registriert: 30. Mär 2011 11:46

Re: Nachtrag zum zweiten String Matching Algorithmus

Beitrag von studypad »

Es wird langsam klarer, doch neben ausreichend Diskussion mit Kommilitonen und der Arbeit mit dem Wiki, die ich noch anstreben werde, stellt sich schon jetzt eine Frage:

Das ganze Gebilde ist etwas wie in FGdI, ein endlicher Automat mit Zuständen. Wir haben ein q was den Zustand simuliert und einen Zustandsübergangsgraph der die Lookup Table bildet. Oder verstehe ich es völlig falsch?

Mir ist jedoch dann die Bildung der Lookup table nicht klar? Diese muss man dann wohl hardcoden oder soll die Implementierung eine Lookup table zur Laufzeit selbst generieren?

Danke

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Nachtrag zum zweiten String Matching Algorithmus

Beitrag von Prof. Karsten Weihe »

studypad hat geschrieben: und der Arbeit mit dem Wiki, die ich noch anstreben werde
Ach so, Sie hatten noch gar nicht richtig ins Wiki hineingeschaut? :shock:

Schade, ich könnte mir vorstellen, dass auch das Wiki zur Klärung Ihrer Fragen hätte beitragen können, nämlich durch Konzentration auf die reinen Fakten in komprimierter Form. Bspw wäre dann sicherlich klar gewesen, dass im zweiten Algorithmus keine Präfixe fallengelassen werden - eben weil Präfixe überhaupt nicht vorkommen.

Aber nichts für ungut: Sie haben mir auf diese Weise viele nützliche Hinweise gegeben für die nächste Vorlesung am Dienstag. Und Sie haben mich dazu gezwungen, selbst noch einmal so didaktisch über den Algorithmus nachzudenken, wie ich es umgekehrt von Ihnen auf dem dritten Übungsblatt einfordere, so dass ich mich hoffentlich besser in Ihre (=Plural) Situation einfühlen kann. 8)

studypad hat geschrieben: Das ganze Gebilde ist etwas wie in FGdI, ein endlicher Automat mit Zuständen. Wir haben ein q was den Zustand simuliert und einen Zustandsübergangsgraph der die Lookup Table bildet. Oder verstehe ich es völlig falsch?
Nein, Sie verstehen es völlig richtig. :)

Daher natürlich auch der Name der Wiki-Seite: String matching based on finite automaton.

Ich habe allerdings das Problem in der GdI II, dass nur etwas mehr als die Hälfte aller Hörer überhaupt die FGdI belegen muss (und davon sicherlich auch noch lange nicht alle belegt haben), so dass ich nicht auf Vorerfahrungen aus der FGdI zurückgreifen kann.
studypad hat geschrieben: Mir ist jedoch dann die Bildung der Lookup table nicht klar?
Diesen Punkt hatte ich in der Vorlesung auch nicht mehr geschafft, der kommt dann am Dienstag. :wink:
studypad hat geschrieben: Diese muss man dann wohl hardcoden oder soll die Implementierung eine Lookup table zur Laufzeit selbst generieren?
Die Lookup Table wird zu Beginn des Algorithmus als zweidimensionaler Array ganz normal mit Operator new kreiert und dann sofort mit den geeigneten Werten auf Basis von T initialisiert. Diese Werte bleiben dann durch den ganzen Algorithmus hindurch konstant. Die Antwort auf Ihre Frage lautet also: zur Laufzeit selbst generieren (denn erst zur Laufzeit kennen Sie ja T).

KW

studypad
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 158
Registriert: 30. Mär 2011 11:46

Re: Nachtrag zum zweiten String Matching Algorithmus

Beitrag von studypad »

Hallo,
ja das Wiki und die Vorstellung des ersten Algorithmus' haben mich zunehmend verwirrt.

Ich habe das Buch "Algorithmen - Eine Einführung" und auf Seite 1007 (3.Auflage) wird der Algorithmus stark formellastig erklärt, doch mit der Zeit des Lesens wird mir etwas neues klar, was sie evt. hätten sagen sollen, damit es viele andere auch verstehen.
Wir arbeiten auf dem gesuchten Wort und "schieben die Textzeile darüber".

Ich werde mich noch weiter damit auseinandersetzen und bis Sonntag/Montag nochmal eine Zusammenfassung der Probleme, die ich hatte, hier posten. Ich wäre ihnen aber wirklich dankbar, wenn am Dienstag nochmal angerissen werden könnte, was vll einfach missverstanden werden konnte in der Aufzeichnung.
Danke

studypad
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 158
Registriert: 30. Mär 2011 11:46

Re: Nachtrag zum zweiten String Matching Algorithmus

Beitrag von studypad »

Also ich habe nun mit Hilfe des Buchs "Algorithmen - Eine Einführung" (gibt es auch bei der Buchaktion) und ihrer Erklärung hier, sowie dem Wiki mir folgende Probleme aus dem Weg räumen können:

- Ich dachte wir arbeiten über S doch gucken nur auf T -> Wir arbeiten auf T und wandern S entlang
- Ich verstand die Verbindung mit endlichen Automaten erst nicht -> Wiki + Google + Erklärung hier -> Es ist ein Automat des Wortes und bei Durchlaufen von S wandert man möglicherweise in akzeptierende Zustände, sprich T wird erkannt.
- Wie der Automat aussieht, ist zu berechnen -> Erklärung im Buch sehr gut -> Zustandsübergangsfunktion
- Ich verstand erst nicht wie so wir uns nur q merken müssen, doch mithilfe einer Lookup table ist das wirklich schlau :-)

Hoffe mit einer Erklärung am Dienstag alles weiterhin zu verstehen :-)

Danke für ihre direkte Hilfe und die Bemühungen

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Nachtrag zum zweiten String Matching Algorithmus

Beitrag von Prof. Karsten Weihe »

studypad hat geschrieben: Ich habe das Buch "Algorithmen - Eine Einführung" und auf Seite 1007 (3.Auflage) wird der Algorithmus stark formellastig erklärt, doch mit der Zeit des Lesens wird mir etwas neues klar, was sie evt. hätten sagen sollen, damit es viele andere auch verstehen.
Wir arbeiten auf dem gesuchten Wort und "schieben die Textzeile darüber".
Achtung: Diese Metapher habe ich mit Absicht nicht erwähnt! :shock:

Warum: Diese Metapher gibt zwar einen schönen Aha-Effekt, man fühlt tiefes Verständnis durch alle Gehirnwindungen fließen - sie passt aber leider nicht auf die Algorithmen und ist m.E. daher eher irreführend. Oder wie soll diese Metapher in Einklang gebracht werden mit der simultanen Verwaltung mehrerer Präfixe mit unterschiedlichen Startpunkten? Welcher dieser Präfixe entspricht denn der verschobenen Textzeile in der Metapher?

Würde mich freuen, wenn Sie mir das erklären könnten (das ist nicht ironisch, sondern ernst gemeint). Sie, ich und alle Teilnehmer der GdI II würden davon profitieren.

KW

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Nachtrag zum zweiten String Matching Algorithmus

Beitrag von Prof. Karsten Weihe »

studypad hat geschrieben: - Ich dachte wir arbeiten über S doch gucken nur auf T -> Wir arbeiten auf T und wandern S entlang
Stimmt, so kann man das gut sehen.

studypad hat geschrieben: - Ich verstand die Verbindung mit endlichen Automaten erst nicht -> Wiki + Google + Erklärung hier -> Es ist ein Automat des Wortes und bei Durchlaufen von S wandert man möglicherweise in akzeptierende Zustände, sprich T wird erkannt.
Ja, für jeden, der mit Automaten vertraut ist, ist das sicher ein gut verständlicher Hinweis. Wie gesagt, sind das bei weitem nicht alle Teilnehmer der GdI II.

Wobei man noch genau differenzieren muss: q=|T| ist kein akzeptierender Zustand, denn dann wäre der Algorithmus ja vorbei. Das ist ein Zustand wie jeder andere auch, nur dass außerhalb des Automaten etwas vom Automaten völlig Unabhängiges passiert, das man ebenfalls "akzeptieren" nennen kann (nämlich S[i-q+1] als Treffer akzeptieren). Eigentlich müsste man noch einen akzeptierenden Zustand zum Automaten hinzunehmen, der eintritt, wenn das Ende von S erreicht ist (bei ASCII-Dateien könnte man sagen: wenn S=EOF).

Sie sehen: Man kann bei diesem Thema sehr leicht zu früh der Meinung sein, man hätte es jetzt. :wink:


studypad hat geschrieben:
- Ich verstand erst nicht wie so wir uns nur q merken müssen, doch mithilfe einer Lookup table ist das wirklich schlau :-)


Ja, das ist genau der Punkt, den ich am Donnerstag nicht mehr geschafft habe und am Dienstag betrachten werde.


studypad hat geschrieben:
Hoffe mit einer Erklärung am Dienstag alles weiterhin zu verstehen :-)


Hoffe meinerseits auf Manöverkritik nach dem Dienstagstermin, die mir hilft, die Wiki-Seite zu verbessern und - wenn nötig - am Donnerstag noch etwas Zielführendes dazu zu sagen.

KW

studypad
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 158
Registriert: 30. Mär 2011 11:46

Re: Nachtrag zum zweiten String Matching Algorithmus

Beitrag von studypad »

Okay, vll bin ich etwas vom Aha-Gefühl überrannt worden.
Doch ist es nicht so, dass man sich mit Hilfe der LookUp table die Zustandsübergangsfunktion des Automaten auf T überlegt und dem Automaten dann S als "Futter" gibt?

Sprich der Automat bekommen zeichenweise S und verwaltet durch die Zustände die Zahl q, die der länge des längsten Präfixes von T bzw beim Treffer der Länge von T entspricht?
Nun arbeitet der Automat zeichenweise sich durch S und plötzlich passt das nächste Zeichen c nicht mehr, so guckt man im längsten Präfix+c nach dem längsten Suffix, dass ein Präfix von T ist bestimmt somit sein q neu.

Oder versteh ich das so grundlegend falsch?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Nachtrag zum zweiten String Matching Algorithmus

Beitrag von Prof. Karsten Weihe »

studypad hat geschrieben: Doch ist es nicht so, dass man sich mit Hilfe der LookUp table die Zustandsübergangsfunktion des Automaten auf T überlegt und dem Automaten dann S als "Futter" gibt?
Absolut richtig!

Ich glaube, ich hatte ihnen diesen Punkt schon bestätigt. :wink:

studypad hat geschrieben: Sprich der Automat bekommen zeichenweise S und verwaltet durch die Zustände die Zahl q, die der länge des längsten Präfixes von T bzw beim Treffer der Länge von T entspricht?
Korrekt.
studypad hat geschrieben: Nun arbeitet der Automat zeichenweise sich durch S und plötzlich passt das nächste Zeichen c nicht mehr, so guckt man im längsten Präfix+c nach dem längsten Suffix, dass ein Präfix von T ist bestimmt somit sein q neu.
In der Implementation schaut man natürlich nur in der Lookup Table nach, das schreibe ich noch einmal deutlich, damit Mitleser nicht durcheinanderkommen.

Aber der Wert in der Lookup Table ist genau das, was Sie geschrieben haben. Man kann das auch so schreiben: Wir nehmen den momentan längsten Präfix P von T, hängen S an und suchen in (P,S) nach dem längsten Präfix P' von T, das rechtsbündig in (P,S) angeordnet, also ein Suffix von (P,S). Die Länge von P war das alte q, die Länge von P' ist das neue q.


studypad hat geschrieben:
Oder versteh ich das so grundlegend falsch?


Mir scheint, Sie verstehen das alles absolut richtig! :mrgreen:

KW

studypad
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 158
Registriert: 30. Mär 2011 11:46

Re: Nachtrag zum zweiten String Matching Algorithmus

Beitrag von studypad »

Ich danke ihnen dafür, dass sie mit mir die Probleme aus dem Weg geräumt haben und hoffe mit einer gewissen Reifephase des Wissens das dritte theo.Übungsblatt auch gut zu bearbeiten :-)

Eichhorn
Windoof-User
Windoof-User
Beiträge: 36
Registriert: 9. Mär 2012 18:11

Re: Nachtrag zum zweiten String Matching Algorithmus

Beitrag von Eichhorn »

Hallo, ich habe gerade den zweiten String Matching-Algo aufarbeitet und wollte anhand ihres DNA-Beispieles mal gezielt die Induction Basis zur Erstellung der Look-Up-Table ansehen.

Sei wie in ihrem Beispiel \(\Sigma = { A,C,G,T }\) und das gesuchte Wort T = ACAG. Nehmen wir jetzt an, ich gehe in die Implementation und fange mit j = 0 an, den ersten Buchstaben
den ich überprüfe ist A aus \(\Sigma\). m sollte 4 sein.

\(k := \min\{m,j+1\}\)
min{4, 1} ist 1, also k = 1.

Jetzt gehts in die while-Schleife und es wird geschaut, ob k > 0 ( ist gegeben ) und \((T[1],\ldots,T[k])\neq(T[j-k+2],\ldots,T[j],c)\)
Wenn ich da jetzt aber konkrete Werte einsetze, steht da \((T[1],\ldots,T[1]\neq(T[1],\ldots,T[0],A)\). Wie liest man allgemein solche Folgen von Elementen?
\((T[1],\ldots,T[1])\) bedeutet wohl einfach T[1]? Aber wie muss ich \((T[1],\ldots,T[0],A)\) lesen? Einfach als A? Falls ja, kann man das irgendwie erklären? Ich denke da immer schnell an Arrays und da würde man
bei T[0] ja eine Exception um die Ohren bekommen, weil T ja scheinbar ab T[1] anfängt.

Zumindest sollte an meinem Beispiel da ja am Ende überprüft werden, ob \(T[1]\neq A\), was ja nicht der Fall ist, da \(T[1] = A\). Die while-Schleife wird also nicht mehr ausgeführt und
\(\Delta[0,A]:=1\) wird gesetzt.

Antworten

Zurück zu „Archiv“