Wird die Radix -Sortierung für die Suffix -Sortierung verwendet?

Question

Ich versuche, Blocksortierung zu implementieren. Dies ist aus den Höhlen Wheeler Papier.

(Vor diesem Schritt erstellen Sie ein V -Suffix -Array von S)

Q4. [Radix -Sortierung
Sortieren Sie die Elemente von V unter Verwendung der ersten beiden Zeichen jedes Suffix als Sort -Schlüssel. Dies kann mit der Radix -Sortierung effizient erfolgen.

Ich verstehe also, dass Sie die Suffixe mit Radix -Sortierung sortieren.
Wie soll das das Array V aktualisieren? Erst nachdem die Radix -Sortierung fertiggestellt war, kann ich die sortierte Position eines Suffix kennen. Angenommen, das 4. Suffix ist das erste nach der Sortierung. Also v [0] = i. In diesem Fall wissen wir (weil ich Ihnen gesagt habe), dass ich = 4. Aber woher weiß der Algorithmus das, da wir ihre Position nicht im Auge behalten? Sollte ich eine Klasse erstellen, die sowohl das Suffix als auch seine Suffixnummer enthält?

Answer 1

Nach einer kurzen Lektüre; Ich denke, Burrows-Wheeler hat einen Fehler und soll sagen, die Elemente von W mit dem Array V zu sortieren, um die endgültigen Orte der Elemente von W. IE zu verfolgen und abzubilden. So dass W unverändert und V eine sortierte Liste von Indizes enthält.

Das Papier scheint V als eine Reihe von Zeigern auf Elemente in W von diesem Zeitpunkt an zu behandeln.

Kasse http://michael.dipperstein.com/bwt/ Es gibt eine großartige Beschreibung sowie Quellcode für den Algorithmus unten auf der Seite.