前回は、大規模データ処理実践入門としてMySQLなどで処理できない規模のデータを対象に計算を行いたい場合の対処法についてまとめた。ここでは、データサイズ、I/O高速化との関係を意識する必要がある圧縮プログラミングの実装について解説する。
１ [課題]整数データをコンパクトに持つ
整数データをコンパクトに持つ
テキストで152MBのCSV（Comma Separated Values）データを、整数の符号化を工夫してサイズを半分以下にして扱えるようにする。
出題意図
- 大きな整数列をコンパクトに持つ方法を知ること。コンパクトにできるとディスクI/Oを軽減でき、高速な処理が可能になる。またRDBMSに持たせるとどうしてもかさんでしまうようなデータを最小限のサイズに抑えて扱える
- VB Codeの速度感をつかむ
- データ型のサイズなどに意識を持つ
- 検索エンジン開発での応用、機械学習やデータマイニングなどで役立つ
課題で扱うファイルの中身
- はてなブックマークのタグのデータ：perl => [25, 51, 111, …]
- テキストで持つと152MB
２ VB Codeと速度感覚
VB Code
VB Code（Variable Byte Code、可変長バイト符号）は整数の符号化手法の1つで、最小限のバイトで情報を表現するものである。
VB Codeの疑似コード
「introduction to Information Retrieval」（IIR）という情報検索の教科書参照。
ソート済み整数を「ギャップ」で持つ
- 1つ前の値とのギャップを取る
- 小さな値がたくさん、大きい値は少ない分布になる
- これをVB Codeで符号化することにより、圧縮効果が得られる
補足１：圧縮の基礎
圧縮の基礎は、記号の出現確率の確率分布を考えて、最適な符号を生成するというものである。すなわち記号の確率分布から頻出記号に短い符号を、そうでない記号には長い符号語を与えるといった、モールス信号と同じ原理である。
補足２：対象が整数の場合
整数は圧縮対象の記号そのものが値として意味を持っている。差分を取って変形するなど、整数である特徴をうまく利用して圧縮する。
３ 課題の詳細と回答例
課題の詳細
- テスト用データファイルをギャップ＋VB Codeで符号化したものを書き出すプログラムを作る
- 書き出したバイナリを復元するプログラムを作る：符号化/復号化のテストを先に用意する
- オリジナルのテキストファイルがどの程度小さくなったかを確認
- 解決したらVB Code以外の符号化手法を試す（γ符号など）
参考１：pack( )関数
pack( )関数はPerlの内部データ構造をマシンレベルの表現に変える関数で、Perlの内部のデータ構造をバイナリで吐き出すというものである。逆はunpack( )という関数。マニュアルはperldoc -f packを参照。
今回の課題に置けるpackの使いどころは、VB Codeでバイト列を生成するところと、VB Codeを実装する前にpack(‘w*’,…)で確認できるという点である。
参考２：バイナリのread/write
ファイルにバイナリを書く（write）、読む（read）ではデータの区切りにタブや改行が使えない。各データのデータ長を一緒に書き出すとよい。
参考３：プロファイリング
自分の実装の速度を調べるときにはプロファイラを使うとよい。Devel::NYTProfを使うと簡単にプロファイリングができる。
回答例と考え方
以下のように進む（詳細は省略）。
- テスト
- VB.pm
- vb_encode.pl（圧縮/符号化）
- vb_decode.pl（復号）
最後に
整数データをコンパクトに持つという課題を解くことで、大きな整数列をコンパクトに持つ方法を知ることができる。また、VB Codeの速度感をつかむことや、データ型のサイズなどに意識を持つことができる。こういった知識は、検索エンジン開発などで応用することができる。
次回は、理論・研究の実践投入であるアルゴリズムの実用化について解説する。
 |
[Web開発者のための]大規模サービス技術入門 ―データ構造、メモリ、OS、DB、サーバ/インフラ (WEB DB PRESS plusシリーズ) |
