文档相似度算法 Simhash

这篇文档简单介绍一下Simhash算法

 一. Simhash  计算文档相似度的算法， 比如用在搜索引擎的爬虫系统中，收录重复的网页是毫无意义的，只会造成存储和计算资源的浪费。有时候我们需要处理类似的文档，比如新闻，很多不同新闻网的新闻内容十分相近，标题略有相似。如此问题，便可以应用Simhash 文档相似度算法，查看两篇文档相似程度，删去相似度高的web文档。

二.  传统比较两个文本相似性的方法，大多是将文本分词之后，转化为特征向量距离的度量，比如常见的欧氏距离、海明距离或者余弦角度等等。两两比较固然能很好地适应，但这种方法的一个最大的缺点就是，无法将其扩展到海量数据。

simhash是locality sensitive hash（局部敏感哈希）的一种，最早由Moses Charikar在《similarity estimation techniques from rounding algorithms》一文中提出。Google就是基于此算法实现网页文件查重的。我们假设有以下三段文本： 

the cat sat on the mat   

the cat sat on a mat    

we all scream for ice cream    

Simhash 算法实现：

1、选择simhash的位数，请综合考虑存储成本以及数据集的大小，比如说32位 
2、将simhash的各位初始化为0 
3、提取原始文本中的特征，一般采用各种分词的方式。比如对于”the cat sat on the mat”，采用两两分词的方式得到如下结果：{“th”, “he”, “e “, &

今天的文章文档相似度算法 Simhash分享到此就结束了，感谢您的阅读。