VB Code(Variable Byte Code)で整数データの圧縮

はじめに

大規模サービス技術入門を読んでいてVB Codeという圧縮アルゴリズムを知りました。
私は大学の授業で習ったハフマン符号しかわからず、他の圧縮アルゴリズムについては無知だったので、学習のためにVB Codeについてまとめてみたいと思います。

データ圧縮の重要性

大きなデータを圧縮することのメリットはディスクI/Oの負荷を軽減できる点です。
ディスクはメモリーに比べ10万倍から100万倍遅いと言われています。メモリーは電気的な部品なのでポインターを高速に動かしデータを取得できますが、ディスクは円盤を回転させ、そこからデータを読み取ります。つまり、メモリとは違って回転などの物理的な動作を伴っています。　
そして円盤の回転をなるべく減らすためにデータ圧縮が必要なのです。

VB Code(Variable Byte Code)

VB Codeは整数の符号化手法の一つです。
現代のパソコンでは5という整数を固定長32ビットで0...00000101と表現します。これをバイナリ符号と言いますが、この表記だと下位1バイト意外は冗長で無駄です。そこでVB Codeの符号方法を使うと、10001010になります。

数値                  固定長バイナリ                VB Code
5        00000000 00000000 00000000 00000101    10001010
130      00000000 00000000 00000000 10000010    00000001 10000010

VB Codeでは先頭の1ビットがフラグになり、残りのビットでバイナリ符号を表しています。　
上の5を見ると頭の1がこの整数のビット列がこのバイトで終わりということ示しています。130の方は先頭のバイトの頭が0なのでそのバイトでは終わらないことを示し、二つ目のバイト列の頭に1があるので、そのバイトで終わることを示しています。00000001下位7ビットで128を、2バイト目の10000010下位7ビットで２を表しているので128+2で130になります。

疑似コード

疑似コードを参考にPythonで書いてみました。

vb_code.py

from struct import pack, unpack

def vb_encode_number(number):
    byte_list = []
    while True:
        byte_list.insert(0, number % 128)
        if number < 128:
            break
        number = number // 128
    byte_list[-1] += 128
    return byte_list

def vb_encode(number):
    byte_list = vb_encode_number(number)
    bytestream = pack('%dB' % len(byte_list), *byte_list)
    return bytestream

def vb_decode(bytestream):
    n = 0
    numbers = 0
    bytestream = unpack('%dB' % len(bytestream), bytestream)
    for byte in bytestream:
        if byte < 128:
            n = 128 * n + byte
        else:
            n = 128 * n + (byte - 128)
            numbers.append(n)
            n = 0
    return numbers

色々な記事を参考に書きましたが、structライブラリは初めて使い色々理解するのに大変でしたが、とてもいい経験になりました。公式ドキュメントを参考に

最後に

Twitterでこの本大規模サービス技術入門を見つけたのですが学ぶことがたくさんあり、読んでて楽しいです。僕のような初学者はこの本で知識増やすのがいいと思います。