Code aus der Vorlesung (Preprocessing String Matching BOFA)

Bei Postings zu Vorlesungsthema X lassen Sie Ihr Betreff bitte mit "X: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Vorlesungsthema X lassen Sie Ihr Betreff bitte mit "X: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
Janosch
Mausschubser
Mausschubser
Beiträge: 50
Registriert: 17. Mär 2014 14:28

Code aus der Vorlesung (Preprocessing String Matching BOFA)

Beitrag von Janosch » 24. Apr 2016 15:25

Hallo,


ich habe immer noch einige Schwierigkeiten diesen exemplarischen Beispielcode richtig zu verstehen, da dieser bewusst nur angedeutet ist.

Gibt es vielleicht einen vollständig funktionierenden Code welchen ich mir unter echten Bedingungen Schrittweise durcharbeiten kann, welcher auf diesen adaptiert?
Habe mir diese Stelle auch mehrmals auf der Aufzeichnung angehört und kann leider vieles nicht nachvollziehen. Wenn ich mich an die Implementation wagen würde, sehe dies völlig anders aus und höchstwahrscheinlich auch am Grundthema vorbei.


Gruß

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Code aus der Vorlesung (Preprocessing String Matching BOFA)

Beitrag von Prof. Karsten Weihe » 24. Apr 2016 16:20

Janosch hat geschrieben: ich habe immer noch einige Schwierigkeiten diesen exemplarischen Beispielcode richtig zu verstehen, da dieser bewusst nur angedeutet ist.
Ich nehme an, Sie meinen die Datei "Preprocessing String Matching BOFA.rtf"?

Das einzige, was zu einer vollständigen Implementation fehlt, sind doch die exakten Implementationen von "for ( char c im Alphabet )" und "(T[1],..,T[k]) == (T[j-k+2],..,T[j],c)". Ist das ein Problem?

KW

Janosch
Mausschubser
Mausschubser
Beiträge: 50
Registriert: 17. Mär 2014 14:28

Re: Code aus der Vorlesung (Preprocessing String Matching BOFA)

Beitrag von Janosch » 24. Apr 2016 16:35

Hauptsächlich "for ( char c im Alphabet ) ".
Ich verstehe c als Aktuelle Stelle in S. Evtl. ist genau dieser Gedanke falsch. Etwas anderes erscheint mir aber eher unlogisch.

Und stellt Delta das mehrdimensionale Array als Tabelle für den Automaten dar?


Gruß

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Code aus der Vorlesung (Preprocessing String Matching BOFA)

Beitrag von Prof. Karsten Weihe » 24. Apr 2016 16:52

Janosch hat geschrieben:Hauptsächlich "for ( char c im Alphabet ) ".
Ich verstehe c als Aktuelle Stelle in S. Evtl. ist genau dieser Gedanke falsch. Etwas anderes erscheint mir aber eher unlogisch.
Das Preprocessing schaut sich \(S\) überhaupt nicht an. Es steht da ja auch "for ( char im Alphabet )" und nicht so etwas wie "for ( char c in S )" oder ähnlich. Das ist ja gerade der Witz an diesem Algorithmus, dass er minimal mit dem potentiell laaaaaaangen String \(S\) arbeitet, dafür etwas aufwändiger mit dem meist eher kurzen String \(T\) im Preprocessing.

Immer wenn wir von Strings reden, steht dahinter ein Alphabet, aus dem die Zeichen der Strings entnommen sind, z.B. "a..z" oder ASCII, Iso-Latin-1 oder Unicode oder auch das Alphabet (A,C,G,T) im Beispiel DNA-Sequenzen. In der Lookup Table haben Sie für jedes Zeichen des zugrundeliegenden Alphabets eine Spalte. Mit "for ( char c im Alphabet )" durchlaufen Sie alle Zeichen des Alphabets und damit alle Spalten der Lookup Table. Die doppelte for-Schleife durchläuft schlicht und einfach alle Zellen der Lookup Table und setzt deren Werte.

