So sortieren Sie Array -Suffixe in der Blocksortierung

Question

Ich lese den Block -Sortieralgorithmus aus den Höhlen- und Wheeler -Papier. Dies ist ein Schritt des Algorithmus:

Angenommen s = Abracadabra

Initialisieren Sie ein Array w von n Wörter w [0, ..., n - 1], so dass W [i] die Zeichen s '[i, ..., i + k - 1] enthält, so dass Ganzzahl vergleiche Die Wörter stimmen mit lexikografischen Vergleiche über die K-Charakter-Saiten überein. Das Verpacken von Zeichen in Wörter hat zwei Vorteile: Es ermöglicht es, zwei Präfixe gleichzeitig mit K -Bytes mit ausgerichteten Speicherzugriffen zu vergleichen, und es ermöglicht es, viele langsame Fälle zu beseitigen

(Notiz: S' ist das Original S mit k EOF Angehörte Zeichen, K ist die Anzahl der Zeichen, die in ein maschinelles Wort passen (ich bin in einer 32 -Bit -Maschine, also k=4)

EOF = '$'

Korrigieren Sie mich, wenn ich falsch liege:

S'= abracadabra$$$$  
W= abra brac raca acad cada adab dabr abra bra$ ra$$ a$$$

Dann sagt der Algorithmus, dass Sie das Suffix -Array von sortieren müssen S (Namen v), von Indexierung in das Array W.

Ich verstehe nicht vollständig, wie Sie Suffixe sortieren können, indem Sie in Indizierung in die Indexierung W. Zum Beispiel: Nehmen Sie angenommen, Sie erhalten zwei Suffixe. i und j, und du musst sie vergleichen. Da Sie indexieren in W, Sie überprüfen zu dieser Zeit 4 Zeichen.
Angenommen, sie haben beide die gleichen ersten 4 Zeichen. Dann müssten Sie für jedes Suffix ihre nächsten 4 Zeichen überprüfen, und Sie tun dies, indem Sie aus der 4. Position jedes Suffix in Zugriff aufnehmen W. Ist das richtig? Beschleunigt dieses "Verpacken von Charakteren in Wörter" die Dinge wirklich?

Answer 1

Die Art und Weise, wie Sie es in der Frage beschreiben, ist völlig korrekt. Und ja, es beschleunigt die Dinge, weil es, wie Sie sagten, vier Zeichen gleichzeitig vergleicht.

Es gibt jedoch zwei Bemerkungen zu machen:

1. Wenn Sie Suffixe i und j vergleichen, wie in Ihrem Beispiel, vergleichen Sie Einträge mit W [i] und W [j] in der Tat. Das Ergebnis davon ist das gleiche, als hätten Sie das Vierfach der Zeichen s [i..i+3] und s [j..j+3] lexikographisch verglichen, sodass Sie die Rechenzeit gespeichert haben, die drei Charaktervergleiche entspricht. Und ja, wenn das Ergebnis angibt, dass die beiden Vierrupel identisch sind, müssen Sie weiterhin W [i+1] und W [j+1] vergleichen. jedoch: Du machst es nicht sofort. Die Art und Weise, wie ihr Algorithmus funktioniert, ist die einer Radix -Art. Das heißt, Sie legen die Suffixe direkt nach dem ersten Vergleich (möglicherweise beide in denselben Eimer) in Eimer und sortieren dann die Eimer rekursiv.
2. Der Algorithmus, der im Originalpapier von Burrows and Wheeler beschrieben wird (aus dem Sie zitieren; es gibt eine Kopie hier Zum Beispiel), was aus dem Jahr 1994 stammt, ist nicht der optimale Suffix -Array -Konstruktionsalgorithmus. Zunächst wurden 2003 mehrere O (N) direkte Baumethoden entdeckt; Zweitens wurden seitdem viele weitere Verbesserungen der Umsetzung vorgenommen. Der Kern des Papiers von 1994 ist die Idee, die Burrows-Wheeler-Transformation als Grundlage für die Stringkomprimierung zu verwenden, nicht die genaue Art und Weise, wie die Transformation selbst erzeugt wird.

Answer 2

Das Array V ist kein Suffix -Array, sondern ein Array von Indizes in W. Sobald die Sortierung abgeschlossen ist, sollte V Indizes in W halten, so dass wenn

V[i] <= V[j]

dann

 W[V[i]] <= W[V[j]].

Ich hoffe, ich habe das richtig gesagt :) Es ist kein Problem, und jede Bestellung ist in Ordnung. Der Punkt ist, dass Sie, wenn Sie die umgekehrte Transformation anwenden, W wiederherstellen müssen, um die ursprüngliche Zeichenfolge wiederherzustellen, und identische Elemente von W werden kein Problem damit verursachen.