北京SEO

Charikar的simhash算法对检测数万亿的存
储级别的相似网页是非常实用的。作为指纹技术
的simhash具有相似文档的指纹只存在很小位数
的不同特性。在detecting near-duplicates for web
crawling一文中验证了,对于8B的网页,64位的
指纹和k=3是合适的。Simhash是一种降维技
术,可以将高维向量映射为位数较小的指纹。它在
网页中的应用过程如下:首先将文档转化为特征码
的集合,每个特征码附有一个权值。特征码的生成
采用IR技术,比如分词、大小写转换、停止词去除。
一个附有权值的特征码的集合构成一个高维向量,
通过simhash可以将这个高维向量转化为f位的
指纹,f的值很小,比如64[3]。
给出一个从文档中提取的带有权值的特征码
集合,通过simhash生成f位指纹的过程如下:首
先生成一个f维的向量V,每一维都初始化为0。
将每个特征码哈希为f位的哈希值。这些f位的
哈希值可以将V的f个元素增加或减少它所对应
的权值大小的值。过程如下:如果哈希值的第i位
 

对应的值是1,就将V的第i个元素增加它所对应
的权值大小的值;如果哈希值的第i位为0,就将V
的第i个元素减去它对应的权值大小的值。当所
有的特征码都这样处理完,V中有的元素为正,有
的为负。这些元素的符号决定了最终指纹的相应
位数上的值[4~5]。
那给出一个刚抓取的网页的64位的指纹,如
何快速发现有哪些指纹和它最多相差3位呢?
假设有8B的64位的指纹,我们要在微秒级的
时间里判断其中是否有和要查询的指纹F最多有
3位不同,首先探讨两种简单但并不切合实际的方
法。第一种,为所有存储的指纹建立一张排序表,
给定要查询的指纹F,检索该表查找和F的海明距
离最大是K的指纹F′。因要检索的次数太大而不
切合实际,如果是64位的指纹,K的值为3,那么
需要C(64,3)=41664次。另一个改进的方法是
预先计算出和所有F′的海明距离最大是K的指
纹。这种方法的预先计算量也因太大而不切实际:
是表中指纹数的41664倍之多。
设想一个2d由f位随机指纹组成的排序表,
其中最高的d位几乎相当于一个计数器,因为对很
少有这d位重复的,另一方面,低f-d位几乎是
随机的。
选择一个d′,使得|d′-d|的值很小,因为表是有
序的,一次检测就能够找出所有和F′在最高的d′位相
同的指纹,因为|d′-d|的值很小,所有符合要求的指
纹数目也比较小,对于其中的每一个符合要求的指
纹,我们可以轻易的判断出它是否和F最多有K位
不同(这些不同很自然的限定在低f-d′位)。
上面介绍的方法帮我们定位和F有K位不同
的指纹,多有不同的位被限定在低f-d′位中。这
对大部分情况来说是合适的,为了覆盖所有的情
况,需要建立一小部分附加的表。
我们建t个表:T1,T2,……Tt。每一个表都
有两个相关的量:一个整数pi和一个f位指纹上
的排列πi。Ti是对每一个指纹应用排列πi后形
成的有序表。给定一个指纹F和整数值K,我们
并行的检索这些表:
第一步:找出Ti中所有排列后最高Pi位是和
πi(F)的最高Pi位相同的指纹。
第二步:对所有第一步中查找出的排列后的指
纹,查看它是否和πi(F)最多有K位不同。
举例如下:假设f=64,k=3,那么近似网页的
指纹最多有3位不同。假设我们有8B=234的已
有指纹,即d=34。我们有不同的设计,每种设计
有不同的排列集和PI值。
20个表:把64位分成6块,分别是11,11,11,
11,10和10位。共有C(6,3)=20种方法从6块
中选择3块。对于每种选择,排列π使得选出的块
中的位成为最高位(有几种这样的排列,我们统一
的随机选择其中一种)。Pi的值就是选出的块中
的位数的总和。因此Pi=31,32,或者33。平均每
次检测返回最多234~31个排列后的指纹。
16个表:把64位分成4块,每块有16位,共有
C(4,1)=4种方法从4块中选择一块,对于每种选
择,我们把这48位再分割成4块,每块有12位。
共有C(4,1)=4种选择方法。对表的排列使得选
出的块中的位成为最高位。Pi的值是28。平均每
次检测返回最多234-28个排列后的指纹。