Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

String-Matching Rabin-Karb-Algorithmus
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> String-Matching Rabin-Karb-Algorithmus
 
Autor Nachricht
muhkuh24
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 28.01.2009
Beiträge: 2

BeitragVerfasst am: 28 Jan 2009 - 16:09:36    Titel: String-Matching Rabin-Karb-Algorithmus

Hallo allerseits,

ich komm nicht ganz klar mit dem String-Matching-Algorithmus von Rabin und Karb.

Dabei geht es um folgendes:
Gegeben sei ein String-Muster P der Länge m und ein Text T der Länge n
Gesucht wird jede Verschiebung s, wo das Muster P[1..m] mit dem Text T[s..s+m] übereinstimmt.

Rabin und Karb sehen dabei die Zeichenkette als Zahl, weil Zahlen schneller verglichen werden können als Zeichen für Zeichen.
Das Umwandeln der Zeichen für p=P[1..m] und t_0=T[1..m] geht ganz leicht mittels HornerSchema in O(m):
p=P[m]+10(P[m-1]+10(...+P[1]))..)

Jede weitere TextZahl t_s+1 erhaält man in konstanter Zeit aus t_s:
t_s+1=10(t_s - (10^(m-1)) * T[s]) + T[s+m+1]

Da Zahlen schnell sehr groß werden können wenden wir jetzt einfach die moduloFunktion an (mit einer großen Primzahl):
also p=P[m]+10(P[m-1]+10(...+P[1]))..) mod q
t_0=T[m]+10(T[m-1]+10(...+T[1]))..) mod q
und
t_s+1=10(t_s - h * T[s]) + T[s+m+1] mod q
wobei h=(10^(m-1)) mod q

Mein Problem:
und genau das mit dem "h=(10^(m-1)) mod q" versteh ich nicht.
Ich nehme dazu ein Beispiel her:
T=314152
P=31415
q=13

p= 7 ; t_0 = 7 ; alles schön
jetzt kommt t_s+1 = t_1 = 10(314152 - (h * 3)) + 2 mod 13
laut Algorithmus ist t_1= 8
aber wenn ichs per Hand nachrechne:
t_1 = 10(314152 - (((10^4)mod 13) *3)) + 2 mod 13
= 10(314152 - (4 *3)) + 2 mod 13
= 10(314152 - (12)) + 2 mod 13
= 10(314140) + 2 mod 13
= 3141402 mod 13
= 4

und offensichtlich ist 4 != 8

was ist falsch???

Danke für eure Hilfe im Voraus.
gruß muhkuh24[/u]
Smutje
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 18.07.2008
Beiträge: 3004
Wohnort: Gießen

BeitragVerfasst am: 28 Jan 2009 - 17:23:44    Titel:

t_1 = 10(314152 - (((10^4) mod 13) *3)) + 2 mod 13
= 10(314152 - (3 * 3)) + 2 mod 13
= 10(314152 - 9) + 2 mod 13
= 10(314143) + 2 mod 13
= 3141432 mod 13
= 8

Die falschen Stellen hab ich mal fett markiert.
muhkuh24
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 28.01.2009
Beiträge: 2

BeitragVerfasst am: 28 Jan 2009 - 18:44:02    Titel:

ahh danke,
nur ein rechenfehler.
dachte schon die sonne dreht sich um die erde Very Happy

vielen vielen dank.
gruß muhkuh24
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> String-Matching Rabin-Karb-Algorithmus
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