ZIPのdeflate圧縮やLHAのlhXシリーズ圧縮は、 ハフマン法 と 辞書式 という二つのアルゴリズムで構成されています。
二つのアルゴリズムを使っているのは、脈絡なしに組み合わせてみたものではありません。辞書式の難点をハフマン法がうまく吸収しているうまい組み合わせです。
辞書式
記号列の規則性を利用した圧縮法です。
記号列を読んでいて出てきたフレーズが以前にも出てきたものであるとき、「○○個前から××個」と書き換えてしまうことで省略します。
例えば
お前のものは俺のもの、俺のものも俺のもの
という文字列なら
お前のものは俺⑤③、④④も③④
と書き換えるという具合。ここで"⑤③"は5文字前から3文字（"のもの"）という意味です。
ちなみに
あたたたたたたたたたたたたたたたた
なら
あた①⑮
に書き換えられるのです。こういうのもありなんですね（コピー元とコピー先が重なっているのです）。
辞書式には、前方から一致するフレーズを探すための工夫と前方参照の表現の仕方でいろいろ流派があり、ZIPも採用している人気の手法がLZSSと呼ばれるものです。
ハフマン法
記号の出現頻度を利用した最適ビット列化手法です。
多く出現する記号は短い符号で、出現の少ない記号は長い符号で、と符号化します。直観的には、よく使う英単語"a", "the", "it"とかが少ない文字数に、日常的に使わない単語、たとえば"unexpectedly"なんかが長い文字数になっているのを想像してもらうと理解しやすいでしょうか。
晴晴晴晴曇曇晴雨晴晴曇晴晴晴雪晴晴晴晴晴
という記号列をビットで表すとき、晴,曇,雨,雪という記号に平等に2ビットずつ00,01,10,11という符号を割り当ててしまうと40ビット必要です。
0000000001010010000001000000110000000000
出現頻度の多い晴,曇,の順に短い符号を割り当てて0,10,110,111などとすれば
000001010110000100011100000
27ビット。短くなりました。そして、こうなるように最適な符号長を割り当てる手法がハフマン法です。
ごく簡単に説明すると、記号全種類を葉に持つような二分木を組み上げます。このとき、最初はすべての葉が独立したノードである状態から始めて、頻度の小さい方から二つを組んで木にします。この二つのノードの頻度の合計が新しい木の頻度になります。これを、すべてが一つに木にまとまるまで繰り返すというもの。二分木内でのアドレスがそのまま符号です。
辞書式をハフマン法で補完する
辞書式にはちょっとした難点があります。
例えばバイト列に辞書式を適用する場合、元のファイルの記号の種類は256種類だったのですが辞書式を適用すると「○○文字前から」「××文字」を意味するコピー命令の記号が加わって256種類よりも増えてしまいます。
256種類ならちょうど8ビットであらわせていたのですが、種類が増えると1記号あたりのビット数が長くなってしまうだけでなく、種類が2のべき乗個でなくなることでビット効率も落ちてしまいます。
そこでハフマン法。先ほどの例では4種類の記号をハフマン符号化していましたが、ハフマン符号は記号の種類が2のべき乗個でなくても作れます。偶数個である必要さえありません。
そこで
- 元ファイルを辞書式で圧縮する
- その結果は半端な種類数の記号集合で表されているので、ハフマン法で最適にビット列化する
の2段階を踏むことで規則性と文字頻度の偏りを排除した短いバイト列に変換できる、これがZIPやLHAの圧縮過程です。