テーブルの圧縮管理

テーブルの作り方が分かった瞬間もの凄く内容が理解できるようになったので圧縮の方法も書いておく。後でブロックサイズという物を用意するが、今は簡単のため、全てを圧縮する物として話を進める。

とりあえず各テーブル毎にソート済みの64-bit値の配列を持っている。次に隣同士のxorを取る。結果のMSB(1のとこ)の位置は[0, 63]の値を取るので、それぞれ頻度表を作りHuffman符号を作る。そしたらまず最初のfingerprintをそのまま書き込む。次に、最初のfingerprintと次のfingerprintのxorを取り、MSBの位置に応じて対応するHuffman符号を出力。そしたらxorした結果のMSBより下のbitをそのまま出力する。次に2個目と3個目のxorを取り…といった感じに繰り返し処理していく。

次に復号方法。まず、最初のfingerprintを得る。次にHuffman符号を読み込んで、対応するMSBの位置を得る。そうしたら次の「MSBの位置」-bitを読み込んでくっつける。そしてそれに最初のfingerprintをxorした物が2個目のfingerprint。次は3個目のfingerprintのMSBの情報を読んで、その下の情報を読んで…ってやっていくと全部復元できる。

以上が圧縮の方法である。得られたデータはこんな感じになりますよ↓。

f[i] = fingerprints
^ はxor
msb(n) = MSBの1bitの位置
h[n] = MSBの位置に対応した可変長の符号

データ
f[0] h[msb(f[1]^f[0])] f[1]^f[0]の下位msb(f[1]^f[0])-bit f[2]^f[1]の同じデータ ...

例えば11111101と11111110が隣接していた場合はxorを取って00000011。
MSBは1-bit目なので h[1] 1と言うデータが出力されることになる。

ただ、よく考えてみるとこのデータに対して探索しなければならないので、全部丸ごと圧縮してしまうと、伸張してから効率よく探索するか、伸張しながら線形探索するといったアホな事になってしまう。そこで、ブロックという概念を導入する。考え方は簡単で、ある程度のサイズまで出力されたら、次のfingerprintを最初のfingerprintとして、そこから新たな圧縮ブロックを生成すると言った感じになる。そして、ブロックの「最後の」fingerprintをそのブロックのキーとして保持する。そうすれば、まず効率よく目的の要素が入っているブロックを探した後に、そこだけ局所的に伸張して比較できる。

あーもっとうまく説明できるようになりたい。