搜索引擎长文本去重策略分析


原创不易,互联网抄袭成风,很多原创内容在网上被抄来抄去,改来改去,爬虫如何判断一个新网页是否与网页库中已有的网页重复呢?

【传统签名算法与文本完整性判断】

问题:

    1、运维上线一个bin文件,将文件分发到4台线上机器上,如何判断bin文件全部是一致的?

    2、用户A将消息msg发送给用户B,用户B如何判断收到的msg就是用户A发送的msg?

思路:

    一个字节一个字节的比对两个大文件或者大网页效率低,我们可以用一个签名值(例如md5值)代表一个大文件,签名值相同则认为大文件相同(先不考虑冲突率)

回答:

    1、将bin文件取md5,将4台线上机器上的bin文件也取md5,如果5个md5值相同,说明一致

    2、用户A将msg以及消息的md5同时发送给用户B,用户B收到msg后也取md5,得到的值与用户A发送过来的md5值如果相同,则说明msg正确

结论:

    md5是一种签名算法,常用来判断数据的完整性与一致性

    md5设计原则:两个文本哪怕只有1个bit不同,其md5签名值差别也会非常大,故它只适用于“完整性”check,不适用于“相似性”check。

新问题:

    有没有一种签名算法,如果文本非常相似,签名值也非常相似呢?


【文本相似性的签名算法】

问题:

    上文提出的问题,可以用局部敏感哈希LSH(Locality Sensitive Hash)解决,局部敏感哈希是一类文本越相似,哈希值越相似的hash算法,有兴趣的同学自行查一下,这里分享一下minHash的思路。

思路:

    什么是minHash?

回答:

    minHash是局部敏感哈希的一种,它常用来快速判定集合的相似性,也常用于检测网页的重复性,其思路为,用相同的规则抽取集合中的少部分元素代表整个集合,如果少部分元素的重合度很高,非常可能整个集合的重复度也很高。

举例:

    待判定的集合为

        A{1, 7, 5, 9, 3, 11, 15, 13}

    已有的集合为:

        B{10, 8, 2, 4, 6, 0, 1, 16},

        C{100, 700, 500, 900, 300, 1100, 1500,1300},

        D{1, 3, 2, 4, 6, 5, 8, 7}

    假设使用部分元素代替全体集合的规则为:集合内元素进行排序,取值最小的4个(这个过程有信息损失,我们可以认为是一个hash过程)

    处理结果为:

        A{1, 3, 5, 7}

        B{0, 1, 2, 4}    =>A    与B有1个元素相同

        C{100, 300, 500, 700}    =>A    与C有0个元素相同

        D{1, 2, 3, 4}    =>A    与D有2个元素相同

    判断结论:

        我们认为集合A与集合D是最相似的

    这个例子有点2,但基本能说明整体思路,实际在执行的过程中:

        1、我们可以使用更多的元素来代表集合,以提高准确性(例如,将上例中的4个元素代表集合升级为8个元素代表集合)

        2、我们可以使用更多的hash函数来代表集合,以提高准确性(例如,上例除了“排序后取值最小的4个元素代表集合”,还可以增加一个哈希函数“排序后取值最大的4个元素代表集合”)

        3、minHash可以量化评判相似度,亦可以评判网页是否重复(一个分类问题),设定相似度阈值,高于阈值为重复,低于阈值为不重复

        4、实际排重过程中,网页库中的哈希值都可以提前计算,只有待判定的集合或者网页的哈希值需要临时计算


【minHash与长文本重复度检测有什么关系】

问题:

    目前看来没什么关系,但如果我们能将每一个长文本用一个集合来表示,就能将长文本的相似度用minHash来解决了。

思路:

    如何将长文本转化为集合?

回答:

    我去,分词不是就可以么

举例:

    待判定的长文本为

        A{我是wzx,我来自中国北方}

    已有网页库集合为:

        B{我是一只来自北方的狼}

        C{中国,北方}

        D{这事和我没关系,我是凑数的}

    使用分词将上述文本集合化:

        A{我,wzx,来自,中国}

        B{我,wzx,来自,狼}

        C{来自,中国,北方}

        D{事,我,凑数,关系}

    判断结论:

        当转化为集合后,可以快速判断A与B的相似度最高,当然实际执行过程中,除了分词还得考虑词频,用这种方法对长文本进行相似度检测,准确率非常高(文本越长越准)


【还有没有更有效的方法】

问题:

    使用上述方法进行文本相似度检测,需要进行中文分词,词频统计,哈希值计算,相似度计算,计算量微大。

    然而,抄袭成风,一字不改的风气,让技术有了更广阔的优化空间,赞!

思路:

    怎么优化呢?

回答:

    不再进行分词,而是进行“分句”,用标点符号把长文按照句子分开,使用N个句子集合(例如一篇文章中5条最长的句子作为签名,注意,长句子比短句子更具有区分性)作为文章的签名,在抄袭成风的互联网环境下,此法判断网页的重复度能大大降低工程复杂度,并且准确度也异常的高。


【结论】

    在抄袭成风的互联网环境下,采用“分句”的方式,用5条最长的网页内容作为网页的签名,能够极大的降低排重系统复杂度,提高排重准确率,不失为一种好的选择。


【tips】

    本文只是对去重策略做了一个简介,其实还有:余弦向量、simHash、minhash、kshigle都是不错的方法,有兴许的同学可以关注一下。

上一篇 下一篇

评论

登录后可发表评论