Burrows Wheeler Transform (BWT)¶
Michael Burrows と David J. Wheeler によって考えられた可逆変換の一種．
素朴な方法¶
入力文字列を循環させた文字列から成る表を考える．
例）： \(S=banana\)
i 0 1 2 3 4 5 0 b a n a n a 1 a n a n a b 2 n a n a b a 3 a n a b a n 4 n a b a n a 5 a b a n a n
\(S\) を巡回させた文字列から成る表を辞書順にソート
i 0 1 2 3 4 5 0 a b a n a n 1 a n a b a n 2 a n a n a b 3 b a n a n a 4 n a b a n a 5 n a n a b a
この表の \(i=n\) 番目( \(n=|S|\) )の文字をつなげたものが BWTを行った文字列"\(nnbaaa\)"となる．
接尾辞配列を用いる方法¶
def BWT(S,d):
SA = []
BWT = ""
for k,v in sorted(d.items(), key = lambda x:x[1]):
SA.append(k)
for i in range(len(SA)):
print(S[SA[i]-1])
BWT += S[SA[i]-1]
return BWT
入力を変換¶
元のテキストとBWTを行ったテキストの圧縮率の違いを比較
・元テキスト = dummy
・圧縮テキスト = dummy
・圧縮率 = dummy
・BWTテキスト = dummy
・圧縮テキスト = dummy
・圧縮率 = dummy