如果你仔细读了我曾经在先前的一篇博文中提及的《如何在爬网过程中检测到几乎相同的网页》（Detecting Near-Duplicates for
Web Crawling）一文，你可能会对simhash算法的工作原理感到好奇。该算法没有在此文中详述，作者只是提及了他引用的由Moses
Charikar撰写的《扰动算法中的近似度估算技巧》（Similarity Estimation Techniques from
Rounding
Algorithms）一文。不幸的是，simhash这个词并未在Charikar的论文中提及，如何将两者联系起来对一般读者而言并非是显而易见的。
然而，论文中的一些描述对我们理解整个概念还是提供了有用的帮助。
在经典的信息提取（Information Retrieval，IR）算法中，要估算两篇文本的相似度一般是将其转换成所谓的“特征向量”，然后计算这些向量在“欧几里德空间”中的夹角。如果两篇文本是完全相同的，它们之间的夹角为0。它们之间的差异越大，夹角也越大。
你可以把特征向量想象成高维度空间中的一个点。其中每一个维度对应于特征向量中的一个特征值。用一个实际的例子来说，假设我们的特征值就是英文单词，那么这
个高维度空间的坐标标签就是象quick、brown、fox这样的英文单词，而不是我们熟知的x、y、z。这个空间的维度数就是英语中的单词的数目。
一篇文本可以用一个在此高维度空间中的点（即特征向量）表示。这个特征向量的第i个元素代表了单词w，可能取以下值：
- 0，如果单词w没有在此文本中出现
- 1，如果单词w在此文本中至少出现一次
- k，如果单词w在此文本中出现k次，或者我们要表示这个单词出现的重要性（权重）为k
任意给定两个向量，你就可以计算出它们之间的夹角（就是它们的点积的arccos值）。
在Charikar的论文中，他设计了一种“轮廓”特征向量。两个“轮廓”之间的相似性就表示了两个特征向量之间的相似性。所谓“轮廓”，就是一个对象的浓
缩的表示，例如字符串的哈希码。由于“轮廓”是高度浓缩的，他们在存储和计算上有很大的实用价值。论文第三章“用于向量的随机超平面哈希函数”
（Random Hyperplane Bashed Hash Functions for
Vectors）描述了一种将n维特征向量浓缩到k维比特向量（n远大于k）的方法。具体的做法是：
- 在目标向量空间中随机选择k个向量，假设为r_i，（0 <= i < k）
- 定义k个单比特的哈希函数如下：
- h_i(v) = 1，如果dot(r_i, v) >= 0
- h_i(v) = 0，如果dot(r_i, v) < 0
这个长度为k比特的浓缩的哈希值就是将特征向量v依次用这k个哈希函数计算后，将结果串起来。
数学上可以证明，将上述的”轮廓“算法应用于两个向量u和v，sketch(u)和sketch(v)相等的概率是1 - theta / pi。其中theta是向量u和v之间的夹角。
现在，整个链条中的最后一环是，simhash和这里描述的”轮廓“算法是怎么联系起来的？答案是，它们基本上就是一回事。Charikar的论文中没有明
确地证明它们是等价的，考虑到这篇博文已经够长的了，我在这里也不想做这个数学证明。如果你有兴趣，请详细地读一下Charikar论文的第三章，也许你
能自己完成这个证明。
没有评论:
发表评论