optimal number of tables - nobu-qの日記

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は恒偽なので意味無い。

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