第2回目 MG勉強会

本日はManaging Gigabytes勉強会の第2回目でした。本日の内容はText CompressionのさわりとHuffman Coding。Canonical Huffman Codingスゲーという感じのお話。

Text Compression

まずはText Compressionとはなんぞや、という話。テキストを普通に保存する場合、単純に保存する1文字8bitとか使うことになってしまうのですが、普通の言語の場合、すべての文字が同じ出現頻度で出現することはありません。たとえば、英語の場合"e"という文字の出現頻度は高くて、"z"みたいな文字の出現頻度は低くなります。その出現頻度を考慮して、出現頻度の高い文字には短いビット長、出現頻度の低い文字列には長いビット長を割り当てることで、全体としてのビット長を短くしましょう、というのが基本になります。この方法がCompressionということになります。このときの割り当て単位として、各文字ごとに決めていく方法をSymbolwise法で、単語やあるまとまりごとに行う方法をdictionary法といいます。


単にCompressionとはいっても、これには2つの段階、ModelingとCodingというものがあります。Modelingというのは、各語の生起確率を求めることで、その生起確率から各語にビットを割り当てる部分がCodingになります。このとき、まずModelを求めてから、それに応じてCodingを行う方法をStatic Compression(またはSemi-static Compression)、Modelを求めつつCodingをして、次々とModelを更新していく方法をAdaptive Compressionなどと言ったりします。

Models

モデリングとは、各語の生起確率を求める方法になります。ここで出てくるシャノンの情報量定理の式( I(s) = - log Pr[s] )という式はよく使われるのでチェックです。


実際にはModelというと、必ずしも各語の生起確率だけではなく、前後の関係によって生起確率が変わることなどを考慮したfinate state machineを利用した方法もあります。


また、実装のことなども考えた場合、出現頻度が0となってしまう語が出現する場合(zero frequency problem)なども問題になります。モデル作成時には出現頻度0としたが、Codingの時にその後が出現してしまった場合、その後は符号化できなくなってしまいます。これを避ける方法なども実際にはモデル化に取り込んでいかないといけないことになります。

Huffman coding

コーディングの最初の手法は、比較的よく知られたHuffman Codingです。これは各語の生起確率からトーナメント表のようなものを作って、それぞれに0,1を割り当てることによって接頭符号を作る方法です。トーナメント表を作るときに、生起確率の小さいものから組み合わせていくことで、出現頻度が高いものは短い符号、出現頻度が低いものは長い符号となるようにします。


このHuffman codingの特性を利用し、さらにいくつか制約を科すことによって、より効率的に符号化・復号化できるようにした手法がCanonical Huffuman Codingです。この部分はまだ理解が追いついてないので、理解できたらまた別エントリで。




Managing Gigabytes: Compressing and Indexing Documents and Images (Morgan Kaufmann Series in Multimedia Information and Systems) (ハードカバー)
Managing Gigabytes: Compressing and Indexing Documents and Images (Morgan Kaufmann Series in Multimedia Information and Systems)
Ian H. Witten (著)
Alistair Moffat (著)
Timothy C. Bell (著)
¥ 10,294