Diskussion:Baeza-Yates-Gonnet-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Hier eine meiner Meinung nach einfachere Darstellung:

Pattern: "abac" Text: "ababcabaab"

Zuerst wird das Pattern vorprozessiert und für jedes Symbol, das im Pattern vorkommt T[n] bestimmt. Dabei steht an der Stelle wo das Symbol im Pattern vorkommt eine 0 und sonst eine 1 (Achtung: von rechts gelesen). Alle übrigen Zeichen (die nicht im Pattern vorkommen) wird T[n] mit Einsen gefüllt.

T[a] = 10010
T[b] = 11101
T[c] = 01111
T[x] = 11111Beliebig anderes Zeichen

Es wird mit einem Statusvektor der mit Einsen gefüllt ist gestartet. Nun wird erst geshiftet und dann ein bitweises Oder mit dem aktuellen Symbol des Textes ausgeführt. Hier die tabellarische Darstellung:

1. Weiterhin werden die charakteristischen Vektoren für alle möglicherweise im Text vorkommenden Zeichen benötigt:

Textababcabaac
T[ ]10010111011001011101011111001011101100101001001111
shift11110111001101010100110101111011100110101010001100
or11110111011101011101111111111011101110101011001111

Was meint ihr? Michael

Beginne eine Diskussion über den Artikel „Baeza-Yates-Gonnet-Algorithmus“

Eine Diskussion beginnen