Bzip3が何をやってるのか浚ってみた
vim-jp Slackにてbzip3なるものが紹介されていた。軽く見る限り、圧縮が速く小さくなっているようだ。bzip2は中身も含めそこそこ調べたことがあるので、どうしてbzip3が速く小さくなるのか気になって、少しだけ中身を読んで調べてみた。本記事はその記録…なんだけど、あんまり厳密な議論はしてない。
どのくらい速く小さくなっているかはREADMEを見てもらえればよい。ここの前半に挙げられている比較は、詳しく見てわかったことだが、bzip3が有利になるケースをかなり意図的に選択しているようだ。実利用上の数値としては後半のCorpus benchmarksあたりを参考にするのが妥当だろう。
ソースコードをざっくり眺めた感じ、bip3はbzip2の本体と言って良いBWTの前にRLEとLZ+Pを噛ませたものと考えて良さそうだ。BWT自身もsuffix arrayによる工夫がありそう。RLEとLZ+Pを噛ませるとBWTの効率が良くなるよ、ということらしい。
その上で速く小さくなるのには、大きなブロックサイズ(最大511MiB)とマルチスレッド(デフォルトで16スレッド、最大64スレッド)が効いている、と言うことのように見える。
方式
あとはそれぞれの方式のポインタと、可能なものは簡単な解説を上げておこう。
RLE
いわゆるランレングス圧縮、連長圧縮といわれているもの。
bzip3で使われているものは少し特殊で、ある値cについて連続する以上に個別に登場する場合には圧縮しない仕組みになっている。また各cについて圧縮しているかどうかを示すメタデータが、ブロックのヘッダ(32バイト)として付与されている。連続した数の表現も、255を超えていたら255を1つ出力し、255未満であれば その値-1 を出力している。
LZ+P
Lempel–Ziv + Prediction の略。LZは言わずと知れたLZMAなのでそちらを参照。
Prediction部分はおそらくこれ。
実装は大きくないので、時間をかければ読めるはず。あるいはAIにでも解説させれば良いのだろう。
BWT
BWTは以下が詳しい。
すごーく大雑把に説明すると、周期的なデータが同じ値の連続したものになりやすいので、より圧縮が効くというイメージ…いや乱暴が過ぎるので、ちゃんと上の記事を見たほうが良い。
bzip3ではlibsaisを(ヘッダーライブラリ化したものを)使っている。
libsaisは以下の論文の実装っぽい感じ。また理解に役立ちそうなリンクをいくつか挙げておく
- https://synergy.cs.vt.edu/pubs/papers/timoshevskaya-saisopt-iccabs14.pdf
- https://ieeexplore.ieee.org/document/5582081
- https://blog.tiqwab.com/2018/09/17/suffix-array.html
以上
Discussion