γ符号、δ符号、ゴロム符号による圧縮効果

通常の整数は 32 ビットは 4 バイトの固定長によるバイナリ符号ですが、小さな数字がたくさん出現し、大きな数字はほとんど出現しないという確率分布のもとでは無駄なビットが目立ちます。

Variable Byte Code (Byte Aligned 符号とも呼ばれます) は整数の符号化手法の一つで、この無駄を幾分解消します。詳しくは Introduction to Information Retrieval (以下 IIR) の第5章に掲載されています。(http://nlp.stanford.edu/IR-book/html/htmledition/variable-byte-codes-1.html で公開されています) Variable Byte Code はその名の通りバイトレベルの可変長符号で、1バイトの先頭1ビットを continuation ビットとして扱い、続く 7 ビットでバイナリ符号を行います。小さな数字を 1 バイトで表現し、大きな数字でも複数バイトで表現できる符号化手法です。

例として 5 や 130 といった数値を符号化するとそれぞれ

数値 固定長バイナリ符号 Variable Byte Code
5 00000000 00000000 00000000 00000101 10000101
130 00000000 00000000 00000000 10000010 00000001 10000010

となって、固定長符号では上位の3バイトが無駄になりがちなところ、Variable Byte Code では無駄が少ないことが分かります。

このように整数の符号化手法によっては小さな数字をより小さな符号長で表現することができ、結果として圧縮効果が得られます。Variable Byte Code 以外にもγ符号やδ符号、ゴロム符号など整数の符号化には多数の手法があります。そしてそれらの手法でなぜ圧縮効果が得られるのか、というところを見ていこうというのが今回の話の主旨です。

検索エンジンの転置インデックスを圧縮する

例えば検索エンジンの転置インデックスでは、文書IDを整数で扱い、整数の並びで索引を表現します。「perl という単語が含まれる文書は [ 3, 5, 20, 21, 23, 76, 77, 78 ... ] です」という具合です。これらの整数を符号化するのに固定長バイナリ符号ではなく、ちょっとした前処理を施してから Variable Byte Code を使うと圧縮効果が得られます。

ちょっとした前処理というのは、文書ID をそのまま使うのではなく、前の数字との差分で同じリストを表現するように変形してやります。[ 3, 5, 20, 21, 23, 76, 77, 78 ] → [ 3, 2, 15, 1, 2, 53, 1, 1 ] です。こうしてやると小さな数字がたくさん出現するようになります。全体として小さな数字の出現確率が高ければ Variable Byte Code で圧縮効果が得られるのは直感的に分かります。

ビットレベルの符号化 ･･･ γ符号, δ符号

ところで Variable Byte Code はバイトレベルの符号化なので、どんなに小さな数字でも 1 バイトは 8 ビット未満にまで小さくして表現することはできません。バイトレベルではなくビットレベルでの整数の符号化手法は多数ありますが、ポピュラーなのは γ符号, δ符号でしょうか。

γ符号は整数 x を、

  • 1 + floor(log x) を unary 符号で
  • x - 2floor(log x) をバイナリ表現した floor(log x) ビットで

する符号化手法です。unary 符号は 1 を 3 を 110, 4 を 1110, 5 を 11110 ... とビットの立っている数で整数を表現する符号化手法です。γ符号における unary 符号部は、続くバイナリ部分のビット数を表現します。

これだけだとよくわからないので、Managing Gigabytes (以下 MG) にある γ符号の例を示します。x = 9 の場合

  • floor(log x) = 3 より、1 + floor(log x) = 4 → 4 を unary 符号で符号化 → 1110 (これはバイナリ部分が 3 ビットであることを示す)
  • 9 - 2floor(log 9) = 9 - 23 = 9 - 8 = 1 → 1 を 3 ビットで表現 → 001

となり、結果として 9 は 1110 001 というビット列で符号化されます。

一方の δ符号はγ符号で unary 符号を使うところを、γ符号で符号化したものです。それぞれの手法で小さな整数がどのように符号化されるかを以下に示します。MG の P.117 は Table 3.6 から引用します。

整数 x unary符号 γ符号 δ符号
1 0 0 0
2 10 10 0 100 0
3 110 10 1 100 1
4 1110 110 00 101 00
5 11110 110 01 101 01
6 111110 110 10 101 10
7 1111110 110 11 101 11
8 11111110 1110 000 11000 000
9 111111110 1110 001 11000 001
10 1111111110 1110 010 11000 010

となります。γ符号、δ符号両者ともに、小さな数字は 8 ビット以下で表現できていることが分かります。

ロイターのニュース記事を集めた RCV1 のような一般的な文書コーパスを対象に転置インデックスを構築した際は Variable Byte Code よりもγ符号、δ符号で文書IDを符号化する方が全体として圧縮率は高いそうです。IIR の第5章によれば、RCV1 の転置インデックス (の postings file) は 32 ビット固定のバイナリ符号で 400MB になるところ、Variable Byte Code で 116 MB、γ符号で 101 MB になるそうです。

なぜγ符号やδ符号で圧縮されるのか

それで、γ符号やδ符号のあらましは分かったのですが、なぜこれらの符号でそのような圧縮効果が得られるのかがしばらく理解できていませんでした。今回改めて MG の第3章を読んで理解したことを記します。

ポイントになるのは固定長バイナリ符号、γ符号やδ符号をはじめとする整数の符号化が、暗黙的に確率モデルを内包しているという所です。以下、そこを見ていきます。

γ符号、δ符号共に、整数 x が分かると符号長 lx が分かります。γ符号は unary 符号部が 1 + logx, バイナリ部分が logx なので 2logx + 1 ビット, δ符号はγ符号の unary 符号部をγ符号に変えたものなので、そこから定式化できます。

  • γ符号 : lx = 1 + 2logx ビット
  • δ符号: lx = 1 + logx + 2log(1 + log x) ビット

となります。x に対する符号長が定式化できるとあとはシャノンの情報量の式 lx = -log Pr[x] から、符号確率 Pr[x] は Pr[x] = 2-lx として求められます。この式から多少の近似を用いて導くと

  • γ符号: Pr[x] = 1 / 2x2
  • δ符号: Pr[x] = 1 / 2x(logx)2

という分布が得られます。これが各符号が暗に持つ確率分布です。

ギャップリストを固定長バイナリ符号で表現した場合よりも、これらの符号で符号化した方が圧縮できるということは、この各符号の確率分布がギャップリストにより適した分布になっている、と言えそうです。実際には、ギャップリストが持つ実際の確率分布と各符号化手法が暗黙に持つ確率分布の違いが小さければ小さいほど、最適な符号長となります。Wikipedia の Univeral code によれば、二つの確率分布の距離は Kullback-Leibler ダイバージェンス (KLダイバージェンス) で定量化することができて、この値が小さいほど最適な符号長に近づくとのことです。

"Universal code" (ユニバーサル符号) という言葉が出てきました。*1 整数の符号化の文脈でユニバーサル符号というのは、確率分布が monotonic (整数を i としたとき Pr[i] ≧ Pr[i + 1] ･･･ つまり、大きい数ほど出現確率が下がる) な分布のとき、その分布が実際にはどんな分布であるかに関わらず、最適な符号の定数倍程度の長さの符号長に符号化できる符号化手法だそうです。γ符号やδ符号はユニバーサル符号です。Wikipedia によると、ユニバーサル符号の分布は冪上則な分布 1/n2 に近似することができて、この分布に対してはユニバーサル符号が最適に近い符号長を実現することが分かっています。IIR 5章によると、γ符号はギャップリストをエントロピーの 2 ~ 3 倍程度に抑えることができるそう。

まとめます。γ符号やδ符号は暗黙的に確率モデルを内包していて、それがギャップリストを表現するのにより適した確率分布となり、結果として圧縮効果が得られます。また、ユニバーサル符号としてのγ符号、δ符号は実際の確率分布がわからなくても、符号長を最適な平均符号長の定数倍に収められるという特徴を持っています。ですから、ギャップリストが実際にどのような分布になっているかは分からなくても、γ符号やδ符号で符号化すると、とにかく結構な圧縮率で圧縮できるというわけです。

幾何分布に最適なゴロム符号

ユニバーサル符号は実際の確率分布に関わらず圧縮を実現するのですが、ギャップリストの実際の確率分布を仮定して、その確率分布に適したモデルを考えるとどうなるでしょう。転置インデックスのギャップリストはベルヌーイ試行でモデル化することができ、その結果として確率分布は幾何分布 (ja.wikipedia.org) になります。

このモデル化に関しては、MG 輪読会で id:sleepy_yoshi さんの説明が分かりやすかったです。 [ 4, 3, ... ] というギャップリストは、4 が出た後、5, 6 が出ないで、7 が出たということを示します。これを定式化すると、ある単語が確率 (1-p) の確率で x - 1 回出現せず、その後に確率 p で単語が 1 回出現する確率 Pr[x] = (1-p)x-1p となって、幾何分布となります。

そして幾何分布に対して最適な符号長を達成する符号化手法としてゴロム符号 (en.wikipedia.org) が良く知られています。MG によるとこれは参考文献 [5] で証明されているとのことです。ゴロム符号はパラメータフリーなγ符号やδ符号とは異なり、符号長を調整するためのパラメータが必要になります。このパラメータは転置インデックスの場合、全体の文書数や単語の数から求めることができます。よって、ギャップリストを圧縮するのに、ゴロム符号は良い選択肢となります。

MG 第3章の途中までですが、整数の符号化によって圧縮効果が得られる云々、というのはこんなところになります。

まとめ

整数の符号化手法によってギャップリストを圧縮するにあたって、なぜそれで圧縮されるのかを見てきました。

整数の符号化手法は他にも色々あるのですが、ここでは自分がよく目にする Variable Byte Code、γ符号、δ符号、ゴロム符号について見てきました。整数の符号化が面白いのは、符号化対象が整数であるという特徴から、符号化の手法そのものが暗黙のうちに確率モデルを規定するというところです。この確率モデルが与える確率分布によって、どの程度の符号長で整数群が表現できるかが決まり、それが結果として最適に近い分布であるほど圧縮効果が得られるということでした。

Managing Gigabytes: Compressing and Indexing Documents and Images, Second Edition (The Morgan Kaufmann Series in Multimedia Information and Systems)

Managing Gigabytes: Compressing and Indexing Documents and Images, Second Edition (The Morgan Kaufmann Series in Multimedia Information and Systems)

参考文献, URL

[1] の第5章で、転置インデックスの圧縮の話があります。Variable Byte Code とγ符号についての解説が中心です。[2] でも同様に転置インデックスの圧縮として整数の符号化が解説されています。[2] の解説の方がより濃度は濃いです。[3] にはユニバーサル符号について概要があります。[4] ではゴロム符号が、幾何分布に対して最適な符号長を与えることについて言及されているそうです。(未読です)

[5], [6] には各種整数符号化の実装方法があります。[5] には Python による実装、[6] には C++ のそれが記載されています。Perl による拙作の習作は id:naoya:20081015:1224084885 などをご覧ください。

*1:ユニバーサル符号と日本語で書くと、LZ法などの"入力データが長くなるにつれて圧縮率が情報源のエントロピーに収束するという性質を有する符号" (http://www.it.ss.titech.ac.jp/uyematsu/intro-j.html より) の意味のこともあるようですが、英語でははこちらは Universal source coding と呼ぶようです。Wikipedia にも両者を混同しないように、とあります