« 1速、2速、3速のはなし ---(車の話はありません) | トップページ | つれづればなし »

2010年6月 9日 (水)

圧縮むだばなし

LZH 書庫の脆弱性の問題(http://www2.nsknet.or.jp/~micco/vul/2010/mhvi20100425.htm)が徐々に話題にのぼりはじめていますね。ウィルス対策ソフトウエアの中にも、ヘッダ処理時にバッファオーバーフローが発生すると、対応する書庫に対する処理を打ち切るものがあり、結果として書庫内のファイル検疫が行われない可能性がある、というものです。

▽ バッファオーバーフローとはまた古典的な話ですが、古典的でも問題を引き起こすとなれば、対策を取るべきなのは当然です。

※ 今朝ほどのメンテナンスの影響で、公開作業が遅れてしまいました。失礼致しました。

■ LZH というと、個人的には 1990 年頃のことでしたか、吉崎栄泰氏の lharc.exe を見たのが最初だったかと思います。と、いいますか、この国産の LZH(LZSS圧縮データをHuffman圧縮する方法)が吉崎氏によって開発されたのがまさにこの頃ですから、開発当初から見知っていたことになりましょうか。
 比較的高効率で、手軽に使えるインタフェースを備えた lharc は、確かに便利であったのです。

■ 情報圧縮、というのは一種の魔法みたいに見えることがあります。何せ長ったらしい文章をごく短い文章に置き換えてしまうというのですからね。
 ちなみに、bit.ly みたいな「圧縮」は、情報自体は圧縮(というか短縮)されますが、この短縮された情報そのもの(短い情報)からは元の情報(長い情報)が出てきません(図)。

10060901

 短縮処理時に、長い情報と、当該長い情報を短縮して得た短い情報とを関連づけた「関係づけテーブル」がサーバ側にできていて、これを参照して「短い情報」を「長い情報」に戻すことになるわけです。

■ 情報圧縮という場合、一般的なイメージでは、こういう関係づけテーブルもまたローカルのデータに内在していて(あるいは伸張アプリケーションに内在させてあって)、サーバに問い合わせなくても伸張ができる、というイメージではないかと思います。
 では、そんな情報圧縮はどういう仕組みなのか、というと、それが、それほど難しい話では決してないのです。

■ コンピュータは数値情報を主に扱うので、例えば文字の情報としてのアルファベットも内部的には数値化して扱っているわけです。例えば「A」は「1」、「B」は「2」、…というように。よく聞く話かと思いますが、これを二進数(「0」と「1」と)で表現するので、「A」は「1」、「B」は「10」…というようになります。アルファベットは(大文字だけに限れば)26字なので、このデンでいくと、「Z」は「11010」と5桁になる勘定です。桁数が一々違うのは面倒なので、桁数を揃えます。具体的に言うと、桁数が4以下の場合、5桁になるよう、上位の桁に「0」を詰めます(パディング)。
 そうして、

  • A:00001
  • B:00010
  • C:00011
  • Z:11010

という符号が完成するわけです。

■ ここで「桁数が違うと面倒」と言ったのは、例えば、「ABB」とつなげた場合に、桁数が違っているのを構わずにつなげる(連接する)と、

「11010」

と表現され「Z」と区別がつかなくなるからです。桁数を5桁に揃えておけばこれが

「000010001000010」

と書けて「5桁ずつ見る」ことができ、ちゃんと復号ができるわけです。

■ さて、これからが「圧縮」です。
 英文を書く場合、AからZはまんべんなく出てくるわけではありません。Qなんて文字はあまり出てきませんし(出てくるときは必ずUを伴う)、「Z」もそれほど頻度は高くないでしょう。一方、一番頻度が高いのは「E」だそうです。
 そこで、

頻出する文字については、桁数を短くできないか、

と考えるわけです。
 例えば、

  • E:1
  • E以外:0(から始まる)

としてしまう。
 そうすると、先頭に

「1」

があったら、それは「E」ということになり、先頭が「0」で始まっていれば、それは「E」以外であると解釈ができる。そうして、例えば

  • E:1
  • A:10
  • T:110
  • N:1110

とすると、「NAT」という文字列は、

111010110

と符号化され、「1,1,1,0」と読んだ時点で、Nと読め、続く「1,0」でAと読め…と桁数が違ってもちゃんと復号できるしくみ。
 ここでは比較的簡単な例にしてみましたが、実際にはもう少し複雑に符号化しても大丈夫です。例えば、

  • E:11
  • A:10
  • T:00
  • N:011

としても大丈夫。この場合の文字列「NAT」は、

011100

と符号化されるのですが、「0,1」と読んだところでE,A,Tのどれでもなく、続く「1」まで含めてNであることがわかるでしょう?
※ヒソカに処理しましたが、EATNの4文字しかない世界にしたので符号がより短くなったのです。
 このような符号化の方法は、Huffman によって与えられたので、Huffman 符号化と呼んでいます。原論文は wikipedia から辿ることができます(http://compression.ru/download/articles/huff/huffman_1952_minimum-redundancy-codes.pdf)。

■ LZH は、この 1950年代(!)からあった符号化方法を、LZSS 方式という別の圧縮方法に組み合わせたものです。LZSS 方式はまた、ちょっと違う考え方で情報を圧縮するものですが、そのやり方については(記事も長くなってきたので)また今度に致しましょう。

|

« 1速、2速、3速のはなし ---(車の話はありません) | トップページ | つれづればなし »

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック


この記事へのトラックバック一覧です: 圧縮むだばなし:

« 1速、2速、3速のはなし ---(車の話はありません) | トップページ | つれづればなし »