bzip2を読む ブロックソート1

こんにちは、junkawaです。

本記事では、bzip2のブロックソートアルゴリズムについて概要を紹介します。

ブロックソートは、入力データを圧縮しやすい形 (出現パターンに偏りがある形) に変換するアルゴリズムです。

ブロックソートは別名、Burrows–Wheeler transform、BWTと呼ばれます。

高速文字列解析の世界——データ圧縮・全文検索・テキストマイニング (確率と情報の科学) 岡野原 大輔 著 より引用

上記の図では、英文をブロックソートした結果、同じ文字が連続して出現しやすい形になっているのが分かります。この理由については後ほど紹介します。

このように、ブロックソートでは入力データを並び替え、出現順序に偏りが出るように変換します。

また、後で行うMoveToFront(MTF)変換と組み合わせることで、さらに情報に偏りを持たせ、最終的にランレングス符号化(Run Length Encoding / RLE)・ハフマン符号化でデータを圧縮します。

前の記事

bzip2を読む はじめに

では、ブロックソートアルゴリズムについて紹介します。

ブロックソートアルゴリズムの概略

1. 入力データから、nBlock x nBlock の巡回行列を生成する

入力データを abracadabra、nBlock=11 とした例を図示します。

これを左詰めにした巡回行列を図示します。

もう少し詳しく説明します。

入力データ配列 block[0..nBlock-1] (nBlockは900,000) を行列の1行目とします。 

「厳密には前段のランレングス符号化により、nBlockは900,000より小さくなっています。」
これは誤りでした。前段のランレングス符号化後、nBlockが900,000になるデータを1ブロックとしています。(2018.5.11 追記)

次に、1バイト目から始まり、巡回して0バイト目で終わる配列block[1..nBlock-1,0] を2行目とします。

同様に、2バイト目から始まり、巡回して1バイト目で終わる配列 block[2..nBlock-1,0,1] を3行目とし、

nBlock-1目から始まり、巡回してnBlock-2目で終わる配列block[nBlock-1,0..nBlock-2]をnBlock行目とします。

これで、横nBlock、縦nBlockのnBlock x nBlockの行列ができます。

巡回行列の縦列を見ると、どの列も、入力データを並べ替えたものになっているのがわかります。

例) 一番左の列は、上から見ると、a,b,r,a,c,a,d,a,b,r,a となっている

また、例ではアルファベットにしていますが、実際は0〜255の値です。

2. 辞書順に行をソート

この処理がブロックソートの中で一番複雑で、時間のかかる部分です。詳しくは後ほど紹介します。

3. ソート後の行列で、最後の「列」と元の入力データのindexが、ブロックソートで出力する値

BWT変換の出力データは、下記となります。

変換後データ：rdarcaaaabb (行列の最後の列)
BWT逆変換に必要な情報：2 (オリジナルの文字列abracadabraの、ソート後のインデックス番号)

行列の、最後の「列」は
・入力データを並び替えたもの
・出現順序に偏りがある

このようにBWTを適用した後の文字列は同じ文字が連続して出現しやすくなる。なぜこのような現象が起こるかというと、まずBWTは各文字を後続する接尾辞の辞書式順序をキーとしてソートする。このとき、後続している文字列が似ている場合、同じ文字が直前に出現しやすい。例えば、英語では”The”という文字が頻出するが、この場合”he …”という接尾時の直前には”T”が出現しやすいので、BWTの中で接尾辞が”he …”に対応する領域ではTが出現しやすくなる。
高速文字列解析の世界——データ圧縮・全文検索・テキストマイニング (確率と情報の科学) 岡野原 大輔 著 より引用

引用中の接尾辞とは、巡回行列の各行と考えてもらって問題ありません。厳密には、巡回行列では bracadabraa となっているものが、接尾辞では bracadabra となり、巡回しない表現になります。

また、元の入力データに戻すための情報は、行列中の「入力データ」の行番号だけでよいです(別記事で紹介します)。元の入力データに戻すことを今後はBWT逆変換と呼称します。

出現順序に偏りを持たせることだけを考えたら、いくらでも並び替える方法はありますが、並び替えたデータをもとに戻すための情報が大きいと、圧縮したことにはならないです(圧縮データには、もとに戻すための情報も含めるため)。

bzip2のブロックソートでは、行番号(最大899,999)を24ビットで圧縮ファイル中に保存しています。もとに戻すための追加の情報が、たった24ビットで済みます。

巡回行列を辞書順にソートする方法

bzip2では、入力データサイズ(ブロックのサイズ)のサイズによって、ソートするアルゴリズムを変えています。

ここでは、10,000バイト以上のアルゴリズムについて紹介します。通常、ブロックは900,000バイトなのでここで紹介するアルゴリズムが主に実行されます。

入力データをブロックに分割した最後のブロックなど、10,000バイト未満の場合については、別の記事で紹介します。

ソートアルゴリズム概要

例では、説明を容易にするためにシンボルをa〜zで表していますが、実際のシンボルは0〜255です。

1. 先頭の2バイトでソート

例) aaから始まる接尾辞、abから始まる接尾辞、... 、zzから始まる接尾辞、の順にソートされる。3文字目以降は未ソート。

2. 先頭バイトのシンボルの出現頻度が少ない順に下記を行う

ここでは、シンボル t が最も出現頻度が少ないと仮定して説明する

a. 先頭2バイトが異なる値、の行をソート

例) taから始まる行を3文字目以降でソート、tbから始まる行を3文字目以降でソート、...、tsから始まる行を3文字目以降でソート、tuから始まる行を3文字目以降でソート、...、tzから始まる行を3文字目以降でソート

b. 先頭2バイトが同じ値、の行をソート

例) ttから始まる行を3文字目以降でソート

c. (後のソートを高速化するためにソート結果を保存)

2-aと2-bを分けている理由は、2-b をソートする時に、2-aの結果を利用して高速にソートすることが可能となるからです。詳しくは別の記事で紹介します。

まとめ

本記事では、ブロックソートの概要、アルゴリズムの概要、巡回行列ソート方法の概要について紹介しました。