Array::Gap - naoyaのはてなダイアリー明日は一ヶ月ぶりのIIR輪読会 です。主催のたつをさんから「教科書の話題から何か適当に実装せよ」という課題が出ていたので、5章 のインデックスの圧縮の所で見た Variable byte codes (以下 VB code) を使った圧縮の実装を作ってみました。 整列済みの整数を圧縮する手法 ここでの圧縮のポイントは二つ。 昇順に並べられた整数を、整数そのままの数で扱うのではなく、一つ前の要素との差で扱う。差で扱うと 21,314,156 → 21,314,157 という数は "1" というより小さい数で表現することができる。(整列済みなので、差が分かれば逆の操作で復元が可能) 32 ビット int の整数を固定長 32 ビットで表現するのではなく可変長バイトで表現する。(これが VB code) VB code なら小さな数字は 32ビット = 4バイトよりも小さなビット数で表現できる
