基于相似度估计文档重复率检测算法研究

王钰宁，刘晓霞，周绍军

（四川水利职业技术学院信息工程系,四川崇州,611231）

关键字：重复率；相似度；估计；检测算法

1 当前现状

Web 信息正经历着爆炸性增长，海量文档中存在大量的相似信息，斯坦福大学研究成果表明：近似的网页数量占总网页数量的比例为29%，而完全相同的网页数量大约占总的网页数目的22%。这些重复网页大多只在内容上略微修改，有的甚至只是格式不同。这些相似性文档一方面消耗了高额的检索资源，另一方面影响了用户的使用。文档的数字化和易获性在提供了更方便的交流学习环境的同时，也使得非法复制、剽窃等行为越来越容易。

文档的相似性检测技术从文档内容的相似程度上判断文档是否为有抄袭剽窃的嫌疑。所谓文档相似性检测，就是判断一个文件的内容与另外一个或者多个文件的相似程度，以检测抄袭剽窃。而剽窃不仅仅意味着对原作原封不动地照抄，还包括对原作的移位变换、同义词替换以及改变说法重述等方式。文档相似性检测技术可以应用在数字化图书馆、搜索引擎、论文查重、基金申请、奖励评审等很多领域，为用户减小信息的存储空间，高速搜索信息，防止论文、基金申请书、项目报奖、专利剽窃和网页去重提供了很好的解决方案。

文档相似性检测的核心内容就是判断两篇文本内容是否存在重复成分，并给出一个相似度数值评估。两篇文档A 和B的相似度R(A,B),是一个介于0 和1 之间的数。相似度越大，文本重复成分越多。计算文档相似度，首先需要把文档用数据模型表示。目前，根据不同的文档表示方式，可以把目前的主要的文档相似性检测方法分为三类：基于词频统计的方法[3,4]、基于近似指纹的字符串匹配的算法和基于相似度估计的算法。基于词频统计的文档相似性的检测方法主要检测的就是文档词频的相似性。基于字符串比对的文档相似性检测方法主要检测的就是文档经过分词处理后的字符串集合的交集大小。基于相似度估计的算法既有检测文档词频相似性的方法，例如随机投影。也有检测字符串集合交集为目标的minwise 相似度估计方法。

基于词频统计的方法存在着检测结果准确率低、误判率大的缺点。文档中一些常用词汇频率较高，易出现误差带来噪声。并且该方法的向量空间模型的列的维度很大，实际比对时所花费的时间多。基于字符串比对的方法使用简单，但只能进行简单的字符串匹配，无法发现复杂的相似性方式的重复文本，比如同义词替换、改变说法等。同时对于海量数据，该方法需要两两文档的比对，这种方法实际上是不可行的。

2 检测算法

基于相似度估计的算法一般采用降维的方式，将文档向量或者字符串集合转化为k 个指纹的集合，指纹即为固定长度的较短的文档的字符串，这k 个指纹集合用来表征一篇文档，从而当求解相似度时，直接比对指纹集合的相似度即可得文档的相似度。

shingle 算法是最常见的文档相似性检测算法。将一个文档分解成由w 个短字符构成的字符串集合后，一个连续的的子字符串被称为一个shingle。得到字符串集合后就可以通过Jaccard 相似度等简单的度量标准进行相似度检测了。比如，一个文档

其中S(A)表示集合A的大小。整个抽取过程如图1所示：

图1 shingle 算法流程图

如果是低维的小数据集，我们通过线性查找就可以容易解决，比如使用shingle 算法，但如果是对一个海量的高维数据集采用线性查找匹配的话，会非常耗时。研究者想通过建立Hash Table 的方式我们能够得到O(1)的查找时间性能，其中关键在于选取一个比较好的散列函数，一般的，在对数据集进行hash 的过程中，会发生不同的数据被映射到了同一个桶中（即发生了冲突collision），这一般通过再次哈希将数据映射到其他空桶内来解决。在文本检测时，相似的内容转化为数据时会被转化为相邻的数据点，但研究者希望原先相邻的数据点能被映射到同一个桶中，因此需要一个比较好的散列函数。

在shingle 算法的基础上提出的minwise 哈希方法可以解决该问题。minwise 哈希算法将字符集合的求交集问题转化为某一事件发生的概率问题。在算法中，不是简单的对shingle 集合进行计算量较大的比对，而是对每个文档的shingle 集合进行minwise 散列函数处理，进行降维，然后再计算相似程度。minwise 哈希函数是一类局部敏感散列。

