基于N-Gram的文本去重方法研究

王小华，卢小康

（杭州电子科技大学计算机应用研究所，浙江杭州310018）

0 引 言

随着因特网的迅速发展，越来越多的信息出现在互联网上。信息规模无限，而人们的精力有限，搜索引擎技术的产生，使得人们能够以最快的速度找到需要的信息。然而，互联网上存在大量的重复信息，降低了搜索引擎的效率，使资源检索的效果大打折扣。如何快速，准确地去除重复的文本信息是一个值得研究的课题。由于大部分的重复信息都是通过直接或间接复制产生的，所以文本去重有时也被称为文本复制检测。目前，国内外研究学者对文本去重已经取得不少成果，国外典型的有sif系统，该系统提出基于字符串匹配的方法来度量文件之间的相似性［1］；还有Stanford大学提出的COPS系统等［2］。国内典型的有CDSDG系统［3］，该系统以数字水印技术为基础，采用基于注册的机制来解决数字商品非法复制问题。本文提出基于N-Gram和特征映射的文本去重方法，将文本映射成哈希值序列，通过比较哈希值序列之间的相似来程度来判断文本是否重复。本文创新点在于将N-Gram项与映射函数结合起来，将文本映射到一个足够大的空间。该空间能保证不同的文本映射到同一个值的概率非常小。实验证明，该方法速度快，同时能达到满意的去重效果。

1 去重算法思想概述

1.1 常用汉字选取

《中华字海》收录了汉语单字85 568字，可见构成文本的汉字数量相当大，而大部分的汉字并不常用，因此如果将不常用的汉字和一些特殊符号作为禁用词，在文本预处理阶段将它们从文本中去掉，可以提高程序的处理的速度。大规模的文本实验结果显示，《现代汉语常用字表》提出的2 500个常用字覆盖率达97.97%，1 000个次常用字覆盖率达 1.51%，合计（3 500字）覆盖率达99.48%［4］。常用汉字的覆盖率如此之高，所以本文利用《现代汉语常用字表》提出的2 500个常用汉字对文本进行预处理。建立常用字编码对照表，将选取的2 500个常用汉字（汉字记为W）进行编号（编号记为V），编号从1-2 500。通过查表可以得到每个汉字的编码，或每个编码对应的汉字。如表1所示：

表1 常用字编码表

1.2 N-Gram 项

对文本进行处理，需要提取文本特征，文本特征的表示方法非常关键。本文通过提取文本的NGram项，将N-Gram项组成的序列作为文本特征［5］。对于中文来说，N-Gram项一般由相邻的字构成。例如：从现代汉语中提取2-Gram项，可以得到现代、代汉、汉语3个2-Gram项。N-Gram作为文本的特征与提取词语作为文本的特征相比，可以避免使用词典和分词程序，从而提高特征提取的速度。采用N-Gram项作为文本特征还有一个重要的优点是它不会遗漏任何连续N个字符重复的文本序列。N-Gram项也存在缺点：与真正的词相比，语义没有那么明显。而且，随着N的增长，N-Gram项组成的序列所占的空间会大大增加，同时，计算机处理N-Gram的计算量也大大增加。因此，N的取值一般不宜过大。

1.3 文本特征映射模型

由于N-Gram项所占的空间比较大，如果直接利用N-Gram项进行文本特征匹配计算量非常大，对程序的运行速度影响很大。因此，采用一种哈希映射的方式，把N-Gram项映射到一个数值，原本在去重过程中，需要进行字符串匹配，现在只需要进行数值查找，这样一来就将去重算法从匹配算法转变到查找算法。这样不但降低了算法的时间复杂度，也降低了算法的空间复杂度。

2 算法过程描述

该算法过程可以描述成以下步骤：

第一步 对照常用汉字编码表，将文本转换成汉字编码的数值序列。在这个过程中，首先剔除文本所有非常用汉字，标点符号以及其它的字符，仅保留常用汉字，将得到的汉字序列通过对照常用汉字编码表转换成汉字编码的数值序列，即（Vn）；

第二步 对第一步中所得到的数值序列（V0，V1，V2，V3，V4，V5，…，Vn）提取 N-Gram 项。对于数值序列提取N-Gram项的方法与提取中文N-Gram项类似。本文取N为4。数值序列提取得到4-Gram项序列：（），…），该步骤最终输出一个N-Gram项的序列；

第三步 对N-Gram项进行哈希映射，将N-Gram项映射到一个4字节的数值。我们将每个NGram项通过哈希函数映射到一个可以用4字节表示的数字Hi，即（Hi。这样就由N-Gram项的序列映射成哈希值的序列（H1，H2，H3，…）。为了叙述方便，称该哈希值序列为文本哈希序列Sh；

第四步 从文本哈希序列Sh中抽取文本特征序列S′f。具体抽取策略下文会进一步描述；

第五步 用待去重文本的文本特征序列S′f与已经注册文本的文本哈希序列Sh进行查找对比。如果和Sh中相同值的数量比值达到设定的阈值Tset，判定文本重复，否则不重复。

3 算法改进与效率优化

