ブロックソート
出典: フリー百科事典『ウィキペディア（Wikipedia）』
ブロックソート、ブロックソーティング、Burrows-Wheeler変換 (Burrows-Wheeler Transform; BWT) とは、1994年にMichael Burrowsとデビッド・ホイーラー(David Wheeler)によって開発された可逆変換の一種で、主にデータ圧縮の前処理として用いられる。
単にブロックソートを施しただけではデータの大きさはほぼ不変であるが、データが整列されて圧縮され易くなる。 通常はMove To Front (MTF)、連長圧縮 (RLE)、エントロピー符号との組み合わせてデータ圧縮に応用される。
ブロックソートを用いた圧縮プログラムの実装としてはUNIXで主に用いられるbzip2がある。
目次 |
[編集] 原理
長さ n のデータを巡回シフトし、得られるすべての文字列を辞書順にソートする。このようにしてできた n×n 行列の第 n 列を取り出したものが、BWT系列である。このBWT系列と、元の文字列がソートされた時行列の第何番目になったかを記憶しておくと、これから元の文字列を復号する事ができる。
[編集] 符号化の手順
元の文字列:
cacao
生成された巡回行列:
| A | B | C | D | E | |
|---|---|---|---|---|---|
| 1 | c | a | c | a | o |
| 2 | o | c | a | c | a |
| 3 | a | o | c | a | c |
| 4 | c | a | o | c | a |
| 5 | a | c | a | o | c |
ソートされた行列M:
| A | B | C | D | E | |
|---|---|---|---|---|---|
| 5 | a | c | a | o | c |
| 3 | a | o | c | a | c |
| 1 | c | a | c | a | o |
| 4 | c | a | o | c | a |
| 2 | o | c | a | c | a |
得られたBWT系列:
ccoaa, 3
(ソートされた行列の右の列を縦に取ったものと,元の文字列がソートした後に何番目の行にあったかを覚える)
[編集] 復号の手順
復号は非常に単純かつ機械的に行えるが、「なぜ」きちんと復号されるかを直観的に理解するのは少し難しい。そこで理解のため、元の巡回行列を復元する事を考える。
まず、BWT系列の文字列「ccoaa」をソートすると行列MのA列が得られる。 (A列とE列に含まれるアルファベットは同一であり, A列はソートされているため)
| A | B | C | D | E | |
|---|---|---|---|---|---|
| 1 | a | ? | ? | ? | c |
| 2 | a | ? | ? | ? | c |
| 3 | c | ? | ? | ? | o |
| 4 | c | ? | ? | ? | a |
| 5 | o | ? | ? | ? | a |
各行は元の文字列を巡回シフトしたものであるため、各行のE列、A列の文字は元の文字列で連続しているか、先頭と末尾の文字であったはずである。 この性質から、全列右シフトを行い、ソートを行うことでB列を得ることができる。
右シフトした状態:
| A | B | C | D | E | |
|---|---|---|---|---|---|
| 1 | c | a | ? | ? | ? |
| 2 | c | a | ? | ? | ? |
| 3 | o | c | ? | ? | ? |
| 4 | a | c | ? | ? | ? |
| 5 | a | o | ? | ? | ? |
ソート後の状態:
| A | B | C | D | E | |
|---|---|---|---|---|---|
| 1 | a | c | ? | ? | ? |
| 2 | a | o | ? | ? | ? |
| 3 | c | a | ? | ? | ? |
| 4 | c | a | ? | ? | ? |
| 5 | o | c | ? | ? | ? |
この操作を繰り返し行うことで、最終的に行列Mを得ることができる。しかし、手順のたびにソートを行うのは非効率であるため、実際には連続する文字の対応表を作り、それを元に再現を行う。
[編集] アルゴリズム
ブロックソートをするには、巡回した文字列をソートする必要があるが、通常のソート方法(例えばクイックソートなど)を単純に適用すると文字列の長さ n に対して O(n2logn) の時間が必要になってしまう。そこで通常は巡回文字列であることを利用して、より効率的なソートを行う。
このためのアルゴリズムは複数提案されており、 O(n) 、 O(nloglogn) 、 O(nlogn) のアルゴリズムが知られているが、実用上は, 自然言語などのような一般的な入力データに対しては O(nlogn) のものが速度やメモリ効率の点で最適である。
bzip2では O(nloglogn) と O(nlogn) のアルゴリズムを入力に応じて最適なものに切り替えて使用している。また、入力がある程度以上大きい場合にはブロックソートにかなりの時間、メモリが必要になるので、一定サイズのブロック（通常は900 KB）に分割して圧縮を行う。
[編集] 圧縮のための後処理
ブロックソートしただけでは、データは「圧縮しやすく」なるだけでサイズはほぼ変化しない。実際に圧縮に応用するには後処理が必要となる。実用上はMTF (Move-To-Front) 法、RLE、エントロピー符号が用いられる。
BWT系列は、同じ記号が連続しやすい性質を持つため、MTFを用いると小さい整数の値が大きく偏る。そのため、RLEとエントロピー符号を適用することで、圧縮が行える。
