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

12 comments:

  1. This comment has been removed by the author.

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

    ReplyDelete
  3. This article is interesting and useful. Thank you for sharing. And let me share an article about health that God willing will be very useful. Thank you :)

    Obat gatal Kudis/gudik
    Walatra Gamat Emas Kapsul
    Vitamin Untuk Kesehatan Anak
    Penyebab sering mimisan
    Cara Mengatasi Cacar Air
    Cara Menghilangkan Kantung mata
    Obat Telinga Berkerak dan Berair

    ReplyDelete
  4. Free download Poweramp apk Pro view website
    Showbox Pro apk for android latest version website

    ReplyDelete