Simhash算法在文本去重中的应用

张 航，盛志伟，张仕斌，杨 敏

成都信息工程大学 网络空间安全学院，成都610225

1 引言

随着计算机与信息技术的高速发展以及信息存储技术[1]的广泛应用，人们已经步入大数据时代[2]，数字化信息量呈现爆炸式增长。数据量大、复杂度高以及冗余度高是当前大数据信息的特点。研究表明，一些存储系统中的冗余数据已经达到了60%[3]，并且会随着数据量的上升而增多。因此在有限的存储空间和时间内，如何存储更多有效精炼的信息成为当前研究的热点。

在去除冗余数据方面，Simhash 算法是当前公认的最好的去重算法。该算法是一种局部敏感哈希算法[4]，它能够将高维数据进行概率降维并映射为位数较少且固定的指纹，之后再对指纹进行相似度比较来反应数据之间的相似程度。其中比较算法通常使用海明距离[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算法的分析

定义1 Simhash 算法的原理是对于两个给定的变量x,y，哈希函数h 总是满足下式：

其中，Pr 表示h( x )=h( y )的可能性，sim( x,y )∈[0,1]是相似度函数，一般也用雅可比函数Jac(x,y)来表示变量x,y 的相似度，sim( x,y )表示如下：

h 属于哈希函数簇F，需要满足以下条件：

称F 为(d1,d2,p1,p1)上的敏感哈希簇函数[11]。其中d( )

x,y 表示x,y 变量之间的距离，通俗而言，表示如果x,y 足够相似时，那么它们映射为同一hash 函数的概率也就足够大，反之哈希值相等的概率足够小。

由于传统hash函数[12]与Simhash函数最大的不同在于局部敏感性，如果针对输入的数据做些局部修改，经过传统hash函数运算后可能会得到完全不同的结果，而Simhash 计算的结果则很相似，因此可以使用Simhash函数产生的指纹相似程度来表示源数据之间的相似程度。

2.2 Simhash算法流程

Simhash 算法的流程是首先定义一个f 维度的空间，然后在这个空间中定义每一个特征所对应的向量，接着将所有的向量结合自身的权重进行加权、求和就得到了一个和向量作为结果。最后再对该结果进一步地进行压缩转化，其规则是：对每一个向量得出一个相对应的f 位签名信息，若向量维度的值大于0，则置其签名所在的位置为1，否则置为0。通过这样的转化方式，得到的签名信息表证了此向量在各个维度中的值的信息。Simhash的算法流程图如图1所示。

图1 Simhash指纹生成

Simhash算法的具体步骤如下：

步骤1 初始化

针对数据集大小及存储成本确定Simhash 位数以及f 维向量空间，同时初始化f 位二进制数S 均置为0。

步骤2 文档预处理

主要包含两部分，第一部分是分词，寻找文档的特征词汇以及去除文档停用词等。第二就是赋权，一般而言这里普遍忽略了权重的计算设置为1[13]。

步骤3 生成hash值

利用传统的散列算法对步骤2 中的每个特征词计算一个f 位hash值，并进行下列运算：

for k in V ：

for i in f ：

if（i==0）：

Vi=Vi+wki

else：

Vi=Vi-wki

步骤4 压缩变换

针对最后生成的向量V ，对每一位进行转化处理。

if V[i]＞0：

S[i]=1

else：

S[i]=0

步骤5 指纹生成

输出最终的签名S 作为该文档的指纹，之后再进行海明距离或编辑距离计算相似度。

步骤6 距离计算

在Simhash 算法中通常使用海明距离进行相似度计算。海明距离通过比较两个文档指纹中不相同的个数来度量两个文档之间的相似度[14]。海明距离越大，代表两个字符串的相似度越低，反之则两个字符串相似度越高。对于二进制字符串而言，可以使用异或运算来计算两个二进制的海明距离。举例说明如下：

例1 设a,b 为两个二进制数，其中：

则可知a,b 两个二进制数只有第二位不同，故Hamming(a,b)=1。

也可利用异或操作，统计异或结果中1 的个数。a⊕b=01000，共有1个1，故海明距离为1。

2.3 Simhash存在的一些问题

传统Simhash算法在权重计算方面通常设置为1或特征词出现的次数，这很容易造成信息丢失，导致最终的Simhash 指纹准确性降低，并且根据Simhash 算法可知它不表现出词汇分布信息，关键特征词调整顺后，不会影响最终生成的Simhash指纹。

如图2所示，两个关键词的位置调整下就可能导致最终的意义大不相同，但是传统的Simhash算法生成的指纹却是一样的。

3 改进的Simhash算法

本文提出了一种新的基于信息熵的Simhash 算法，考虑到传统Simhash算法中针对权重的计算不充分，以及不能更好地反应文档中词汇的分布特征，本文中引入信息熵理论来解决上述问题，并且在hash计算中加入位置关系特征，从而提升Simhash算法的准确度。

3.1 熵加权权重计算方法

（1）词频-逆向文件频率

词频-逆向文件频率（TF-IDF）[15]算法是一种常用的文本特征权重计算方法，特征词tk在文档dj中的TF-IDF值记为tfidf(tk,dj)，有如下定义：

定义2 特征项tk在文档dj中出现的频率tf(tk,dj)为：

式中，nj,k表示特征词tk在文档dj中出现的次数，表示文档dj中的所有特征词的个数。

定义3 反文档频率idf(tk,dj)是权衡特征词重要性的系数，其定义为：

式中，{ j:tk∈dj} 为含有特征词tk的文档综述，|D|为语料库中的文件总数。

定义4 TF-IDF函数，特征词的词频权重定义为：

（2）信息熵

信息熵[16]是由香农在1948 年提出的一个概念，用它来表示在随机事件发生之前的结果不确定性的量度，以及在随机事件发生之后，人们从该事件中得到的信息量。

根据信息熵的定义：

其中，X 表示信息概率空间X=(x1:P(x1),x2:P(x2),…,xn:P(xn))，H( )X 表示随机变量X 不确定性的量度。（3）左右信息熵

左右熵[17]是指多字词表达的左边界的熵和右边界的熵。左右熵的公式如下：

式中，W 表示某个单词，El(W)表示该单词的左熵，P( a W|W )表示该单词左侧出现不同词的概率，a 变量是一个变化值，表示与W 相结合的词汇。Er(W)右熵同理。

（4）熵加权计算法

本文采用熵加权计算方法这里对特征词左右信息熵取平均。用Hk(w)来表示该单词的熵信息量。把熵因子Hk加入权值计算公式中，取两者的平方平均数作为词权重，如下所示：上式的物理意义为：特征项tk在文档dj中出现的次数越多，在训练集中出现该特征项的文档越少，并且其信息量越大，则其权重越高。

3.2 基于熵加权的Simhash算法

基于信息熵的Simhash 算法主要是在权重方面进行优化，首先利用基于TF-IDF 算法与信息熵进行加权得到权重，并按照其在文档中的分布进行排序，针对每个特征词汇生成的hash再与其所在位置进行异或。

但是经过改进的权重计算后，由于训练集的不完整等因素，会导致部分特征次权重过大，最终引起查准率下降，为了解决这一问题，引入权重阈值Wt。下面就权重不均导致的问题进行证明。

设一个文档中提取出n 个关键词分别为{p1,p2,…,pn}，各关键词的权重为W={w1,w2,…,wn}。对n 个关键词生成hash 值，其结果为H={h1,h2,…,hn}，经过叠加后生成二级指纹F={f1,f2,…,fm} ，m 为指纹位数，最后根据F 中fi是否大于0生成Simhash指纹为S。

若存在某一特征词pk，其权重：

则S 主要由pk决定。证明如下：

设hi={ai1,ai2,…,aim},aij是一个二进制变量，则：

提取出wk，则有：

因wk≫wj，故：

所以此时：

最终有F 主要与pk相关，证明完成。

以上证明同时也反映出权重对Simhash 指纹的影响。

引入权重阈值后，此时的权重计算如式（13）所示。

综上所述，E-Simhash算法流程如图3所示。

图3 E-Simhash算法过程

E-Simhash 算法与传统的Simhash 算法有三点不同，这里主要在TF-IDF 的基础上引入信息熵进行特征词权重计算，并使用两者的平方平均数作为最后的特征词权重，同时为了避免权重过高的情况导致指纹失真，引入权重阈值，计算方式如式（16）所示。最后在生成特征词hash 时与特征词位置进行异或，使其hash 包含文档的位置分布信息。

4 仿真实验与分析

本章主要模拟真实的应用场景，验证E-Simhash 算法的性能是否比传统Simhash算法优越。

4.1 实验环境及数据集

实验环境部署在一台台式机上，机器参数如表1所示。

数据集来自搜狗实验室中的全网新闻数据2012版，它是来自多家新闻站点近20个栏目的分类新闻，剔除低于800 字符的数据，并从中随机选取1 565 篇进行后续实验。

首先从1 565篇新闻中，根据修改比例，随机选取若干篇新闻进行修改、删除、移位、替换等随机操作，并控制修改后的文章与原始文章有一定阈值T 的相似度，生成待测样本集，之后使用传统Simhash与本文中的算法进行比较，统计实验的相关指标。

表1 实验环境参数

4.2 实验结果分析

实验结果中常用四种指标进行评估，分别是去重率、查准率、召回率以及F 值[18]，其中去重率是指分类正确的样本数与总样本的比值，就本实验而言即预测为同源文章集数与总文章数的比值。

实验1 去重率对比

在1 565 篇新闻中随机选取1 162 篇进行任意修改，选取不同的海明距离，对比两种算法中的准确率，实验中T =15%，即每篇新闻保持不超过15%修改，指纹长度为128 位，词权重阈值Wt=90，实验结果如图4所示。

图4 不同海明距离下去重率对比

实验结果表明在海明距离大于2 时，E-Simhash 算法均具有很高的去重率。在实际应用中海明距离一般取10左右，所以E-Simhash算法的去重效果更好。

实验2 修改T 阈值对比

本次实验修改文本的相似度阈值T ，分别对5%、10%、15%、20%的修改下，海明距离选为10，即低于10 则认为相似，比较两种算法的去重率，结果如图5所示。

图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 算法的查准率、查全率以及F1 值。其中海明距离选取10；实验进行100 次，并取它们的平均值，作为最终结果，结果如图6所示。

图6 综合性能比较

通过实验数据可知，E-Simhash 算法在查准率0.963∶0.818，召回率0.867∶0.621，F1 值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算法的适应范围。