Tuesday, January 21, 2014

Deflate (gzip) のアルゴリズムを視覚化してみた

DeflateとそのバリエーションであるZIPやgzipは、HTTPにおけるデータ転送やファイル圧縮など、様々な場面で使われる圧縮アルゴリズムです。

そのアルゴリズムの解説としてはslideshare.net/7shi/deflateを始め優れたものがいろいろあるかと思いますが、実際のデータをエンコードして視覚化できるものがないのが不満でした

というわけで、作った注1

ソースコードは、github.com/kazuho/visiflateにあります。

こいつをダウンロードして動かすと、記事の末尾の出力結果のようにダラダラと、どのようにエンコードされているかが表示されます。

この出力を見ることで、例えば、不思議の国のアリスのテキストをgzipすると

テキスト圧縮長
(ビット)
複製位置
"Alice was beginning to get very tired of sitt"224なし
"ing "1329バイト前
"by her"32なし
" si"1115バイト前
"st"9なし
"er "117バイト前
"on the bank, an"72なし
"d of "1342バイト前

のような感じにエンコードされることが分かります。

自分の好きなデータで試すことができて便利!という話でした。


PS. 以下は実行結果です。

% make
% gzip < alice.txt > alice.txt.gz
% ./puff -10 alice.txt.gz
puff() succeeded uncompressing 1328 bytes
8 compressed bytes unused
inpos=406,inbits=224,outpos=0,outbytes=45
    41 6c 69 63 65 20 77 61 73 20 62 65 67 69 6e 6e 69 6e 67 20 74 6f 20 67 65 74 20 76 65 72 79 20 74 69 72 65 64 20 6f 66 20 73 69 74 74
    A  l  i  c  e     w  a  s     b  e  g  i  n  n  i  n  g     t  o     g  e  t     v  e  r  y     t  i  r  e  d     o  f     s  i  t  t 

inpos=630,inbits=13,outpos=45,outbytes=4,distance=-29
    69 6e 67 20
    i  n  g    

inpos=643,inbits=32,outpos=49,outbytes=6
    62 79 20 68 65 72
    b  y     h  e  r 

inpos=675,inbits=11,outpos=55,outbytes=3,distance=-15
    20 73 69
       s  i 

inpos=686,inbits=9,outpos=58,outbytes=2
    73 74
    s  t 

inpos=695,inbits=11,outpos=60,outbytes=3,distance=-7
    65 72 20
    e  r    

inpos=706,inbits=72,outpos=63,outbytes=15
    6f 6e 20 74 68 65 20 62 61 6e 6b 2c 20 61 6e
    o  n     t  h  e     b  a  n  k  ,     a  n 

inpos=778,inbits=13,outpos=78,outbytes=5,distance=-42
    64 20 6f 66 20
    d     o  f    

注1: 元にしたのは、zlibに付属する参照実装であるPuff

9 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. شركة نقل عفش بالدمام الشرق الاوسط متحصصه فى نقل عفش واثاث بالدمام ونقل العفش بالخبر كما انها توفر شركة نقل عفش بالجبيل والخبر وشركة نقل عفش بالقطيف والاحساء وجميع خدمات نقل العفش والاثاث بالمنطقة الشرقية بارخص اسعار نقل عفش بالدمام وتقدم ايضا شركة تخزين عفش بالدمام والخبر
    نقل عفش بالدمام
    شركة نقل اثاث بالدمام
    شركة نقل اثاث بالخبر
    شركة نقل اثاث بالجبيل

    ReplyDelete