ブロックソートのソースを表示

'''ブロックソート'''、'''ブロックソーティング'''、'''Burrows-Wheeler変換''' ('''Burrows-Wheeler Transform'''; '''BWT''') は、1994年にマイケル・バローズ (Michael Burrows) と[[デビッド・ホイーラー]] (David Wheeler) が開発した可逆変換の方式で、[[データ圧縮]]の前処理に応用される。

ブロックソート自体はデータの大きさを変えない。しかし、データを整列することでデータ中に出現するパターンを、いくつかのよく知られている手法で圧縮し易いものにできる。後処理として[[Move To Front]] (MTF)・[[連長圧縮]] (RLE)・[[エントロピー符号]]と組み合わせて、データを圧縮する。

実装は[[bzip2]]等。

Python言語による実装例が文献<ref>辻真吾、下平英寿：「Pythonで学ぶアルゴリズムとデータ構造」、講談社、ISBN 978-4-06-517803-4 (2019年11月26日) の 第10.3.2副節："ブロックソート".</ref>に出ている。

== 原理 ==
長さ ''n'' の[[データ]]を巡回シフトし、得られるすべての文字列を[[辞書順]]に[[ソート]]する。このようにしてできた ''n''×''n'' 行列の第 ''n'' 列を取り出したものが、BWT系列である。このBWT系列と、元の文字列がソートされた時行列の第何番目になったかを記憶しておくと、これから元の文字列を復号する事ができる。

=== 符号化の手順 ===
元の文字列:
 cacao

生成された[[巡回行列]]:

{| border="0" cellspacing="0" cellpadding="3" align="center"
|-bgcolor="#ccddee"
!   !! A !! B !! C !! D !! E
|-bgcolor="#eeddcc"
|bgcolor="#ccddee"| 1 || c || a || c || a || o
|-
|bgcolor="#ccddee"| 2 || o || c || a || c || a
|-
|bgcolor="#ccddee"| 3 || a || o || c || a || c
|-
|bgcolor="#ccddee"| 4 || c || a || o || c || a
|-
|bgcolor="#ccddee"| 5 || a || c || a || o || c
|}


辞書式順序で行同士を比較して、昇順となるように行を並べ替えて得られた行列<math>M</math>:

{| border="0" cellspacing="0" cellpadding="3" align="center"
|-bgcolor="#ccddee"
!   !! A !! B !! C !! D !! E
|-
|bgcolor="#ccddee"| 5 || a || c || a || o || c
|-
|bgcolor="#ccddee"| 3 || a || o || c || a || c
|-bgcolor="#eeddcc"
|bgcolor="#ccddee"| 1 || c || a || c || a || o
|-
|bgcolor="#ccddee"| 4 || c || a || o || c || a
|-
|bgcolor="#ccddee"| 2 || o || c || a || c || a
|}


得られたBWT系列:
 ccoaa, 3

これは行が昇順にソートされた後の行列の最終列(右端のE列)の要素を並べたものと、元の文字列が並べ替えた後に何番目の行に移ったかの記録である。

=== 復号の手順 ===
復号は非常に単純かつ機械的に行えるが、「なぜ」きちんと復号されるかを直観的に理解するのは少し難しい。そこで理解のため、元の巡回行列を復元する事を考える。

まず、BWT系列の文字列「ccoaa」をソートすると行列<math>M</math>のA列が得られる。
(A列とE列に含まれるアルファベットは同一であり, A列はソートされているため)

初期状態：（表1）
{| border="0" cellspacing="0" cellpadding="3" align="center"
|-bgcolor="#ccddee"
!   !! A !! B !! C !! D !! E
|-
|bgcolor="#ccddee"| 1 || a || ? || ? || ? || c
|-
|bgcolor="#ccddee"| 2 || a || ? || ? || ? || c
|-bgcolor="#eeddcc"
|bgcolor="#ccddee"| 3 || c || ? || ? || ? || o
|-
|bgcolor="#ccddee"| 4 || c || ? || ? || ? || a
|-
|bgcolor="#ccddee"| 5 || o || ? || ? || ? || a
|}

各行は元の文字列を巡回シフトしたものであるため、各行のE列、A列の文字は元の文字列で連続しているか、先頭と末尾の文字であったはずである。
この性質から、全列右シフトを行い、左端の列(ここではE列)をキーにソートすることでD列を得ることができる。このとき、左端の文字が同じ行については、他の列の文字によらず、元の表での順序を保ったままにする。すなわち、ソートは[[安定ソート]]でなければならない。

右シフトした状態:（表2）
{| border="0" cellspacing="0" cellpadding="3" align="center"
|-bgcolor="#ccddee"
!   !! E !! A !! B !! C !! D
|-
|bgcolor="#ccddee"| 1 || c || a || ? || ? || ?
|-
|bgcolor="#ccddee"| 2 || c || a || ? || ? || ?
|-bgcolor="#eeddcc"
|bgcolor="#ccddee"| 3 || o || c || ? || ? || ?
|-
|bgcolor="#ccddee"| 4 || a || c || ? || ? || ?
|-
|bgcolor="#ccddee"| 5 || a || o || ? || ? || ?
|}

