|
|
最近研究文档去重技术,研究了一下去重算法后,最终选择了simhash算法.这个算法相对而言最简单,效果又好,难怪被google选用.
简单来讲,simhash分为3步:
1.将文本去掉格式后,分词.
2.将每一个分词hash为一组固定长度的数列.比如32bit的一个整数.
3.建立一个长度为32的整数数组(假设要生成32位的数字指纹,也可以是其它数字),对每一个分词hash后的数列进行判断,如果是1000...1,那么数组的第一位和末尾一位加1,中间的30位减一,也就是说,逢1加1,逢0减1.一直到把所有的分词hash数列全部判断完毕.最后对数组进行判断,大于0的记为1,小于等于0的记为0,得到一个32bit的数字指纹.
在实际编码中,有如下几点体会:
1.中文文档进行分词后,其中的一些助词,语气词,人称代词等常用字会带来很大的干扰,比如说"的","我","了","这"等,要把这些词去掉,增加去重精度.
2.分词后,尽量给每个分词一个权重数字,代表这个词的重要程度,这样能够极大提高精度.比较简单的算法是,把每个词在文章中出现的次数作为权重.比如,"美国总统克林顿登上了长城,这是登上长城的第x位美国总统.",那么分词后,长城权重2,美国权重2,总统权重2,克林顿权重1,其它分词权重0,可以忽略掉.
3.分词算法,我参考了中科院的ICTCLAS.可以直接分析出文章的关键词,只让关键词参与到simhash算法中会提高效率和效果.
4.对大量文章通过simhash提取数字指纹后,指纹间的海明距离代表了文章的相近程度.对于二进制来将,海明距离是两个数字的异或后1的个数.
我觉得下面这个算法计算1的个数很高效: int Count(int v)
{
int num=0;
while(v)
{
v&=(v-1);
num++;
}
return num;
} |
5.对于大量数字指纹的保存,需要考虑一种高效的数据结构.我没有自己设计,而是直接将数字指纹保存到了全文检索引擎提供的数据库中,这样的好处是,去重和全文检索可以和谐统一到一起.全文检索引擎我选择了xapian,实际用后,没有发现什么缺点.
----------------------------
原文链接:https://blog.51cto.com/2588084/558873
程序猿的技术大观园：www.javathinker.net
[这个贴子最后由 flybird 在 2020-03-19 10:12:47 重新编辑]
|
|
Java技术网站 → 『 Java开发技术 』 → 『 数据结构和算法专题 』 → 对simhash算法的一些思考
消息
查看
搜索
好友
邮件
复制
引用
IP: 已设置保密
