例のnear-duplicatesを快適にdetectingしちゃう論文の話

11/17追記: 勘違いしてたのでこっちに加筆。参考までにこっちも残しておく。

テーブル化はある程度理解できたのかなぁ。とりあえずテーブルの作り方、そこからの探し方の雰囲気擬似コード。探す方は効率とか全然考えて無くてあくまで雰囲気。なんかuniqueっぽいことしてるけど、数が限られてるし、一回一回の処理のコストは単純なHamming距離の計算の方が低いと思うので(要検証)、集合の要素とfを全部比較しちゃっても良いんじゃないかとも思う。Hamming距離の素敵な計算方法はきっとHacker's Delightを読めば何とかなるはずだ。うん。

とりあえず説明を言葉に出来なかったので頭の中の俺言語を直した擬似コードだけメモっておく。論文の中の16-16-16-16の奴を雰囲気で書いてみた。

uint64 mask1[4] = { 0xffff, 0xffff0000, 0xffff00000000, 0xffff000000000000 };
uint64 mask2[4] = { 0xfff, 0xfff000, 0xfff000000, 0xfff000000000 };

uint64 shrink(uint64 f, uint64 m) {
    fからmの1が立っている部分だけを繋げて返してくれる素敵な関数;
    // 例えばf=1101001, m=0011100だったら、11(010)01の010を返す
}

set<uint64> table[4][1 << 16][4][1 << 12];

// 既存の集合に追加するとき
f; // ←追加する奴

for (int m1 = 0; m1 < 4; m1++) {
    for (int m2 = 0; m2 < 4; m2++) {
        table[m1][shrink(f, mask1[m1])][m2]
            [shrink(shrink(f, ~mask1[m1]), mask2[m2])].insert(f);
    }
}

// 既存の集合から見つけるとき
f; // これとk-bit以下のHamming距離の奴を見つける
set<uint64> found;

for (int m1 = 0; m1 < 4; m1++) {
    for (int m2 = 0; m2 < 4; m2++) {
        found.insert(table[m1][shrink(f, mask1[m1])][m2]
            [shrink(shrink(f, ~mask1[m1]), mask2[m2])]の中身);
    }
}

for_each(ff in found) {
    fとffのHamming距離が3以下ならnear-duplicates
}

とりあえずこれを日本語に直すのは俺にはレベルが高すぎる。英語できっちり書いてるGoogleの中の人は本当に凄いと思う。

後は圧縮とかの部分を読んで頑張って実装レベルまで持って行かないと。