ゼロから始めるDeflate圧縮

#きっかけ
ブロックチェーン、ディープラーニング、ワンピース、等々。。流行語を「わかった風」に語るも、コアな技術を理解してない。そんな、中身空っぽな自分。
ワンピースに至っては、何回読み返してもリュウグウ王国辺りでストーリーをロスト。
そんな自分に嫌気がさし、一年勃起一念発起してDeflate圧縮を勉強。RFC1951(Deflateの定義)を見ても1ミリもわからなかった、私の奮闘をお納めください。

#やりたいこと
Deflate圧縮のアルゴリズムを理解したい。
なぜって？意味はない。なんでもいいから理解したかった。

##Deflate圧縮とは
PNG画像やPDFのデータ圧縮に使われている圧縮方法。Unix,Linux系でよく使われるgzipにも使われる。

#Deflate圧縮に使われている技術

• LZSS
• ハフマン符合
• ランレングス符合

まずは、これらを順にくどくどと説明していく

##LZSS圧縮
一度でた情報を繰り返し「書かない」ことで、全体のデータサイズを小さくする。
一度でた指示を繰り返し「わすれる」ことで、上司からの信頼を失う私とは大違い

例えば

「どりょくはかならずむくわれる。もしむくわれないどりょくがあるのならば、それはまだどりょくとよべない。」(by 王貞治。都合により平仮名で記載)

という50文字の文があった場合、
「どりょくはかならずむくわれる。もし**(4,8)ない(4,23)があるのならば、それはまだ(4,40)とよべない。」
と書けば、44文字で済むので6文字節約できる。この場合「(4,8)」は2文字（2つの数字）と数える。
(4,8)というのは8文字前(距離)から4文字(長さ)ほどコピーするという指示**だと勝手に決めている。
長さ・距離の2つの数字を使うため、2文字以上を置き換えないと圧縮の効果がない。

##ハフマン符合
###前提～データの表現方法～
コンピュータの中ではデータを1と0の数字で表現。画像、文字、音楽、人生の全てが1と0の並びに変換されて管理されている。
この1,0の並びを1桁取り出したものを**"1bit(ビット)"と呼び、8桁取り出したものを"1byte(バイト)"**と呼ぶ。

Deflate圧縮では、元データの1,0の並びを8桁ずつ(1byte)に区切り、それぞれの固まりを10進数の数字にする。各固まりは0～256の数字の並びに変換される。
ちなみに、1byteになれない半端なbitが余ったら0を付け加えて1byteにする等の対応が必要。

###ハフマン符合の概要
0～255の数字でデータを表現したら、当然人気のある数字と不人気な数字が出てくる。1回も登場しない数字だってあり得る。
あれだけ小学校のころ習った平等は現実社会で実現されていることを見たことがない。どこでも人気と不人気はある。
元々、1つの数字は8bitの1,0できていた。でも人気がある数字も不人気な数字も平等に8bitを使うというのは非効率だ。
ハフマン符合のアイデアは、これらの0～255のうち、よく出てくる数字に「短い」桁数のbitを割り振り、あまり出てこない数字には「長い」桁数を割り振る。そして一度も出てこない数字にはbitを割り振らないというもの。
極端な話、0～255のうち、46と120しか出てこないのであれば46を「0」にして120を「1」にすればよい。「46,120」は元々「00101110, 1111000」と16桁で管理されていたところ、「0, 1」という2桁で管理できる。
**この新たに作った1,0の組み合わせを「ハフマン符合」**と呼ぶ。

###符合表
とはいえ、何も知らない人に[0,1,1,0,1]のようなハフマン符合で表現されたデータを渡しても、**「なんじゃこりゃ！？」となる。
データに加えて「0」は「46」を意味し、「1」が「120」を意味するという対応表を付けておかないといけない。この対応表のことを「ハフマン符合表(もしくは単純に、符合表)」**と呼ぶ。
「え、リアコ？」と言ったところで、おじさんには分からない。(おじさんへ：リアルに恋する＝リアコ)
ギャルはハフマン符合を使いこなしている。わかりみが深い。

