こんにちは。ブレインズテクノロジーの岩城です。
先日、データ圧縮時のオプションの一つの"compression level" (または圧縮レベル)の設定を検討する機会があったので、調べた内容をご紹介します。
本記事では特に、圧縮レベルの値の違いでの「速度や圧縮率の方向性」ではなく、「何が違ってその結果が得られたのか」を議論するための素材の提供に重点を置いています。
1. 本記事のゴール
本記事のゴールは以下の2つに設定しました。
- 圧縮レベルによる内部処理の違いを設定値として確認すること
- さらに調査を進めるための資料の整理
そのため、アルゴリズムの詳細な内容は対象としていません。
1.1. 圧縮レベル設定と検討のメリット
圧縮レベルは圧縮の速度と圧縮率のバランスを調整するパラメータです。
この値の検討により、可能な限りデータを圧縮したい場面や速度を重視したい場面など、目的に応じた設定ができるようになります。
1.2. 調査対象
今回の記事ではzlibを主な調査対象としました。 選定理由としては、zlibは情報が充実していたほか、pythonでよく使うshutilやjoblibでも利用されていることが挙げられます。
その他の方式として、lzmaなどいくつかのライブラリで部分的に参考になりそうな情報があったため、末尾にリンクを整理します。
2. 結論
まず結論です。 zlibではcompression levelごとに圧縮処理で使われるパラメータや関数が変わるようでした。 この情報が記載されていた資料のリンクと、ソースコードへのリンクを示しておきます。
Understanding zlib 3.3.4. Adaptive Serach Limit
また、分かりやすさのためソースコードの該当箇所を引用してご紹介します。
local const config configuration_table[10] = { /* good lazy nice chain */ /* 0 */ {0, 0, 0, 0, deflate_stored}, /* store only */ /* 1 */ {4, 4, 8, 4, deflate_fast}, /* max speed, no lazy matches */ /* 2 */ {4, 5, 16, 8, deflate_fast}, /* 3 */ {4, 6, 32, 32, deflate_fast}, /* 4 */ {4, 4, 16, 16, deflate_slow}, /* lazy matches */ /* 5 */ {8, 16, 32, 32, deflate_slow}, /* 6 */ {8, 16, 128, 128, deflate_slow}, /* 7 */ {8, 32, 128, 256, deflate_slow}, /* 8 */ {32, 128, 258, 1024, deflate_slow}, /* 9 */ {32, 258, 258, 4096, deflate_slow}}; /* max compression */
(https://github.com/madler/zlib/blob/master/deflate.cより引用。)
この部分はUnderstanding zlibにも記載がありますが、一次情報であることを考慮しソースコードを直接引用しました。
圧縮アルゴリズム等を勉強された方はご存知かとは思いますが、結局辞書的な表現に直すために過去の出現とのマッチングを行う必要があり、 その探索の際のパラメータのセットをいくつか準備している、ということのようです。
good, lazy, nice, chainはいずれも文字列のmatchに関するもので、chainのあとの*はdeflate(圧縮部分の処理)で使う関数です。
good, lazy, niceについてのコメントを簡単に整理すると以下の通りです。
- good: match_lengthがこの値より大きいとlazy searchを減らす
- lazy: match_lengthがこの値より大きいとlazy searchをしない
- nice: この値よりも大きいmach lengthでは探索をやめる
lazy search (lazy match)は、ある長さNの一致が見つかった後で次の入力byteに対してより長い一致を探す処理のことのようです。 (参考: https://tools.ietf.org/html/rfc1951)
また、chainはmax_hash_chainとも呼ばれるもので、記号列一致の候補を探すときに使われます。
いずれのパラメータも値が大きいほどより長い一致記号列を探したり、より多くの圧縮表現作成に使用する情報をもつなど、圧縮率を高くする方向の役割をするようになります。
その他、zlib自体はlossless, つまり可逆圧縮であることも把握しておくと良いでしょう。
パラメータは分かったものの、パフォーマンスがどう変わるかはさすがに分からないので、あとは実験結果などを参考に妥当な値を使用するか、推奨値を使用するかなどの判断をすることになるかと思います。
なお、後述のjoblib.dump()ではcompressionをTrueとした場合はcompression levelを3としており、この値を"often a good compromise"、つまり良い妥協点としています。
3. zlibに関する参考資料
zlibに関して、今回の調査で最も参考になったサイトがこちらです。
zlibの原理やパラメータ、最近の研究などが簡潔かつ分かりやすくまとまっており、とても参考になりました。
また、もちろんですがzlib自体のホームページとgithubで公開されているソースコードも非常に参考になりました。
アルゴリズムなども含めて詳細な内容が知りたい方は上記のリンクなどが有用かと思います。
補足資料
さて、ここまでで本記事の目的はほぼ達成しました。
ここからは関連しそうな周辺情報の整理と、少しだけzlibの中身を確認してみたいと思います。
A.1. zlib周辺情報の整理
A.1.1. 様々な圧縮ツール
圧縮ツールといっても様々な種類があります。 zilbも含めて後述のライブラリとも関わってくる代表的な手法から4つ紹介しておきます。
- zlib
- gzip
- bz2
- lzma
詳細は本記事のフォーカスではないため割愛します。
A.1.2. pickleと圧縮
pythonでデータを保存 (dump) するときにぱっと思い浮かぶのがpikcleだと思います。 pickleは公式でも記述がある通り、serializingとde-seriazilingが主な役割です。
つまり、python objectの構造をbyte streamに変換して保存する・読み出すのが役割です。
pickleは相対的に小さなbinaryでの表現にはしてくれるものの、圧縮は別で考える必要があります。
公式ではpickleしたデータに対して圧縮もできる、という形で言及されています。
https://docs.python.org/3/library/pickle.html
A.1.2.1. pickle.dump()の引数の"protocol"
pickle.dump()については、引数の"protocol"の設定を知っておくと後述のjoblibなど、別のところで役に立つかもしれません。
プロトコルはPython 3.8.5の時点では0から5のいずれかの整数で、番号によってserializeする方式が異なっています。
大きいほど新しくて、高速化や大きなオブジェクトのサイズへの対応が追加されているようです。
デフォルト値はPython 3.0以降は3、Python 3.8以降は4になっています。
https://docs.python.org/3/library/pickle.html#pickle-protocols
A.1.3. joblib
joblibはPythonでpipeline jobを扱うツールを提供するライブラリです。
本記事との関連要素として大きいのはjoblib.dumpです。 joblib.readthedocs.io
joblibではzlib, gzip, bz2, lzma, xzといった圧縮方式が選択可能ですが、特に重要なポイントは、圧縮のデフォルトがzlibであることです。
(参照: https://joblib.readthedocs.io/en/latest/persistence.html#persistence )
拡張子での指定およびパラメータでの指定をしなかった場合はzlibが使用されるため、知らないうちにお世話になっていたかもしれません。
A.1.4. shutil
pickleのcompressの記述は以下のページにリンクしています。
https://docs.python.org/3/library/archiving.html
ここでshutilのArchive operationが紹介されているように、shutilからも圧縮処理が可能です。
compression levelが指定できなさそうではありますが、圧縮手段の一つとしてのご紹介でした。
A.2. zlibの簡単な紹介
zlibについても簡単に記載したいと思います。
先ほどもご紹介した以下リンクを読めばおよそ知りたいことが得られるので、きちんと知りたい方は改めてこちらをお勧めします。
A.2.1. 代表的な情報
まずは大まかなポイントとなる情報を箇条書きで整理します。
- 1995年に作られた。
- 圧縮部分はJean-loup Gailly, 解凍部分はMark Adlerにより書かれた。
- 圧縮にはdeflete method、解凍にはinflate methodが用いられる。
- それぞれLZ77とハフマン符号化を使用。
- deleteの文字列一致の探索では、Rabin-Karp algorithmのようなアルゴリズムも使用。
- zlib Licenseというライセンス
A.2.2. パラメータ
続いて、少しだけパラメータの話です。ここでは圧縮のみを対象とします。
圧縮 (deflate)ではLZ77による圧縮とハフマン符号化を行います。
A.2.2.1. LZ77
圧縮レベルでのパフォーマンスの違いを決めるパラメータはこのLZ77関連です。
ここでは要素を極めて簡単にご紹介します。
詳しく知りたい方は、以下リンクの2章2項と3章部分を順番に読んでいただくのが理解の助けになると思います。本記事を書く上ではWikipediaも参考にしました。
https://www.euccas.me/zlib/#deflate_lz77 https://www.euccas.me/zlib/#zlib_implementation https://ja.wikipedia.org/wiki/LZ77
LZ77はsliding windowを用いて、新たに注目する記号列が過去の記号列の中にあったかどうか探索し、出現していた場合はlenght-distance pairと呼ばれる、文字列の長さと出現位置を示す記号での表現に置き換える手法です。
LZ77についてはポイントが大きく2つあります。
一つ目のポイントとしては、Sliding Windowを用意して、ファイルの部分文字列に対して過去の出現情報を辞書化する処理を行うことが挙げられます。
Sliding Windowは"search buffer"と"look-ahead buffer"の2つの部分から構成され、look-ahead bufferは新たに辞書化する対象文字列を、search bufferは過去の文字列を保持します。
二つ目のポイントはlength-distance pairで、これは(検索対象記号列からの距離、一致した文字列長さ、look-ahead bufferの最長一致長さの次の文字列)で表現されています。
文字で説明すると非常にわかりづらいので、以下の箇所をご確認いただくのが良いでしょうか。
https://www.euccas.me/zlib/#deflate_length_distance_pair
A.2.2.2. パフォーマンスとパラメータ
最後に、パラメータとパフォーマンスの話です。
defleteのパフォーマンスを決めるパラメータとして最も重要なのは、"一致文字列の探索をどこまでするか"になります。
(Sliding Windowのサイズも重要に思えますが、デフォルトが64KBであり、可変ではあるものの圧縮レベルのパラメータには含まれていません)
zlibの実装では最長一致を見つけるために、大きく以下の2つの処理をしています。
- 短い長さの文字列で一致候補を見つける
- 候補に対して一致を評価し、current longest matchを決める。
このプロセスで最長一致対象を見つけるか、事前に決めたlongest match limitを超える物を見つけるまで探索を行うことになっているとのことです。
さらに一つ目ではRabin-Karp Algorithmを元にしたアルゴリズムを使っていることのポイントになります。
Rabin-Karp Algorithmはrolling hashという手法を用いた文字列のhashを用いた文字列の一致を効率的に見つけることが可能なアルゴリズムです。
zlibでは部分文字列の一致評価を行うために、Hash Chainという構造を使用し、Rabin-Karp algorithmのように部分一致情報を効率よく活用します。
このhash_chainの最大長さを決めるのが、パラメータの一つのmax_chain_lengthになります。
A.2.2.3. ハフマン符号化
ハフマン符号化の方はwikipediaをはじめ様々な資料が出てくるので、そちらをご参照いただければ基本的には問題ないかと思います。
パフォーマンスに関連する要素も、zlibに関しては内部処理の中で一度dynamic Huffman treeを作ってstatic treeかdynamic treeを使うかを決めていることをおさえておけば大丈夫ではないでしょうか。
ハフマン符号 - Wikipedia https://www.euccas.me/zlib/#zlib_huffman_encoding
A.3. その他のツールとcompression level
あまり詳しくは確認できていませんが、zlib以外でもいくつかcompression levelの参考になりそうな資料があったので記載しておきます。
- lzma
- 7zip
まとめ
この記事ではcompression levelの具体的に何が変わるかをzlibを題材に調査した結果をご紹介しました。
圧縮レベルについて調査をした際に、"compression level"や"圧縮レベル"で検索してみたものの情報が不十分だったり、パフォーマンスの方向性は示されていても、原理や設定値での違いがすぐには見つからず、手間取ってしまったことが今回記事を書くきっかけでした。
圧縮処理の際のパラメータや関数セットの違いということが確認でき、個人的には知りたいところまでは納得できたのですが、この記事にたどり着いた方にも十分な内容になっていれば幸いです。
今回は特に、知りたいことが検索してもなかなか出てこなかった背景もあり、リンク等も含めて皆様のお役に立つことを願っています。
ブレインズテクノロジーでは「共に成長できる仲間」を募集中です。
採用ページはこちら
参考資料
zlib関連
- Understanding zlib
- zlib Home Site
- github/madler/zlib
- zlib License - Wikipedia
- RFC 1951 - DEFLATE Compressed Data Format Specification version 1.3
zlibに関わるpython関連
- pickle — Python object serialization — Python 3.8.5 documentation
- Joblib: running Python functions as pipeline jobs — joblib 0.17.0.dev0 documentation
zlibのアルゴリズム関連
その他のツールとcompression level
