BurrowsWheelerTransformの逆変換

逆変換する場合、ソートされてるから逆もソートされてるんだよっていう部分は
一旦は納得したもののそれでもなんとなくしか理解できてなかったんだけど、
ようやっと意味がわかった。のでメモ。

"数字文字列"
ってフォーマットだけど文字列は単に並び替えてるだけなのですべての要素は出現している。
prefix文字列はこの文字列をソートした結果なのでBWTしたsuffix文字列をソートしても同様の結果を得られる。

よってソート後のsuffixとprefixの文字列に関しては上記の方法で得ることができた。
suffixとprefixがわかれば、文字間の関係性がわかるのでそれを元に復元することが可能。

おそらく、復元した文字列ブロックは元の文字列ブロックとは同じにならない気がする。
完全に戻せるのは番号がわかっている元の文字列だけ。のはず？

http://golf.shinh.org/p.rb?Reverse+BWT
ご丁寧に逆変換のgolfもあるので挑戦しようと思います。
最近のライバルはplanque氏。
Luaでの参加者が少ないのが切ないです。みんなRubyかよ！