BurrowsWheelerTransform

http://golf.shinh.org/p.rb?BWT
アナゴル鯖が復活したのでいろいろとLuaでチャレンジしてるんですが、新しく登録されたBWTとかいうやつの変換法則がわからなかったので調べた。

サンプルアウトプットを見る限りだとなんか圧縮しやすそうな変換に見えるけど
調べてみたらまさに圧縮/展開に用いる変換方法らしい。
割りかし近代的な手法なんだって。

http://www.01-tec.com/document/basic_compression.html#BlockSorting

1文字ずつシフトさせたそれぞれのデータ列のsuffixをソートしたものに元のデータがソートによって何番目に移動するかを付加すればいいぽい。

でもgolfで短く記述するのはめんどくさいかもしれない。
まぁ時間あったらやってみよう。

家で考えてたけど、これでもどうやってもどすのかよくわからんのだけど。
ソートしちゃったら並び順の情報損失しない？

と思ったらid:mokeheheさんがソートはローテート後の先頭の文字で行うから大丈夫らしい。
ずっとSuffixArrayをソートするのかと思ってたので納得。

BWTはできました。ローテートした後に同じ並びになるような文字列だとidがずれちゃうので
nがnilの時だけ更新するように変更してみました。191バイト。

for l in io.lines()do 
t=l;p={}e=#l 
n=nil 
for i=1,e do 
p[i]=l;l=l:sub(2,e)..l:sub(1,1)end 
table.sort(p)s=""
for i=1,e do if(t==p[i])then n=n or i-1 end 
s=s..p[i]:sub(e,e)end 
print(n.." "..s)
end

あんまり横に長いとはてなのレイアウトが崩れるので改行を入れてみた。

無駄が多いので省略してみた。最後は逆にイテレーションすることで特別な例外を除外してみました（golf用）。
実際に使う時に、ローテート後の文字列で同じものがあった場合は多分重複チェックとかしなくても多分大丈夫だと思います。

for l in io.lines()do 
p={}
for i=1,#l do p[i]=l;l=l:sub(2)..l:sub(1,1)end 
table.sort(p)
s=""
for i=#l,1,-1 do 
p[p[i]]=i-1 
s=p[i]:sub(-1)..s 
end 
print(p[l].." "..s)
end