确定去重算法后，可通过两两文本的对比进行去重。以下几点是对算法改进和优化。

（1）映射哈希函数的构造。本文使用如下哈希函数：

在本文中，N-Gram项所选取的N为4，且V的取值范围是从1-2 500，因此可将哈希值看成是2 500进制的数字，即当b=2 500时，该哈希函数映射空间完全不存在冲突。虽然该函数的哈希值在理论上完全不冲突，但是计算机实际上难以处理。因为函数产生的最大哈希值为2 5004-1，当前32位字长的无符号整型最大为232-1。由于无法利用32位来保存该哈希值，如果用大于32位的空间来保存哈希值，计算机处理起来效率很低。因此我们需要选择一个合适大小的基数b值，使得N-Gram项映射到的值产生的冲突的概率很小并且函数哈希值能用32位空间表示。在本文中，b值的选取满足不等式：2 500×b3+2 500×b2+2 500＜232-1。解该不等式，b!44。本文选取b=44，实验证明，该取值同时能满足上述的两个要求。

（2）文本特征序列S′f的抽取策略。从文本哈希序列Sh中抽取合适的文本特征序列S′f，要求文本特征序列S′f选择合适的长度，过长的S′f序列会导致算法的运行效率过低；S′f太短则会影响算法的准确率。本文S′f提取策略是从每个文本哈希序列Sh中每隔一定距离D（距离长度记为D）提取一个数值组成文本特征序列 S′f。例如，当距离参数 D=20 时，Sh=（H0，H1，H2，H3，…），则所提取的 S′f=（H0，H20，H40，H60，…）。一种经过改进的策略是动态的改变D的值，不同的文本长度取不同的D的值以及在文本中不同位置取不同的D值，以提高去重的正确率。

（3）待去重文本的文本特征序列S′f与已经注册文本的文本哈希序列Sh进行查找对比算法的效率优化。由于Sh序列和S′f序列都由数值组成，可以先对Sh和S′f进行排序，然后利用折半查找算法进行对比查找。折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。

4 实验结果与讨论

根据上述算法进行了程序实现，用以评价算法正确性与效率。算法正确性主要有以下两个标准：重复文本的召回率（Recall）和去重的准确率（Precision），下面给出定义：Recall=实验中采用的语料库是搜狗实验室提供的文本分类语料库，该文本分类语料库来源于搜狐新闻网站保存的大量经过编辑手工整理与分类的新闻语料与对应的分类信息［6］。从每个类别中随机选取了1 000篇作为实验文本，8个类别一共8 000篇文本。经过人工与计算机结合的方式，确定其中存在重复文本的数量为450篇，事先已经将重复文本做标记。然后利用本实验系统对这8 000篇文本进行测试。

实验测试不同的阈值对去重结果的影响。实验结果如图1所示，为了能更直观地表示实验结果，本文横坐标Tset的值从大到小递减。

从实验结果可以看出，当Tset=0.6的，去重的准确率和召回率两者效果都较为理想。观察发现，当Tset=0.7时，误判为重复的文本主要是体育报道以及照片描述类文章。误判为重复的文本之间有共同的特点：文本的结构大部分相同，只有少数词语和数据改变；文本长度通常较短。

本文根据上述初步的实验结果分析，对程序做了修改，对文本长度小于200的文本单独做测试，发现在Tset=0.7的时候，对于短文本的去重效果最为理想。这表明，一个合适的解决方法是动态地设置Tset值，把Tset值与文本长关联起来，对于较短的文本设置较大的值，灵活的设置Tset值能提高去重效果。

5 结 论

本文提出了基于N-Gram的文本去重算法，在文本去重时采用不同Tset阈值设置，能满足不同的去重效果需求，说明算法具有很大的灵活性。算法的速度较快，在对普通网页文本去重应用中，取得了很好的效果。算法存在的缺点之一没有利用文本的语义信息，这会导致对在句子中因少数关键字不同而含义不同的文本的去重效果不理想。只有利用文本的语义信息才能判断上述的重复情况。所以，如果能将文本的内容信息与语义信息结合起来，会取得更好的去重效果，这应该是在文本去重的下一步研究的方向。

图1 Tset参数对去重结果的影响

［1］ Manber U.Finding similar files in a large file system［C］.California：Proceedings of theWinter USENIX Conference，1994：1-10.

［2］ Brin S，Davis J，Garcia-Molina H.Copy detection mechanisms for digital documents［C］.California：Proceedings of the ACM SIGMOD Annual Conference，1995：98-409.

［3］ 宋擒豹，沈钧毅.数字商品非法复制和扩散的监测机制［J］.计算机研究与发展，2001，（38）：121-125.

［4］ 朱巧明.中文信息处理技术教程［M］.北京：清华大学出版社，2005：16-17.

［5］ 苗夺谦.卫志华.中文文本信息处理的原理与应用［M］.北京：清华大学出版社，2007：220-221.

［6］ 搜狗实验室.搜狗实验室文本分类语料库［EB/OL］，http：//www.sogou.com/labs/dl/c.html，2008-12-31.