BWT と PPM

Burrows Wheeler Transform (BWT, Block-sorting) と Prediction by partial matching (PPM) は本質的に同じ事をやっている、というお話です。

先日 Managing Gigabytes を読んでいたところ、P.69 で "block sorting is very closely related to the PPM* method, which is a variant of PPM that allows arbitrary-length contexts." という記述があり、どうにも気になったので調べてみました。

サマリとしては、BWT と PPM の一種である PPM* はいずれも文脈から次の1文字を一意に決定するという概念で見ると本質的に同じことをやっていると言える、というところです。

BWT のあらまし

BWT に関して詳しくは id:naoya:20081016:1224173077 も参照してください。以下、この記事でも扱った abracadabra$ ($ は記号列の最後を表す) を変換する過程を見ます。abracadabra$ の先頭の文字を末尾に持って行って bracadabra$a、という処理を繰り返すと

abracadabra$
bracadabra$a
racadabra$ab
acadabra$abr
cadabra$abra
adabra$abrac
dabra$abraca
abra$abracad
bra$abracada
ra$abracadab
a$abracadabr
$abracadabra

というブロックを構成します。これを辞書式順序でソートすると

$abracadabr a
a$abracadab r
abra$abraca d
abracadabra $
acadabra$ab r
adabra$abra c
bra$abracad a
bracadabra$ a
cadabra$abr a
dabra$abrac a
ra$abracada b
racadabra$a b

となります。ここから各行の末尾から1文字ずつ取ったものが、BWT の出力です。(末尾が分かりやすいように切り離して記述してみました。) abracadabra$ → ard$rcaaaabb です。この BWT の出力では同じ文字が連続して出現しやすくなっています。このとき BWT 後の記号列をこのまま zero-order でモデリングしても、BWT は元々の記号列の位置を変更しただけなので、出現確率は変わらず圧縮率には寄与しません。しかし MTF (Move to front, 先頭移動法) などを行うと、同じ文字が連続して出現しやすいという所から記号(MTF で変換した後の数値)の確率分布が変化し、偏りが出るので圧縮率が上昇します。(MTF については id:naoya:20081019:1224427368 も参照してください)

BWT 後の記号列に同じ文字が連続して出現するのはなぜか

BWT 後の記号列に同じ文字が連続して出現しやすい、というところが圧縮の観点から重要なのが分かるのですが、なぜ同じ文字が連続して出現しやすくなるのかが気になります。結論としては、BWT では文脈 (contexts) を考慮した変形が行われているから、というところです。

BWT の最後の過程で、ブロックから末尾の文字を切り離していますが、この末尾の文字は、それ以外の記号列から見たとき、オリジナルにおいて1文字前に相当します。例えばブロック中の

bracadabra$ a

は、末尾が a ですが、この a はもともと abracadabra$ の先頭の a で、bracadabra$ から見ると1文字前に相当します。

ここで BWT の処理中のソーティングの処理を考えてみます。ソートをすると、当然ですが、同じような記号列が同じ場所に集まってきます。つまり、同じ文脈を揃えていることになります。ソート後のブロックの

bra$abracad a
bracadabra$ a

を見るといずれも bra で始まる文脈です。そしてこの末尾の a は「1文字前」だったのですから、結局 BWT は「1文字前の文字を、文脈でソートしている」ということになります。1文字前にせよ、1文字後にせよ、同じ文脈に続く記号は特定の文字になりやすい (例えば appl ときたら次の文字は apple と想像しますよね。pple と来たら1文字前は apple と想像しますね) ので、文脈でソートした BWT 後のテキストは、同じ文字が連続して出現しやすいのです。

BWT は文脈を考慮した変換である、というのがここまでで分かりました。

PPM と BWT

PPM は、記号列を先頭から見ていく間、次の文字の出現確率を直前の k 文字による文脈から推定するアルゴリズムです。次の文字を文脈から推定する、というところで既に BWT との繋がりが何となく分かります。PPM のポイントは単なる有限文脈モデルとは異なり、文脈の k 文字を固定せずに切り替えるところにあります。最初に 5 文字の文脈から推定して、推定できなかったら 4 文字、3 文字 ･･･ と切り替えます。

