はじめに
α（アルファ）符号・γ（ガンマ）符号・δ（デルタ）符号は、自然数を表現するための不定長ビット列です。筆者は、δ符号については、雑誌『Interface』の2002年10月号で知りました。以下、δ符号について詳細を解説します。
対象読者
データ圧縮、特に独自方式での高密度データ格納に興味がある方を対象としています。この記事を読むためには、C++の基本的な文法および演算子についての知識が必要です。クラスやテンプレート、STLなどは使用していません。
必要な環境
本稿の対象環境は、Microsoft Visual C++ 6.0以降のMicrosoft社製C++コンパイラです。一部にインラインアセンブラ、およびPentium命令を使用しています。他のC++環境への移植はさほど困難ではありません。しかし、C環境に移植する場合は、関数の多重定義に留意してください。
δ符号について
通常、データ中に数値を格納する場合、その数値が取りうる範囲を根拠に、適当なデータ領域を確保します（0～255の範囲に収まる範囲なら、当然8ビット）。ここで、必要なデータ領域を節約するために、例えば比較的小さな値が多い場合には、δ符号を用いて数値を格納すると、平易な実装の割に良好な結果が得られます。
δ符号の理解に必要な前提知識として、まずα符号とγ符号を取り上げます。
α符号
1進数のようなイメージでとらえてください。nという値を表現するには、nビットを用います。n=1の場合は、1（1ビット）となり、n>1の場合は、n-1桁だけ0のビットを列挙し、最後のビットのみ1となります。
4は、0001（4ビット）となります。
γ符号
2進数表記した数値を基準に考えます。nという値を表現するには、まずnが何ビットの値かを調べ、これをα符号で表記します。桁数を表現するこのα符号に続けて、nの2進数表記を最上位ビットを取り除いて連結します。n=1の場合は、1（1ビット）となります。一般に、nがxビットで表現できる場合、γ符号は2x-1ビットで表現されます。
4は、00100（5ビット）となります
δ符号
基本的な考え方はγ符号と同様ですが、δ符号の場合は、表現する値のビット数をγ符号で記します。n=1の場合は、1（1ビット）となります。
4は、01100（5ビット）となります。
以下に、数値とα・γ・δ符号の関係を一覧表で示します。nが2～3と8～31までの間は、γ符号の方がδ符号よりも1ビット短いものの、32以上の値ではδ符号の方が短くなることが分かります。
| n | α | γ | δ |
| 1 | 1 | 1 | 1 |
| 2 | 01 | 01 0 | 010 0 |
| 3 | 001 | 01 1 | 010 1 |
| 4 | 0001 | 001 00 | 011 00 |
| 5 | 00001 | 001 01 | 011 01 |
| 6 | 000001 | 001 10 | 011 10 |
| 7 | 0000001 | 001 11 | 011 11 |
| 8 | 00000001 | 0001 000 | 00100 000 |
| 32 | ・・・・ | 000001 00000 | 00110 00000 |
| 128 | ・・・・ | 00000001 0000000 | 0001000 0000000 |
δ符号を使ったCODECのインターフェイス関数
ここでは、データを圧縮・伸張するソフトウェアCODECのインターフェイス関数をδ符号を使って実装します。各関数の詳細は以下の通りです。
以下に、ヘッダおよびソースコードを示します。各関数の使用方法については、ヘッダのコメントを参照して下さい。
// // Delta.h // // 標準仕様のδ-符号CODECのインターフェイス関数 // // (C)2004, 05, 06 BeautyPlanets typedef unsigned char BYTE; typedef unsigned long DWORD; // // 名称 void DeltaInit(void *pWork); // 機能 δ-符号CODEC(1)の初期化を行う。 // 引数 void * δ-符号の格納先メモリアドレス // 返値 なし // 解説 CODEC側では、メモリは確保しない。 // また、負荷軽減のため、ポインタのエラーチェックを行わない。 // 初期化忘れやNULLの引き渡しをすると、確実に＊飛ぶ＊ので // 呼び出し側で責任を持つこと。 void DeltaInit(void *pWork); // 名称 BYTE *SetBoundery(); // 機能 境界調整を行う。 // 引数 なし // 返値 δ-符号列が格納された最終アドレスの次のアドレス // 解説 前述の通りδ-符号は不定長なので、末尾の1～7ビットが // メモリ上に存在する可能性がある。 // 外部からは、これらの管理情報に関与する必要はないが、 // エンコードが完了した際に、この関数を使用すると、 // 上述のアドレスを返す。この返値によって、エンコードされた // δ-符号列のデータサイズを求めることができる。 BYTE *SetBoundery(); // 名称 BYTE *Delta(DWORD dwValue); // 機能 数値からδ-符号への変換 // 引数 DWORD δ-符号へ変換する数値 // 返値 8ビットのδ-符号を、次に格納するアドレス // 解説 1つの数値をδ-符号へ変換し、指定されたバッファに出力する。 // δ-符号は不定長なので、連続して呼び出した場合は、 // 直前のδ-符号の最終ビットの次のビットから格納される。 // 返値は、これから出力するアドレスなので、この値を // チェックすることによってバッファオーバーランを防止できる。 BYTE *Delta(DWORD dwValue); // 名称 DWORD Delta(); // 機能 δ-符号からの変換 // 引数 なし // 返値 DWORD デコードした値 // 解説 δ-符号でエンコードされたデータ列のバッファから、 // デコードした数値を1つ取得する。 // メモリ範囲チェックができないので、 // 最初から取得する個数を考慮しておくこと。 DWORD Delta();
// // Delta.cpp // // 標準仕様のδ-符号CODECのインターフェイス関数 // // (C)2004, 05, 06 BeautyPlanets typedef unsigned long DWORD; typedef unsigned char BYTE; typedef unsigned short WORD; BYTE *g_pbyPtr; BYTE g_byMask; // codec初期化 void DeltaInit(void *pWork) { g_byMask = 0x80; g_pbyPtr = (BYTE*)pWork; } // bit boundery調整 BYTE *SetBoundery() { if(g_byMask != 0x80) { g_pbyPtr++; g_byMask = 0x80; } return g_pbyPtr; } // 1 bit read inline DWORD Bit() { DWORD dwRV = (*g_pbyPtr & g_byMask) ? 1 : 0; if(!(g_byMask >>= 1)) { g_byMask = 0x80; g_pbyPtr++; } return dwRV; } // n bit read inline DWORD Bits(int iCount) { DWORD dwRV = 0; BYTE by = *g_pbyPtr; for(int i = 0; i<iCount; i++) { dwRV <<= 1; if(by & g_byMask) { dwRV++; } if(!(g_byMask >>= 1)) { g_byMask = 0x80; by = *++g_pbyPtr; } } return dwRV; } // 1 bit write // 引数 DWORD bit : 出力する値(0, 1) inline void Bit(DWORD bit) { // エンコード済データの格納領域をcallocで確保する場合は、 // 次の行をコメントアウトする。 #define ALLOC_WITH_MALLOC if(bit) { *g_pbyPtr |= g_byMask; } #ifdef ALLOC_WITH_MALLOC else { *g_pbyPtr &= ~g_byMask; } #endif if(!(g_byMask >>= 1)) { g_byMask = 0x80; g_pbyPtr++; } } // n bit write // 引数 DWORD dwCode : 出力する値 // int iCount : 出力するビット数 inline void Bits(DWORD dwCode, int iCount) { DWORD dwMask = 1L << iCount; BYTE by = *g_pbyPtr; #ifdef ALLOC_WITH_MALLOC by &= ~(g_byMask | (g_byMask - 1)); #endif while(dwMask >>= 1) { if(dwMask & dwCode) { by |= g_byMask; } if(!(g_byMask >>= 1)) { g_byMask = 0x80; *g_pbyPtr++ = by; by = 0; } } *g_pbyPtr = by; } __declspec(naked) int bsr(DWORD dwValue) { __asm { mov ecx, [esp+4] bsr eax, ecx inc eax ret } } // γ符号の出力 inline BYTE *Gamma(DWORD dwValue) { if(dwValue) { if(1 == dwValue) { Bit(1); } else { /* for(DWORD dwLGamma = 2; dwLGamma < 32; dwLGamma++) if(dwValue < ( (DWORD)1 << dwLGamma ) ) break; */ DWORD dwLGamma = bsr(dwValue); if(dwLGamma < 16) { Bits(dwValue, dwLGamma * 2 - 1); } else { Bits((DWORD)0, dwLGamma - 1); Bits(dwValue, dwLGamma ); } } } return g_pbyPtr; } // δ符号の出力 BYTE *Delta(DWORD dwValue) { if(dwValue) { if(1 == dwValue) Bit(1); else { /* for(DWORD dwLDelta = 2; dwLDelta < 32; dwLDelta++) if(dwValue < ((DWORD)1 << dwLDelta) ) break; */ DWORD dwLDelta = bsr(dwValue); Gamma(dwLDelta); Bits(dwValue, dwLDelta - 1); } } return g_pbyPtr; } // α符号読込 inline DWORD Alpha() { DWORD dwCount = 1; while(!Bit())dwCount++; return dwCount; } // γ符号読込 inline DWORD Gamma() { DWORD dwLength = Alpha() - 1; if(!dwLength) { return 1; } return Bits(dwLength) + ((DWORD)1 << dwLength); } // δ符号読込 DWORD Delta(){ DWORD dwLength = Gamma() - 1; dwLength &= 0x1f; if(!dwLength) { return 1; } return Bits(dwLength) + ((DWORD)1 << dwLength); }
bsr関数について
ソースコード中、1点だけ注釈が必要と思われる箇所がありますので解説します。bsr関数は、unsigned longの値において、最も左にある1のビットの位置を得る関数です。LSBの場合は1を、MSBの場合は32を返します。bsr関数を呼び出す箇所の直前の数行のコメントは、bsr関数と同等の処理をC++のコードにて実装したものです。この値はPentium以降のCPUが持っているbsr命令の結果に1を加えて得られるものです。Pentium/MMXにおいては時間のかかる命令（11+2*n）ですが、Pentium Pro以降のCPUであれば1～2サイクルしかかからないので、インラインアセンブラを使用して命令を埋め込んでいます。
サンプルコードについて
実装例として、カンマ区切りの十進数⇔δ符号バイナリの相互変換を行う、対話型のコマンドラインツールを用意しています。Visual Studio .NET 2003のsolution形式なので、Visual Studio 6.0で使用する場合は、Win32のコンソールプロジェクトを作って利用してください。同ツールの操作方法は、実行すると表示されます。
なお、入力されたデータは、その件数を先頭に付与した形でエンコードされます。また、デコードしようとするデータは、そのδ符号のバイナリ列が含むデータ件数を、先頭にδ符号の形で格納されているものとします。
1,1,1,1(入力：十進カンマ区切り) → 4,1,1,1,1(先頭にデータ件数を付加) → 01100 1 1 1 1(δ/二進) → 67 80(出力：δ/十六進)
まとめ
ここでは、δ符号を用いたCODECのインターフェイス関数を紹介しました。本稿の続編として、δ符号の使用範囲を自然数から整数全体に拡張した応用事例と、Bit単位での入出力を完全に排除した超高速CODECルーチンを予定しています。
参考資料
- 『データ圧縮ハンドブック 改訂第2版』 Mark Nelson・Jean-Loup Gailly 著、山口英・荻原剛志 訳、ピアソンエデュケーション、2000年4月
- Interface 2002年10月号 『組み込みデータベースを使ったテキスト全文検索エンジンの実装』
