相似文档查找算法之simHash学习笔记

https://github.com/askender/askender.github.com/issues/8 只是个人整理，如果想深入了解，请看文末的参考文档实现了python版simhash算法（java版本就不提供了），代码稍后push上来 hash 算法传统的 hash 算法只负责将原始内容尽量均匀随机地映射为一个签名值Google 的 simhash 算法产生的签名，对相似的内容产生的签名也相近。出人意料，这个算法并不深奥，其思想是非常清澈美妙的。 传统文本相似度比较采用经典方法是文本相似度的向量夹角余弦但由于有可能一个文章的特征向量词特别多导致整个向量维度很高，使得计算的代价太大对于Google这种处理万亿级别的网页的搜索引擎而言是不可接受的 Simhash 算法简介simhash算法的主要思想是降维，将高维的特征向量映射成一个f-bit的指纹(fingerprint)，通过比较两篇文章的f-bit指纹的Hamming Distance来确定文章是否重复或者高度近似。simhash算法的输入是一个向量，输出是一个 f位的签名值。为了陈述方便，假设输入的是一个文档的特征集合，每个特征有一定的权重。比如特征可以是文档中的词，其权重可以是这个词出现的次数。 simhash 算法如下： 1，将一个 f 维的向量 V 初始化为 0 ； f 位的二进制数 S 初始化为 0 ； 2，对每一个特征：用传统的 hash 算法对该特征产生一个 f 位的签名 b 。对 i=1 到 f ： 如果b 的第 i 位为 1 ，则 V 的第 i 个元素加上该特征的权重； 否则，V 的第 i 个元素减去该特征的权重。3，如果 V 的第 i 个元素大于 0 ，则 S 的第 i 位为 1 ，否则为 0 ； 4，输出 S 作为签名。 注意干掉停用词 英文分词 词根还原"的","我","了","这"等,要把这些词去掉,增加去重精度分词后,尽量给每个分词一个权重数字,代表这个词的重要程度,这样能够极大提高精度.比较简单的算法是,把每个词在文章中出现的次数作为权重.simhash算法的精确度也会有所损耗，并且与simhash的位数b有关，b越大精确度越高。 适用场景simHash在短文本的可行性：测试相似文本的相似度与汉明距离相似度在0.8左右的Hamming距离为7，只有相似度高到0.9412，Hamming距离才近到4根据经验值，对 64 位的 SimHash ，海明距离在 3 以内的可以认为相似度比较高。 在80亿网页规模下汉明距离=3刚好合适。按照Charikar在论文中阐述的，64位simhash，海明距离在3以内的文本都可以认为是近重复文本。当然，具体数值需要结合具体业务以及经验值来确定。 由于文本已经压缩成8个字节了，因此其实Simhash近似查重精度并不高 Google对此算法的应用场景网页近重复、镜像网站、内容复制、嵌入广告、计数改变、少量修改。以上原因对于长文本来说造成的相似度都会比较高而对于短文本来说，如何处理海量数据的相似度文本更为合适的？ 扩展到海量数据的近重复检测对于64位的待查询文本的simhash code来说，如何在海量的样本库（>1M）中查询与其海明距离在3以内的记录呢假设我们要寻找海明距离3以内的数值，根据抽屉原理，只要我们将整个64位的二进制串划分为4块，无论如何，匹配的两个simhash code之间至少有一块区域是完全相同的1、将64位的二进制串等分成四块 2、调整上述64位二进制，将任意一块作为前16位，总共有四种组合，生成四份table 3、采用精确匹配的方式查找前16位 4、如果样本库中存有2^34（差不多10亿）的哈希指纹，则每个table返回2^(34-16)=262144个候选结果，大大减少了海明距离的计算成本 我们可以将这种方法拓展成多种配置，不过，请记住，table的数量与每个table返回的结果呈此消彼长的关系，也就是说，时间效率与空间效率不可兼得，参看下图： 事实上，这就是Google每天所做的，用来识别获取的网页是否与它庞大的、数以十亿计的网页库是否重复。另外，simhash还可以用于信息聚类、文件压缩等。 或者直接将数字指纹保存到了全文检索引擎提供的数据库中 Ref: Similarity Estimation Techniques From Rounding Algorithms Moses Charikarhttp://wwwconference.org/www2007/papers/paper215.pdfhttp://blog.csdn.net/lgnlgn/article/details/6008498 Detecting Near-Duplicates for Web Crawling http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.78.7794&rep=rep1&type=pdf http://my.oschina.net/leejun2005/blog/150086 http://grunt1223.iteye.com/blog/964564 http://en.wikipedia.org/wiki/Locality_sensitive_hashing http://www.cnblogs.com/linecong/archive/2010/08/28/simhash.html http://2588084.blog.51cto.com/2578084/558873 http://leoncom.org/?p=650607 http://www.lanceyan.com/tech/arch/simhash_hamming_distance_similarity2-html.html http://www.lanceyan.com/tech/arch/simhash_hamming_distance_similarity.html http://en.wikipedia.org/wiki/Hamming_distance http://www.cnblogs.com/zhengyun_ustc/archive/2012/06/12/sim.html good http://www.gooseeker.com/cn/node/knowledgebase/shingling http://blog.csdn.net/beta2/article/details/5045020 http://blog.csdn.net/beta2/article/details/5014530 http://blog.csdn.net/liuaigui/article/details/6897314 http://tech.uc.cn/?p=1086 .