###ハフマン符合の作り方
ハフマン符合を作るためには、2つのことを考える必要がある。

• 1つ目は、各数字の符合の長さの決め方。人気数字には短く、不人気数字には長くという指針だけだと、具体的に何桁にすればよいかわからないので、何桁を割り振ればよいのか計算する方法が必要。
• 2つ目は、各数字の桁数が決まった後、具体的な符合を割り振る方法。例えば2桁と言われても、00、01、10、11の4つの候補の中からどれを選べばいいかわからない。桁数から実際の符合を割り当てる方法が必要。

ちなみに、ハフマン符合の割り当て方を工夫すると**「データを読みやすく」することができる。
例えば、「46」に2桁、「120」に3桁割り振るという桁数が決まったとする。このとき、46に「10」、「120」に「101」というハフマン符合を割り振ると、「読みにくい」**データになる。
なぜなら、「10101」というデータを読むときに、初めの符合が「101」なのか「10」なのか瞬時にはわからない。最後までデータをみると「10, 101」ということがわかる。
一方、46に「01」、「120」に「100」というハフマン符合を割り振ると[01100]というデータは、初めが「01」で次が「100」ということが瞬時にわかる。
どうせ、ハフマン符合を割り振るなら、瞬時にわかるほうが便利だ。
**「君の話は最後まで聞かないとわかんないんだ！」**と言われて「最後まで聞かないお前が悪い」と(心の中で)歯向かう私には目からうろこの発想。

###各数字の符合の長さの決め方
前提として、Deflateで使うハフマン符合は最大でも15桁と決まっている。
こういった最大桁数の制約がある中で、符合の長さを決める方法として**「パッケージ・マージ・アルゴリズム」**というのがある。
仰々しい名前だが、やってることは単純。

• ステップ1

  • 数字の頻度表を作成し頻度の少ない順に並べる(ちなみに、データに登場しない数字は無視する)

• ステップ2

  • 左から順に2組のペアをつくる。
  • ペアの数字は元の数字を並べたもの(例えば、元の数字が2,3であれば、ペアの数字は2/3)、頻度は元の数字の頻度の合計とする。

• ステップ3

  • ステップ2で作ったペアを頻度表に埋め込み、再度頻度の少ない順に(ペアも含めて)並び変える

• 繰り返し

  • ステップ3で作成した表を新たな頻度表としてステップ2、3を繰り返す。
  • ステップ2・3は全部で最大桁数-1回分**(Deflateでは15-1=14回)**実施する。
    (繰り返していくと、ペアのペアができて表現が「2/4/2/4/2/4/5/6」みたいに長くなるが気にしない。)

• ステップ4

  • 繰り返した後に出来上がった頻度表の中に、それぞれの数字が何回出現するかを数え、それを桁数とする。(10/32は10と32が1度ずつ出現すると考える)

ステップ2・3を1回適用すると、結果として2回出現する数字がでてくる。
ステップ2・3を2回適用すると、最大でも3回でてくる。
つまり、14回適用すると、最大でも15同までしか同じ数字が登場せず、Deflateの15桁以下という要件を満たす。
また、出現頻度が多い数字は頻度表の右端にいるので、ペアを作るときにスキップされステップ3でペアとして現れない(つまり、その数字の出現回数は低くなり、桁数の割り当てが短くなる)。

---

ちなみに、こういったアルゴリズムの紹介を読んでると、出来レースのように思えてなんとも腑に落ちないときがないだろうか。
アルゴリズム自体は理解できるが、なぜそれで目的が達成できるのか分からないというなんともいえない気持ち悪さが残るときがあるのだ。
そうなったら、もうひたすら繰り返しアルゴリズムを読む・自分で動かしてみるということをやるしかない。自分のポンコツさを呪いながら何度も読んでるうちにだんだんしっくりくる。