ソート後の状態:（表3）
{| border="0" cellspacing="0" cellpadding="3"  align="center"
|-bgcolor="#ccddee"
!   !! E !! A !! B !! C !! D
|-
|bgcolor="#ccddee"| 4 || a || c || ? || ? || ?
|-
|bgcolor="#ccddee"| 5 || a || o || ? || ? || ?
|-
|bgcolor="#ccddee"| 1 || c || a || ? || ? || ?
|-
|bgcolor="#ccddee"| 2 || c || a || ? || ? || ?
|-bgcolor="#eeddcc"
|bgcolor="#ccddee"| 3 || o || c || ? || ? || ?
|}

このときBWT系列の性質から、右端となったD列には表1の右端と同様にBWT系列の文字列「ccoaa」が順番に入ることになる。

右端を埋めた状態：（表4）
{| border="0" cellspacing="0" cellpadding="3"  align="center"
|-bgcolor="#ccddee"
!   !! E !! A !! B !! C !! D
|-
|bgcolor="#ccddee"| 4 || a || c || ? || ? || c
|-
|bgcolor="#ccddee"| 5 || a || o || ? || ? || c
|-
|bgcolor="#ccddee"| 1 || c || a || ? || ? || o
|-
|bgcolor="#ccddee"| 2 || c || a || ? || ? || a
|-bgcolor="#eeddcc"
|bgcolor="#ccddee"| 3 || o || c || ? || ? || a
|}

この操作を繰り返し行い順次C、Bと求めていくことで、最終的に行列<math>M</math>を得ることができる。

==== 復号の手順の効率化 ====
しかし手順のたびにソートを行うのは非効率である。

このため、表2から表3への各行の移動が毎回固定的に一対一対応することに着目し、その対応を追うことで復元を行うのが一般的である。

表2から表3への各行の移動の対応表：
{| border="0" cellspacing="0" cellpadding="3"  align="center" style="text-align:center"
|-bgcolor="#ccddee"
! ソート前 !! ソート後
|-
|bgcolor="#ccddee"| 1 || 4
|-
|bgcolor="#ccddee"| 2 || 5
|-
|bgcolor="#ccddee"| 3 || 1
|-
|bgcolor="#ccddee"| 4 || 2
|-
|bgcolor="#ccddee"| 5 || 3
|}

これを元の文字列であった3から追いかけると、3→1,4,2,5,3となる。

この位置の文字をBWT系列の文字列「ccoaa」から順番に取り出すと「cacao」となり、元の文字列が得られる。

== アルゴリズム ==
ブロックソートをするには、巡回した文字列をソートする必要があるが、通常のソート方法(例えば[[クイックソート]]など)を単純に適用すると文字列の長さ <math>n</math> に対して <math>\mathrm{O}(n^2\log n)</math> の時間が必要になってしまう。そこで通常は巡回文字列であることを利用して、より効率的なソートを行う。

このためのアルゴリズムは複数提案されており、 <math>\mathrm{O}(n)</math> 、 <math>\mathrm{O}(n\log\log n)</math> 、 <math>\mathrm{O}(n\log n)</math> のアルゴリズムが知られているが、実用上は, 自然言語などのような一般的な入力データに対しては <math>\mathrm{O}(n\log n)</math> のものが速度やメモリ効率の点で最適である。

bzip2では <math>\mathrm{O}(n\log\log n)</math> と <math>\mathrm{O}(n\log n)</math> のアルゴリズムを入力に応じて最適なものに切り替えて使用している。またブロックサイズは100kバイトから900kバイトまで、<code>-1</code> ～ <code>-9</code> オプションで選択でき、デフォルトは900kバイトである。

== 圧縮のための後処理 ==
ブロックソートしただけでは、データは「圧縮しやすい」ものに変換されただけあって、サイズはほとんど変わらない。そのため実際に圧縮に応用するには後処理が必要となる。実用上はMTF (Move-To-Front) 法、RLE、エントロピー符号が用いられる。

BWT系列は、同じ記号が連続しやすい性質を持つため、MTF法を用いると小さい[[整数]]の値が大きく偏る。そのため、RLEとエントロピー符号を適用して圧縮を行う。

== 脚注 ==
{{脚注ヘルプ}}
{{Reflist}}

== 外部リンク ==
* [http://www.hpl.hp.com/techreports/Compaq-DEC/SRC-RR-124.html HP Labs のテクニカルレポートアーカイブ上にある論文]
* [http://www.nct9.ne.jp/m_hiroi/light/pyalgo48.html Algorithms with Python:データ圧縮 (後編)ブロックソート (BlockSorting)(M.Hiroi's Home Page)]


{{データ圧縮}}
{{DEFAULTSORT:ふろつくそと}}
[[Category:ソート]]
[[Category:データ圧縮]]