Nachtrag zum zweiten String Matching Algorithmus

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 »

Eichhorn hat geschrieben: \((T[1],\ldots,T[1])\) bedeutet wohl einfach T[1]? Aber wie muss ich \((T[1],\ldots,T[0],A)\) lesen? Einfach als A?
Ja, siehe https://hermes.algo.informatik.tu-darms ... hp/Numbers, Stichwort Intervalle. Ich dachte, das wäre so bekannt, sollte ich dann vielleicht am Donnerstag noch einmal kurz ansprechen...

Eichhorn hat geschrieben: Falls ja, kann man das irgendwie erklären?
Eine Definition kann man motivieren: Dass \((x,\ldots,x[j])=\emptyset\) für \(i>j\) sen soll, ist eine Standarddefinition in der Mathematik. Andere Beispiele sind etwa \(\sum_{i=1}^0x_i=0\), \(a^0=1\) und \(0!=1\). Die Motivation ist immer dieselbe: Man will ein Konzept, das für \(>0\) definiert ist, so auf den Fall \(=0\) ausdehnen, dass es passt, das heißt, dass alle Formeln und Aussagen für den Fall \(>0\) ohne Umformulierung auch gleich für den Fall \(=0\) passen.

KW

christophbued
Mausschubser
Mausschubser
Beiträge: 54
Registriert: 12. Mär 2012 13:43

Re: Nachtrag zum zweiten String Matching Algorithmus

Beitrag von christophbued »

Ich habe noch ein frage zur lookup tablle und was passiert wenn ich zwei überlappende Kandidanten find wie im beispiel gefordert.

also mein SuchString ist T = ABAB und mein Alphabet ist folgendens = ABCD

mein String S ist so aufgebaut

A B C A A B A B A B A B D A B C B A B )
1 2 3 4 5 6 7 8 9 10 11 12 usw.
an der stelle 5-8 haben ich ja einen treffer und bei 7-10 und von 9 bis 11 könnte ja wieder ein treffer entstehen...(das weiß man ja vorher noch nicht da ich ja nur schritt für schritt durch die liste gehe)

Mein frage ist wie speicher ich mit mein zweites enstehenden Treffer(geht ja bei 7 los) ich hab ja nur q als speicher der den längtes möglichen treffer ist ja noch nicht komplett fertig wenn bei 7 schon der neue anfäng..
Das gleiche problem habe ich ja dann wieder bei 9.

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

Re: Nachtrag zum zweiten String Matching Algorithmus

Beitrag von JannikV »

Dein q kann in diesem Fall ja 5 mögliche Zustande einnehmen:
0 - sieht schlecht aus
1 - wir haben das erste A
2 - das erste B
3 - das nächste A
4 - und das letzte B (jetzt den Index Berechnen und in die Ergebnismenge einfügen)

In deinem Beispiel bist du nach Iteration 8 ja in Zustand 4. Jetzt kommt in Iteration 9 wieder ein A. In welchen Zustand würdest du denn jetzt übergehen? (Kleiner Tipp, der 1. ist es nicht :P )

VG

onbes
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 30. Jul 2011 18:43

Re: Nachtrag zum zweiten String Matching Algorithmus

Beitrag von onbes »

Moin moin,

habe eine Frage grundsätzliche Frage zum Aufbau der Lookup Table:
Wenn ich die Tabelle "intuitiv" (intuitiv im Sinne von FGDI, weil man da Automaten ja bis zum erbrechen durchgekaut hat) mache habe ich eine 7x3 (Zeilen x Spalten) Tabelle in max. 1 Minuten inkl. überprüfen hingeschr..
Wenn ich wie im 4. Punkt der Implementation der Induction basis vorgehe brauch ich für die Tabelle min. 10-15 Minuten, weil ich alles hinschreiben muss um mich nicht zu verheddern.

Hinsichtlich der Prüfung: Muss man 100% Schritt für Schritt Punkt 4 der Implementation in der Induction Basis anzugeben in der Prüfung beim Erstellen der Tabelle oder gilt hier hauptsache eine gültige Zustandsübergangstabelle für einen/den DFA? (denn wer die Zustandsübergangstabelle erstellen kann sollte ja wohl das Prinzip von dem korrekt Algorithmus verstanden haben)

Falls "..100% Schritt für Schritt Punkt 4..": Jmd. einen "Eselsbrücke" wie man es ohne verheddern ala Punkt 4 machen kann?

Schönen Gruß
Onbes

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 »

onbes hat geschrieben: habe eine Frage grundsätzliche Frage zum Aufbau der Lookup Table
Ihre Frage ist eher zum Aufbau einer evtl. Klausuraufgabe? :wink:

onbes hat geschrieben: Hinsichtlich der Prüfung: Muss man 100% Schritt für Schritt Punkt 4 der Implementation in der Induction Basis anzugeben in der Prüfung beim Erstellen der Tabelle oder gilt hier hauptsache eine gültige Zustandsübergangstabelle für einen/den DFA? (denn wer die Zustandsübergangstabelle erstellen kann sollte ja wohl das Prinzip von dem korrekt Algorithmus verstanden haben)
Eine Iteration des Induction Step (bzw wahlweise eine Iteration der Induction Basis) = eine Aufgabe.

Beantwortet das Ihre Frage?

KW

onbes
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 30. Jul 2011 18:43

Re: Nachtrag zum zweiten String Matching Algorithmus

Beitrag von onbes »

Moin Herr Weihe,

vielen Dank für Ihre Antwort. Meine Frage ist leider immernoch offen.
In dem Dokument bezüglich der Prüfung steht ja, dass 3 Aufgaben von dem Typ "...Muster..." vorkommen werden und keine Fragen während der Prüfung zugelassen sind. Woher soll man wissen ob mit Iteration Nr. x eine Iteration in der Induction Base oder im Induction step gemeint ist? Das größe Problem bez. der Prüfung sehe ich Moment bei sowas, weil man dadurch ungewollt schnelle/einfache Punkte verschenken kann.
Wenn jetzt bei dem String Maching based on Automaton von _einer_ Iteration die Rede ist, ist eine Iteration beim abstract view klar.
Bei der Basis im Bezug auf die Tabelle steht "The look-up table must be built".
Im Vorfeld wurde gesagt, dass die Implementation für die Prüfung irrelevant ist.... oder stelle ich mir gerade einfach nur an?^^

Schönen Gruß
Onbes


PS: Ich finde gerade keine Übersicht der Termine für Sprechstunden. Ist die irgendwo verlinkt?

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 »

onbes hat geschrieben: Woher soll man wissen ob mit Iteration Nr. x eine Iteration in der Induction Base oder im Induction step gemeint ist?
Ok, die Aufgabenstellung wird das genau klarstellen. Aus dem Beispiel, auf das Sie den Algorithmus anwenden sollen, würde es ansonsten sowieso klar würde.

Wir reden hier über einen Aspekt, der nur bei einem einzigen Algorithmus aus der Vorlesung überhaupt vorkommt, oder?
onbes hat geschrieben: PS: Ich finde gerade keine Übersicht der Termine für Sprechstunden. Ist die irgendwo verlinkt?
Kommt noch.

KW

onbes
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 30. Jul 2011 18:43

Re: Nachtrag zum zweiten String Matching Algorithmus

Beitrag von onbes »

Ja, diese "Unklarheit" ist (sofern ich die anderen Algorithmen noch vollständig im Kopfhabe) nur dem string matching based on automaton Algorithmus zu eigen.

Danke für die Sprechstundentermine nächste Woche!:)

r_fakhry
Neuling
Neuling
Beiträge: 5
Registriert: 30. Jul 2012 17:40

Re: Nachtrag zum zweiten String Matching Algorithmus

Beitrag von r_fakhry »

Eine Frage zum 2. Induktionsschritt, in dem Fall wo q=m ist.
Ist es irgendwo beschrieben worden, dass nachdem ein Treffer gefunden ist, q dann auf das nächste, längste Präfix k gesetzt wird?
Wenn das nicht gemacht wird, stimmt das Ergebnis schon, aber ich denke zu diesem Zeitpunkt, wo einen Treffer gefunden wird und unmittelbar vor der nächsten Iteration q=m bleibt, dann stimmt die 2. Invariante (das q den Wert des längsten Präfixes enthält) nicht. Oder habe ich dabei etwas übersehen?

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 »

r_fakhry hat geschrieben:Eine Frage zum 2. Induktionsschritt
Also genauer zum 2. Schritt des Induktionsschrittes?

Wie können wir die einzelnen Auflistungspunkte im Induktionsschritt nennen? Das Wort "Schritt" ist zwar naheliegend und passend, führt aber wie hier zu Konfusionen mit "Induktionsschritt", was aber als eingeführter Begriff genau so heißen sollte.

r_fakhry hat geschrieben: in dem Fall wo q=m ist.
Ist es irgendwo beschrieben worden, dass nachdem ein Treffer gefunden ist, q dann auf das nächste, längste Präfix k gesetzt wird?
Das passiert doch im 1. Schritt in der unmittelbar nächsten Iteration, bevor im 2. Schritt dann \(q\) zum nächsten Mall evaluiert wird.

KW

Antworten

Zurück zu „Archiv“