---

###瞬時にわかるハフマン符合
さて、今手元にはデータに現れる各数字とその数字に割り振るべき桁数の一覧ができた。
ここから、実際に符合(1,0の並び)を割り振る方法について紹介する。
絶対に例を持ち出す意味はないが無理やり比喩すると、子どもの名前を決めるときに先に字画を決めて、字画に合うよう具体的な名前を決めるみたいなものだ。

• まず、数字に割り振るべき桁数の少ない順に並べる。このとき、桁数が同じ場合は数字が小さいほうが先にくるように並べる。

• 次に、一番初めの数字に「0」を割り振る。ただし、0は桁数分割り振る。例えば2桁なら「00」となる。

• それ以降は、基本的には前の符合に「1」を足して符合をつくる。ただし、この足し算は「二進数」上での足し算ということに気を付ける。

• もし、1を足した後の符合が、その数字の桁数が足りない場合は桁数になるよう0を右側に付け加える。

必要なのはたったこれだけ。ハフマンという名前にびびってたが意外に大したことない。
このルールで符合を割り振ると、大きい桁が割り振られている数字の1,0の並びの先頭部分が、より短い桁数が割り振られている数字の1,0の並びと被ることがなくなり、先頭から安心して読んでいくことができる。

##ランレングス圧縮
同じ数字が続く場合、続く回数を指定することで実際に数字を書くよりも短く表現する圧縮法。
無量大数は100000000000000000000000000000000000000000000000000000000000000000000です。というより、無量大数は「1の後に0が68個」というほうが簡単に済む。

###Deflateにおけるランレングス圧縮の出番
Deflateでは、データ中の各数字に割り振られる桁数を管理している。管理方法は単純で、1～285までの各数字に対して順に、1,3,1,2,・・・,5,5といった風に数字を並べて管理している。
1には1桁、2には3桁・・・というように左から順に0,1,2,・・・285までの桁数を表している。当然、桁数の数字は0も含めて286個ある。

最大桁数は15なので、0～15までの数字が桁数として現れるが、新たに16,17,18という数字を仲間に入れる。
16～18までの数字は直前の数字(もしくは0)が何回繰り返されるのかを表すと決めておくと、286個の数字を使って管理していた桁数表がより短く表現することができる。
16～18の数字が何を意味するかは後ほど触れる。

自分の人生をランレングス圧縮したら、絵日記1枚分ぐらいにまとまりそうな気がする。寝る・食べる・ネットしてたまに働く。シンプルで美しい人生だ。

#では、ようやくDeflate圧縮の流れ
まず、元のデータをbit列(1,0の並び)で表現したものを8桁ずつに区切り、各区切りを0～255の数字に置き換える。

##次に、このデータをLZSSを使って圧縮
具体的には、3つ以上連続で前に出てきた数字と同じ並びの数字が出てきたら「連続する数字の長さ」と「前に出てくる場所までの距離」の2つのペアの数字に置き換える。
ただし、「長さ」と「距離」は単純に数字として表現するのではなく、下の表を使って「数字＋拡張ビット」で表現する。

表を見ると、例えば長さ7に対応する符合は261で、拡張ビットの桁数は0なので、拡張ビットはなしとする。
一方、長さが53ならば、53は表中の長さの列の「51-58」に含まれるため符合は275で、53から51(275の符合で表現する際の最も小さい長さ)をひくと2になるので、拡張ビットは2を表現する2進数「010」とする。拡張ビットは3桁と指定されているので「010」としている。

ちなみに、元々のデータには0～255までしか使われないため、257以上の数字がでてきたらそれは「長さ」を表現しているということが自動的にわかる。

一方、距離は0～29の数字と拡張ビットで表現される。この数字はデータで使っている数字と被っているが、「距離」は必ず「長さ」の後にくるため、データとは区別して識別することができる。
表を見るとわかるように、長さは最大258まで、距離は32768までとなっている。

