Textsuche

Shift-And-Algorithmus

 aufwärts

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  =   geschweifte Klammer
1      falls  uj Suffix von w ist
0    sonst

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.

baabbab z
a 0
ab 1
abb 0
abba 0
abbab 1
abbaba 0
abbabab 0

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  genau dann wenn  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 Element A ist definiert durch

ch(p, a)j  =   geschweifte Klammer
1        falls  pj = a
0    sonst

für alle j Element {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.

 

baabbab z
a 0
ab 1
abb 0
abba 0
abbab 1
abbaba 0
abbabab 0
 
baabbaba z'
a 1
ab 0
abb 1
abba 0
abbab 0
abbaba 1
abbabab 0
  ch
  1
  0
  0
 und  1
  0
  1
  0
  z''
  1
  0
  0
= 0
  0
  1
  0

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, auf­fassen.

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 Element A.

 

void shiftAndPreprocess()
{
    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.

 

void shiftAndSearch()
{
    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 auf­treten können, wird zunächst der charakteristische Vektor q des Zeichens "?" gebildet. Dieser wird anschließend auf alle Alphabetzeichen übertragen.

 

void approximateShiftAndPreprocess()
{
    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(vertikaler Abstand) Themen des Buches: Sortieren, Graphenalgorithmen, Arithmetik, Codierung, Kryptografie, parallele Sortieralgorithmen.

[Weitere Informationen]

Buch  
[Web 1]http://www-igm.univ-mlv.fr/~lecroq/string/  

 

Weiter mit:   up

 

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

Hochschule Flensburg
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