Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Boyer Moore Algorithmus Suffix und Match Tabelle
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> Boyer Moore Algorithmus Suffix und Match Tabelle
 
Autor Nachricht
wlankabel2
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 15.01.2014
Beiträge: 1

BeitragVerfasst am: 15 Jan 2014 - 16:54:11    Titel: Boyer Moore Algorithmus Suffix und Match Tabelle

Hallo alle zusammen,

da ich neu hier bin stelle ich mich mal kurz vor:

ich bin 23, studiere im 5. Semester Medieninformatik in Stuttgart und habe ein Problem Wink.

Es geht wie genannt um den Boyer Moore Algorithmus, die Theorie dahinter und das Vorgehen sind mir klar - nicht allzu schwer. Jedoch haben wir in der Vorlesung immer eine Suffixtabelle, eine Match Tabelle und eine Last Occurence Tabelle aufgestellt - hier ist der Knackpunkt.

Ich habe wirklich das ganze Netz durchgesucht, bin dabei auf die Berechnung des Suffixes gekommen, jedoch nicht auf die anderen Tabellen.

Ich wäre sehr dankbar dafür, wenn mir jemand erklären könnte was genau eine Suffixtabelle überhaupt ist, und für was ich diese brauche. Genau dasselbe Spiel mit der match und match-unsafe Tabelle.



Liebe Grüße

Das Wlankabel
verselapaciente
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 23.01.2014
Beiträge: 1

BeitragVerfasst am: 23 Jan 2014 - 01:14:35    Titel:

Hi,
ich studiere auch MIB und gehe davon aus das wir zusammen die Prüfung schreiben werden Wink

Last occurrence Tabelle:
Suchmuster: A B C A A B
Alphabet= {A,B,C,D}
A B C D
1 0 3 6

Man fängt im Suchmuster am letzten Zeichen an und zählt dann bis zum nächsten vorkommenden Zeichen. Das schreibt man dann zu dem jeweiligen Buchstaben aus dem Alphabet (das gegeben ist).
ALSO:von dem letzten Buchstaben B bis A(der erste Eintrag in deiner Tabelle) musst du um 1 verschieben. Von dem letzten Buchstaben (wieder) B bis B (der zweite Eintrag in deiner Tabelle) musst du um 0 verschieben...

Suffix
Suchmuster:A C B A B C B A
index 0 1 2 3 4 5 6 7
Suffix 1 0 0 3 0 0 0(8 )

Man fängt im Suchmuster am letzten Zeichen an und guckt wo das nächste Zeichen wieder vorkommt (das übereinstimmt). Merkt sich die beiden stellen (unter die gefundene Stelle schreibt man die Anzahl der matches.)
ab der gefundenen stelle ist es ein match. Dann eins weiter nach links an deinem letzten und an deinem gefundenen Zeichen. Matches eins hochzählen. solange fort fahren bis Suchmuster zu ende ist oder ein Mismatch erfolgt. Und das macht man wieder mit allen Zeichen und dem letzten Zeichen.

Um den Boyer Moor Alg effizient zu gestalten, wird für Die Good Suffix Heuristiken in einem Vorverarbeitungsschritt jeweils eine Sprungtabelle errechnet. Die Tabelle für die Good-Suffix-Heuristik enthält für jedes Teilmuster (von hinten aus gesehen) den Abstand vom Ende des Musters, ab dem es wieder im Muster vorkommt. (Versuch es mal mit Wikipedia Wink )

Match unsafe und match muss ich mir selber noch mal durchlesen.

Lg
Chibchib
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 24.01.2014
Beiträge: 1

BeitragVerfasst am: 24 Jan 2014 - 18:56:30    Titel:

Hier auch gleicher Studiengang Very Happy und wir haben uns glaub vorhin in Theory of Game Development Prüfung mal kurz unterhalten Very Happy
Hab inzwischen ne Lösung zu der Tabelle in unserer Dropbok (müsste glaub alles Stimmen) https://www.dropbox.com/s/7ssx2zaxf4drd6j/Algorithmen%20und%20Datenstrukturen.pdf Auf S.6 findest du alles anhand eines Beispieles erklärt^^ hoffe es hilft^^
tuxonymous
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 04.02.2017
Beiträge: 1

BeitragVerfasst am: 04 Feb 2017 - 15:10:22    Titel:

Hey! Smile

Ich hab das gleiche Problem, gleiche Hochschule, gleicher Prof, gleiche Situation ... Very Happy hast du noch die Files vom Dropboxlink? Der ist leider inzwischen down...
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> Boyer Moore Algorithmus Suffix und Match Tabelle
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum