Diskussion:Suffix-Array-Induced-Sorting
Der Pseudocode ist falsch[Quelltext bearbeiten]
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?