Simhash算法在试题查重中的应用

冉崇善+邵春霞

摘 要：随着在线教育平台的兴起，为了解决大量试题带来的存储开支问题，试题查重技术应运而生。提出将改进的Simhash算法应用到试题查重中，首先根据结巴分词技术将试题文本进行切分，然后根据TF-IDF技术并结合词语的词性及词长算出关键词权重，以期达到对Simhash签名值的精确计算，最后通过带有索引功能的海明距离检测出相似试题。实验结果验证了此方案的可行性。

关键词：试题查重；Simhash算法；海明距离；签名值

DOIDOI：10.11907/rjdk.172357

中图分类号：TP319

文献标识码：A 文章编号：1672-7800（2018）002-0151-03

0 引言

随着互联网的普及，信息化技术已经与人类的日常生活息息相关，它不仅影响了人类的生活方式，还能引起教育变革。我国《义务教育课程标准》明确指出：“为了给学生创设良好的学习条件，促进学生主動学习，更好地理解和掌握学习内容，提高学习效率，教育工作者应积极开发和利用各种课程资源”[1]。因此，在线教育产品成为全球化发展的趋势和必然。在各在线教育平台兴起的同时，由于提供给学生的试题知识点不断增长，这无疑会造成在线教育平台的存储开支问题。研究发现，在试题库中有大量相似或相同试题，也即是说，有相当一部分试题的核心内容相同，试题库中只存储一道此类型的题目即可。否则，随着时间推移，这种相似试题造成的存储成本问题将变得越来越严重。因此，试题查重技术的研究将发挥重要作用。通过该查重技术希望可以达到识别冗余数据的目的，从而大大降低存储成本，缩减不必要的存储开支。

Simhash算法是一种用于识别试题题目信息是否相似的算法，可以粗粒度地识别试题库中的冗余部分。通过Simhash算法识别试题库中存在的重复数据，并使用python语言删除重复试题信息，可实现相同试题只被存储一次的理想状态。一般情况下，单个试题的签名值可以通过哈希函数算出，但是不同程度的碰撞问题也随之出现，即使试题不同也有可能出现签名值相同的情况。

针对该问题，本文研究了一种改进的Simhash算法，由于目前Simhash算法的关键词权重计算是基于单词出现的频率，并未考虑到词性及词长，本文通过引入TF-IDF技术以及考虑到关键词的词性与词长等因素，计算出关键词权重，从而增加Simhash签名值计算的准确性，然后通过使用带有索引功能的海明距离检测试题之间的相似程度。最后通过实验，验证了该方案的可行性。

1 相关技术

1.1 结巴分词技术

结巴分词是一个使用python语言进行中文分词的模块，可以使用其进行关键词抽取。本文使用结巴分词对输入的试题进行切分，它主要具有三大特性：

（1）结巴分词是使用Trie树结构实现高效的字词扫描，生成试题中汉字所有可能组成词语情况构成的有向无环图（DAG）。根据Trie树结构的词图扫描，将结巴分词自带的2万多条词语放到一个Trie树中，而Trie树是指前缀树，即一个词语前几个字一样则表示它们具有相同前缀，具有相同前缀字则可使用Trie树存储。Trie树具有查找速度快的优势[2]。

（2）结巴分词采用动态规划查找最大概率路径，从而找出基于词频的最大切分组合[5]。动态规划中，先查找待分词句子中已切分好的词语出现的频率，如果没有该词，则把词典中出现频率最小词语的频率作为该词的频率，然后根据动态规划查找最大概率路径的方法，对句子从右往左反向计算最大概率，从而得到最大概率的切分组合。

（4）结巴分词对于未登录词，采用基于汉字成词能力的HMM模型，并使用Viterbi算法。中文词汇按照BEMS 4个状态标记，B表示开始位置，E表示结束位置，M表示中间位置，S表示单独成词的位置。

根据结巴分词的特性，可以得到其工作的一个大体流程。首先，结巴分词需要加载字典，生成Trie树；然后，给待分词的试题文本使用正则表达式获取连续的中文字符和英文字符切分成的短语列表，对每个短语使用动态规划得到最大概率路径，对DAG中没有在字典中查到的字组成一个新短语，并对于这些新生成的词语使用HMM模型进行分词，即识别字典外的新词；最后，使用python的yield语法生成一个词语生成器，逐个返回所需的关键词。

1.2 Simhash算法介绍