Übrigens: Wenn Ihr Alphabet so etwas wie "a..z" ist, bietet es sich zur Vermeidung von fehleranfälligen Indexrechnereien an, dass Sie der Lookup Table Spalten von 0 bis zum ASCII-Index von 'z' geben, aber die Spalten vor dem ASCII-Index von 'a' nicht benutzen.
Janosch hat geschrieben: Und stellt Delta das mehrdimensionale Array als Tabelle für den Automaten dar?
Yep.

Klarer geworden?

KW

Janosch
Mausschubser
Mausschubser
Beiträge: 50
Registriert: 17. Mär 2014 14:28

Re: Code aus der Vorlesung (Preprocessing String Matching BOFA)

Beitrag von Janosch » 24. Apr 2016 17:30

Viel klarer!

Vielen Dank dafür!


Hauptproblem war meine völlig fehlgeleiteter Gedanke, dass dieser Code den gesamten String matching BOFA implementiert.
Ich sollte es unter diesen Bedingungen und mit klarem Kopf nochmal durchgehen. Heute ist erst mal Selbstärgernis angesagt.


Danke nochmal

yi_
Neuling
Neuling
Beiträge: 9
Registriert: 6. Aug 2016 18:07

Re: Code aus der Vorlesung (Preprocessing String Matching BOFA)

Beitrag von yi_ » 6. Aug 2016 18:23

Prof. Karsten Weihe hat geschrieben:Immer wenn wir von Strings reden, steht dahinter ein Alphabet, aus dem die Zeichen der Strings entnommen sind, z.B. "a..z" oder ASCII, Iso-Latin-1 oder Unicode oder auch das Alphabet (A,C,G,T) im Beispiel DNA-Sequenzen. In der Lookup Table haben Sie für jedes Zeichen des zugrundeliegenden Alphabets eine Spalte. Mit "for ( char c im Alphabet )" durchlaufen Sie alle Zeichen des Alphabets und damit alle Spalten der Lookup Table. Die doppelte for-Schleife durchläuft schlicht und einfach alle Zellen der Lookup Table und setzt deren Werte.

Übrigens: Wenn Ihr Alphabet so etwas wie "a..z" ist, bietet es sich zur Vermeidung von fehleranfälligen Indexrechnereien an, dass Sie der Lookup Table Spalten von 0 bis zum ASCII-Index von 'z' geben, aber die Spalten vor dem ASCII-Index von 'a' nicht benutzen.
Hallo,
so wie Sie das hier schreiben (und in allen Implementationen die ich online gefunden habe) wird immer ein Alphabet genutzt, dass alle Buchstaben umfasst, die im langen String enthalten sein können (also z. B. einfach A-z). Ich habe beim erstellen der Tabelle ein Set aus den Buchstaben des gesuchten Strings erstellt und das Set dann als Alphabet genutzt. Das heißt alle Buchstaben, die nicht auch im Suchwort vorkommen, tauchen in der Tabelle gar nicht auf. Beim zuweisen von q (nächster längster Kandidat) habe ich dann einfach geprüft, ob ein Eintrag vorhanden ist und falls nicht, q auf 0 gesetzt.
Ich wollte nur nachhaken, ob das irgendein Problem birgt.

Lieben Gruß

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Code aus der Vorlesung (Preprocessing String Matching BOFA)

Beitrag von Prof. Karsten Weihe » 7. Aug 2016 00:19

yi_ hat geschrieben: so wie Sie das hier schreiben (und in allen Implementationen die ich online gefunden habe) wird immer ein Alphabet genutzt, dass alle Buchstaben umfasst, die im langen String enthalten sein können (also z. B. einfach A-z). Ich habe beim erstellen der Tabelle ein Set aus den Buchstaben des gesuchten Strings erstellt und das Set dann als Alphabet genutzt. Das heißt alle Buchstaben, die nicht auch im Suchwort vorkommen, tauchen in der Tabelle gar nicht auf. Beim zuweisen von q (nächster längster Kandidat) habe ich dann einfach geprüft, ob ein Eintrag vorhanden ist und falls nicht, q auf 0 gesetzt.
Ich wollte nur nachhaken, ob das irgendein Problem birgt.
Wie prüfen Sie denn, ob ein Eintrag vorhanden ist?

KW

yi_
Neuling
Neuling
Beiträge: 9
Registriert: 6. Aug 2016 18:07

