Diskussion:Baeza-Yates-Gonnet-Algorithmus
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] = | 11111 | Beliebig 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:
| Text | a | b | a | b | c | a | b | a | a | c |
|---|---|---|---|---|---|---|---|---|---|---|
| T[ ] | 10010 | 11101 | 10010 | 11101 | 01111 | 10010 | 11101 | 10010 | 10010 | 01111 |
| shift | 11110 | 11100 | 11010 | 10100 | 11010 | 11110 | 11100 | 11010 | 10100 | 01100 |
| or | 11110 | 11101 | 11010 | 11101 | 11111 | 11110 | 11101 | 11010 | 10110 | 01111 |
Was meint ihr? Michael