bzip2を読む はじめに

こんにちは。 junkawa です。
bzip2 圧縮(compress)プログラムのソースコードの紹介をしていきます。

圧縮プログラムとは、データの大きさ(サイズ)を小さくする(圧縮する)プログラムのことです。
データを小さくすると何が嬉しいのでしょうか？
・小さいデータの方が、大きいデータより速くダウンロードできる
・小さいデータの方が、大きいデータより多く保存できる
など、データを圧縮することで有限な資源(ネットワーク帯域、ストレージ容量) を有効活用することができます。

圧縮プログラムは、ソートなどのアルゴリズムを組み合わせて作られます。
いくつかソートを学んだ方は、学んだソートアルゴリズムが実践的にどうやって使われるか気になったのではないでしょうか。
圧縮プログラムでは、基本的なソートアルゴリズムを独自に改良して使用しています。
よって、圧縮プログラムを学ぶことで、理論的な知識に加え実践的な理解を得ることができます。

今回紹介する圧縮するプログラムは、bzip2 です。ソースコードのバージョンは、1.0.6 となります。
ソースコードは GitHub で公開しているので、必要に応じて参照ください。
https://github.com/junkawa/bzip2/tree/master/bzip2-1.0.6

圧縮プログラムは数多くありますが、実用的な面で下記の違いがあります。
　・圧縮にかかる時間
　・伸長(uncompress / 圧縮したデータをもとのデータに戻す処理のこと)にかかる時間
　・圧縮率(どれだけデータを小さくできるか)

bzip2 は、圧縮速度、伸長速度、圧縮率の全てにおいて、そこそこの性能を出している、平均的な性能を持つ圧縮プログラムです。
　参考：@nishemon さんの「2016年のOSS圧縮ツール選択カタログ」

bzip2 は、他の圧縮プログラムではあまり用いないブロックソートというアルゴリズムを使用しています。
今回、bzip2を題材に選んだのも、このブロックソートに興味があったかったからです。

では、bzip2 の圧縮処理について概要を紹介します。

bzip2 圧縮処理の概要

bzip2 の圧縮処理は、大きく分けて3つになります。

　1. ブロックソート(BWT)変換
　2. Move-To-Front(MTF)変換 + ランレングス(RLE)符号化
　3. ハフマン符号化

また、1. の前段階として、入力データをランレングス符号化します。

各処理の詳細は、別の記事で紹介します。

bzip2の圧縮とは

ブロックソート変換、MTF変換では、後のランレングス符号化、ハフマン符号化で圧縮しやすい形にデータを変換します。
その後、ランレングス符号化、ハフマン符号化によって、データを圧縮します。

ハフマン符号で圧縮しやすい形とは、「入力中に現れるシンボル(文字、値)の出現回数に偏りがある」場合です。
詳細は別の記事で紹介しますが、出現回数の多いシンボルに短い符号を割り当て、出現回数の少ないシンボルに長い符号を割り当てることで、割当後のデータサイズが小さくなります。

圧縮しにくい例)
　「あいうえおあいうえおあいうえお」
　出現頻度 あ=3回、い=3回、う=3回、え=3回、お=3回
　ハフマン符号化 あ=00、い=01、う=10、え=110、お=111
　符号化後 000110110111000110110111000110110111 → 36ビット

圧縮しやすい例）
　「あああああああああああいうえお」
　出現頻度 あ=11回、い=1回、う=1回、え=1回、お=1回
　ハフマン符号化 あ=0、い=100、う=101、え=110、お=111
　符号化後 00000000000100101110111 → 23ビット

上記の例では、圧縮しやす例の方が 13ビット(36-23) 短くなっています。

ブロックソート変換、MTF変換は、下記の性質を持ちます。
　・入力データを、(シンボルの出現回数が偏るように)別のシンボルに置き換える
　・伸長時に上記シンボル置き換えの逆変換を行うが、この時に必要となる(圧縮したデータ以外の)データが小さい
　　いくらシンボルを置き換えてハフマン符号化で圧縮しやすくしても、(圧縮ファイルに加える)置き換えの逆変換に必要なデータが大きかったら、圧縮できたことにはならない

bzip2 の使い方

bzip2 を、Linux のターミナルで使う方法を紹介します。一番簡単な使い方は、
bzip2 圧縮したいファイル名
です。

具体例
$ bzip2 datafile

これで、datafileは圧縮されて、datafile.bz2 というファイルが作られます。
参考：bzip2のオプション一覧 

