本ドキュメントは、zlib 公式サイトにて公開されてる文書『An Explanation of the Deflate Algorithm』 を futomi が日本語化したものです。みなさまの理解に役立てれば幸いです。なお、緑色で記載された文章は、futomi が注釈として加筆したものです。また、一部、直訳ではなく、意訳した部分がございます。原文と表現が異なることがございますので、ご了承ください。
注意: この日本語訳は、futomi が理解を深めるために、自分なりに日本語化したものです。本日本語訳には、翻訳上の誤りがある可能性があります。したがって、内容について一切保証をするものではありません。正確さを求める場合には、必ず原文を参照してください。当方は、この文書によって利用者が被るいかなる損害の責任を負いません。
もし誤りなどを見つけたら、こちらからご連絡いただければ幸いです。
この記事は、もともとは 1997/8/23 に comp.compression に投稿されたものです。
DEFLATE を理解しようとする前に、それを構成する他の 2 つの圧縮手法を理解することが重要です。それは、ハフマン符号化と LZ77 圧縮です。
ハフマン符号化は、意外と思われるかもしれませんが、プレフィックス符号化という方式の一つです。しかし、あなたは、ほぼ間違いなくプレフィックス符号を使ってきているんですよ。それは、電話をかけるときです。ダイヤルトーンが聞こえたら、5, 7, 8, 11, 12 や他の数字のボタンを押しますよね。そして、押されたボタンの番号の列によって、相手の電話回線につながるのです。
さて、あなたは、大企業の多くがそうであるように、社内電話交換台（PBX のことだと思われます。）があるオフィスにいるとしましょう。銀行内にある他の電話はどれでも、本来 7 桁のところが、5 桁で電話かかります。それは、あなたがよくそれらの番号に電話をかけると期待しているからです。あなたは、さらに他の番号をかける必要があるかもしれません。だけれども、すべての番号の先頭が 9 になっているのです。
それがプレフィックス符号なのです。あなたが特定したい各要素は、数字で構成されている符号を持っています。そして、一つの要素に対する符号は、決してどんなほかの要素に対する符号で始まることはありませんので、あなたはその符号の中でタイプすることができ、あなたが意味するものであるということに関して、曖昧さは一切ありません。
ハフマン符号は、特別なアルゴリズムによって事前に用意されたプレフィックス符号です。ここでは、0 ～ 9 の数字で構成される符号列の代わりに、0 もしくは 1 のビット列の符号を使います。電話番号を表す符号の代わりに、特定のアルファベットの要素で表す符号を使います。（ASCII 文字集合のようなもので、DEFLATE でハフマン符号化を使うときだけではなく、ごく一般的なものです。）
ハフマンアルゴリズムは、アルファベットの要素を組み立てることから始まります。各アルファベットは、"重さ" が割り当てられます。"重さ" とは、圧縮データ内で、そのアルファベットがどれだけの頻度で発生したかを表した数字です。）これらの重さは、事前に推測されるかもしれません。もしくは、データを読み込みながら正確に計測できるかもしれません。もしくは、それらの組み合わせかもしれません。場合によっては、一度に 2 つの要素が選ばれるのですが、最も低い重さの要素が選ばれます。2 つの要素は、2 本の枝を持つノードの葉ノードとされます（私は、あなたがノードと木を知っていることを切に願います。）。とにかく、下表のような、要素と重さの集合があるとしましょう。
A 16 B 32 C 32 D 8 E 8
最初に D と E を取り出し、それらを単一ノードの枝にします。一つは "0" の枝とし、もう一方を "1" の枝とします。
( )
0 / \ 1
D E
この時点で、完全な符号が与えらた要素はまだありません。しかし、最後の二進数を除いて、D と E に対する符号は、正確に同じだろうと分わかります。つまり、D は 0 で終わり、E は 1 で終わります。
D と E をつなげたノードは、まだつながっていない要素の後ろに戻されます。そして、葉ノードの合計値と同じ重さを与えられるのです。このケースでは、8 + 8 = 16 です。再度、我々は、最も少ない重さの 2 つのノードを取り出します。それは、A と、D-E です。そして、それらをさらに大きなノードに結合します。
( )
0 / \ 1
( ) A
0 / \ 1
D E
今度は、ノード A-D-E が要素のリストの後ろに入れられます。残っている要素は、どれも同じ重さ 32 となりますが、少なくとも、古典的なハフマンアルゴリズムにおいては、3 つのうちどの 2 つが選択され結合されるかは重要ではありません。。
すべてのノードが単一の "ハフマン木" に統合されたとき、根からスタートし、各ステップで 0 もしくは 1 を選択していくことで、木の中のどんな要素にも到達することができます。これで、各要素はハフマン符号が割り振られているのです。それは、木をたどって得られた 0 と 1 の列です。
今、そのような木や符号集合を、圧縮でどのように使うかは、もうお分かりでしょう。もし、例えば、ありきたりなテキストを圧縮するなら、ASCII 文字集合の半分以上が、すっかりと木から左に外すことができるでしょう。"E" や "T" や "A" のような、良く使われる文字は、より短い符号が得られるでしょう。そして、いくつかの符号は実際により長くなってしまうかもしれませんが、それらは、あまり使われていない文字なのでしょう。
しかし、符号化されたデータを使って、どうやって木を再現するのか？と疑問に思うでしょう。もしあなたが木を生成するために使うアルゴリズムを少しだけ変更すれば、極めて単純な方法があることが分かります。
古典的なハフマンアルゴリズムでは、要素と重さの集合が一つ与えられると、何種類もの木を作れてしまいます。Deflate 標準では、2 つのルールが追加される点で、古典的なハフマンアルゴリズムとは異なります。より短い符号を持つ要素はより長い符号の左側に置かれます。（前述の例では、D と E が最も長い符号を巻き上げ、巻き上げられた符号はすべて右側に来ます。） 符号の長さが同じだった場合には、要素集合内で最初に来る要素が左側に置かれます。（もし、同じ長さの符号となる要素が D と E だけだったなら、D が E の前に置かれ、D は 0 の枝を得て、E は 1 の枝を得るのです。）
木に対して、これら 2 つの制限が適用されると、要素とそれに対応する符号長の集合すべてに対して考えられる木は、高々 1 つしかないことが分かるでしょう。木を再現するには、符号長だけが分かっていればよいのです。それゆえに、送信するときにも符号長だけが分かっていればよいのです。
LZ77 圧縮は、繰り返されるデータ列を発見することで機能します。"スライディングウィンドウ" という言葉が使われますが、それが本当に意味するところは、データ内で与えられたどんなポイントでも、以前にどんな文字が記録されたかがわかるという点だけです。32K のスライディングウィンドウは、圧縮器（解凍器）が最後の 32768 (32 * 1024) 文字がどんな文字だったかという記録を保持します。圧縮された次の文字列がスライディングウィンドウの中に見つけられる文字列に一致するとき、文字列は 2 つの数字に置き換えられます。それは、ウィンドウ内でどれだけ戻って列が開始するかを表す距離と、列が一致する文字の数を表す長さです。
私は、これはまさに百聞は一見にしかずだと思います。いくつかの高圧縮可能なデータを見てみましょう。
Blah blah blah blah blah!
我々のデータストリームは、"B", "l", "a", "h", " " そして "b"という文字を受け取ることから始まります。しかし、次の 5 文字を見てください。
vvvvv
Blah blah blah blah blah!
^^^^^
すでにデータストリームに入った文字列の中に、それら 5 文字と完全に一致する箇所があります。そして、それは我々が今いるポイントに続いて、正確にその 5 文字で始まります。このケースでは、我々は、長さに対する数字と距離に対する数字を表す特別な文字を、ストリームに出力することができます。
我々が読み込んだデータは今のところ、このようになっています。
Blah blah b
このデータを圧縮すると、このような形式になります。
Blah b[D=5,L=5]
この圧縮形式を最大限に活用すれば、圧縮の過程で賢さの 1 ビットが必要となりますが、さらに高圧縮が可能です。我々が決め一致した 2 つの文字列を見てください。それらの次にくる文字を比べて下さい。いずれのケースでも、それは "l" です。だから、我々は長さを 5 だけではなく 6 にもすることができるのです。しかし、チェックを続けていくと、次の文字も、次の文字も、次の文字も一致していることが分かります。これは、たとえ、いわゆる "前置" 文字列が、圧縮データとして表現しようとしている文字列と重なったとしてもです！
結局、2 番目の文字から始まる 18 個の文字列は、7 番目の文字で始まる 18 個の文字列と一致するということになります。解凍の過程で、この関係を表す長さと距離の対を読み込んでも、我々はそれら 18 文字の文字列はまだ何なのかを知らないのが実情です。しかし、すでに読み込んで分かっている文字列を導入すれば、どれをさらに次に置けるのかを知ることができます。または、長さ > 距離 という関係になっている "長さ - 距離" の対は、何度も（距離）文字を繰り返しているということが分かるので、我々はまさにそれをするように解凍器をセットアップできるのです。
我々の高圧縮可能なデータは、結果的に、ちょうどこのように圧縮することができることが分かります。
Blah b[D=5, L=18]!
deflate 圧縮器は、データ圧縮方法に関しては相当な柔軟性が与えられます。プログラマーは、適切な選択ができる賢いアルゴリズムを設計するという問題を取り扱わなければいけませんが、圧縮器にはデータ圧縮方式の選択肢が与えられているのです。
圧縮器が利用可能な圧縮方式は 3 つあります。
データは、"ブロック" に分割されます。そして、各ブロックでは単一のモードの圧縮が使われます。もし圧縮器が非圧縮ストレージから、この仕様によって定義された木を使った圧縮へ、または、特定されたハフマン木を使った圧縮へ、または、異なる対のハフマン木を使った圧縮へ切り替えたいなら、現在のブロックは終了されなければいけなく、新しいブロックが開始されなければいけません。
もう少し詳細に調べると、LZ77 と ハフマンがどのように一緒に機能するかに関して詳細に分かります。いったん、生データがリテラルと特定の長さ/距離の対に変わってしまえば、これらの要素はハフマン符号で表現されているはずです。
これは、標準的な専門用語ではありませんが、我々がビットの中で読み込み始めるポイントを "ダイヤルトーン" と呼びます。誤解がないようもう一度言いますが、これは一般的な専門用語ではありませんよ。結局のところ、我々の例えでいえば、ダイアルトーンは、最終的に、特定の電話にマッピングするであろう数字列を特定しはじめられる場所なのです。だから、すべての先頭を "ダイアルトーン" と呼ぶのです。そのダイアルトーンでは、文字、一対の長さ-距離、ブロック終端のいずれかになりえます。我々はそれがどれなのかを区別できなければいけませんので、可能性のあるリテラル、可能性のある長さの範囲を指し示す要素、特別なブロック終端指示子は単一のアルファベットにすべて結合されます。そのとき、そのアルファベットは、ハフマン木の土台になります。距離はこのアルファベットに含まれる必要はありません。なぜなら、それらは長さの直後に直接現れることができるからです。一度、リテラルや長さ-距離の対が復号されると、我々は別の "ダイアルトーン" にいることになり、そして我々は再度そこから読み込み始めるのです。もし我々がブロック終端を表す記号を得たなら、もちろん、我々は別のブロックの先頭にいるか、もしくは圧縮データの最後にいることになります。
長さ符号または距離符号は、実際のところは、基本値を表現する符号といってもよいでしょう。基本値の後ろには、追加すべき整数を形成する拡張ビットがきます。
多分、DEFLATE 仕様の中で一番理解に苦しむところは、データが特定する木を使って圧縮されたとき、そのデータを使って木がどのように符号化されたかという点です。
木は、前述の通り、それらの符号長によって転送されます。符号長は、すべて 0 ～ 15 の数列にまとめられます（生成されるハフマン木は、15 以上にはならない符号長に維持されなければいけません。これが分かりにくい点なのであり、要素の順番が強要されることに関する部分が分かりにくいのではありません。）。
すべての要素に符号長が与えられるわけではありません。もし最後のアルファベットの要素の符号長が 0 なら、それらを除外することができますし、多分、そうすべきです。2 つのアルファベットそれぞれの要素の数字が転送されるでしょう。だから、取り除かれたアルファベットは、単一の列にまとめられます。
いったんこの符号長列が形成されると、それは、いわゆるランレングス圧縮形式で圧縮されます。生データ中のいくつかの要素が同じ符号長（時には 0）を持つとき、特定の記号が、この符号長を持つ要素の数を指し示すために使われるかもしれません。我々の列は、今、0 ～ 18 の数字の列です（多分、基本値を修正するために整数を形成する拡張ビットを使って、長さと距離の符号を使ったケースであったように）。
ハフマン木は、この 0 ～ 18 のアルファベットのために作られます。やれやれ。0-18 の符号列と拡張ビットは、0-18 の要素を置き換えるハフマン符号で事前に用意されるのです。
このハフマン木は、もちろん、データと一緒に含める必要があります。他のハフマン木のように、それは、要素の符号長を記録することによって、含められるでしょう。しかし、さらに、やれやれ。それらは、0, 1, 2, 3, 4 ... 16, 17, 18 の順で記録されないのです。それらは、特別な順番で記録されます。16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15。これの背後にあるロジックは、列の終端に近い要素は、間違いなく、0 の符号長を持つようだということです（つまり、木の中に全くないのです）。もしそれらが本当に 0 なら、それらを列の最後から取り除くことができます。直接的に記録されている要素の数は、データの中にも含められているのです。
以上が、DEFLATE 仕様でつまづきやすいポイントだと思います。その仕様それ自身と少しの時間をつかって、物事がはっきりすれば幸いです。他に質問があれば、どうぞお問合せ下さい。
- Antaeus Feldspar ( feldspar@netcom.com)