###拡張ビット
しかし、この「拡張ビット」というのがなんともややこしい。長さが3～258までなのであれば、長さを表す数字を257～512とすれば拡張ビットは必要ないのではと思う。
しかし圧縮おじさん(誰だか知らないが)から言わせれば、あまり使いそうもない長さ258といった数字に数字を1つ割り振るのはもったいないそうだ。
こういったレアキャラにはまとめて一つの数字を割り当てておいて、もし出現したら拡張ビットを付け加えて判別するほうがデータ容量的に効率がよいらしい。

ちなみに、ここで登場した拡張ビットはこの後の圧縮処理においては完全に放置され、そのまま圧縮データの中に記録される。

##そしてハフマン符合
次に、LZSSで圧縮したデータに出てくる「データ・長さ」(0～285の数字)と「距離」(0～29の数字)についてハフマン符合を作る。
頻度表は、0～285までの数字に対する頻度表(データ・長さの数字のみを対象)と0～29までの数字に対する頻度表(距離の数字のみを対象)の2種類を使う。

まずは、頻度表をベースに先ほど説明した**「パッケージ・マージ・アルゴリズム」で、各数字に割り振る桁数を決める。
桁数表も「データ・長さ」に登場する数字用と、「距離」に登場する数字用の2種類ができる。（先に説明したように符合の最大桁数は15）
また、桁数表ができれば、これまた先ほど説明したハフマン符合の作り方に従ってハフマン符合**を作ることができる。
最後はLZSSで圧縮したデータ内の数字を、計算したハフマン符合表したがってbit列(0,1の並び)に置き換えていく。もともと、1つの数字に対して8桁の0,1を割り振っていたものと比べると、トータルの長さは短くなってるはずだ。
しつこいようだが、拡張ビットは放置してそのままにしておく。

これで無事圧縮一件落着。とはいかない。
しかし、この圧縮されたデータを渡されても、受け手は各0,1の並びが何の数字を表しているのかわからない。
おじさんに**「ぴえん」だの「ぱおん」**だの言っても無駄である。だってわかんないんだもん。

そのため、先ほど作ったハフマン符合と数字の対応表も相手に渡す必要がある。(ギャルはそんな親切なことはしてくれない)
でも、ハフマン符合を渡そうと思えば、0～285の数それぞれに対応する1,0の並びと、0～29に対応する1,0の並びを渡さなければいけないのだが、どう考えても面倒くさいし、データ量が大きくなりそうだ。
そこで、手を抜いて各数字に割り振った桁数だけを教えることにする。桁数さえわかればハフマン符合の作り方に従って符合はデータの受け取りてでも作れる。甘えは許さん。
ちなみに、桁数の並びを渡す時も、最後に0が続く場合は、0を省略することにする。本来ならば0～285に対応する桁数なので286個数字が並ぶ必要があるが、もし最後に0が続くならばデータ量削減のため0は書かない。
ただし、0～256までの桁数は省略できないというルールにする。257～285に対応する桁数は以降の桁数がすべて0であれば省略する。

しかし最後の0を省略すると、桁数の並びが260個続くのか、270個続くのか、286個続くのか誰にも分からなくなる。そこで、別途「データ・長さ」用の桁数の並びの数も相手に伝えることにする。
ちなみに、0～256までの数に対応する桁数は省略できないので、「データ・長さ」用の桁数の並びは257個～286個になる。そのため、桁数の並びの数を、0(257個)～29(286個)で表現する。

もちろん、「距離」を表すデータについても各数字の桁数を相手に伝える必要がある。
「データ・距離」の場合と同様、最後に0が続く場合は省略する。最低でも1つの桁数は入れなければいけないので、0～29までの数字に対応する30個の桁数の長さは、0(1個)～29(30個)で表現する。

メインデータが圧縮できたというのに、その後の処理が面倒。。。
ここまですると、データは以下のようになっているはず。