話を BWT に戻します。abracadabra$ のブロックをソートする場合、ブロックの各行を辞書式順序でソートするのですが、例えば bra$abracada と bracadabra$a の辞書式での大小関係は全記号を見なくても、bra$ まで見れば決まります。それぞれの行のどこまで見れば順序が決まるかを書き出してみます。

文脈   L
________
$      a
a$     r
abra$  d
abrac  $
ac     r
ad     c
bra$   a
brac   a
c      a
d      a
ra$    b
rac    b

となります。先にも述べた通り、末尾の文字 (上記で L) は各行を文脈としたときその1文字前です。よって上記は、各 L の文字が決定されるための文脈を表しています。例えば文脈 ac に対して 末尾が r というのは、abracadabra$ という記号列では、ac という文脈の1文字前は必ず r である、ということを示しています。そして、L を決めるための文脈の文字数がそれぞれ異なっているというところにも着目します。PPM は次の1文字を推定するのに、文脈の長さを切り替えながら推定していくのでした。BWT も、ソート処理の際に、「1文字前の文字を決定するのに必要な文字数分の文脈を見る」ということを暗黙的に行っています。ここが、BWT と PPM の共通点です。

PPM には PPMA や PPMC など、エスケープ確率の扱いの違いや文脈の扱いの違いによる幾つかの変種があります。例えば PPMC では 5 ~ 6 order の文脈からはじめて、記号を決定できるまで 4, 3, 2 と文脈を減らしていくのが一般的です。PPM は原理的には全文脈を見たとき圧縮率が最適になるそうですが、PPMC では実装上の都合 (エスケープ記号を出力する必要がある) と計算量的な観点から最大 5 ~ 6 次の order ぐらいが最良です。

計算時間は妥協しながら原理的な最善を目指すために過去の全文脈から、次の文字を一意に決定できる最短の文脈 (deterministic-context) を利用しようとするのが PPM* です。次の1文字を一意に決定する最短の文脈 ･･･ そうですね、BWT がやっていることと全く同じです。結局、本質的に PPM* と BWT が同じ事をやっている、というのが分かります。ただし同じことをやっているものの、BWT はソートする = 入力を最後までみいて PPM* は都度判定ですから、前者は静的、後者は適応型ということになります。

なお、ここまでの説明ですと PPM* は1文字後、BWT は1文字前を文脈から決定していますが、BWT は文脈を逆から見てソートすることもできるので、その違いはあまり重要ではありません。

急いでまとめたので間違いもあるかもしれませんが、自分の理解ではこんなところです。BWT でなぜより高い圧縮率を達成できるのか、それは文脈ベースの手法と本質的に同じ事をやっているから、という理論的な根拠の理解が明確になって良かったです。BWT と Suffix Array の繋がり、圧縮全文索引への応用、PPM と同じ･･･など、BWT は本当に面白いアルゴリズムです。

The Burrows-Wheeler Transform:: Data Compression, Suffix Arrays, and Pattern Matching

The Burrows-Wheeler Transform:: Data Compression, Suffix Arrays, and Pattern Matching

参考文献

[1] には PPM や BWT の解説があります。[2] は PPM* の論文です。論文の中で、PPM* と BWT の共通点について解説がありました。PPM* で利用する Context trie と BWT の文脈が一対一で対応している、などの面白い話もあります。

[3] にも BWT の詳しい解説があります。また MTF を施したとき確率分布がどのように変化するのかなど、具体例があるので分かりやすかったです。聖書を文脈でまとめると、4,047,392 文字に 644 回登場する "the hea" という文脈の後に続く文字は、たったの 6 文字に絞られて、更にそれを MTF で符号化すると 1 が 294 回、2 が 134 回と非常に偏った確率になる、などの例があります。

[4] は BWT に関する話題を包括的に扱っている書籍で、PPM* と BWT の関係についての言及があります。