Textsuche

Algorithmus von Karp-Rabin

 aufwärts

Idee

Das Verfahren von Karp und Rabin [KR 87] ähnelt in gewisser Weise dem naiven Algorithmus, denn das Muster wird mit jedem Textfenster verglichen. Aber statt das Muster an jeder Position symbolweise mit dem Textfenster zu vergleichen, wird nur ein einziger Vergleich durchgeführt, und zwar wird die Signatur des Musters mit der Signatur des Textfensters verglichen. Eine Signatur ist ein möglichst eindeutiges Merkmal.

Beispiel:  Das Alphabet ist A = {0, ..., 9}, das Muster  p = 1 3 0 8 und die Signatur­funktion ist die Quersumme. Die Quersumme von 1 3 0 8 ist  1 + 3 + 0 + 8 = 12.

Bild 1: Quersummen in verschiedenen Textfenstern
Bild 1: Quersummen in verschiedenen Textfenstern

Die Quersumme des an Position 0 beginnenden Textfensters 7 6 2 1 ist 16. Hier kann also das Muster nicht über­einstimmen. Bei den Textfenstern an den Positionen 1 und 3 stimmt die Quersumme überein. Hier muss geprüft werden, ob das Muster tatsächlich über­einstimmt.

Damit das Verfahren effizient ist, sind an die Signatur­funktion zwei Anforderungen zu stellen:

Eine Kollision entsteht, wenn die Signatur über­einstimmt, das Muster aber nicht. Wie an obigem Beispiel ersichtlich, ist die Quersumme nicht besonders gut als Signatur geeignet, da sie gegenüber Kollisionen sehr anfällig ist.

Hingegen lässt sich jede Signatur aus der vorher­gehenden in konstanter Zeit berechnen: die Zahl, die das Textfenster verlässt, wird subtrahiert, die neu zum Fenster hinzu­kommende Zahl wird addiert. Wenn das Fenster von Position 0 nach 1 verschoben wird, verlässt 7 das Fenster, 3 kommt hinzu. Die neue Quersumme ergibt sich also aus der alten wie folgt:

16 - 7 + 3  =  12

Signatur

Definition:  Sei A ein Alphabet und M eine Menge. Eine Signatur­funktion ist eine Abbildung s : APfeil nach rechts M, die jedem Wort x Element A* einen Wert aus s(xElement M zuordnet. Der Wert s(x) ist die Signatur von x.

Definition:  Sei s : APfeil nach rechts M eine Signatur­funktion. Eine Kollision ist ein Paar von Wörtern

(x, x')   mit   x ≠ x'  aber  s(x) = s(x')

Wie in obigem Beispiel sei A = {0, ..., 9}. Eine bessere Signatur­funktion als die Quersumme ist die durch die Ziffern der Zeichenreihe gebildete Dezimalzahl, also z.B. die Zahl 1308 für die Zeichenreihe 1 3 0 8. Bei dieser Signatur­funktion sind sogar Kollisionen aus­geschlossen.

Die auf diese Weise zustande kommenden Zahlen sollten allerdings jeweils in ein Maschinen­wort passen, so dass sie in konstanter Zeit berechnet werden können. Hat die Zeichenreihe eine Länge von höchstens 9 Zeichen, so passt die zugehörige Zahl in ein 32-Bit-Wort. Bei mehr als 9 Zeichen werden nur die letzten 9 Zeichen berück­sichtigt, allerdings kann es dann zu Kollisionen kommen.

Diese Signatur­funktion ist formal wie folgt definiert:

s(x0 ... xm-1)  =   Summe j = 0, ..., m-1  10 j · xm-j-1   mod  109

 

Die Signatur s' des Textfensters ti+1 ... ti+m wird aus der Signatur s des vorher­gehenden Fensters ti ... ti+m-1 wie folgt berechnet:

s'  =  ((s  – 10m-1·ti)·10 + ti+m)   mod  109

Diese Signatur­funktion ist auch für größere Alphabete mit mehr als zehn Zeichen anwendbar, allerdings mit größerer Gefahr von Kollisionen.

Die folgende Implementation des Karp-Rabin-Algorithmus führt entsprechende Berechnungen zur Basis 2 modulo 232 durch.

Algorithmus

Die Multi­plikation mit 2 wird durch eine Linksschiebe-Operation realisiert. Die Multi­plikation mit 2m-1 kann nicht durch Links­schieben um m-1 realisiert werden, jedenfalls nicht, wenn mgrößer gleich32 ist. In der 32-Bit-Arithmetik von Java werden Schiebe­distanzen modulo 32 gerechnet. Statt z.B. um 34 würde also um 2 geschoben werden. Es wird daher eine Variable h = 2m-1 mod 232 benötigt. Die Operation mod 232 wird implizit durch die 32-Bit-Zahlen­darstellung bewirkt.

Wiederum wird angenommen, dass der Preprocessing- und der Such­algorithmus in einer Klasse KarpRabin gekapselt sind. In der Klasse sind die Integer-Variablen h und sp deklariert. Die Variable sp enthält die Signatur des Musters.

Karp-Rabin-Preprocessing
void krPreprocess()
{
    int i;
    h=1; sp=p[0];

    for (i=1; i<m; i++)
    {
        h<<=1;
        sp=(sp<<1)+p[i];
    }
}
Karp-Rabin-Such­algorithmus
void krSearch()
{
    int i, st=0;

    for (i=0; i<m; i++)
        st=(st<<1)+t[i];

    for(i=m; i<n; i++)
    {
        if (sp==st && matchesAt(i-m)) report(i-m);
        st=(st-t[i-m]*h<<1)+t[i];
    }
    if (sp==st && matchesAt(n-m)) report(n-m);
}

Die Funktion matchesAt vergleicht das Muster mit dem an Position i beginnenden Textfenster auf eine beliebige Weise. Im Such­algorithmus wird matchesAt jedoch nur dann aufgerufen, wenn die Signaturen des Musters und des Textfensters über­einstimmen.

Analyse

Der Preprocessing-Algorithmus benötigt Θ(m) Schritte. Der Such­algorithmus benötigt im schlechtesten Fall Θ(n·m) Schritte, z.B. wenn p = am und t = an. Im Durchschnitt allerdings hat der Algorithmus eine Komplexität von Θ(n).

Literatur

[KR 87]R. Karp, M. Rabin: Efficient Randomized Pattern-Matching Algorithms. IBM Journal of Research and Development 31, 249-260 (1987)
[Web 1]http://www-igm.univ-mlv.fr/~lecroq/string/  

 

Weiter mit:   [Shift-And-Algorithmus]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 20.03.2001   Updated: 29.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik