局部敏感的哈希——SimHash

说明

一般的哈希考虑的是均匀分布，即使是对于一个极大的文本串中仅有一处偏差也可能引起极大的计算差异

而谷人希出品的 SimHash 是一种具有局部敏感性特征的哈希，简单地说就是克服了前面提到的的缺点~~（讲道理应该叫局部不敏感吧）~~

因此 SimHash 不仅能判断是否相等，还能判断是否高度重复

定义

$f e a t u r e$ ：特征，一般是文本串中的关键字

$w e i g h t$ ：权重，由对应的 $f e a t u r e$ 经过哈希得出，是个整数

$f i n g e r p r i n t$ ：指纹，文本串最终形成的产物，是个整数

当两个 $f i n g e r p r i n t$ 的 hamming 距离（就是相互 xor 的 bitcount）小于一定值时，我们认为文本串是高度重复的

指纹的生成过程

假设有 $n$ 个特征，那就有对应的 $n$ 个权重 $weight_i$$

依次考虑这 $n$ 个权重的每一位 $j$ ，若为 $1$ 则对 $f i n g e r p r i n t_{j}$ （表示第 $j$ 位）贡献 $1$ ，否则贡献 $- 1$

统计完后对 $f i n g e r p r i n t$ 的 $j$ 位重新设置，若 $j$ 位的贡献 $< 0$ 则置为 $0$ ，否则置为 $1$ （其实就是概率上的对半分）

完了，就是这么简单！

用途

搜索引擎过滤重复结果、Online Judge 防作弊等都可用到

完成版

这里提供一个简单的实现

为了方便，这里对每一个 ASCII 都作为关键字

为了方便 (x2)，对权重的哈希处理采用 mt19937 随机数映射（rand() 不够大，char 又太小）

bitcount 因为采用了打表 + 分治的做法导致看起来复杂了点。。

随便试了一下，对于长文本的效果确实不错（应该没写错），谷歌牛皮

#include<bits/stdc++.h>
using namespace std;

class Simhash {

private:
    array<int,0x100> bitmask;
    array<int,0x80> transfer;
    mt19937 roll;

    void init_bitmask() {
        for(int i = 0xff; i; --i) {
            if(bitmask[i]) continue;
            for(int j = i; j; j -= j&-j) {
                ++bitmask[i];
            }
            for(int j = i, k = bitmask[i]; j;  j -= j&-j) {
                bitmask[j] = k--;
            }
        }
    }
    void init_transfer() {
        for_each(transfer.begin(),transfer.end(),
            [&](int &that) { that = roll(); } 
        );
    }
    int bitcount(unsigned int bit) {
        return bit ? bitmask[bit & 0xff] + bitcount(bit>>8) : 0;
    }
    int get_fingerprint(const string &str) {
        int fingerprint = 0;
        for(int i = 0; i < 32; ++i) {
            int cnt_i = 0;
            for(auto feature : str) {
                int weight_i = transfer[feature] >> i;
                if(weight_i &1) ++cnt_i;
                else --cnt_i;
            }
            if(cnt_i >= 0) fingerprint |= 1<<i;
        } 
        return fingerprint;
    }

    Simhash(): bitmask{0}, transfer{0}, roll{19260817} {
        init_bitmask();
        init_transfer();
    }

public:
    Simhash(const Simhash &) = delete;
    Simhash& operator = (const Simhash &) = delete;
    static Simhash& instance() {
        static Simhash simhash;
        return simhash;
    }
    bool operator () (const string &s1, const string &s2, int n = 3) {
        return bitcount(get_fingerprint(s1) ^ get_fingerprint(s2)) < n;
    }
};

int main() {
    string s1, s2;
    auto &simhash = Simhash::instance();
    while(cin >> s1 >> s2) {
        cout << simhash(s1,s2) << endl;
    }

    return 0;
}