Burrows Wheeler Transform (BWT)
A reversible transformation proposed by Michael Burrows and David J. Wheeler
Naive algorithm
Consider a table filled by all rotations of a string
Example: \(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
Sort all rotations of \(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\)”となる．
接尾辞配列を用いる方法
入力を変換
元のテキストとBWTを行ったテキストの圧縮率の違いを比較
・元テキスト = dummy
・圧縮テキスト = dummy
・圧縮率 = dummy
・BWTテキスト = dummy
・圧縮テキスト = dummy
・圧縮率 = dummy