Simhash算法是通过将文本转化为n位签名，然后通过比较文本签名值的海明距离计算文本相似度的算法[3]。本文提出将Simhash算法应用于相似试题信息的检测识别中，相似试题信息的检测通常可以分为两个阶段：单个试题Simhash签名值的计算阶段和试题之间Simhash签名值的匹配阶段。在签名值计算的分词阶段，本文使用结巴分词技术，选出具有代表性的关键词为Simhash签名值的精确计算作铺垫。在关键词的权重计算过程中，不仅要考虑该关键词出现的频率，还要综合考虑名词、动词、形容词等重要词性及词长，同时把经典的TF-IDF计算方式应用于Simhash算法当中，通过对关键词权重的考虑改进Simhash算法以达到试题精确检测的目的[4]。Simhash算法工作流程如图1所示。

1.2.1 Simhash签名值计算

本文采用TF-IDF权值计算技术，同时考虑词性、词长等因素计算关键词权重，代替传统Simhash算法以分词识别出来的关键词作为特征值，以及以关键词出现频率作为权重的计算方法[5]。TF-IDF是一种用于评估一个关键词对于一个文件重要程度的统计方法，关键词的重要性与其在文件中出现的次数成正比，与在语料库中出现的次数成反比[6]。本文是研究对某一试题库中相似试题的检测，试题题目相当于一个短文本，所以可以将TF-IDF权值技术应用于试题查重中。TF-IDF计算过程如下：在一份给定的试题中，词频是指某一个给定词语在该试题中出现的频率。对于在某一特定试题题目信息中的关键词而言，它对于整个试题的重要程度可表示为：endprint

其中，ni，j是该词在试题中的出現次数，而∑knk，j则是在试题库中所有字词的出现次数之和。逆向文件频率是一个关键词重要程度的度量。对于某一特定的IDF，可以由总试题数目除以包含该词语的文件数目，再将得到的商取对数得到：

其中，|D|是语料库中的文件总数，{j：ti∈dj}表示包含词语的文件数目（即ti的文件数目），如果该词语不在语料库中，则会导致被除数为零。因此，一般情况下使用1+{ti∈dj}。最后试题信息的权重可表示如下：

词频虽然可以作为研究试题题目特征的一个重要指标，但是仅以频率作为权重，而没有考虑词性及词长，还是不能全面表示出试题特征，造成Simhash签名值计算结果不精确[7]。因为试题题目的特征往往与词语的词性与词长有着不可分割的关系，所以在引入TF-IDF技术的同时，本文也通过考虑关键词的词性与词长，精确计算试题的Simhash签名值。根据经验判断，名词表征着文档更多特征，动词次之，形容词再次之，其余最低。结合场景，并运用专家意见法即德尔菲法（Delphi Method）得出权重系数[8]，如表1所示。

另外，在词长方面，根据对2008年度CSSCI关键词库中的关键词长进行统计，发现4～6个字组成的词成为关键词的概率较高[9]。因此，试题文本中的权重计算公式则变为：

其中，λ为参数，取值与试题文本的长度有关，Len（ωi）定义如下：

因此，综合试题信息各个关键词的词频、词性以及词长，能够更加准确地计算出试题关键词的权重，全面表示出试题特征，使计算出的Simhash签名值更加精确。

1.2.2 Simhash签名值匹配阶段

试题信息相似性的判断是通过计算试题之间Simhash签名值的海明距离进行判断的[10]。签名值使用二进制数表示，海明距离是指两个码字的对应比特取值不同的比特数，也即是说，两个二进制数异或之后，1的个数即为海明距离。对试题查重而言，则变成根据Simhash算出单个试题的签名值后，再计算两个试题签名的海明距离即可。根据经验，对64位的Simhash而言，海明距离在3以内的两个试题可以认为其相似。假设对64位的Simhash，要寻找海明距离在3以内的所有签名，可以把64位的二进制签名均分成4块，每块16位。根据鸽巢原理可知，如果两个签名值的海明距离在3以内，那么它们必有一块是相同。由上可知，海明距离的计算十分简单，但是当数据量特别大时，逐个进行异或的方式是不现实的。例如，对于64位的Simhash值，所有3位之内的组合要进行C（63，3）=41 664次查询，或者需要分配41 664倍的存储空间。为了解决该问题，本文引入索引归类的方法[11]，算法大致流程如下：①将每个m bit的签名值划分为n份；②利用排列签名值建立n！（n-k）！*k个表；③精确匹配m*（1-k/n）位的签名值；④在存有2d个签名值的数据库中，每个指针产生2d-m*（1-k/n）个指纹值。

