金相場

misc

最近金の相場が良いようで、スロ屋でコインを買うだけ買って換金する人、換金所以外で同額買い取りをしている人が増えている模様。ちなみに、スロ屋だと2500円相当の金が今日現在3000円近くで買い取られている。万枚だしたら数万得する計算。換金所涙目。これで売る人が増えたらどの程度相場下がるんだろうなぁ。

optimal number of tables

study memo

Detecting near-duplicates for web crawling

3.1.2の式の意味を考えてみた。fはfingerprintのbit数、kは最大許容Hamming距離、2^dは比較するfingerprintの数。pminはテーブルでチェックしたい(処理をやり過ごしたい)最低bit数。定数τはこれ以下の時はテーブル使わずに直接処理するというbit数、すなわち d - pmin。rはブロックの数。比較するbit同士が違う部分を簡単のため「誤り」と表現する。4つのパラメータ(f,k,d,pmin)を用いて以下の関数Xを計算することで、最小のテーブル数を計算することができる。

X(f, k, d) = \left\{\begin{array}{ll}1 & \text{if }d \leq \tau \\ min_{r>k}\text{ }{}_rC_k X(\frac{fk}{r}, k, d - \frac{(r - k)f}{r}) & \text{otherwise} \\ \end{array}\right.

上は閾値未満以下ならテーブルが必要ないという事で1を返す。rCkは誤りを含んだブロックの選び方。次に、f/rはブロックの平均長(bit)なので、fk/rは誤りを含んだブロックの長さを表す。再帰的にそのブロックに必要な最小のテーブル数を求めている。それに先ほどの組み合わせを掛ければ最適なテーブル数が求まるという話。最後に d - (r - k)f/r だが、r-kは誤りを含んでいないブロックの数、f/rは平均長というわけで、残りのチェック出来ていない部分の長さ(bit)を表す。

ちなみに定数τは当然の事ながらXの引数のdではなく、最初にXに渡したdの値を元に計算しないといけない。つーかそうじゃないとd < d - pminは恒偽なので意味無い。

漸化式って凄いね(こういうのを漸化式と呼ぶのか知らんけど)。俺は三項間漸化式の一般項求められないけどね関係ないけど。良いよ良いよどうせ俺が計算できなくてもプログラムが勝手に計算してくれるから(つд`)

テーブルの作り方が違ったようです

study memo

論文のやり方だと、各テーブル毎にπという関数を用意。この関数はnブロック中、テーブル毎に固有なkブロックを先頭p-bitになるように移動する。T[i].insert(π(f))と言うイメージっぽい。Tの中身はソートされている。これでバイナリサーチとか書かれていた意味が分かった。

俺が最初に勘違いした方法では、問答無用で2^pi個要素がある配列を作らなければならなかったため、明らかにこっちの方が省スペース。しかもまとまった一つのでかい配列が出来るので、後に書かれているHuffman符号を使った圧縮もかなり効率的に行うことができる。ｶｼｺｽ。

テーブルの圧縮管理

study memo

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

とりあえず各テーブル毎にソート済みの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をそのブロックのキーとして保持する。そうすれば、まず効率よく目的の要素が入っているブロックを探した後に、そこだけ局所的に伸張して比較できる。

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