###圧縮おじさん登場～
これで大分圧縮されたと思いきや、圧縮おじさんはまだ頑張る。
まだ、「ハフマン符合の桁数表」を表現している部分が圧縮できる余地があるからだ。
そこで、次にランレングス圧縮を使って、「データ・長さの桁数表」と「距離の桁数表」を圧縮する。
具体的には、桁数表内のデータ(0～15の値)にはでてこない、16,17,18の数字を使って圧縮を行う。

• 16:ひとつ前に出現した数字が3～6回続く場合は、「16」と2桁の拡張ビットに置き換える
  • 例えば、[1,3,5,5,5,5,5,5,5,3]というデータの場合、[1,4,5,16,(11),3]とする。ちなみにカッコ内の11は拡張ビットで2進数
• 17:0が3～10回繰り返される場合は、「17」と3桁の拡張ビット
  • 例えば、0が8回続く場合は、[17,(101)]となる
  • 0が続く回数は拡張ビットを10進数に直したもの+3で繰り返し回数がわかる
• 18:0が11～138回繰り返される場合は、「18」と7桁の拡張ビット
  • 例えば、0が92回続く場合は「18,(1010001)」となる
  • 0が続く回数は拡張ビットを10進数に直したもの+11で繰り返し回数がわかる
    この圧縮を行うと、データ構造は以下のようになる。

###圧縮おじさんは更にしつこい。
「データ・長さの桁数表をランレングスで圧縮したもの」「距離の桁数表をランレングスで圧縮したもの」を更にハフマン符合を使って圧縮する。
「データ・長さの桁数表をランレングスで圧縮したもの」「距離の桁数表をランレングスで圧縮したもの」の中には、0～18までの数字と拡張ビットしか出てこない。
そこで、ここに出現する0～18の数字に対し頻度表を作り、「パッケージ・マージ・アルゴリズム」で各数字に対する桁数を計算し、ハフマン符合を計算する。
そして、「データ・長さの桁数表をランレングスで圧縮したもの」「距離の桁数表をランレングスで圧縮したもの」のデータを計算したハフマン符合で置き換える。
このとき、ハフマン符合の最大桁数は7以下になるようにする。

###悲報：もう一度桁数表が必要です。
データ本体をハフマン符合で置き換えた時と同様、0～18の数字に対する桁数表を付けないと受け手はデータを読み解けない。
普通に考えるとこれまでと同様、0～18まで順番に桁数を並べればよいと思う。でも、Deflateでは桁数を次の数字の順番で並べる約束になってる。
「16、17、18、0、8、7、9、6、10、5、11、4、12、3、13、2、14、1、15」
つまり、1,1,2,3・・・・6,6とあれば、数字16に1桁、数字17に1桁、数字18に2桁、数字0に3桁、・・・・、数字1に6桁、数字15に6桁が割り振られているということになる。ややこしい。

ただし、この場合も、もし桁数表の最後に0が続くならば省略するという約束。ただし、これは数字8に対応する桁数以降に適応できる。最低でも16,17,18,0の4つの数字に対する桁数は存在する。
[1,1,2,3,・・・・,1,3,0,0,0]という並びであれば、最後の3個の0は省略され、[1,1,2,3,・・・・,1,3]となる。

**なんでこんなにややこしいの！**😡、、、といわれても。。
たぶん、あまり発生しそうにない、15とか1というものを最後にもってきたのだろう。
(元のデータに15桁もの長いハフマン符合が割り振られる可能性や、1といった極端に短いハフマン符合が割り振られる可能性は低い。ということは、元のデータの桁数表に15や1が一度も現れない可能性が高い。ということは桁数表をハフマン符合で圧縮する際に、15や1には0桁のハフマン符合を割り振ることができる。そして、桁数表をハフマン符合で圧縮した際の桁数表の最後に0が続くとその部分を省略できるという決まりによって、桁数表を短くすることができる)

そして、最後の0を省略してる可能性があるので桁数の並びの個数を別途データとして持っておく必要がある。
この並びの個数は0～15までの数を持ち、実際に並びの個数を計算するときにはこの数字+4をする。
ここまでするとデータは以下のようになる。

