- 2 サイト表紙
- 3 しらぎくさいと実験室
- 4 資料集
- 5 ウェブで用いられる画像
- デフレート圧縮(LZ77圧縮)
PNG画像を生成するのに欠かせないデフレート圧縮(LZ77圧縮)について解説します。
デフレート圧縮は、LZ77圧縮アルゴリズムを応用したもので、圧縮技術としてはかなり旧くからあるもので、GZIP(ZLib)やZIPファイル圧縮技術などに用いられております。
デフレート圧縮は枯れた技術であり、特許問題も無い技術として知られており、この為PNG画像の基幹技術としても採用されたのです。
特許問題の無い技術とされるデフレート圧縮にも、実は特許に引掛かるアルゴリズムが存在します。しかしながら、特許問題が生じるアルゴリズムは効率を上げるためのものなので、効率が悪くても特許に触れないアルゴリズムを撰べば問題はありません。
特許問題が生じない事の確認に長い時間を費やしたと書かれております。
LZ77圧縮とは、ヤコブ=ジフ(J. Ziv)とアブラハム=ランペル(A. Lampel)両氏が西暦1977年(昭和52年)に考案した圧縮アルゴリズムで、平たく言えば「既に出てきている文字の並び(単語)が再度出てきたら、それをより短い符号に置換えてしまう」と言うものです。
以下、一般常識とはちょっと懸け離れた意味で使われる用語を解説しておきます。
ここで言う文字とは、 1オクテット( 8ビット)で表される 1データの事を指します。
単語とは、複数個の文字(オクテット)で構成されるデータの塊を指します。
尚、デフレート圧縮では単語は 3文字以上258文字以内とします。
ここでは、説明を分かり易くするため、具体的に"ABCDEFGABCDEF"というアスキィ文字列で考えて見ましょう。
この様な原理から、同じ文字列が何度も出てくればより圧縮効率が高まると言う事になります。
更に言えば、単語が長ければ長い程、より効率よく圧縮出来る事になります。
LZ77圧縮を施す事で、(文字)と(単語の長さ,単語の位置)という二種類のデータが発生します。
単語の場合は以下のようになります。
つまり、デコーダは最初のデータが文字データ( 0〜255)ならそのまま出力して、257〜285なら単語という事でこの後に付随するデータを読込んで単語を決定します。256ならそこで処理を終了させます。
上述の通り、 8ビットの文字列を圧縮した際に 8ビットを越える符号データが発生します。
また、付随するデータには 8ビットに満たないものもあります。
そうすると、ビット長が不定のデータ列をどのようにして構築出来るかと言う問題が発生します。
この答えとして、デフレート圧縮ではハフマン符号が使われます。
ハフマン符号はプレフィックス符号と呼ばれる二進数での符号の一種です。
プレフィックス符号の大きな特徴は、一つ一つのデータの大きさが不定だという事です。しかしながら、予め決めておいたデータの形式により、問題無く頭から順に一つづつデータを切出す事ができる様になっております。
このプレフィックス符号を依り効率の良いものにした符号がハフマン符号と呼ばれるものです。
デフレート圧縮では、予め仕様にてハフマン符号を定義してある固定ハフマン符号と、ハフマン符号を再定義してより効率よく符号化を行う独自ハフマン符号が利用できます。
更にLZ77圧縮を一切利用しない無圧縮も撰べます。この場合は仕様に従って元のオクテットデータをそのまま並べたフォーマットにします。
尚、固定ハフマン符号は静的ハフマン符号、独自ハフマン符号は動的ハフマン符号と直訳される場合が多いのですが、静的ハフマン符号及び動的ハフマン符号という言葉には別の意味があるため、敢えて固定ハフマン符号及び独自ハフマン符号と意訳しました。
実際のデフレート圧縮データでは、最初に読込むデータ( 0〜285)に対してハフマン符号を当て、単語においては単語の位置を表す０〜29のデータにも別系統のハフマン符号を当てます。
LZ77圧縮の原理を考えると、圧縮された符号(単語の長さと同じ単語がある位置の組)に関して、単語の位置と単語の長さにはある関係があると考えられます。
すなわち、(l,d)=(単語の長さ,単語の位置)としたときに、l ≦ d となっている筈だという事です。
これを否定する l > d と言う関係、例えば圧縮データが「"ABCDEFG"(7,3)」となっているとしたら(7,3)という符号は「 7文字の単語が 3文字前にある」となりますが、これだと"EFG"という 3文字しか取出せず、 7文字の単語を取出す事ができません。
しかしながら、デフレート圧縮の仕様書ではこの様なデータの存在を明確に認めております。
l > d と言う関係を持つ符号では、単語の字数を満たすように取出せた文字列を繰返し並べると言う決まりになっているのです。
先ほどの「"ABCDEFG"(7,3)」の場合、(7,3)符号では 7文字になるまで"EFG"と言う３文字を繰返す事になっており、つまり"EFGEFGE"となります。
結局「"ABCDEFG"(7,3)」="ABCDEFGEFGEFGE"と言うデータとなる訳です。
この決まり事は、PNG画像には特に有効でしょう。
画像の場合、同じ色のピクセルが連続して並ぶと言う事はよくある事です。
単一のピクセルとまで行かなくても、複数のピクセルの列が規則正しく並ぶと言う事も珍しくありません。
この様な「同じデータが連続する」事が多い画像には、有効な圧縮手段を提供された事になります。
デフレート圧縮では、ハフマン符号に以下の規則を追加しております。
分かり易く言えば、二進数での 0及び 1を文字に見立てて辞書的な決まりに従って符号を決めて行くと言う事です。
具体例を挙げてみましょう。
デフレート圧縮で独自ハフマン符号を用いる場合、圧縮される文字/文字列長及び距離に対して、一つ一つにビット長を指定した形の符号表を提示します。
更にこれらの符号表自身もハフマン符号で圧縮され、その為のハフマン符号表は当然これらの符号表より前に定義されるものとなります。
具体的には、以下の順にデータが並ぶ事となります。
(※1)文字/文字列長及び距離データのハフマン符号表を圧縮するための、ハフマン符号表。HCLEN+4個のデータが並ぶ。各データは 3ビットと固定されている。
尚、固定ハフマン符号ではハフマン符号が既に仕様で定義済みなので実際の圧縮データのみが並ぶ事になります。
圧縮データは、既に述べた通り、任意の区間ごとに無圧縮, 固定ハフマン符号によるエンコード及び独自ハフマン符号によるエンコードの三種類から撰べます。
このため、各区間の先頭に３ビットからなるフラグが付与されます。
先頭の 1ビットは最後の圧縮区間の場合に 1になります。
後続の２ビットは「無圧縮, 固定ハフマン符号によるエンコード及び独自ハフマン符号によるエンコード」のいずれかを明示します。
ところで、デフレート圧縮の決まりに従って圧縮しても、そのままのデータでは取扱えません。
最後に、GZIPフォーマットに合せて出力することになります。
GZIPフォーマットは、PNGで採用されているデフレート圧縮データのフォーマットです。
具体的には圧縮されたデータの先頭に 2オクテットのデータ(圧縮方式とフラグ)、末尾に圧縮前のデータに関する 4オクテットのチェックディジットがそれぞれ附加されます。
デフレート圧縮の原理を考えると、圧縮されたデータは文字ないし単語の列と言う形になる訳ですが、圧縮ルーティンのバグが原因で間違ったデータを出力していた場合、形式的に不正で無い限り、デコーダはその間違いを見出す術がありません。
このため、圧縮前のデータを基にチェックディジットを計算しておく事で、展開されたデータに対して同様にチェックディジットを計算して比較する事で圧縮データの誤りを見出せるようになる訳です。
一応和訳版もありますが、表組みが崩れていたり、文章が分かり難い箇所もあります。
英語が分かる方は、英語版をご覧になった方が分かり易いでしょう。
ハフマン符号については詳しい解説がありますが、LZ77圧縮については解説があまり詳しく無いので予備知識が無いと理解出来ないかも知れません。
LZ77圧縮に関しては、宇都宮大学に分かり易い文書があったのですが、現在はサーヴァごと？削除されて見られません。
この文書はインターネット・アーカイヴに保存されている当該文書です(日本語)。
GZIPフォーマットの仕様書です。
デフレート圧縮をしても、このフォーマットに従わなければ読込んでもらえません。
