Textsuche

Shift-And-Algorithmus

 aufwärts

Idee

Der Shift-And-Algorithmus [WM 92] bildet zu jedem Textfenster einen Zustands­vektor z, der angibt, an welchen Positionen des Fensters ein mögliches Vorkommen des Musters beginnt. Der Zustandsvektor lässt sich aus dem Zustands­vektor des vorher­gehenden 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 beispiels­weise 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 Zustands­vektor z = z0, ..., zm-1 eines Textfensters w folgender­maß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 über­einstimmt, enthält der Zustands­vektor 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 Zustands­vektor 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 über­einstimmt. 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 weiter­geschoben, so verlässt ein Zeichen das Fenster und ein neues kommt hinzu. Die dazwischen liegenden Zeichen bleiben gleich. Dies wird ausgenutzt, um den Zustands­vektor des neuen Textfensters in konstanter Zeit aus dem vorherigen Zustands­vektor 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 Zustands­vektor z, in konstanter Zeit aus der Signatur des vorherigen Fensters berechnet. Der Zustands­vektor des neuen Textfensters ergibt sich durch eine Und-Verknüpfung des um eine Position geschobenen vorherigen Zustands­vektors 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 Zustands­vektor z'' zu berechnen, wird der alte Zustands­vektor z zunächst um eine Position nach unten geschoben (z'). Denn wenn vorher das Präfix uj-1 mit einem Suffix des Textfensters überein­gestimmt 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 nicht­deterministischen endlichen Automaten, eines String-Matching-Automaten, auf­fassen.

Algorithmus

Ist die Länge des Musters höchstens 32, so lassen sich die Zustands­vektoren 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 Zustands­vektor 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 Alphabet­zeichen an der ent­sprechenden 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 Alphabet­zeichen ü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 aus­geschlossen 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   ©   Created: 08.04.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