1引言
随着计算机与信息技术的高速发展以及信息存储技术[1]的广泛应用，人们已经步入大数据时代[2]，数字化信息量呈现爆炸式增长。数据量大、复杂度高以及冗余度高是当前大数据信息的特点。研究表明，一些存储系统中的冗余数据已经达到了60%[3]，并且会随着数据量的上升而增多。因此在有限的存储空间和时间内，如何存储更多有效精炼的信息成为当前研究的热点。
在去除冗余数据方面，Simhash算法是当前公认的最好的去重算法。该算法是一种局部敏感哈希算法[4]，
Simhash算法在文本去重中的应用
张航，盛志伟，张仕斌，杨敏
成都信息工程大学网络空间安全学院，成都610225
摘要：为了提升Simhash算法的文本去重效果、准确率，解决Simhash算法无法体现分布信息的缺点，提出了基于信息熵加权的Simhash算法（简称E-Simhash）。该算法引入TF-IDF和信息熵，通过优化Simhash算法中的权重及阈值计算，增加文本分布信息，使得最终生成的指纹更能体现关键信息的比重，并对指纹信息与权重的关联性进行了分析。仿真实验表明：优化权重计算能有效地提升Simhash算法的性能，E-Simhash算法在去重率、召回率、F值等方面均优于传统Simhash算法，并且在文本去重方面取得了
良好的效果。
关键词：Simhash；信息熵；词频-逆向文件频率；权重优化；文本去重
文献标志码：A中图分类号：TP301doi：10.3778/j.issn.1002-8331.1902-0246
张航，盛志伟，张仕斌，等.Simhash算法在文本去重中的应用.计算机工程与应用，2020，56（11）：246-251.
ZHANG Hang,SHENG Zhiwei,ZHANG Shibin,et al.Application of Simhash algorithm in text deduplication.Computer Engineering and Applications,2020,56（11）：246-251.
Application of Simhash Algorithm in Text Deduplication
ZHANG Hang,SHENG Zhiwei,ZHANG Shibin,YANG Min
School of Cybersecurity,Chengdu University of Information Technology,Chengdu610225,China
Abstract：To improve the text deduplication effect and accuracy of Simhash algorithm,as well as to solve the shortcomings of Simhash algorithm that cannot reflect the distribution information,an improve
d Simhash algorithm based on information entropy weighting,abbreviated as E-Simhash,is proposed in this paper.Firstly,by introducing TF-IDF and information entropy,optimizing the weight and threshold calculation in Simhash algorithm,as well as adding the text distribution information,the final generated fingerprint can better embody the proportion of key information.Meanwhile,the correlation between fingerprint information and weight is also be certificated.Finally,the experimental results demonstrate that the performance of Simhash algorithm can be effectively improved by optimizing the weight.The modified algorithm is superior to the traditional Simhash algorithm in terms of deduplication rate,recall rate and F value,and also has good performance in Chinese similarity detection.Thus,the effectiveness and accuracy of the proposed method are verified.
Key words：Simhash;information entropy;term frequency-inverse document frequency;weight optimization;text deduplication
基金项目：国家重点研发计划（No.2017YFB0802302）；四川省教育厅项目（No.18ZA0093）；四川省高校科研创新团队项目（No.
17TD0009）；四川省学术和技术带头人培养支持经费资助项目（No.2016120080102643）；四川省应用基础项目（No.
2017JY0168）；四川省重点研发计划项目（No.2018TJPT0012）；四川省科技支撑计划项目（No.2016FZ0112，No.2018GZ0204）。作者简介：张航（1992—），男，硕士研究生，研究方向为网络与系统安全、大数据安全；盛志伟（1977—），男，副教授，研究方向为云计算与大数据处理、物联网工程及应用等。
收稿日期：2019-03-01修回日期：2019-07-12文章编号：1002-8331（2020）11-0246-06
CNKI网络出版：2019-07-19,knski/kcms/detail/11.2127.TP.20190719.0930.002.html
它能够将高维数据进行概率降维并映射为位数较少且固定的指纹，之后再对指纹进行相似度比较来反应数据之间的相似程度。其中比较算法通常使用海明距离[5]及编辑距离[6]。Simhash 算法优势在于处理速度快，并且结果准确度高。
如今，Simhash 算法被广泛应用在近似文本检测、冗余数据去重、异常检测[7]
等领域。文献[8]提出了一种基于多Simhash 指纹算法，利用多种指纹值经过k 维多曲面进行相似度计算，有效地解决了指纹单一、信息丢失严重的问题。文献[9]在Simhash 算法中加入了减值运算，对最后合并的结果序列串结果减去一个阈值T ，从而提升了Simhash 算法的准确性。文献[10]将Simhash 算法和CNN 进行结合用于恶意软件检测，通过转化为灰度图像提高恶意软件识别率和性能。
但是以上对Simhash 的应用都存在一些问题，首先没有突出关键项在Simhash 指纹中的比重，比如文献[8]只是简单地进行了术语长度统计从而确定文章的信息，文献[9]中设置关键词权重为1，这样造成严重的信息失真。其次没有考虑到信息位置分布对指纹的影响。为了提升Simhash 算法的文本去重效果、准确率，解决Simhash 算法无法体现分布信息的缺点，引入信息熵的概念，采用熵加权的方式给文档中的关键词进行赋权，优化权重计算公式，并在hash 计算中加入关键词分布信息，从而达到对传统Simhash 算法的优化，最后通过仿真实验论证了该算法的可行性、合理性。
2相关问题研究2.1
Simhash 算法的分析
定义1Simhash 算法的原理是对于两个给定的变
量x ,y ，哈希函数h 总是满足下式：
Pr h ∈F ()
h ()x =h ()y =sim ()
x ,y （1）
其中，Pr 表示h ()x =h ()y 的可能性，sim ()x ,y ∈[0,1]是相似度函数，一般也用雅可比函数Jac(x ,y)来表示变量x ,y 的相似度，sim ()x ,y 表示如下：
sim ()x ,y =Jac ()x ,y =
||x ∩y |
|x ∪y （2）
h 属于哈希函数簇F ，需要满足以下条件：
（1）如果d ()x ,y ≤d 1，则Pr h ∈F ()
h ()x =h ()y ≥p 1；（2）如果d ()x ,y ≥d 2，则Pr h ∈F
()h ()x =h ()y ≤p
2
。
称F 为(d 1,d 2,p 1,p 1)上的敏感哈希簇函数[11]。其中d ()x ,y 表示x ,y 变量之间的距离，通俗而言，表示如果x ,y 足够相似时，那么它们映射为同一hash 函数
的概率也就足够大，反之哈希值相等的概率足够小。
由于传统hash 函数[12]与Simhash 函数最大的不同在于局部敏感性，如果针对输入的数据做些局部修改，经过传统hash 函数运算后可能会得到完全不同的结果，而Simhash 计算的结果则很相似，因此可以使用Simhash 函数产生的指纹相似程度来表示源数据之间的相似程度。
2.2Simhash 算法流程
Simhash 算法的流程是首先定义一个f 维度的空
间，然后在这个空间中定义每一个特征所对应的向量，接着将所有的向量结合自身的权重进行加权、求和就得到了一个和向量作为结果。最后再对该结果进一步地进行压缩转化，其规则是：对每一个向量得出一个相对应的f 位签名信息，若向量维度的值大于0，则置其签名所在的位置为1，否则置为0。通过这
样的转化方式，得到的签名信息表证了此向量在各个维度中的值的信息。Simhash 的算法流程图如图1所示。
Simhash 算法的具体步骤如下：步骤1初始化
针对数据集大小及存储成本确定Simhash 位数以
及f 维向量空间，同时初始化f 位二进制数S 均置为0。
步骤2文档预处理
主要包含两部分，第一部分是分词，寻文档的特征词汇以及去除文档停用词等。第二就是赋权，一般而言这里普遍忽略了权重的计算设置为1[13]。
步骤3生成hash 值
利用传统的散列算法对步骤2中的每个特征词计算一个f 位hash 值，
并进行下列运算：
Hash 指纹
文档
特
征值特征值
特征值
散列110101*********
…
…1,1,−1,1,−11,−1,−1,1,−1
1,1,−1,1,1
1325,−253,785,−32,7710101图1
Simhash 指纹生成
for k in V ：for i in f ：if （i ==0）：V i =V i +w ki
else ：
V i =V i -w ki
步骤4压缩变换
针对最后生成的向量V ，对每一位进行转化处理。
if V [i ]>0：S [i ]=1
else ：S [i ]=0
步骤5指纹生成
输出最终的签名S 作为该文档的指纹，之后再进行海明距离或编辑距离计算相似度。
步骤6距离计算
在Simhash 算法中通常使用海明距离进行相似度计算。海明距离通过比较两个文档指纹中不相同的个数来度量两个文档之间的相似度[14]。海明距离越大，代表两个字符串的相似度越低，反之则两个字符串相似度越高。对于二进制字符串而言，可以使用异或运算来计算两个二进制的海明距离。举例说明如下：
例1设a ,b 为两个二进制数，其中：a =00110,b =01110
则可知a ,b 两个二进制数只有第二位不同，故Hamming (a ,b )=1。
也可利用异或操作，统计异或结果中1的个数。a ⊕b =01000，共有1个1，故海明距离为1。
2.3Simhash 存在的一些问题
传统Simhash 算法在权重计算方面通常设置为1或
特征词出现的次数，这很容易造成信息丢失，导致最终的Simhash 指纹准确性降低，并且根据Simhash 算法可知它不表现出词汇分布信息，关键特征词调整顺后，不会影响最终生成的Simhash 指纹。
如图2所示，两个关键词的位置调整下就可能导致最终的意义大不相同，但是传统的Simhash 算法生成的指纹却是一样的。
3改进的Simhash 算法
本文提出了一种新的基于信息熵的Simhash 算法，
考虑到传统Simhash 算法中针对权重的计算不充分，以
及不能更好地反应文档中词汇的分布特征，本文中引入信息熵理论来解决上述问题，并且在hash 计算中加入位置关系特征，从而提升Simhash 算法的准确度。
3.1熵加权权重计算方法
（1）词频-逆向文件频率
词频-逆向文件频率（TF-IDF ）[15]
算法是一种常用
的文本特征权重计算方法，特征词t k 在文档d j 中的TF-IDF 值记为tfidf (t k ,d j )，有如下定义：
定义2特征项t k 在文档d j 中出现的频率tf (t k ,d j )为：tf ()t k ,d j =
n j ,k
∑i
n j ,i
（3）
式中，n j ,k 表示特征词t k 在文档d j 中出现的次数，
∑i
n j ,i 表示文档d j 中的所有特征词的个数。
定义3反文档频率idf (t k ,d j )是权衡特征词重要性的系数，其定义为：
idf ()t k =ln
|D |
|
|{}j :t
k
∈d j +1
（4）
式中，{}j :t k ∈d j 为含有特征词t k 的文档综述，|D |为语料库中的文件总数。
定义4TF-IDF 函数，特征词的词频权重定义为：w k =tfidf (t k ,d j )=tf ()t k ,d j ×idf ()
t k （5）
（2）信息熵
信息熵[16]是由香农在1948年提出的一个概念，用它来表示在随机事件发生之前的结果不确定性的量度，以及在随机事件发生之后，人们从该事件中得到的信息量。
根据信息熵的定义：H ()X =-∑x i ∈X
P (x i )lb P (x i )
（6）
其中，X 表示信息概率空间X =(x 1:P (x 1),x 2:P (x 2),…,x n :P (x n ))，H ()X 表示随机变量X 不确定性的量度。
（3）左右信息熵
左右熵[17]是指多字词表达的左边界的熵和右边界的熵。左右熵的公式如下：
E l ()W =-∑∀a ∈A
P ()aW |W ×lb P ()aW |W （7）E r ()W =-∑∀b ∈A
P ()Wb |W ×lb P ()
Wb |W （8）
式中，
W 表示某个单词，E l ()W 表示该单词的左熵，P ()aW |W 表示该单词左侧出现不同词的概率，a 变量
是一个变化值，表示与W 相结合的词汇。E r ()W 右熵同理。
（4）熵加权计算法本文采用熵加权计算方法
图2位置对Simhash 的影响
字符串1：能力比学历重要性高Simhash 指纹：14826313989210732151字符串2：学历比能力重要性高Simhash 指纹：14826313989210732151
H k (w )=
E l (w )+E r (w )
2
（9）
这里对特征词左右信息熵取平均。用H k (w )来表示该
单词的熵信息量。把熵因子H k 加入权值计算公式中，取两者的平方平均数作为词权重，如下所示：
etfid ()t k ,d j =
()tfidf ()t k
,d j 2
+H k 2
/2
（10）
上式的物理意义为：特征项t k 在文档d j 中出现的次数越多，在训练集中出现该特征项的文档越少，并且其信息量越大，则其权重越高。
3.2基于熵加权的Simhash 算法
基于信息熵的Simhash 算法主要是在权重方面进
行优化，首先利用基于TF-IDF 算法与信息熵进行加权得到权重，并按照其在文档中的分布进行排序，针对每个特征词汇生成的hash 再与其所在位置进行异或。
但是经过改进的权重计算后，由于训练集的不完整等因素，会导致部分特征次权重过大，最终引起查准率下降，为了解决这一问题，引入权重阈值W t 。下面就权重不均导致的问题进行证明。
设一个文档中提取出n 个关键词分别为{p 1,p 2,…,p n }，各关键词的权重为W ={w 1,w 2,…,w n }。对n 个
关键词生成hash 值，其结果为H ={h 1,h 2,…,h n }，经过叠加后生成二级指纹F ={f 1,f 2,…,f m }，m 为指纹位数，最后根据F 中f i 是否大于0生成Simhash 指纹为S 。
若存在某一特征词p k ，其权重：w k ≫w j ,j ∈[]1,n ∩j ≠k
（11）
则S 主要由p k 决定。证明如下：
设h i ={}a i 1,a i 2,…,a im ,a ij 是一个二进制变量，则：f j =∑i =1n
-(-1)a ij
w i
（12）
提取出w k ，则有：
f j =w k ∑i =1
n
-(-1)
a ij
w i
w k
（13）
因w k ≫w j ，故：w i
w k
≈0,i ≠k （14）
所以此时：
f j ≈w k ×æ
è
çöø÷-()-1a kj w k w k =-w k ×()-1a kj
（15）
最终有F 主要与p k 相关，证明完成。
以上证明同时也反映出权重对Simhash 指纹的
影响。
引入权重阈值后，此时的权重计算如式（13）所示。
w k =ìí
îïï
()
tfidf ()t k ,d j 2+H k 2
/
2，w k ≤W t
W ′t ，w k >W t
（16）
综上所述，E-Simhash 算法流程如图3所示。
E-Simhash 算法与传统的Simhash 算法有三点不同，这里主要在TF-IDF 的基础上引入信息熵进行特征词权重计算，并使用两者的平方平均数作为最后的特征词权重，同时为了避免权重过高的情况导致指纹失真，引入权重阈值，计算方式如式（16）所示。最后在生成特征词hash 时与特征词位置进行异或，使其hash 包含文档的位置分布信息。
4仿真实验与分析
本章主要模拟真实的应用场景，验证E-Simhash 算
法的性能是否比传统Simhash 算法优越。
4.1实验环境及数据集
实验环境部署在一台台式机上，机器参数如表1
所示。
数据集来自搜狗实验室中的全网新闻数据2012版，它是来自多家新闻站点近20个栏目的分类新闻，剔除低于800字符的数据，并从中随机选取1565篇进行后续实验。
首先从1565篇新闻中，根据修改比例，随机选取若干篇新闻进行修改、删除、移位、替换等随机操作，
并控
权重位置
1
2
n 12
n
…
…
位置散列11010
01101
权重加权
w 1,w 1,-w 1,w 1,-w 1-w n ,w n ,w n ,-w n ,w n
10110Hash 指纹
图3E-Simhash 算法过程
表1
实验环境参数
类别实验机
机器型号DELL R530
系统Windows 2012
存储容量1024GB
内存8GB
运行环境Python2.7Mysql 5.5.53
制修改后的文章与原始文章有一定阈值T 的相似度，生成待测样本集，之后使用传统Simhash 与本文中的算法进行比较，统计实验的相关指标。
4.2实验结果分析
实验结果中常用四种指标进行评估，分别是去重
率、查准率、召回率以及F 值[18]，其中去重率是指分类正确的样本数与总样本的比值，就本实验而言即预测为同源文章集数与总文章数的比值。
实验1去重率对比
在1565篇新闻中随机选取1162篇进行任意修改，选取不同的海明距离，对比两种算法中的准确率，实验
中T =15%，即每篇新闻保持不超过15%修改，指纹长度为128位，词权重阈值W t =90，实验结果如图4所示。
实验结果表明在海明距离大于2时，E-Simhash 算法均具有很高的去重率。在实际应用中海明距离一般取10左右，所以E-Simhash 算法的去重效果更好。
实验2修改T 阈值对比
本次实验修改文本的相似度阈值T ，分别对5%、10%、15%、20%的修改下，海明距离选为10，即低于10则认为相似，比较两种算法的去重率，结果如图5所示。
从实验结果中可知，E-Simhash 算法去重率分别以0.833∶0.679、0.751∶0.529，0.687∶0.476、0.661∶0.451优于传统的Simhash 算法，并且随着文章变动的增加，其去重率都呈现下降趋势。实验结果表明在不同修改阈值T 下，
E-Simhash 算法均优于传统的Simhash 算法。实验3查准率、召回率以及F 值对比
字符串函数去重
在实验中，从新闻集中随机选取一篇文章进行随机修改，并保证与原文有90%的相似度，对比基于Simhash 指纹与E-Simhash 算法的查准率、查全率以及F 1值。其中海明距离选取10；实验进行100次，并取它们的平均值，作为最终结果，结果如图6所示。
通过实验数据可知，E-Simhash 算法在查准率0.963∶0.818，召回率0.867∶0.621，F 1值0.912∶0.706优于传统的Simhash 算法。结果表明E-Simhash 算法在查准率、召回率以及F 值方面均比普通的Simhash 算法有很大的提升，也足以证明E-Simhash 算法的优越性。
5总结与展望
针对传统Simhash 算法在权重计算方面的欠缺，以
及算法中不能考虑到文档特征词汇的分布信息，本文通过优化权重计算，使用TF-IDF 和信息熵的平方平均数作为特征词的权重值，考虑到部分权重过大导致信息失真，引入权重阈值，并在此基础上将特征词的位置信息引入到hash 计算中去，从而提升Simhash 算法的去重率、查准率，并通过仿真实验论证了E-Simhash 算法在各方面均优于传统的Simhash 算法，但是E-Simhash 算法依然存在一些不足，在短文本相似度检测方面准确度不高，而且本文中的权重计算方法仍有可改进之处，计算中的关键词权重未必非常准确，未来可通过优化权重计算，如引入LDA 主题模型[19]可提升Simhash 算法的适应范围。
参考文献：
[1]Bhat W A.Bridging data-capacity gap in big data storage[J].
10111213141516171819
海明距离
1234567891.0
0.80.6
0.40.2
去重率
0E-Simhash
Simhash
图4不同海明距离下去重率对比
1015
20
5
修改阈值T /%
1.00.80.60.40.20
E-Simhash Simhash
去重率图5不同阈值下去重率对比
召回率
1.00.80.60.40.2
E-Simhash Simhash
数值
查准率
F 1
图6综合性能比较

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。