What we talk about when we talk about Technology

技術について語ります。

VB Code

整数列を圧縮する方法にVB Codeというアルゴリズムがあります。
整数の型がUInt32であった場合、整数列の長さは32 * 配列のサイズとなります。
このとき、この32桁(232)に対し小さな値、例えば6は00000000 00000000 00000000 00000110という32桁の数字になり、ぱっと見で感じるように先頭の0が冗長となります。
この冗長な0を省略することで圧縮するアルゴリズムVB Codeです。

具体的には、VB Codeではそれぞれのバイトの先頭の1ビットを、終端かどうかを表すフラグとして使います。 (フラグが立っていれば終端)
そうすることで0だけで表されていたバイトを省略することができます。
例えば先程の6の場合、00000000 00000000 00000000 00000110と表されていましたが、最後の1バイ00000110の先頭のビットを1に変換し、その前についていた00000000 00000000 00000000を省略するため、VB Codeで表すと1000 0110と表されるのでサイズは8/32 = 1/4となります。

先頭の1ビットを終端をあらわすフラグとして用いるため、1バイトで表せる値は127(11111111)までです。
128よりも大きな値のときは、そのまま2バイト目の一番下の桁が128(28)を表すことになります。

00000001   10000000 = 128
       ↑   ↑
     2^8   フラグ

よって例えば150(28 + 24 + 22 + 2)はVB Codeでは00000001 10010110と表せます。

このVB CodeをSwiftで実装したものが以下です。
次は実際にファイル読み込んでどのくらい圧縮されるのか確かめてみたいと思います。

参考

[Web開発者のための]大規模サービス技術入門 ―データ構造、メモリ、OS、DB、サーバ/インフラ (WEB+DB PRESS plusシリーズ)