局部敏感散列的基本思想是：将原始数据空间中的两个相邻数据点通过相同的映射或投影变换（projection）后，这两个数据点在新的数据空间中仍然相邻的概率很大，而不相邻的数据点被映射到同一个桶的概率很小。如图2，球q 和球p 相近，被分到一个桶内，它们与粉球和蓝球相距较远，所以没有被分到一个桶里。

图2 局部敏感散列示意图

如果我们能够找到这样一些哈希函数，使得经过它们的哈希映射变换后，原始空间中相邻的数据落入相同的桶内的话，那么我们在该数据集合中进行近邻查找就变得容易了，将原始数据集合分成了多个子集合，而每个子集合中的数据间是相邻的，且该子集合中的元素个数较小，因此将一个在超大集合内查找相邻元素的问题转化为了在一个很小的集合内查找相邻元素的问题，显然计算量下降了很多。实际上，查找近邻就是在查找文本检测时的相似内容，因为，在转化时，相似的内容会被转化为相邻的数据点。

minwise 哈希算法采用局部敏感散列的思想，首先通过minwise 哈希函数将相似数据映射到一个子集合中，运用蒙特卡罗思想，将集合的求交集问题转换为待查文本内容的数据点被映射到相应集合中的概率问题。通过一定的实验次数k 来估计事件的发生概率，从而估计两篇文档的相似度。同时，将对文档进行釆样的实验中生成的minvalue 存储下来，作为文档的特征值向量，以便之后的其他文档与此文档的相似度比对。

后来，在minwise 哈希算法的基础上，有人提出了simhash 算法。simhash 算法的核心思想是用一个b 位的值来表示文档的特征值，然后使用simhash 之间的海明距离来衡量相似性。海明距离的定义为两个二进制序列中对应位不同的个数。与传统hash 函数相比，simhash 函数也是一种局部敏感散列LSH。因此，函数具有一个特征，即越相似的文档具有越相似的simhash 值，也就是说海明距离越小。显而易见，仅使用b 位的值来表示文件的特征，节省了大量的存储开销；海明距离计算简单高效，simhash 使用海明距离来衡量相似性，计算复杂性也得到大大降低。简而言之，simhash 算法将minvalue 值从髙位降低到位，然而，simhash 算法的精确度也会有所损耗，并且与simhash 的位数b 有关，b 越大精确度越高。

3 问题探讨

目前的文档相似性检测技术还在一些方面存在着一定的问题，同时这些问题也即是该技术在未来的研究方向。

3.1 海量性文档的相似性检测

海量数据的相似性检测一直是文档相似性检测的难点。随着信息爆炸时代的到来，各个系统中的数据都是亿万级别的，数据特征的存储空间和相似性的检测时间都有了更高的要求。b 位minwise 哈希算法中 b 越大精度越高，但是相应的存储空间和计算时间也变得巨大。所以需要一种比较好的方法去解决这个问题。

3.2 语义级文档相似性检查

中文信息处理技术目前还不成熟，分词、词义标注和句法分析的处理效率还不是非常理想，此外，汉语是一种意合语言，其语言现象非常复杂。目前包括minwise 在内的文档相似性检测方法只能发现一部分的文本复制方式，例如同义词替换、断句等等，但是对于句子结构发生变化的一些复杂文本复制方式，还没有找到理想的解决方法。需要考虑将语义分析作为重要突破点，才能从语义层面最终完全解决自然语言的相似性检测。

3.3 跨语言相似性检查

目前，很多相似性的文档并不只存在于同一语言之中，直接抄袭同一语言的著作较为容易被检査到，但若拿一篇文档通过翻译或摘译后则很难发现。在未来的工作中，可以考虑不同语言的因素，综合各类语言的句法结构和语义两方面的信息来生成相似的指纹信息，从而度量不同语言的文档间的相似性。

3.4 分布式数据相似性检测

现今大量的文档以分布式的形式散列在各地，这些大规模的数据相似性的文档相当多，而目前的文档相似性检测系统大多只能针对系统内部的文档进行检测，而进行分布式数据相似性检测是未来检测的发展方向。

4 总结

文档相似性检测技术的广泛应用推动了信息时代的发展，有效的保护了原创的信息内容。针对海量数据下的相似性检测，基于相似度估计的检测方法保持高效的性能的同时，大大降低了时间复杂度和空间内存消耗。本文对基于相似度估计的shingle 算法和minwise 算法进行了一定分析。特别地，minwise 哈希算法采用局部敏感序列的思想，降低了在海量数据下的检测相似性的部署难度。同时，文档相似性检测技术的还存在着一定不足，本文总结了该技术目前存在的一些问题和未来的研究方向。