本文是一篇软件工程硕士论文，本文提出一种基于语义指纹和 Simhash 的中文文本快速去重方法。根据中文文本的特点，在 Simhash 算法的基础上改进了中文文本的语义指纹生成方法，并结合 single-pass 快速聚类算法对语义指纹进行快速聚类，实现了中文文本的快速重复数据去除过程。同时，在实验过程中，从算法运行速度、精度、鲁棒性等方面与 Shingle 算法进行了比较，证明了该方法的优越性。
第 1 章 绪论
1.1 研究背景和意义
随着互联网的迅速发展，网络信息共享给人们带来了极大的便利，但也因此造成了数据的大爆炸。据 2018 年 7 月中国互联网络信息中心发布的统计报告显示[1]，当用户回答“查询时遇到的最大问题是什么”时，文本中重复信息过多的比例为43.5%，排名第一。可以看出，删除网页中的重复信息可以提高用户使用搜索引擎的体验。对于搜索引擎本身，它也可以提高搜索精度，更能减少数据的存储空间。近年来，由于万维网上网站数量的指数级增长，巨大的文本数量推动了搜索技术的大跃进发展，其智能化程度也越来越高。在访问互联网的过程中，很容易复制信息和加载信息，导致大量相似甚至重复的文本。许多重复的文本无疑增加了搜索引擎的搜索负担。文本搜索引擎返回的结果包含大量重复的内容，甚至返回的搜索结果部分重复或相同的大量重复，不仅增加了浏览信息的负担，还会消耗昂贵的存储资源，降低了效率指数，并影响搜索引擎的性能。因此，如何实现准确、快速地去除重复网页是提高搜索引擎性能的关键技术之一[2]。
目前，网络上有很多相似的文本。重复的文本内容会增加访问的成本，也会影响搜索引擎检索算法的效率和性能。过滤掉重复的文本可以减轻系统的负担，提高检索效率。因此，大量重复文本的去除是搜索引擎急需解决的问题，这也关系到网站对搜索引擎权重计算的影响。
文本去重属于自然语言处理的基础研究领域，是文本智能处理过程中的关键技术和基础技术，它渗透到自然语言处理的许多方面，如信息检索、文本分类、自动问答、自动摘要、信息抽取等。它的使用价值体现在生活和工作的各个方面，比如对于文字录入人员来说，手工去重的方法费时费力，不适合日益增长的数据需求。因此，迫切需要利用计算机自动去重技术来检测文本中是否存在副本，并给出文本的位置来帮助人们去除副本。目前在大量的应用中都开始选择使用去重技术，当搜索引擎在处于运行状态下，需要进行存储的过程中，如果存在大量的文本是重复性的，不但会提高其负载度，还会对搜索引擎检索的性能产生干扰。从一定的角度分析，删除重复文本有助于系统负担的减轻，更大程度上提高搜索的效率，也有助于提高用户对搜索结果的满意程度[3]。在文档重复删除方面，可以采用重复内容删除的方法来识别文档内容的相似度，从而识别论文抄袭现象[4]。
1.2 国内外研究现状
与文本去重有关的分析，最开始是在程序复制。在上世纪 70 年代开始，相关的专家学者就开始研究避免程序被大量复制的软件和技术。1976 年，Ottenstein第 1 次提出了在对软件剽窃进行检测时，应用属性计数法。但是属性计数法相对比较简单，需要对大量的程序结构信息进行丢弃，因此造成出现过多的错误。在1996 年，Verco 和 Wise[5]提出若检测算法使用的只是属性计数的方式，并不会避免出现过多的错误。对属性计数方式进行优化的方法就是增加程序的结构信息，同时与结构度量相结合，也被叫做借助于控制流对剽窃进行检测。当前检测程序的重复度主要是借助于不同类型的方式，把程序结构测量和属性计数两者相互结合[6-8]。Parke[9]等人和 Clough[10]针对以上讲解的不同类型的检测方式进行更加细致化的讲解。除此之外，还有的专家学者借助于神经网络模型对程序重复进行检测[11]。
在研发时间上，相较于程序复制检测的方式，应用自然语言文本进行检测的技术相对较晚，大致晚了 20 年。亚里桑纳大学的 Manber 在 1993 年研发出一类工具，叫做 SIF[12]，此工具主要应用于规模较大的文件系统内，对其中具有相似内容的文件进行寻找。应用此工具无法直接对检测文本复制的问题进行解决。然而，该工具提供了一种方式与指纹类似，能够以字符串匹配作为基础对不同文件之间的相似程度进行检测。之后经过不断的发展此种方式已经被应用于检测文本复制的系统中。在 1995 年，斯坦福大学的研究人员布林（Brin）以及加西亚（Garcia）等人第 1 次在项目“数字图书馆”中提到 COPS（复制保护系统）系统的有关算法[13]。复制保护系统为之后的自然语言文本复制检测系统的发展打下了基础，因为之后，从系统框架上来看和复制保护系统近乎一致。Garcia 和Shivakumar 等还指出了 SCAM（斯坦福复制分析方法）[14]的原型，主要以复制保护系统作为基础进行完善，以对知识产权冲突进行查找作为目的。SCAM 主要借助于信息检索技术内的向量空间模型[15]借助于以统计词语的频率的方式作为基础，完成不同文本之间相似程度的检测。
第 2 章 文本去重算法与技术介绍
2.1 语义指纹基本概念
文本需要“指纹”的目的也有两个：一是检索，二是防假。语义指纹可用于检索，主要是在做一些关键字查询时不可能拿这些关键字与所有的文本原文进行比对，时间上是不可能的，比对的一定是事前整理好的特征文本，这就是文本的语义指纹。所以文本提取语义指纹是我们在文本海洋中搜寻的前提。语义指纹技术也是搜索公司特别关注的新技术之一。
语义指纹还可以用于防假，将信息打上相关的指纹就可以防止他人侵占革命成果，这有些类似于数据签名、CA 验证之类的。例如，对博客文章进行语义指纹提取就能很好地识别重复，另如将不同密级的信息进行指纹提取给信息本身一个指纹更方便而且安全的识别信息密级。
对存储在文档内的通过二进制数组形式进行代表的语义进行直接性提取，并将提取出来的数据的相等性进行对比，从而对文档的重复性进行判定的方式就是语义指纹识别。通常情况下，语义指纹属于容量较大的数组类型，因此如果将所有的语义指纹都在内存中进行存储，就会造成内存发生溢出，常规的数据库工作效率低下，因此选择应用 Berkeley DB 内存数据库，可以通过 Berkeley DB 判断该语义指纹是否已经存在。另外一种方法是通过布隆过滤器来判断语义指纹是否重复。该方法是从纯化后的文本中，选取最具代表性的关键字集，利用关键字集生成语义指纹，借助于对两个不同的文本语义指纹的汉明距离进行对比，以此对两个文本之间的相似度进行判定[24]。
2.2 文本信息处理技术
文本分析整体上属于系统性的流程，构成该流程的首个部分就是文本预处理。对网络文本信息进行采集并加工处理，进而方便计算机对采集到的网络文本信息进行识别以及处理加工。本文信息处理的部分包括停用词、中文分词以及文本表示。
2.2.1 文本分词
分词就是分割文本的过程，将其划分成不同的单词系列，而且该序列与实际的语言相符合。分词技术已经研究了很长时间[25-26]。目前通常将分词的方式划分成以统计作为基础、以字符串匹配作为基础以及以理解作为基础[27]。
首先讲解的是以统计作为基础的分词方式，此种方式在对不同汉字之间进行交互的数据进行测量时，都是结合文档内相靠近的字符频率完成的。之后再对获取的交互信息，对能否构成一个单词进行判定。应用该方式的优势就在于能够对没有在词典内加载的新出现的词语进行辨别。通常应用此种方式的统计模型有最大熵模型、隐马尔可夫模型以及 N 元语法模型。
第二种则是以字符串匹配作为基础的分词方式，也被叫做字典匹配方式。该方式依据相应的规则将要求进行划分的文本和之前设定的字典内的单词完成对比，进行匹配遵循的原则就包括最小、最大以及最优匹配原则。其中，使用最广泛的匹配方式就是正向和反向的最大匹配方式[28]。
最后，在理解的基础上进行分词。该方法主要是对分词过程中的句法和语义进行关注和分析。应用以理解作为基础的分词方式的系统通常包括神经网络以及专家系统等[29]。
第 3 章 基于语义指纹和 Simhash 的中文文本去重研究...........................22
3.1 研究模型............................22
3.2 语义指纹提取方法.................23
第 4 章 实验及结果分析.....................................32
4.1 实验环境............................................32
4.2 实验数据集............................................32
第 5 章 文本去重系统实现......................................43
5.1 系统模型..............................................43
5.2 分词模块..............................44
第 5 章 文本去重系统实现
5.1 系统模型
上一章介绍了基于语义指纹和 Simhash 的中文文本去重模型设计及实验对比，并取得了较好的效果，具有一定的实用性。在本章中，将从生活应用场景出发，以算法 Simhash 作为基础开发的文本去重系统。 ICTALAS 开源分词工具实现原始文本内容的分词。 Redis + MySQL + HBase 用于数据存储，以设计和实现文本去重系统。
图 5-1 是本文文本去重系统的整体功能模块设计图。整个系统主要分为三个部分：一是分词模块，该模块对系统进行 JSON 格式设计，并对原始文本内容进
