论文部分内容阅读
摘要：随着信息技术的飞速发展，人们在互联网上越来越容易获取到某个主题的相关信息，并把相关信息稍加修改地放入自己的文档中。本文提出了一种基于向量空间模型的中文文本相似度的检测算法，并给出了系统设计与实现的思路。算法包括预处理、中文分词、生成文本向量模型、文档相似度计算。系统通过spring框架搭建，采用多线程并行运算的方式，充分利用现代多核处理器的性能，提高了计算速率。通过在实际场景中的测试和使用，较好的验证了该算法的准确性和该系统的可行性，对文档内容抄袭行为的发现提供了很大的帮助。
关键词：中文查重；向量空间模型相似度；相似度；中文分词
1 引言
文本相似度算法有很多种，譬如简单共有词、余弦相似度、欧氏距离、Jaccard相似性等等。本文主要研究和应用了基于向量空间的TF-IDF余弦相似度算法，并且对输入的词频向量进行了一定有优化，如去停用词等。在实现该算法的过程中，充分考虑到了多核cpu的优势，采用并行运算的方式提升计算速率。在系统设计方面，本系统采用的是较新的设计理念——微服务架构，使用springboot框架将其分成多个微服务，各个微服务之间通过restful接口调用。实验表明该算法和系统具有较好的可用性。
本文首先介绍中文分词原理与实现，接下来详细介绍余弦相似度算法的原理和实现，然后是查重系统的设计和实现。
2 系统设计与实现
文档查重算法的实现需要经过文档预处理、中文分词、文档向量模型生成、文档相似度计算这几个步骤。以下图1显示了该算法的大致流程。
系统设计方面，我们将整个系统划分成三个微服务，各个微服务之间通过rest方式进行调用。以下图2是该系统的大致微服务模块图。
2.1文档预处理
在进行中文分词之前，我们需要对文档进行预处理。预处理的步骤大致如下：
1、判断文件格式是否正确，以防出现格式伪造的文档导致读取异常；
2、读取文档的文字，跳过标点符号、附件、图片、复杂的公式等内容；
3、将文本内容保存在String数据结构中。
提取文档内容用到的工具是POI。POI是Apache软件基金会赞助的一个开源项目[1]，该项目提供了多个Java API用于对Microsoft Office格式档案的读写功能，包括doc、docx、xls文档格式等。解析文档获得文本之后，进入中文分词阶段。
2.2 中文分词
中文分词主要有以下几类方法：基于词典的方法、基于统计的方法、混合方法[2]。
基于词典的方法的基本思想在于：按照一定的规则对待分词的中文与一个“大词典”中的词汇进行比较，如果相同则获取到一个分词。基于词典的方法可以按两个指标进行划分：扫描方向和匹配长度。扫描方向包括正向扫描、反向扫描和双向扫描，匹配长度包括最大匹配和最小匹配。
基于统计的方法的基本思想在于：词由字组成，统计相连的字在不同的文本中出现的频率，频率越高则说明该相连的字是词的可能性越大。利用相连的字在不同文本中出现的频率来反应其成词的准确度，当这些相连的字频度高于某一个阈值时，可认为这些相连的字构成一个中文词语。常用的统计模型有N-gram模型、隐马尔可夫模型（HMM）[3]。
混合方法即把基于词典的方法和基于统计的方法结合起来。这种方法是的以上两种分词方法优势互补，但由于考虑的因素多，实现比较复杂。
本查重系统中使用了开源库ansj分词器，它采用了Bigram+HMM分词模型。所谓的Bigram即为N-gram模型的一种，它表示一个词的出现仅仅依赖于出现在它前面的一个词。ansj的分词流程大致如下：
1、使用Double-array Trie高效索引词典，按照核心词典第一次分词；
2、根据上面的分词结果，求解最大联合概率；
3、利用隱马尔可夫模型识别未登录词典的词汇，譬如姓名；
2.3 文档向量模型生成
在经过上述的中文分词、去停用词之后，文档内容就可以用一个向量表示：
W（w1，w2，w3，...，wn）。
W表示一个文档，w表示文本中的词汇。
在进行文档相似度进行之前，我们首先要生成一个文档向量模型。文档向量模型就根据TF-IDF词频权重的方法生成的。TF-IDF是一种常用的加权技术，主要用于评估一个字词在文本当中的重要程度[4]。该方法有两部分组成，其一是TF（Term Frequency），即词频，表示一个词汇在文本当中出现的次数。用公式表示为：
TF =
其二是IDF（Inverse Document Frequency），即逆向文本频率，表示一个词对整篇文本的权重大小。一般情况下，IDF的大小可以用如下公式表示：
IDF =
当某个词汇出现在多篇文本当中时，表示该词汇所占的权重较小；当某个词汇仅出现在少数几篇文本当中时，表示该词汇占的权重大。通过TF和IDF结合使用，便过滤掉常见的词语，而保留重要的词。
通过TF-IDF方法，就可以生成文本的向量模型。
2.4 文档相似度计算
余弦相似度是测量两个n维向量之间相似度的一种常见方法。余弦相似度在文本挖掘、信息检索、相似对比等诸多领域都有所涉及。余弦相似度用余弦值来衡量两个向量之间的夹角大小，向量之间的夹角越小，表明两个向量越相似，反之越不相似。
回顾一下高中的余弦定理，我们知道在二维空间中，有如下的公式：
当把二维推广到n维向量的时候，上述公式变为：
此时，只需要把分词获得的数组和另一个文本分词获得的数组合在一起，统计词频，再结合逆向文本频率，便可获得文档向量，用来计算相似度。 2.5 系统设计与实现
由图2可知，整个系统由三个微服务组成：web接口服务、分词服务、查重服务。微所谓的服务架构，其实是一种使用一套小服务来开发单个应用的方式途径，每个服务运行在自己的进程中，并使用轻量级机制通信，通常是HTTP API，这些服务基于业务能力构建，并能够通过自动化部署机制来独立部署。这些服务可以使用不同的编程语言实现，也可以使用不同数据存储技术，并保持最低限度的集中式管理。
web接口服务，主要的功能是提供用户操作的web接口，譬如上传文件、查看相似度等。分词服务，主要的功能是接收web接口的文件上传请求，并完成后续的预处理、去停用词、分词等功能。它们之间的关系如图3所示。
web接口服务上传文档之后，立即返回，无需等待后续步骤，即web接口服务和分词服务之间的交互是异步进行的。待分词成功或确认失败之后，分词服务会主动通知结果。分词完成的结果存放到Redis中。Redis是一个开源的非关系型内存数据库，它支持多种数据结构，譬如string、hash、list、set、map等，本系统主要使用其中的map和list。
1、提供web接口给用户操作；
2、学生上传电子版作业完成后，无需等待后续步骤，便立即返回。
3、文本解析器将word文档中的文字提取出来，输入到Ansj分词器；
4、Ansj分词器进行分词、去停用词，得到分词数组，把数组保存到Redis数据库，并记录该学生的相关信息；
5、教师想看作业的查重结果，便通过web接口发起一次请求；
6、相似度模块根据作业的标识符，请求redis中的相关数据，获得所有已经提交的作业的分词数组；
7、开启多个线程，计算当前学生和其他所有学生提交作业的相似度，得出结果。
3. 實验
取十个学生的提交的电子版作业文档，将这些文档通过web接口服务提交到服务器，然后查看文档相似度。在检测多个文档的相似度的时候，只有最高相似度才有比较的意义，因此我们默认只在页面中展示最高相似度。相似度结果如下表所示。
通过观察上表我们发现，F和H的相似度非常高，超过了0.9，这时候人工抽查，发现其文档的结构、措辞都非常相近，很多句子只是颠倒顺序或者增加一些无意义的、已经被加入到停用词表的词汇，比如“的”、“了”之类的。实验证明该系统具有可行性，该算法具有参考性。
4 结语
本系统应用Bigram+HMM分词模型的Ansj分词器将文本分词、去停用词，应用余弦相似度算法检测文档向量的相似性，采用springboot框架构造微服务架构，并结合多线程并行运算提供查重服务。该系统所检测文本的范围是某个主题，系统将从Redis中取出属于该主题的、已经分词了的文档向量进行余弦相似度计算。从实际环境中来看，对于相似度较高或较低的两个文本，检测的准确度较高。故而，经过系统查重之后，对于那些有过高相似度的文本，最好经过人工检查是否构成抄袭。
参考文献：
[1]黄青云，裴冬菊. POI在Word文档不同颜色文本分离中的应用[J].南昌工程学院学报. 2014年6月 第33卷第3期
[2]周宏宇，张政.中文分词综述.安阳师范学院学报[J]，2010，1671-5330（2010）02-0054-03.
[3]魏晓宁.基于隐马尔可夫模型放到中文分词研究.计算机教育[J]，2007，1009-3044（2007）21-40885-02
[4]殷耀明，张东站. 基于关系向量模型的句子相似度计算[J]. 计算机工程与应用，2014，50（2）：198-203.
关键词：中文查重；向量空间模型相似度；相似度；中文分词
1 引言
文本相似度算法有很多种，譬如简单共有词、余弦相似度、欧氏距离、Jaccard相似性等等。本文主要研究和应用了基于向量空间的TF-IDF余弦相似度算法，并且对输入的词频向量进行了一定有优化，如去停用词等。在实现该算法的过程中，充分考虑到了多核cpu的优势，采用并行运算的方式提升计算速率。在系统设计方面，本系统采用的是较新的设计理念——微服务架构，使用springboot框架将其分成多个微服务，各个微服务之间通过restful接口调用。实验表明该算法和系统具有较好的可用性。
本文首先介绍中文分词原理与实现，接下来详细介绍余弦相似度算法的原理和实现，然后是查重系统的设计和实现。
2 系统设计与实现
文档查重算法的实现需要经过文档预处理、中文分词、文档向量模型生成、文档相似度计算这几个步骤。以下图1显示了该算法的大致流程。
系统设计方面，我们将整个系统划分成三个微服务，各个微服务之间通过rest方式进行调用。以下图2是该系统的大致微服务模块图。
2.1文档预处理
在进行中文分词之前，我们需要对文档进行预处理。预处理的步骤大致如下：
1、判断文件格式是否正确，以防出现格式伪造的文档导致读取异常；
2、读取文档的文字，跳过标点符号、附件、图片、复杂的公式等内容；
3、将文本内容保存在String数据结构中。
提取文档内容用到的工具是POI。POI是Apache软件基金会赞助的一个开源项目[1]，该项目提供了多个Java API用于对Microsoft Office格式档案的读写功能，包括doc、docx、xls文档格式等。解析文档获得文本之后，进入中文分词阶段。
2.2 中文分词
中文分词主要有以下几类方法：基于词典的方法、基于统计的方法、混合方法[2]。
基于词典的方法的基本思想在于：按照一定的规则对待分词的中文与一个“大词典”中的词汇进行比较，如果相同则获取到一个分词。基于词典的方法可以按两个指标进行划分：扫描方向和匹配长度。扫描方向包括正向扫描、反向扫描和双向扫描，匹配长度包括最大匹配和最小匹配。
基于统计的方法的基本思想在于：词由字组成，统计相连的字在不同的文本中出现的频率，频率越高则说明该相连的字是词的可能性越大。利用相连的字在不同文本中出现的频率来反应其成词的准确度，当这些相连的字频度高于某一个阈值时，可认为这些相连的字构成一个中文词语。常用的统计模型有N-gram模型、隐马尔可夫模型（HMM）[3]。
混合方法即把基于词典的方法和基于统计的方法结合起来。这种方法是的以上两种分词方法优势互补，但由于考虑的因素多，实现比较复杂。
本查重系统中使用了开源库ansj分词器，它采用了Bigram+HMM分词模型。所谓的Bigram即为N-gram模型的一种，它表示一个词的出现仅仅依赖于出现在它前面的一个词。ansj的分词流程大致如下：
1、使用Double-array Trie高效索引词典，按照核心词典第一次分词；
2、根据上面的分词结果，求解最大联合概率；
3、利用隱马尔可夫模型识别未登录词典的词汇，譬如姓名；
2.3 文档向量模型生成
在经过上述的中文分词、去停用词之后，文档内容就可以用一个向量表示：
W（w1，w2，w3，...，wn）。
W表示一个文档，w表示文本中的词汇。
在进行文档相似度进行之前，我们首先要生成一个文档向量模型。文档向量模型就根据TF-IDF词频权重的方法生成的。TF-IDF是一种常用的加权技术，主要用于评估一个字词在文本当中的重要程度[4]。该方法有两部分组成，其一是TF（Term Frequency），即词频，表示一个词汇在文本当中出现的次数。用公式表示为：
TF =
其二是IDF（Inverse Document Frequency），即逆向文本频率，表示一个词对整篇文本的权重大小。一般情况下，IDF的大小可以用如下公式表示：
IDF =
当某个词汇出现在多篇文本当中时，表示该词汇所占的权重较小；当某个词汇仅出现在少数几篇文本当中时，表示该词汇占的权重大。通过TF和IDF结合使用，便过滤掉常见的词语，而保留重要的词。
通过TF-IDF方法，就可以生成文本的向量模型。
2.4 文档相似度计算
余弦相似度是测量两个n维向量之间相似度的一种常见方法。余弦相似度在文本挖掘、信息检索、相似对比等诸多领域都有所涉及。余弦相似度用余弦值来衡量两个向量之间的夹角大小，向量之间的夹角越小，表明两个向量越相似，反之越不相似。
回顾一下高中的余弦定理，我们知道在二维空间中，有如下的公式：
当把二维推广到n维向量的时候，上述公式变为：
此时，只需要把分词获得的数组和另一个文本分词获得的数组合在一起，统计词频，再结合逆向文本频率，便可获得文档向量，用来计算相似度。 2.5 系统设计与实现
由图2可知，整个系统由三个微服务组成：web接口服务、分词服务、查重服务。微所谓的服务架构，其实是一种使用一套小服务来开发单个应用的方式途径，每个服务运行在自己的进程中，并使用轻量级机制通信，通常是HTTP API，这些服务基于业务能力构建，并能够通过自动化部署机制来独立部署。这些服务可以使用不同的编程语言实现，也可以使用不同数据存储技术，并保持最低限度的集中式管理。
web接口服务，主要的功能是提供用户操作的web接口，譬如上传文件、查看相似度等。分词服务，主要的功能是接收web接口的文件上传请求，并完成后续的预处理、去停用词、分词等功能。它们之间的关系如图3所示。
web接口服务上传文档之后，立即返回，无需等待后续步骤，即web接口服务和分词服务之间的交互是异步进行的。待分词成功或确认失败之后，分词服务会主动通知结果。分词完成的结果存放到Redis中。Redis是一个开源的非关系型内存数据库，它支持多种数据结构，譬如string、hash、list、set、map等，本系统主要使用其中的map和list。
1、提供web接口给用户操作；
2、学生上传电子版作业完成后，无需等待后续步骤，便立即返回。
3、文本解析器将word文档中的文字提取出来，输入到Ansj分词器；
4、Ansj分词器进行分词、去停用词，得到分词数组，把数组保存到Redis数据库，并记录该学生的相关信息；
5、教师想看作业的查重结果，便通过web接口发起一次请求；
6、相似度模块根据作业的标识符，请求redis中的相关数据，获得所有已经提交的作业的分词数组；
7、开启多个线程，计算当前学生和其他所有学生提交作业的相似度，得出结果。
3. 實验
取十个学生的提交的电子版作业文档，将这些文档通过web接口服务提交到服务器，然后查看文档相似度。在检测多个文档的相似度的时候，只有最高相似度才有比较的意义，因此我们默认只在页面中展示最高相似度。相似度结果如下表所示。
通过观察上表我们发现，F和H的相似度非常高，超过了0.9，这时候人工抽查，发现其文档的结构、措辞都非常相近，很多句子只是颠倒顺序或者增加一些无意义的、已经被加入到停用词表的词汇，比如“的”、“了”之类的。实验证明该系统具有可行性，该算法具有参考性。
4 结语
本系统应用Bigram+HMM分词模型的Ansj分词器将文本分词、去停用词，应用余弦相似度算法检测文档向量的相似性，采用springboot框架构造微服务架构，并结合多线程并行运算提供查重服务。该系统所检测文本的范围是某个主题，系统将从Redis中取出属于该主题的、已经分词了的文档向量进行余弦相似度计算。从实际环境中来看，对于相似度较高或较低的两个文本，检测的准确度较高。故而，经过系统查重之后，对于那些有过高相似度的文本，最好经过人工检查是否构成抄袭。
参考文献：
[1]黄青云，裴冬菊. POI在Word文档不同颜色文本分离中的应用[J].南昌工程学院学报. 2014年6月 第33卷第3期
[2]周宏宇，张政.中文分词综述.安阳师范学院学报[J]，2010，1671-5330（2010）02-0054-03.
[3]魏晓宁.基于隐马尔可夫模型放到中文分词研究.计算机教育[J]，2007，1009-3044（2007）21-40885-02
[4]殷耀明，张东站. 基于关系向量模型的句子相似度计算[J]. 计算机工程与应用，2014，50（2）：198-203.