Diskussion:Suffix-Array-Induced-Sorting

Der Pseudocode ist falsch

Letzter Kommentar: vor 6 Jahren1 Kommentar1 Person ist an der Diskussion beteiligt

Der Pseudocode im Artikel ist falsch. Wenn ein Zeichen gleich seinem rechten Nachbarn ist, dann hat es den gleichen Typ wie sein rechter Nachbar. Im Pseudocode wird der Type aber stets auf L gesetzt.

Auch gibt es eine Sache, die ich nicht verstehe. Wenn ich für den String

babcbcd

ein Suffix-Array konstruieren möchte, dann scheint der Algorithmus die Suffixe folgendermaßen zu klassifizieren:

01234567
babcbcd$
LSSLSSLS
 *  *  *

Daraus konstruiert der Algorithmus nach Sortierung der S*-Suffixes folgende vorbefüllte Buckets:

$ABBBCCD
SSLSSLSL
71 4

Wenn ich das richtig verstanden habe, dann werden die einmal einsortieren S*-Suffixes nie wieder umsortiert. Dann kann aber diese Sortierung nicht stimmen, da bcbcd$ kleiner ist als bcd$, aber nicht links von bcbcd$ einsortiert werden kann, da es sich um einen Suffix des Types S handelt. Habe ich da was falsch verstanden? Oder ist die Beschreibung des Verfahrens inkorrekt?

--FUZxxl^D|M|B 13:27, 22. Jan. 2019 (CET)Beantworten