Textsuche
Shift-And -Algorithmus
Idee
Der Shift-And-Algorithmus [WM 92] bildet zu jedem Textfenster einen Zustandsvektor z, der angibt, an welchen Positionen des Fensters ein mögliches Vorkommen des Musters beginnt. Der Zustandsvektor lässt sich aus dem Zustandsvektor des vorhergehenden Fensters in konstanter Zeit berechnen.
Definition: Sei p wiederum das Muster der Länge m. Mit uj sei das Präfix des Musters p bezeichnet, das an Position j endet (j = 0, ..., m-1):
uj = p0 ... pj.
Insbesondere ist also um-1 = p.
Beispiel: Das Muster p = abbabab hat beispielsweise die Präfixe u0 = a und u3 = abba.
Definition: Sei w ein Textfenster der Länge m. Seien ferner u0, ..., um-1 die Präfixe des Musters p.
Zu gegebenem Muster p ist der Zustandsvektor z = z0, ..., zm-1 eines Textfensters w folgendermaßen definiert:
| zj = |  |
|
Beispiel: Es sei p = abbabab das Muster und w = baabbab ein Textfenster. Die Präfixe u0, ..., u6 des Musters sind in folgender Tabelle unter das Textfenster geschrieben. Dort wo eines dieser Präfixe mit einem Suffix des Textfensters übereinstimmt, enthält der Zustandsvektor z eine 1. Es ist also z = 0100100.
Der Zustandsvektor z kann als eine Art Signatur des Textfensters angesehen werden. Das Muster p stimmt mit dem Textfenster w überein, wenn die Signatur des Musters mit der Signatur des Fensters übereinstimmt. Tatsächlich genügt es, das Bit zm-1 zu testen, denn es gilt zm-1 = 1 ⇔ p = w .
Wird das Textfenster um eine Position weitergeschoben, so verlässt ein Zeichen das Fenster und ein neues kommt hinzu. Die dazwischen liegenden Zeichen bleiben gleich. Dies wird ausgenutzt, um den Zustandsvektor des neuen Textfensters in konstanter Zeit aus dem vorherigen Zustandsvektor zu berechnen.
Definition: Sei p = p0 ... pm-1 das Muster und A das zugrunde liegende Alphabet.
Der charakteristische Vektor ch(p, a) eines Zeichens a ∈ A ist definiert durch
| ch(p, a)j = | |
|
für alle j ∈ {0, ..., m-1}. Der charakteristische Vektor ch(p, a) enthält also Einsen genau an den Positionen, an denen das Zeichen a im Muster p vorkommt.
Ähnlich wie beim Karp-Rabin-Algorithmus wird die Signatur eines Textfensters, hier also der Zustandsvektor z, in konstanter Zeit aus der Signatur des vorherigen Fensters berechnet. Der Zustandsvektor des neuen Textfensters ergibt sich durch eine Und-Verknüpfung des um eine Position geschobenen vorherigen Zustandsvektors mit dem charakteristischen Vektor des neu ins Textfenster gekommenen Zeichens.
|
|
|
|
Um den neuen Zustandsvektor z'' zu berechnen, wird der alte Zustandsvektor z zunächst um eine Position nach unten geschoben (z'). Denn wenn vorher das Präfix uj-1 mit einem Suffix des Textfensters übereingestimmt hat, so stimmt jetzt das Präfix uj mit einem Suffix des Fensters überein. Dies gilt jedoch nur, wenn das neue Textzeichen dasselbe Zeichen ist, das beim Übergang von uj-1 zu uj hinzukommt. Dieses Zeichen ist aber pj. Daher wird der verschobene Vektor mit dem charakteristischen Vektor ch des neuen Zeichens per Und verknüpft.
Der Shift-And-Algorithmus lässt sich auch als Simulation eines speziellen nichtdeterministischen endlichen Automaten, eines String-Matching-Automaten, auffassen.
Algorithmus
Ist die Länge des Musters höchstens 32, so lassen sich die Zustandsvektoren und die charakteristischen Vektoren durch 32-Bit-Integer-Zahlen repräsentieren.
In einem Vorlauf (preprocessing) werden zunächst die charakteristischen Vektoren für alle Zeichen des Musters gebildet. Es wird ein Array ch[alphabetsize] verwendet. Der Eintrag ch[a] enthält jeweils den als 32-Bit-Integerzahl repräsentierten Vektor ch(p, a), für alle a ∈ A.
{
int j, k=1;
char a;
for (j=0; j<m; j++)
{
a=p[j];
ch[a]|=k; // j-tes Bit in ch[a] setzen
lastbit=k;
k<<=1;
}
}
Der Wert von lastbit entspricht einem Bitvektor, bei dem Bit m-1 gesetzt ist.
In der Suchphase wird an jeder Textposition i der Zustandsvektor um eine Position geschoben, eine 1 nachgezogen (durch Oder-Verknüpfung mit 1) und die Und-Verknüpfung mit dem charakteristischen Vektor des Zeichens ti durchgeführt.
{
int i, z=0;
for (i=0; i<n; i++)
{
z=((z<<1) | 1) & ch[t[i]];
if ((z & lastbit)!=0) report(i-m+1);
}
}
Analyse
In der Suchphase führt der Algorithmus pro Textzeichen eine konstante Anzahl von Operationen aus. Die Komplexität der Suchphase liegt also in Θ(n).
Die Vorlaufphase hat eine Komplexität von Θ(m), da pro Zeichen des Musters eine konstante Anzahl von Operationen ausgeführt wird.
Approximative Suche
Um das Muster aa?b zu suchen, wobei das Fragezeichen für ein beliebiges Zeichen des Alphabets steht, wird in den charakteristischen Vektoren von allen Alphabetzeichen an der entsprechenden Position eine 1 eingetragen.
Da auch mehrere Fragezeichen auftreten können, wird zunächst der charakteristische Vektor q des Zeichens "?" gebildet. Dieser wird anschließend auf alle Alphabetzeichen übertragen.
{
int j, k=1, q=0;
char a;
for (j=0; j<m; j++)
{
a=p[j];
if (a!="?")
ch[a]|=k; // j-tes Bit in ch[a] setzen
else
q|=k; // j-tes Bit in q setzen
lastbit=k;
k<<=1;
}
// q auf alle Alphabetzeichen übertragen
for (a=0; a<alphabetsize; a++)
ch[a]|=q;
}
In ähnlicher Weise lässt sich der Fall behandeln, dass ein Zeichen aus einer bestimmten Menge stammen muss, z.B. ein Großbuchstabe oder eine Ziffer sein muss, oder dass an einer Position bestimmte Zeichen ausgeschlossen sein sollen. Der Vorlauf wird dadurch allerdings komplizierter.
Literatur
[BG 92] R. Baeza-Yates, G.H. Gonnet: A New Approach to Text Searching. Communications of the ACM 35, 10, 74-82 (1992)
[WM 92] S. Wu, U. Manber: Fast Text Searching Allowing Errors. Communications of the ACM 35, 10, 83-91 (1992)
[Lan 12] H.W. Lang: Algorithmen in Java. 3. Auflage, Oldenbourg (2012)
Den Shift-And-Algorithmus und weitere Textsuchverfahren (Knuth-Morris-Pratt, Boyer-Moore, ...) finden Sie auch in meinem Buch über Algorithmen.
Weitere
Themen des Buches: Sortieren, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.
Weiter mit: [up]
H.W. Lang mail@hwlang.de Impressum Datenschutz
Created: 08.04.2001 Updated: 05.02.2023
Diese Webseiten sind während meiner Lehrtätigkeit an der Hochschule Flensburg entstanden