## 基于simhash的海量文章排重的实践 ## 简单介绍 ---- simhash是一种能计算文档相似度的hash算法。通过simhash能将一篇文章映射成64bit，再比较两篇文章的64bit的海明距离，就能知道文章的相似程序。若两篇文章的海明距离<=3，可认为这两篇文章很相近，可认为它们是重复的文章。 [这篇博客有详细的介绍][1] simhash-py ---- 要更准确的对文章进行排重，需要找到好的simhash算法。目前我知道的有[python-hashes][2]，simhash-py。两个库通过简单的修改，再加上中文分词库，可以比较好的对中文文章计算hash。[simhash-py][3]可使用我fork的版本以支持中文文章的simhash （通过里面的hash_token或hash_tokenpy两个函数实现对切词之后的中文文章进行simhash计算）。 simhash算法 --------- simhash算法最简单实现的库应该是python-hashes库了。使用过程当中发现，对于排重的使用目的来说，这个库的simhash算法有缺点是：只考虑到文章存在哪些词，没有考虑到词的顺序。不过相应的优点是，可以实现海量文章相似度计算。文章相似度计算忽略词的顺序之后效果更好。 simhash-py内部实现了simhash算法。它里面的simhash使用了cyclic hash算法，这个算法考虑到N（可以在3~5）个词之间的顺序。考虑到词的顺序的hash算法在排重过程当中会更准确，不过这个我也没有特别好的测试:) simhash加快搜索 ----------- 若看过本文推荐的simhash的原理讲解那篇文章，发现可以通过“shard”方式加快simhash值的搜索，从而能快速的知道是否存在重复的文章。而simhash-py库通过C++的Judy库实现了这一点。 simhash集群处理 ----------- 既然可以通过“shard”方式，那么很容易把这个思路拓展到集群上。所以相应的，simhashpy的作者实现了simhash-cluster。 过程当中有疑问可加我开源项目交流QQ群：27498_3126 欢迎对数据处理有兴趣的同学多多交流。 [1]: http://my.oschina.net/leejun2005/blog/150086 [2]: https://github.com/sangelone/python-hashes [3]: https://github.com/jannson/simhash-py