###それからそれから。2進数に変換。あなややこしや。
さて、最後に0,1の並びにまだなっていない部分を2進数に変換する必要がある。（そうしないとデータとして記録できない）
まずは「二つの桁数表の数字(0～18)に対する桁数表」だが、この表のデータは0～7の値をとる。そのため、各数字を3桁の1,0の並びに変換する。
次に、「二つの桁数表の桁数表に含まれるデータの数」は4桁、「距離の数字(0～29)の桁数表に含まれるデータの数」は5桁、「データ・長さの数字(0～285)の桁数表に含まれるデータの数」も5桁の二進数に変換する。

###仕上げに、Deflate用のヘッダ
ここまでひた隠しにしてきたがDeflateには「ブロック」と「圧縮モード」という概念がある。
「ブロック」は単純に元のデータをいくつかの固まりにわけ、それぞれの固まり別々に上記のDeflateの圧縮を適用する。
初めにデータをいくつかの固まりにわけたので、全てのブロックを復元しないと元のデータは手に入らない。そこで、Deflateのヘッダにこの圧縮データが最後のブロックかどうかを判断するフラグを持っておく。
このフラグが立ってない場合は、他のブロックがあるはずなので、そのブロックも復元する必要があると分かる。

一方、「圧縮モード」は深く考えなくてよい。今回説明している圧縮モードは**「カスタムハフマン符合」**というモードだが、他にも「非圧縮」「固定ハフマン」というモードもある。でも普通出くわさない。

そこでヘッダを、以下の通りとする(2進数)。

• 000 最終ブロックではない、非圧縮
• 100 最終ブロック、非圧縮
• 001 最終ブロックではない、固定ハフマン
• 101 最終ブロック、固定ハフマン
• 010 最終ブロックではない、カスタムハフマン
• 110 最終ブロック、カスタムハフマン

**大体ヘッダは「110」**になる。
最終的なデータ構造は以下の通り。
**マジで圧縮されてる？**と聞き返したくなるレベル。だが、結構圧縮される。

##ようやく最後です。本当に。データの書き方です。
上記の説明でDeflateの流れを全てを書いた。この無駄に長い説明を体よく圧縮したい気分だ。
全てのデータが2進数で表現され、あとはその1,0を書き込むだけ。

でもDeflateはここもすんなりといかない。
先頭のヘッダから110・・・と書いていけばよいかと思いきや、書き方が「ハフマン符合で置き換えられた部分」と「ヘッダ、桁数のデータの数、桁数表、拡張ビット」で違う。

---

そもそも、データを書き込む際には8bitを一塊にしたバイト単位で書き込んでいく。
書き込む順番は、1バイト目の1bit、1バイト目の2bit・・・1バイト目の8bit、2バイト目の1bitといった順番に0,1を書き込んでいく。
そのとき、「ハフマン符合で置き換えられた部分」はデータを左から右へ読んで書き込む。
つまり、もしデータが「01101」であれば、1バイト目の1bitは0, 2bitは1, 3bitは1, 4bitは0, 5bitは1といった感じ。
一方、「ヘッダ、桁数のデータの数、桁数表、拡張ビット」はデータを右から左へ読んで書き込む。
つまり、もしデータが「01101」であれば、1バイト目の1bitは1, 2bitは0, 3bitは1, 4bitは1, 5bitは0といった感じ。
途中で8bit目まできたら、次のバイトの1bitに続けていく。

deflate圧縮の説明はこれで終わり。
ご静読ありがとうございました。

#ご参考にさせて頂いたサイト様
この記事を書くにあたり、以下のサイトを参考にしました。ありがとうございます。
http://darkcrowcorvus.hatenablog.jp/entry/2016/09/23/195644
https://qiita.com/zprodev/items/f26fccbb37f480a887a0
https://tools.ietf.org/html/rfc1951