Seite 1 von 1

Preprocessing String Matching BOFA

Verfasst: 10. Aug 2015 18:41
von tmuecksch
Hi Leute,

ich weiß ja nicht wie es Euch geht, aber ich finde das Preprocessing bei der Aufgabe bezüglich String Matching BOFA.

Ich hatte eben eine Aufgabenstellung bestehend aus einem Alphabet mit 7 Zeichen und 20 Zuständen von foo vorgesetzt bekommen. Das heißt es gibt 20*7 = 140 Spalten auszufüllen. Ich habe dafür fast eine Stunde gebraucht und am Ende waren einige Fehler drin. Klar; wenn die Tabelle so riesig ist schleichen sich schnell mal Fehler ein.

Also entweder ist foo zu brutal oder ich arbeite einfach zu ineffizient.

Da ersteres bereits diskutiert wurde, muss es also an mir liegen :oops:

Habt Ihr Tipps oder gar ein Verfahren wie Ihr diese Aufgabe verlässlich und schnell löst?

Vielen Dank im Voraus

Re: Preprocessing String Matching BOFA

Verfasst: 11. Aug 2015 00:44
von CryNickSystems
viewtopic.php?f=561&t=32148&p=164604#p164604

Also eine Stunde ist wirklich heftig.

Große Tabellen fülle ich innerhalb von so 4-5min aus.

Du musst außerdem die meisten Zellen gar nicht ausfüllen, da dort ja eh eine 0 reinkäme.

Re: Preprocessing String Matching BOFA

Verfasst: 11. Aug 2015 16:32
von tmuecksch
Vielen Dank für den Tipp. Damit werde ich es mal versuchen!

Re: Preprocessing String Matching BOFA

Verfasst: 11. Aug 2015 20:11
von CryNickSystems
Ich kann ja mal meine Vorgehensweise für die Tabelle erläutern:

- Zu matchenden String aufschreiben und Indizes durchnummerieren
- Substrings finden und Positionen (gezählt ab 1) von jenen (inkl. Buchstaben) aufschreiben
- Substrings von Blatt in Tabelle übertragen während ich die "normalen" Buchstaben des Matchers durchzähle (beginnend bei 1)
- Zuletzt die Spalte mit dem Anfangsbuchstaben des Matchers komplett mit Einsen (1) befüllen

Ich hoffe, jemand versteht, wie ich das meine :D Vllt. machen das ja sogar einige ähnlich wie ich.

Re: Preprocessing String Matching BOFA

Verfasst: 16. Aug 2015 16:39
von tmuecksch
Hi CryNickSystems,

vielen Dank für Deinen Beitrag. Ich habe es nämlich noch nicht gerafft :roll:

Was bedeutet in Deiner Aufzählung: "Substrings finden" ?

Re: Preprocessing String Matching BOFA

Verfasst: 17. Aug 2015 16:14
von CryNickSystems
Wiederholungen.

Schau dir mal diese Grafik an:
http://puu.sh/jED1S/908402678a.png

Ich habe dort die Zustandstabelle bereits ausgefüllt und zusätzlich an die Seite den derzeitigen Buchstaben sowie eventuelle Wiederholungen inkl. Zustandszahl notiert.

Hier mal beispielhaft für die ersten vier Buchstaben erklärt:

Code: Alles auswählen

acan
^^^^
1234
(oben die Buchstaben, unten die Zustandszahl)

Wenn jetzt statt dem "n" an 4. Stelle nun ein "c" Stünde, könnte man doch in Zustand zwei, also Substring der Länge 2 gefunden haben?
Daher habe ich als "alternativen Pfad" (wenn man ihn so nennen möchte) bei "c" in Zustand 4 eine "2" eingetragen.

Also ist das alles nichts weiter als Wiederholungen finden ;)

EDIT:
In meiner Grafik fehlt natürlich in der gesamten ersten Spalte (also "a"), wo nichts eingetragen ist, eine 1 :)

Re: Preprocessing String Matching BOFA

Verfasst: 28. Aug 2015 18:41
von tmuecksch
Hi CryNickSystems,

danke für Deine Hilfsbereitschaft!

[EDIT:] Hab es jetzt gecheckt :D