文本指纹算法和内容指纹系统介绍

1.       文本指纹介绍

Web大量上的网页集合里存在大量的重复内容网页,无论对于搜索引擎的网页去重和过滤、新闻小说等内容网站的内容反盗版和追踪、还是社交媒体等文本去重和聚类,都需要对网页或者文本进行去重和过滤。

最简单的文本相似性计算方法可以利用空间向量模型,计算分词后的文本的特征向量的相似性,这种方法存在效率的严重弊端,无法针对海量的文本进行两两的相似性判断。模仿生物学指纹的特点,对每个文本构造一个指纹,来作为该文本的标识,从形式上来看指纹一般为固定长度较短的字符串,相同指纹的文本可以认为是相同文本。

最简单的指纹构造方式就是计算文本的md5或者sha哈希值,除非输入相同的文本,否则会发生“雪崩效应”,极小的文本差异通过md5或者sha计算出来的指纹就会不同(发生冲撞的概率极低),那么对于稍加改动的文本,计算出来的指纹也是不一样。

因此,一个好的指纹应该具备如下特点:

1.      指纹是确定性的,相同的文本的指纹是相同的;

2.      指纹越相似,文本相似性就越高;

3.      指纹生成和匹配效率高。

业界关于文本指纹去重的算法众多,如k-shingle算法、google提出的simhash算法、Minhash算法、top k最长句子签名算法等等,本文接下来将简单介绍各个算法以及指纹系统的基本架构和思路。


2.       常用的指纹算法


2.1   k-shingle算法

shingle在英文中表示相互覆盖的瓦片。对于一段文本,分词向量为[w1,w2, w3, w4, … wn], 设k=3,那么该文本的shingle向量表示为[(w1,w2,w3),(w2,w3,w4), (w3,w4,w5), …… (wn-2,wn-1,wn)],计算两个文本的shingle向量的相似度(jarccard系数)来判断文本是否重复。由于k-shingle算法的shingle向量空间巨大(特别是k特别大时),相比vsm更加耗费资源,一般业界很少采用这类算法。


2.2   Simhash算法

Simhash是google用来处理海量文本去重的算法,同时也是一种基于LSH(localitysensitive hashing)的算法。简答来说,和md5和sha哈希算法所不同,局部敏感哈希可以将相似的字符串hash得到相似的hash值,使得相似项会比不相似项更可能的hash到一个桶中,hash到同一个桶中的文档间成为候选对。这样就可以以接近线性的时间去解决相似性判断和去重问题。

simhash算法通过计算每个特征(关键词)的哈希值,并最终合并成一个特征值即指纹。

simhash算法流程

1.      首先基于传统的IR方法,将文章转换为一组加权的特征值构成的向量。

2.      初始化一个f维的向量V,其中每一个元素初始值为0。

3.      对于文章的特征向量集中的每一个特征,做如下计算:

a)        利用传统的hash算法映射到一个f-bit(一般设成32位或者64位)的签名。对于这个f- bit的签名,如果签名的第i位上为1,则对向量V中第i维加上这个特征的权值,否则对向量的第i维减去该特征的权值;

b)       整个特征向量集合迭代上述运算后,根据V中每一维向量的符号来确定生成的f-bit指纹的值,如果V的第i维为正数,则生成f-bit指纹的第i维为1,否则为0。


参数:指纹集合dnas:[]

计算基数radix:=pow(2, log(m)/log(2) )

FOR 片段频率s IN S

    修正频率,每个频率值:=max(频率,基数)

    指纹dna:=空串

FOR tmp IN s[m-5:m]

        将tmp转换成整数,基数为radix

        将tmp转换成字符串,基数为radix

        dna:=dna连接tmp

    dnas:=dnas添加dna

END

输出:指纹集合dnas

 

 4.       指纹系统结构

指纹追踪系统主要由爬虫系统、指纹生成系统、指纹存储、指纹查询和比对、数据分析、后台管理系统等几个主要模块构成。





图3 指纹追踪系统模块图



图4 系统架构图






图5 系统流程图

 

5.       总结

对于网页去重、内容盗版追踪、内容聚类等应用来说,指纹模块都是极其重要的模块。本文介绍了一些比较常用的指纹算法,包括k-shingle、simhash、minhash;同时介绍了指纹追踪系统及其关键算法,在实际的使用过程中,需要根据具体业务场景,确定具体的架构设计和应用算法。

原文链接:https://blog.csdn.net/wh_springer/article/details/52177236

发表评论

必填

选填

选填

必填

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。