大規模サービズ技術入門に紹介されている圧縮プログラミングを試してみます。
圧縮対象のデータは
http://gihyo.jp/book/2010/978-4-7741-4307-1/support#supportDownload
からダウンロードできるeid_tags.txtというデータです。
中身は「タイトル 数字1,数字2・・」と一行ずつデータが書かれています。
整数列を圧縮することでこの180MBのデータを何MBになるのか、を確かめてみます。
何故データの圧縮が必要なのか
大きなデータを扱う際,そのデータがメモリに乗るか乗らないかで速度に大きな差がでてしまう。
メモリからデータを読む速度と,ディスクから読む速度は数十万倍くらいディスクから読む方が遅くなる。
なので、大きなデータを圧縮してメモリに乗り切るサイズにすることが必要。
VB CODE(Variable Byte Code)について
VBCodeは整数の符号化方法の1つ。
一般に整数は固定長バイナリ符号で書き込まれる。
32bit intの5なら00000000 00000000 00000000 00000101
00000000 の部分が無駄なので、これを圧縮する。
例えば、5だと10000101と圧縮できる。これは先頭の1bitが「このバイト列で終わる」というフラグの意味になっている。
130だと、00000001 10000010となる。
まず最初のバイト列の先頭は0なので、このバイト列では終わらない事がわかる。
次のバイト列を見てみると先頭が1になっているのでこのバイト列で終わり。
注意すべき点は最初のバイト列の最後のビットが128という数字を表すことになっている点（各バイト列の最初はフラグに使用するため）
実装(1) VBCodeの実装
VBCodeを実装してみる。本にのっている疑似コードをpythonで書く。
import struct
def encode(num):
bytes = [] while True:
bytes.insert(0,num%128)
if num < 128:
break
num /= 128
bytes[-1] += 128
return struct.pack(‘%dB’ % len(bytes),*bytes)
def decode(bytes):
numbers = [] n = 0
bytes = struct.unpack(‘%dB’ % len(bytes),bytes)
for b in bytes:
if b < 128:
n = 128*n + b
else:
n = 128*n + (b – 128)
numbers.append(n)
n = 0
return numbers
実装(2) ファイルのエンコード・デコード
先に作ったVBCodeのencode,decodeをしてくれるモジュールを使用してファイルをエンコード/デコードする。
（雑な実装ですいません＞＜）
(エンコード）
#coding utf-8
import vb_code as vb
import binascii
import struct
f = open(‘eid_tags.txt’,‘rw’)
outFile = open(‘eid_tags_encode.bin’,‘ab’)
for line in f:
title,content = line.split("\t")
params = [x for x in content.split(",")] vb_vals = [] params_len = 0
for p in params:
val = vb.encode(int(p))
params_len += len(val)
vb_vals.append(val)
row = "{}{}{}".format(struct.pack(‘2i’,len(title),params_len),title,”.join(vb_vals))
outFile.write(row)
（デコード）
#coding utf-8
import vb_code as vb
import struct
f = open(‘eid_tags_encode.bin’,‘rb’)
while True:
bytes = f.read(8)
if not bytes:
break
title_len,params_len = struct.unpack(‘2i’,bytes)
title = f.read(title_len)
params = [] print(title)
for p in vb.decode(f.read(params_len)):
print(p)
注意すべき点は、バイナリデータを扱っているのでカンマやタブなどの文字を区切り文字とすることができない点。
なので、最初の4バイトに「タイトル文字列の長さ」,次の4バイトに「データ文字列の長さ」を格納している。
デコード時に最初に8バイト分読み取っているのはこの長さを得るため。
この長さの分を「1つのデータ」として区切る。
結果(1)
エンコードの結果、180MBが85MBにまで削減された。
デコードもちゃんと出来ているので問題なさそう。
データの特徴を活かして更に圧縮
今回の圧縮対象のデータには、10,32,45,55・・のようにソートされているという特徴がある。
なので、これまでの値との差分だけを保存してやればデコードができる。
例えば10,32,45,55であれば、「10,22,13,10」となる。
VBCodeは数字が小さいほど圧縮率が高まるので、良い方法と言える。
実装(3) 先のエンコード/デコードするプログラムを改良する
（エンコード）
#coding utf-8
import vb_code as vb
import binascii
import struct
f = open(‘eid_tags.txt’,‘rw’)
outFile = open(‘eid_tags_encode.bin’,‘ab’)
for line in f:
title,content = line.split("\t")
params = [x for x in content.split(",")] vb_vals = [] params_len = 0
sum_param = 0
for p in params:
p = int(p)
p -= sum_param
sum_param += p
val = vb.encode(p)
params_len += len(val)
vb_vals.append(val)
row = "{}{}{}".format(struct.pack(‘2i’,len(title),params_len),title,”.join(vb_vals))
outFile.write(row)
（デコード）
#coding utf-8
import vb_code as vb
import struct
f = open(‘eid_tags_encode.bin’,‘rb’)
while True:
bytes = f.read(8)
if not bytes:
break
title_len,params_len = struct.unpack(‘2i’,bytes)
title = f.read(title_len)
params = [] print(title)
sum_param = 0
for p in vb.decode(f.read(params_len)):
print(int(p) + sum_param)
before_param += int(p)
エンコード,デコードともにこれまでの値をsum_paramとして保存し、その差だけを符号化,復号化している。
結果(2)
エンコードの結果、180MBが41.5MBにまで削減された。
因みにzipで圧縮したら55.7MBだったのでそれより良い圧縮率。
やはりデータの特性に合わせた圧縮方法を選択することでより良い結果が得られることがわかった。
所感
バイナリ扱うのって慣れてなくて難しい・・