由此可见，在海明距离的计算过程中引入索引归类的方法，可以减少签名值的比对过程，使之具有更高的查找效率。

2 实验结果及分析

本文采用的数据为100道选择题、100道填空题、100道主观题，试题库为在线教育平台的数据库，算法语言采用Python语言，分词系统采用结巴分词技术。在采用Simhash算法计算试题题目的签名值之前，采用结巴分词技术去掉重用词及无关词，然后结合TF-IDF以及词性、词频计算出关键词权重，然后进行Simhash签名值计算，最后进行各试题信息的海明距离计算。根据经验认为，海明距离小于等于3的两个试题即为重复，然后将试题保留一道，删除其余冗余试题。

在进行实验前，首先需要安装实验环境Linux虚拟机，本次实验是在Ubuntu14.04环境中运行的。然后根据需要安装好结巴分词，准备好实验所需环境之后开始实验。

2.1 评价标准

本文采用传统的准确率、召回率两个关键指标评价本文提出的将改进的Simhash算法应用到相似试题检测中的可行性分析。本文采用的试题查重可以分为以下几个主要步骤：试题语句划分及结巴分词处理、采用TF-IDF技术及综合考虑词性词频与词长确定关键词权重、根据Simhash算法生成签名值、试题签名值对比计算等4个过程。9次实验所得数据如表2所示。

绘制9次实验数据的正确率与召回率折线图，如图2所示。则其各参数表示的意义为：

正确率：指测试正确的相似数据量与测试后找出来的相似数据量之比。

召回率：指测试正确的相似数据量与测试之前已知的相似数据量之比。

2.2 实验分析与总结

如图2所示，本文将改进的Simhash算法应用于相似试题检测当中，文本的准确率和召回率都达到95%以上，算法误判率小于0.01。同时，由于本文使用TF-IDF技术结合词性以及词长计算，经过结巴分词所得关键词的权重简化了传统的Simhash算法，且使用带有索引功能的海明距离计算方式，极大地减少了试题之间的比较次数。因此，将改进的Simhash算法应用到试题查重中，在时间和性能方面都得到了极大提升，且根据实验结果显示完全符合本文主题。

3 结语

针对在线教育平台试题库中大量试题重复的现象，本文提出将改进的Simhash算法应用到相似试题检测中。通过上述实验，可以发现结果完全符合要求。通过使用结巴分词技术进行试题文本的高效切词，对于关键词权重计算，引入了TF-IDF经典的权值计算技术，同时考虑词性与词长，使计算的Simhash签名值更加精确。使用带有索引功能的海明距离计算方式，可大大减少二进制数值的比较次数，使计算过程更加高效可靠，查找速率更快。在今后的研究中，因为目前实验有时会出现错误删除的情况，希望找到更优的方法减少错误删除率，使查找精确性更高。

参考文献：

[1] 潘雪峰，张宇晴，毛敏，等.在线教育产业发展现状及产品设计研究[J].科技和产业，2013（8）：13-16.

[2] 王思力，张华平，王斌.双数组Trie树算法优化及其应用研究[J].中文信息学报，2006（5）：24-30.

[3] 马成前，毛许光.网页查重算法Shingling和Simhash研究[J].计算机与数字工程，2009（1）：15-17，108.

[4] 吴平博，陈群秀，马亮.基于特征串的大规模中文网页快速去重算法研究[J].中文信息学报，2003（2）：28-35.

[5] 王卫玲.web文本分类中特征向量优化技术研究[D].济南：山东师范大学，2007.

[6] 李彬.基于Hadoop框架的TF-IDF算法改进[J].微型机与应用，2012（7）：14-16.

[7] 陆玉昌，鲁明羽，李凡，等.向量空间法中单词权重函数的分析和构造[J].计算机研究与发展，2002（10）：1205-1210.

[8] 蒋昌金，彭宏，陈建超，等.基于主题词权重和句子特征的自动文摘[J].华南理工大学学报，2010（7）：50-55.

[9] 付印金，肖侬，刘芳.重复数据删除关键技术研究进展[J].计算机研究与发展，2012（1）：12-20.

[10] 余意，张玉柱，胡自健.基于Simhash算法的大规模文档去重技术研究[J].信息通信，2015（2）：28-29.

[11] LI HENGXIN，HAN JIANHUA. Efficient duplicate detection for data in relation databases[J].Journal of South ChinaNormal University （Natural Science Edition），2015，47（1）：121-126.endprint