利用相似哈希判断文本近似程度

Author Avatar
AngelMsger 2月 24, 2018

SimHash是一种相似度检查算法.

另一些想法

怎样快速判断两个集合是否相等? 最直接的方法是遍历集合A, 对于A内的每个元素, 去B中查找是否存在. 但是这个算法的时间复杂度达到了O(N^2), 《数学之美》的作者吴军博士在书里提到, 谁要是面试回答他这个, 他准不会让这个人通过.

稍微好一点的办法是, 先将两个结合排序, 然后按顺序比对, 我们知道排序算法时间复杂度可降低为O(NlogN), 外加一次顺序比对, 总时间复杂度可理解为O(NlogN + N), 这比直接蛮干的O(N^2)强了不少.

还有另一种更好的方式, 利用散列表, 你可以先将集合A中的所有元素存储于散列表中, 时间复杂度为O(N), 然后遍历集合B, 对于集合B中的每一个元素, 在散列表中查找是否存在, 遍历集合B的时间复杂度为O(N), 在散列表中查找一个元素的时间复杂度为O(1), 总复杂度可理解为O(N). 我给出的复杂度与书中数据略有出入, 是因为我这里算上了整个过程, 而书中只考虑查找比较部分.

不过这都不是今天的主角, 因为书中最后给出的方法是基于信息指纹的相似哈希技术, 即SimHash.

什么是信息指纹

上面提到了信息指纹, 什么是信息指纹?

假设我们在写一个爬虫, 我们要爬取很多URL, 并且要把已经爬过的URL存下来, 以防止在可能存在的链接环路中一直兜圈子. 如果我们直接存储URL恐怕不太好, 毕竟URL千奇百怪, 有些可能非常长, 而长字符串在计算机中的比较效率是很低的.

我们这里采用一种更好的方法, 你可能听说过MD5, SHA-1之类的算法, 他们可以把长字节序列变成一串又规律的字符, 比如32位的16进制字符串, 这一过程可以称为编码, 也可以称为加密, 并且不同的URL对应不同的编码. 我们把这种可以把各类看起来杂乱的信息映射为格式规整的唯一的短字符串的方式, 称为提取信息指纹.

如果我们选择这些算法中的一个用于URL, 则可以把URL转化为唯一与之对应的编码后的数值, 数值的存储与比较性价比更高.

判断文本相似度SimHash实现

分词与IF-IDF算法

虽然我没有研究过相似哈希在数学上的证明, 不过SimHash本身还是比较好理解的.

SimHash主要的应用领域是判断两个文本的相似程度, 比如两篇文章, 或者两个网页. 首先我们需要将文本进行分词, 并且以每个词在文中的关键程度为权重进行排序. 想做到这件事目前有很多成熟的解决方案, 比如其中应用广泛且易于理解的tf-idf(或这里查看中文页面, 但需要轻功), 其核心思想是在当前文章中的词出现频率越高关键度越高, 但这个词的关键度会因为他也出现在其他文章中而降低, 它在其他文章中出现的频率越高, 则它对于本文的关键度降低的越多. 其最终公式为:

$$TF-IDF(w)=\frac{n_{w}}{N}log(\frac{D}{D_{w}})$$

其中nw为词w在本文中出现的次数, N为本文中所有词的数量, D为文章总数, Dw为词w出现的文章数. 此处如果你看不懂也没关系, 这不是本文的重点, 我们回到最初的目的, 只要知道这样算出的值可以近似代表一个词在文中的关键程度就可以了. 以上过程也不需要我们手动实现, 对于中文分词并计算TF-IDF值, 结巴中文分词封装的很好. 而英文由于单词之间以空格分开, 分词本身并不需要过多考虑, 可选的工作是利用词干提取算法去掉单词后缀(indexing->index), 对此Python也有诸如nltk.stem或PorterStemmer库封装实现.

计算SimHash

接下来我们需要计算两个文本的SimHash值. 假设我们按照两篇文章中词列表的TF-IDF值排序并各取前128个, 并且对于每个词的信息指纹我们选取64位的二进制串, 0101的那种. 现在我们将64个二进制扩张为64个浮点数, 然后遍历我们选取的词列表, 对于每个词的信息指纹, 如果某一位为1, 我们就在我们对应位置的浮点数上加上这个词的TF/IDF值, 反之如果这一位为0, 我们就减去. 将所有128个词遍历完之后, 这64个浮点数经过我们加加减减, 应该各得到一个结果. 下一步我们进行收缩: 将大于0的值写为1, 小于0的值写为0, 再一次得到了二进制串, 这个二进制串即为我们所求的SimHash.

SimHash的一些特点

求出的SimHash有什么用呢? 首先, 因为我们每一步都是确定的, 所以对于相同的文本, 我们得到的SimHash值应当相同, 可以比对两篇文章是否完全一致. 不过我们兜着么一个大圈子显然不能只干这点事, 是的, SimHash还有一些更好玩的特性, 那就是两篇文章的相似程度越高, 则SimHash值越接近. 以64位作为信息指纹的长度, 如果只差一两位, 则仍可肯定两篇文章内容重复的可能性超过80%. 这为我们写一个简单的查重系统提供了一个简单的思路.

不过仅仅通过SimHash来作为查重的依据显然还不够, 比如有一位同学借了其他五位同学的作业, 并把他们的作业揉合在了一起, SimHash可能不会告诉你真实的结果, 你依然需要配合其他手段. 但对于搜索引擎来说, 通过SimHash来对付那些搬运工编辑确是简单又实用的方法.

总结

SimHash与TF-IDF一样是一种相对易于理解实现也比较简单的算法. 本文的重点是对SimHash的介绍, 对于文中提到的分词, TF-IDF算法实现, 以及结巴中文分词的源码初探, 我会在今后的日子完成并总结.

许可协议: CC BY-NC-SA 4.0
本文链接:https://blog.angelmsger.com/利用相似哈希判断文本近似程度/