Re: Code aus der Vorlesung (Preprocessing String Matching BOFA)

Beitrag von yi_ » 7. Aug 2016 18:27

Prof. Karsten Weihe hat geschrieben: Wie prüfen Sie denn, ob ein Eintrag vorhanden ist?
Ich speichere die lookup-table als ArrayList aus HashMaps. Also ArrayList<HashMap<String, Integer>>.
Der relevante Teil sieht so aus:

Code: Alles auswählen

for (int i = 0; i < n; i++) {
      if (lookupTable.get(q).get(String.valueOf(sourceArray[i])) == null) {
        q = 0;
      } else {
        q = lookupTable.get(q).get(String.valueOf(sourceArray[i]));
      }
      if (q == m) {
        R.add(i - m + 1);
      }
    }
Die .get Methode der HashMap liefert null zurück, wenn der Eintrag nicht vorhanden ist. Jetzt wo Sie fragen fällt mir auf, dass das mit einem Array vielleicht nicht so leicht zu lösen wäre. Ich habe mich am Anfang irgendwie dazu entschieden, das mit Collections zu machen, weil ich dachte dass es später schwierig werden könnte, q anhand eines Buchstabens abzufragen. Speichert man die Tabelle als Array, muss man ja den Index des Buchstabens kennen, um den zugehörigen Wert zu erhalten. Da war ich mich nicht ganz sicher, wie das zu lösen ist und dachte es ist leichter, direkt den Buchstaben als String zu übergeben.

Lieben Gruß

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Code aus der Vorlesung (Preprocessing String Matching BOFA)

Beitrag von Prof. Karsten Weihe » 8. Aug 2016 13:07

yi_ hat geschrieben:Jetzt wo Sie fragen fällt mir auf
Das heißt, Problem gelöst?

KW

yi_
Neuling
Neuling
Beiträge: 9
Registriert: 6. Aug 2016 18:07

Re: Code aus der Vorlesung (Preprocessing String Matching BOFA)

Beitrag von yi_ » 8. Aug 2016 13:23

Prof. Karsten Weihe hat geschrieben:
yi_ hat geschrieben:Jetzt wo Sie fragen fällt mir auf
Das heißt, Problem gelöst?
Hm, ja, also beim Ausführen gab es bisher ja kein Problem. Mich hätte nur interessiert, ob es einen Grund gibt, eine lookup-table mit einem Alphabet zu erstellen, das wahrscheinlich deutlich mehr Buchstaben enthält als der gesuchte String. Die Berechnung der Tabelle dauert dadurch doch nicht unwesentlich länger oder nicht? Da das aber in allen Implementationen die ich gefunden habe trotzdem gemacht wurde, war ich mir unsicher ob es nicht doch einen Grund dafür gibt, den ich übersehe.

Lieben Gruß

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Code aus der Vorlesung (Preprocessing String Matching BOFA)

Beitrag von Prof. Karsten Weihe » 8. Aug 2016 14:35

yi_ hat geschrieben:Mich hätte nur interessiert, ob es einen Grund gibt, eine lookup-table mit einem Alphabet zu erstellen, das wahrscheinlich deutlich mehr Buchstaben enthält als der gesuchte String. Die Berechnung der Tabelle dauert dadurch doch nicht unwesentlich länger oder nicht? Da das aber in allen Implementationen die ich gefunden habe trotzdem gemacht wurde, war ich mir unsicher ob es nicht doch einen Grund dafür gibt, den ich übersehe.
Entweder reine Bequemlichkeit der Autoren oder möglichst geringe Laufzeit beim Look Up, würde ich vermuten.

KW

yi_
Neuling
Neuling
Beiträge: 9
Registriert: 6. Aug 2016 18:07

Re: Code aus der Vorlesung (Preprocessing String Matching BOFA)

Beitrag von yi_ » 8. Aug 2016 18:40

Prof. Karsten Weihe hat geschrieben:Entweder reine Bequemlichkeit der Autoren oder möglichst geringe Laufzeit beim Look Up, würde ich vermuten.
Alles klar, dann vielen Dank für die Antworten!

Besten Gruß

Antworten

Zurück zu „AuD: Vorlesung“