基于后缀树的重复文档检测
作者：冯金波
来源：《软件导刊》2015年第05期
        摘 要：传统的重复文档检测方法是以单词或n-grams为单位提取特征，造成特征集合过于庞大。针对该缺点，提出以句子块作为文档特征的提取方法，将每个文档表示成句子长度序列，使用后缀树快速匹配公共子串。实验中，使用两个标准文档集与3种经典方法在有效性和效率方面进行比较，结果表明新算法有较高的准确率和效率。
        关键词：重复文档；后缀树；句子块
        中图分类号：TP312
        文献标识码：A 文章编号：1672-7800（2015）005-0070-04
        作者简介：冯金波（1989-），男，江苏盐城人，江苏大学计算机科学与通信工程学院硕士研究生，研究方向为信息检索、数据挖掘。
        0 引言
        重复和近似重复（near-duplicate）文档在人们日常生活中经常出现。在互联网中，存在着大量相似网页。除常见的网页转载、抄袭外，部分重复网页为少数网站为了提高网页检索排名，作搜索引擎优化（SEO），使用多个URL指向同一个网页及镜像站点（mirror site），由于这些镜像的存在使得网络爬虫在抓取网页时产生了大量的重复网页。研究表明，在一个大型爬虫系统中，如Baidu、Google和AltaVista，大约有30%的网页是冗余信息，即这些网页和另外70%的网页完全重复或近似重复[1]。
        1 研究综述
        Broder[2]提出将文本中连续n个term序列作为文本的一个特征，称之为n-shingle。然后，根据每个文档的shingles集合计算相似度，判断两个文档是否重复。如果文档d有|d|个term，那么该文档有|d|-n+1个shingles。所提取的shingles集合过于庞大，此后Shingle算法又增加了过滤模块，对提取出的shingles集合进行过滤处理。M-Theobald等[3]提出的SpotSigs算法，以停用词（stop word）作为先行词，提取其后的k个词形成一个spot特征码，作为一个特征。停用词选择对SpotSigs算法至关重要，不同的停用词列表会影响最终特征集。Wang等[4]提出了一种句子级别的特征提取算法，以连续的句子长度序列作为一个特
征，每个特征用数值字符串表示。由于该算法没有使用文本信息，且以连续的几个句子为一个特征，在大规模数据集下运行效率较高。
        2 基于句子块的特征提取算法
        以单词或者n-grams为单位提取特征码时，提取出的特征过多，为优化性能，通常需要过滤某些特征，从一定程度上降低了准确率。本文以句子作为一个基本提取单位，将匹配出的两个文档间的公共句子块作为一个特征。
        图1描述了本文算法检测一对文档的处理流程。首先，对文档预处理，比如提取文档正文内容、分割句子及去除停用词（stop word），把每个文档转换成一个字符串，其中每个字符代表一个句子的长度；然后，为匹配出所有的公共句子块，需要出两个字符串的所有公共子串，因此使用后缀树（suffix tree）处理能够快速匹配；最后，对所得到的所有子字符串进行验证。由于本文算法是以句子长度为基本单位，且使用了后缀树求解公共子串问题，因此将该算法简称为SL+ST（Sentence Length+Suffix Tree）。
        2.1 使用后缀树匹配特征
        去除每个句子中的停用词（stop word）后，统计每个句子剩余的单词个数，即句子长度。为方便编写程序，当长度为10～35时用字母a～z替换。对本文实验所采用的两个数据集进行分析，发现去除停用词后长度超过文档字符串是什么35的句子分别只占了0.27%和0.10%，因此对于长度超过35的句子忽略不计。
        采用Kth-in-sentence选择策略对每个句子存储开始的两个词（term）作为一个过滤特征的判断条件[5]，最终将一个文档表示成一个句子长度序列的字符串，其中每个字符表示其对应的句子的长度，字符串长度则代表该文档的句子数量。
        为检测两个文档是否为重复文档，需要比较这两个文档所对应的字符串。文档查重研究可以转换成求解两个给定字符串的公共子串问题。
        文献[6]介绍了几种常用的求解公共子串的算法。对于两个长度分别为m和n的字符串，动态规划算法时间复杂度高达O（mn），而后缀树算法是线性的，为O（m+n），本文采用后缀树算法来求解公共子串。
        2.2 特征提取示例
        2.3 验证特征
        如直接将两个文档间连续的具有相同句子长度的一个句子块作为一个特征，可能会选择错误的句子块。比如匹配出的句子块虽然满足对应的句子长度相等这个条件，其实它们并不是相似的句子。因此需要对提取出的特征进行验证，以过滤掉一些不相似的句子块。
        在预处理阶段，每个句子存储了开始的两个单词（terms），通过比较句子块中每个句子所对应的terms来验证。如果句子块中对应的句子terms相同，则保留；如果句子块中间有某个句子未通过验证，则可以切分该句子块，切分之后句子块长度如为1则丢弃。比如一个句子块长度为5，第三个句子不相似，那么可以切分成两个句子块；如果一个句子块长度为4，第二个和第三个句子不相似，那么丢弃整个句子块。
        2.4 Jaccard相似度
        提取文档对的特征集合后，需要根据特征集合计算出这对文档的相似度，本文使用Jaccard相似度，定义如下：
        3 实验
        3.1 实验数据集
        实验采用两个英文文档集：AP90-S和Twitter。这两个文档集都是从标准TREC数据集中生成，AP90-S是AP90的一个子集，Twitter是ClueWeb12-CatalogB中的一个子集。首先，从AP90中手动选择6个文档；然后将这6个文档作为查询语句并使用Terrier检索系统搜索AP90数据集，得到6个检索结果；最后从这6个结果中依次选择前150个文档，去除重复（指文档ID相同）得到的文档集合就是AP90-S。直接从ClueWeb12-CatalogB中选择以twitter命名的文件夹得到的就是Twitter文档集。AP90-S和Twitter文档集的详细信息见表1。
        3.2 文档集中句子分布
        因为SL+ST算法以一个公共句子块作为一个特征，在匹配句子块时以句子长度为依据，所以需要对文档集中句子大小分布情况作分析。AP90-S和Twitter文档集中句子分布信息见表2（表中句子长度都是指预处理后的句子），以标点集合{. ； ！ ？}划分句子。文档集AP90-S的891个文档共有56 432个句子，平均每个文档有63.34个句子，每个句子平均有10.42个terms。文档集Twitter中平均每个文档有75.04个句子，每个句子平均大小11.53。从表2可以看出，大小超过35的句子很少，分别占0.27%和0.10%，因此将超过35个terns的句子去除对
整体的影响很小。

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