続・BlockSorting(BWT)

BlockSorting - 西尾泰和のはてなダイアリー http://d.hatena.ne.jp/nishiohirokazu/20080218/1203322931

ちゃんと読んだらわかった。ようするにn番目の"X"はn番目の"X"につながると言うことか。どうやったらエレガントに書けるかな…。

すなおに各文字に連番をふったら素直に書けた。

# 復元
from collections import defaultdict
count = defaultdict(int)
def inc(c):
    count[c] += 1
    return count[c]

tails = [(c, inc(c)) for c in tails]
heads = list(sorted(tails))

cur = start
result = []

print start # => 1
print tails # => [('b', 1), ('a', 1), ('b', 2), ('a', 2)]
print heads # => [('a', 1), ('a', 2), ('b', 1), ('b', 2)]

for i in range(len(tails)):
    pair = heads[cur]
    result.append(pair[0])
    cur = tails.index(pair)

print "".join(result) # => abba

ふむふむ。これを思いついた人はいったい何を考えていて思いついたんだろうなぁ。すごいなぁ。

• • • • -

BlockSortingっていうか、まだ普通に全部ソートしてしまっているからBWTと呼ぶべきなのかな。

試しにこのソースをBWTしてみたらこうなった。確かに縮みやすそうだ。