不过,这种构造局部敏感哈希函数的方式也有一些缺陷:在原来的空间中,不同维度本来是有着不同权重的,权重代表了不同关键词的重要性,是一个很重要的信息。但是空间被 n 个超平面随机划分以后,权重信息在某种程度上就被丢弃了。
那为了保留维度上的权重,并且简化整个函数的生成过程,Google 提出了一种简单有效的局部敏感哈希函数,叫作 SimHash。它其实是使用一个普通哈希函数代替了 n 次随机超平面划分,并且这个普通哈希函数的作用对象也不是文档,而是文档中的每一个关键词。这样一来,我们就能在计算的时候保留下关键词的权重了。这么说有些抽象,让我们一起来看看 SimHash 的实现细节。
方便起见,我们就以 Google 官方介绍的 64 位的 SimHash 为例,来说一说它构造过程。整个过程,我们可以总结为 5 步。
- 选择一个能将关键词映射到 64 位正整数的普通哈希函数。
- 使用该哈希函数给文档中的每个关键词生成一个 64 位的哈希值,并将该哈希值中的 0 修改为 -1。比如说,关键词 A 的哈希值编码为 <1,0,1,1,0>,那我们做完转换以后,编码就变成了 <1,-1,1,1,-1>。
- 将关键词的编码乘上关键词自己的权重。如果关键词编码为 <1,-1,1,1,-1>,关键词的权重为 2,最后我们得到的关键词编码就变成了 <2,-2,2,2,-2>。
- 将所有关键词的编码按位相加,合成一个编码。如果两个关键词的编码分别为 <2,-2,2,2,-2> 和 <3,3,-3,3,3>,那它们相加以后就会得到 <5,1,-1,5,1>。
- 将最终得到的编码中大于 0 的值变为 1,小于等于 0 的变为 0。这样,编码 <5,1,-1,5, 1> 就会被转换为 <1,1,0,1,1> 。
通过这样巧妙的构造,SimHash 将每个关键词的权重保留并且叠加,一直留到最后,从而使得高权重的关键词的影响能被保留。从上图中你可以看到,整个文档的 SimHash 值和权重最大的关键词 word 2 的哈希值是一样的。这就体现了高权重的关键词对文档的最终哈希值的影响。此外,SimHash 通过一个简单的普通哈希函数就能生成 64 位哈希值,这替代了随机划分 64 个超平面的复杂工作,也让整个函数的实现更简单。