介绍一个基于simhash作海量文章排重的库:simhashpy

原创
2013/12/17 09:08
阅读数 2W

基于simhash的海量文章排重的实践

简单介绍

simhash是一种能计算文档相似度的hash算法。通过simhash能将一篇文章映射成64bit,再比较两篇文章的64bit的海明距离,就能知道文章的相似程序。若两篇文章的海明距离<=3,可认为这两篇文章很相近,可认为它们是重复的文章。

这篇博客有详细的介绍

simhash-py

要更准确的对文章进行排重,需要找到好的simhash算法。目前我知道的有python-hashes,simhash-py。两个库通过简单的修改,再加上中文分词库,可以比较好的对中文文章计算hash。simhash-py可使用我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 欢迎对数据处理有兴趣的同学多多交流。

展开阅读全文
打赏
0
7 收藏
分享
加载中
用mac尝试,python setup install 没有报错,但是import simhash报ImportError: No module named 'table', 确认table.pyx文件已存在,cython用了anaconda中的,python版本3.5,网上找原因没有找到解决办法~
2016/08/09 22:29
回复
举报
有java版的快速搜索么?
2016/05/07 16:52
回复
举报
余争博主

引用来自“飞翔的猴子”的评论

这个是py的 有java的么
还有就是 这个算法都是两两比较 等数据量大了之后怎么办

它就是为了避免直接两两比较的,针对大数据量的场合。具体原理你研究下这个文章:http://my.oschina.net/leejun2005/blog/150086
2014/04/21 13:52
回复
举报
这个是py的 有java的么
还有就是 这个算法都是两两比较 等数据量大了之后怎么办
2014/04/21 11:18
回复
举报
余争博主

引用来自“oldcai”的评论

好像是加了一个hash_hasher是么,原先的那个有什么问题么,请问

原先的那个问题我也找不到,并且直接跑简单的测试的时候是没问题的。当在爬虫里抓取网页并进行hash计算的时候会有小部分hash值里计算错误。感觉也好像不是代码重入的问题,后来就直接自己写了一个hash,就是在__init__.py里面的那个函数。就是分词之后再传进去,感觉这样的接口更好。
2013/12/30 14:45
回复
举报
明白了,是加了一个直接装载已hash过的数组的函数。
文档比较少,好在注释比较全。
2013/12/29 19:16
回复
举报
好像是加了一个hash_hasher是么,原先的那个有什么问题么,请问
2013/12/29 18:10
回复
举报
昨天又看了下,大概明白了这个项目的脉络,不过确实比较坑,test跑不通。
然后本来昨晚就来评论,结果刚好过了11点不能评论了。。。

博主修改的地方我看了下,大概就是分词分好了后传进去吧。
另外,您是不是改过simhash-cpp,所以改过submodule呀?
https://github.com/jannson/simhash-py/commit/d7efc4019afd4f123049d8764b0227698894db43
之前说从您的fork好像不能直接更新submodule大概就是这个原因吧。
2013/12/29 15:50
回复
举报

引用来自“余争”的评论

引用来自“oldcai”的评论

simhash-cpp编译好像有问题,缺文件util.h,去掉include后缺Catch,找到新版Catch后,发现还是不能编译。
tokenizers/strspn.h:9:71: error: ‘strspn’ was not declared in this scope
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ");
^
test.cpp: In function ‘void TestCaseFunction_catch_internal_123()’:
test.cpp:158:70: error: no match for call to ‘(Simhash::Simhash<>) (const char*, std::basic_string<char>::size_type)’
uint64_t a = hasher(jabberwocky.c_str(), jabberwocky.length());
^
In file included from test.cpp:9:0:
hash.hpp:26:11: note: candidate is:
class Simhash {
^
hash.hpp:39:16: note: Simhash::hash_t Simhash::Simhash<Hash>::operator()(char**) [with Hash = Simhash::jenkins; Simhash::hash_t = long unsigned int]
hash_t operator()(char **tokens) {
^
hash.hpp:39:16:

TT_TT

不知道您是怎么编译的。
PS:直接从你的fork好像不能更新submodule。

补充:tokenizers/strspn.h最后在simhash-py里是不用的,因为中文分词肯定不能通过这个简单的分词办法来分词。

感谢,已安装成功,待会再琢磨下你的修改和中文分词。
2013/12/20 18:51
回复
举报
余争博主

引用来自“oldcai”的评论

simhash-cpp编译好像有问题,缺文件util.h,去掉include后缺Catch,找到新版Catch后,发现还是不能编译。
tokenizers/strspn.h:9:71: error: ‘strspn’ was not declared in this scope
"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ");
^
test.cpp: In function ‘void TestCaseFunction_catch_internal_123()’:
test.cpp:158:70: error: no match for call to ‘(Simhash::Simhash<>) (const char*, std::basic_string<char>::size_type)’
uint64_t a = hasher(jabberwocky.c_str(), jabberwocky.length());
^
In file included from test.cpp:9:0:
hash.hpp:26:11: note: candidate is:
class Simhash {
^
hash.hpp:39:16: note: Simhash::hash_t Simhash::Simhash<Hash>::operator()(char**) [with Hash = Simhash::jenkins; Simhash::hash_t = long unsigned int]
hash_t operator()(char **tokens) {
^
hash.hpp:39:16:

TT_TT

不知道您是怎么编译的。
PS:直接从你的fork好像不能更新submodule。

补充:tokenizers/strspn.h最后在simhash-py里是不用的,因为中文分词肯定不能通过这个简单的分词办法来分词。
2013/12/20 09:50
回复
举报
更多评论
打赏
14 评论
7 收藏
0
分享
返回顶部
顶部