其他
简介
文档去重功能是为了解决搜索引擎的文档语义重复的问题,方法是结合Charikar的simhash指纹编码与Google的Hamming distance拆分算法予以实现。支持海量100亿数据量级的快速重复检测。
应用
说起这个实现,还是先说说需求吧。搜索引擎中常常要对新进来的文档(一般指网页,这里统一以文档称之)进行重复性判断,判断这个文档是否已经在已有数据库中存在了没有,如果存在则不予插入。这也就是通用互联网搜索引擎对整个互联网的网页进行不间断更新的处理过程,当然这个不间断的间隔时间是根据不同站点等其它因素决定的,这里不重点分析这个。
那么怎么判断一个新文档与哪些旧文档是重复的呢?通过数据库中设置的唯一ID来识别,OK,那这个ID怎么来的呢,像上面那种互联网网页的话,你可能一开始想到使用URL作为唯一标识,错!如果那个网页URL没变,但是内容修改了呢?博客、论坛BBS之类的网页常常是这个情况,那么有这些网页里面有更新的数据到时就没有入库建索引,也就搜索不到了。
好,你可能会说那就把网页内容加上去总行了吧,好的,你应该会把URL加上网页内容做一个md5之类的编码作为ID,上面这问题是解决了,但是这个网页里面如果有一个时间计时器什么的,或者访问数什么的,你每次去抓取访问的时候这个数值都会不一样,这样你的这个md5编码的唯一ID就不一样了。(其实我们真正解决的需求还不仅仅是这个网页去重的问题,在搜索引擎内容搜索中,我们经常对于极相近的内容做一个归并呈现出来比较友好,像百度的新闻搜索里出现的“X条相同新闻”就是很典型的应用。)
呜,看来这样不行了。这样我们就想到计算两个网页的语义相似度了,如果两个文档从语义上看差别很小的,那就算这两个文档是相同重复的。哦?真得要这样做吗?诸不知,计算两个语义相似度常常使用的是vsm(Vector space model 向量空间模型)【0】来计算的,可想而知,对于刚刚直接匹配ID的计算量不是一个数量级的。有人说怎么滴不行呀,多一些性能好的配置可以再搞个分布式神马的怎么不能解决呢。的确有XX院的人做一些什么研究性系统或者报告的时候使用这样的方法,不过对于商业化数据量,特别是整个互联网数据,差之毫厘谬以千里啊。
算法
搜索引擎
文档
方法
功能
问题
解决
为了
指纹
重复
语义
哈希
多重
暂无评论