下記では、bzip2 のソースコードを紹介します。

今回は、bzip2 のファイル構成と、bzip2 プログラム実行時の処理の流れ(関数呼び出し)の概要を紹介します。
なお、C言語を学んだことがある方向けの内容となっています。

bzip2 ファイル構成

ソースコードは下記で公開しています。
https://github.com/junkawa/bzip2/tree/master/bzip2-1.0.6

以下に、圧縮、伸長で使用される主要なファイルの概要を紹介します

bzip2.c
コマンドラインオプション解析、入出力ファイルのオープン、クローズ

bzlib.c
圧縮、伸長ファイル操作、bzip2ライブラリ関数

compress.c
圧縮アルゴリズム

decompress.c
伸長アルゴリズム

blocksort.c
ブロックソート(BWT変換)

huffman.c
ハフマン符号化

bzlib_private.h
圧縮、伸長用の構造体定義

bzip2 コマンド実行時の関数呼び出し

fopen()、fread()、fwrite()、fclose()でファイル入出力・標準入出力を行い、入力データを入力バッファへ読み出し、出力バッファを圧縮ファイルを書き出しています。

それ以外の処理では、入力バッファのデータをもとに、変換、符号化を行い出力バッファへ書き込みます。

入力データは900kB(コマンドラインオプション-1〜-9で変更可能。デフォルトは-9)毎に圧縮されます。

各関数の簡単な説明

bzip2.c

main()
コマンドラインオプションの解析

compress()
入出力ファイル、標準入出力の準備

compressStream()
bzlibの圧縮処理呼び出し。入力ファイル読み出し

bzlib.c

BZ2_bzWriteOpen()
圧縮用構造体EStateの初期化、入出力バッファの確保@BZ2_bzCompressInit()。

BZ2_bzWriteClose64()
入出力バッファの開放@BZ2_bzCompressEnd()。

BZ2_bzWrite()
圧縮処理後、出力ファイル書き出し。

BZ2_bzCompress()
圧縮処理の状態管理

handle_compress()
内部構造体の出力バッファ(s->zbits)→出力ファイルバッファ@copy_output_until_stop()
暗号処理の前後のデータ操作(入力ファイルバッファ→内部構造体バッファ、内部構造体バッファ→出力ファイルバッファ)

copy_input_until_stop()
入力ファイルバッファ→内部構造体の入力バッファ(s->block)

ADD_CHAR_TO_BLOCK()
使用シンボルのチェック
4〜255回まで連続するシンボルをランレングス符号化@add_pair_to_block()

compress.c

BZ2_compressBlock()
ファイルヘッダ、ブロックヘッダ、CRC、BWT逆変換用情報(ソート済み接尾辞行列中のオリジナル文字列の行番号)、ファイルトレイラを出力バッファへ書き出す。

generateMTFValues()
不連続なシンボルを連続するシンボルに変換するためのマップ作成@makeMaps_e()。
MTF変換、ランレングス符号化、シンボルの頻度情報の生成(sendMTFValues()で使用)

sendMTFValues()
多重ハフマンテーブルの生成、テーブル割当の改善。MTF変換+ランレングス符号化結果のデータ、50バイト毎にハフマンテーブルを割り当てる。
MTF逆変換用情報(シンボル(0-255)がデータ中に存在するかどうか)、テーブル情報(テーブル数、テーブル割当、テーブル内容)を出力バッファへ書き出す。

blocksort.c

BZ2_blockSort()
BWT変換。
BWT逆変換用情報(s->origPtr)の用意。

fallbackSort()
入力ブロックサイズが10,000バイト未満の時(900kBで分割した最後のブロックなど)に、ブロックソートを行う。
Manber-Myersの接尾辞配列構築アルゴリズムを参考にした処理。

mainSort()
ブロックソートを行う。
先頭2バイトで基数ソート。処理高速化のために先頭シンボルの出現頻度の少ない順に下記を行う。
先頭2バイトが異なる行のソート、先頭2バイトが一致する行のソート。

huffman.c

BZ2_hbMakeCodeLengths()
出現頻度に応じて、シンボルにビット長を割り当てる。
このビット長を使って、全体のサイズが小さくなるように、ハフマンテーブルの割当を改善する。

BZ2_hbAssignCodes()
割り当てられたビット長に応じて、シンボルに符号を割り当てる。

まとめ

今回はbzip2の概要について簡単に紹介しました。
今後、各処理の詳細について紹介していきたいと思います。