Burrows-Wheeler変換(BWT)の圧縮率が高い理由

Burrows-Wheeler変換(BWT, Burrows-Wheeler Transform)されたテキストは同じ文字が並びやすい。従ってランレングス法等と併用することで大きな圧縮効果を得ることができる。
では、なぜBurrows-Wheeler変換によって同じ文字が並びやすいのか。これについて説明するよ。


BWTは与えられたテキストを1文字ずつずらして並べたものを考える。例えばmississippiなら

mississippi#
ississippi#m
ssissippi#mi
sissippi#mis
issippi#miss
ssippi#missi
sippi#missis
ippi#mississ
ppi#mississi
pi#mississip
i#mississipp
#mississippi

という感じ。ここでテキストの先頭と末尾はマーカ#を通じて繋がっていることを記憶にとどめておくように。
次にこれを辞書順でソートする。すると

#mississippi
i#mississipp
ippi#mississ
issippi#miss
ississippi#m
mississippi#
pi#mississip
ppi#mississi
sippi#missis
sissippi#mis
ssippi#missi
ssissippi#mi

となる。この行列の末尾の1文字づつをを並べたものがBWTされたテキスト。つまり

ipssm#pissii

なんとなく同じ文字が並んでいる。この例だとテキストが短いので実感がわかないかもしれないけど、小説1冊分のテキストとかでBWTすると同じ文字がずらっと並んで壮観だったりする。mississippiで納得できない諸氏は大きいテキストでBWTしてみて欲しい。
さて、これから何故同じ文字が並びやすいのかを考えていく。一度BWTされたテキストは忘れて、先程の辞書順に並べた行列に頭を戻す。これらは辞書順ソートされているから、先頭の文字が同じ行で固まっている。つまり

#mississippi

i#mississipp
ippi#mississ
issippi#miss
ississippi#m

mississippi#

pi#mississip
ppi#mississi

sippi#missis
sissippi#mis
ssippi#missi
ssissippi#mi

こういうこと。先頭が同じ文字の行のかたまりを便宜上クラスタと呼んでおく。よくみると末尾の文字(つまりBWTを構成する文字)で同じものが並んでいる部分は、同じクラスタになっているのがわかる(先頭がiのクラスタでは末尾にsが並びやすく、先頭がsのクラスタでは末尾にs、iが並びやすい)。
この現象は偶然ではなく、言語のある特性を生かしたものになっている。ある特性とは

同じフレーズの前に来る文字には偏りがある

というもの。どういう事かというとYorkという単語の前にはNewが高確率で来る(のでYorkの直前はwになりやすい)。とか、「小説」の前には「SF」や「ミステリ」、「恋愛」などが来やすい。といったもの。言語処理の経験がある方はNgramの逆の発想と考えると分かりやすいと思う。この逆Ngram的な発想は最高精度のスムージング手法といわれているKneser-Neyスムージングでも利用されている。
話をもどす。先程の行列の先頭がsのクラスタに着目してみる。

sippi#missis
sissippi#mis
ssippi#missi
ssissippi#mi

記事の冒頭でBWTでは先頭と末尾が繋がっているよ、という話をしたのを思い出して欲しい。これは何を意味するかというとクラスタの先頭文字の直前に来る文字というのは、それぞれの行の末尾に来ているということ。つまりある文字に先行する文字に偏りがあって同じ文字が来やすいから、末尾の文字に同じものが来やすい、ということ。
更に範囲を狭めるなら先頭がsiで始まる部分と、ssiで始まる部分を別クラスタとみなしてみると

sippi#missis
sissippi#mis

ssippi#missi
ssissippi#mi

それぞれのクラスタごとに末尾がs、末尾がiときれいにわかれている。こうした性質はテキストサイズが大きくなるほど顕著になる。
この性質を活かして同じ文字が並ぶようにしたのがBWT、というわけ。