SimHash

定义

SimHash 是 Moses Charikar 提出的一种局部敏感哈希算法,可将任意长度的文档压缩成固定长度(常用 64 位)的指纹,且内容相近的文档指纹的海明距离也小,与普通哈希"微小改动即完全不同"的特性相反。

原理

对文档提取带权特征(如分词后的词项),将每个特征哈希为定长比特串;维护与指纹等长的计数数组,特征哈希某位为 1 则该位计数加权重,为 0 则减权重;最终计数为正的位取 1、为负取 0,得到指纹。比较两文档时计算指纹海明距离,小于阈值即判为近似重复。

应用

SimHash 因被 Google 用于网页抓取去重而闻名,也广泛用于新闻聚合去重、论文查重预筛与舆情分析。

特点

优点是指纹极小、比较极快、适合海量数据;缺点是对短文本效果较差,特征选取与权重设计对效果影响大。