Simhash算法在试题查重中的应用
的信息化技术已经与人类的日常生活息息相关。不仅仅是人类的生活方式，也引起了教育变革。中国的“义务教育课程标准”明确指出。因此，在线教育的产品将成为全球化发展的必然趋势。
在网络教育平台兴起的同时，由于提供给学生的考题知识点不断增加，这无疑会造成在线教育平台的保存支出问题。根据研究，试验问题库有很多类似问题和同样的问题。也就是说，有些试题的核心内容是一样的。如果不到
，随着时间的推移，由于类似问题而产生的保存成本问题会越来越严重。因此，在考试问题上重视技术的研究发挥了重要作用。
可以通过这种加权技术来实现识别冗余数据的目的，并且可以大大降低存储成本并减少不必要的存储支出。Simhash算法是用于识别测试问题信息是否相似的算法，可以粗粒化地识别测试问题库的冗余部分。
通过Simhash算法识别测试问题库中存在的重复数据，使用python语言删除重复测试信息，可以实现同一测试问题只存储一次的理想状态。一般来说，一个测试题的签名值是用散列函数计算出来的，但是会发生一定程度的冲突问题，即使测试问题不同，签名值也有可能相同。
针对这个问题，本文研究了Simhash算法的改进。由于当前Simhash算法的关键字权重计算是基于单词出现频率的，所以不考虑词性和词长。在此导入TF-IDF技术，考虑关键字的词性和词长等，计算关键字权重，增加Simhash。签名值的计算精度使用具有索引功能的海明距离来测量测试问题之间的类似度。最后，通过实验验证了这个方案的可行性。
结巴分词是使用pytohon语言进行中文分词的模块，可以使用关键字来提取。本文使用结巴分词来划分输入的问题，主要有三个特性。
根据Trie树结构的字图进行扫描，将结巴分词所具有的2万个以上单词配置在一个Trie树上，Trie树表示前缀树，即在一个词之前的几个单词具有相同的前缀，并且相同的前缀在具有字的情况下，可以使用Trie树来存储。Trie树具有搜索速度快的优点[2]。
（2）结巴分词通过动态规划和检索最大概率路径，找到基于词数的最重要分类组合[5]。在动态规划中，先调查在分词句中被分割出的词语的出现频率，如果没有这个词，则将词典中频率最小的词语的频率设为该词的频率，然后根据动态计划检索最大概率路径的方法，相对于句子从右到左相反，最大概率计算最大概率的切分耦合。
（4）结巴分词对于未注册的词，采用基于汉字的成语能力的HMM模型，使用Viterbi算法。中文词汇由BEMS4个状态标记，B表示开始位置，E表示结束位置，M表示中间位置，S表示单个成语的位置。
根据结巴分词的特性，可以得到工作的流程。首先，结巴分词需要读取字典，生成Trie树。并且，在分词的问题句中使用正则表现取得连续的中文文字和英语文字的被分割了的词组列表，对各词组动态地计划能得到最大概率路径。对于DAG中查不到的单词构成新的词组。使用HMM模型对这些新生成的词语进行单词分类，识别词典以外的新词。最后，使用pytohon的yield语法生成单词生成器，并逐个返回所需的关键字。Simhash算法是通过将文本转换成n位签名并比较文本签名值的海明距离来计算文本的类似度的算法[3]。
本论文提出将Simhash算法应用于类似测试问题信息的检测识别。类似的测试问题信息的检测通常分为两个阶段。单一测试题分为Simhash签名值计算阶段和测试问题之间Simhash签名值匹配阶段。在签名值计算的分词阶段，本文正确计算并敷设Simhash签名值的代表性关键字。在关键字权重的计算过程中，不仅要考虑该关键字的出现频率，还要综合考虑名词、动词、形容词等重要词性和语长，将经典的TFT-IIDF计算方式应用于Simhash算法，通过对关键字权重的考察，Simhash改进算法，实现准确检测测试问题的目的。
Simhash算法的动作流程如图1所示。因此，综合测试问题信息的各关键字的词汇、词类及词长，更正确地计算问题关键字的重量，全面表示测试问题的特征，能使计算出的Simhash签名值更准确。
测试问题信息的类似性的判断是计算测试问题之间Simhash签名值的海明距离来判断的[10]。签名值使用二进制数表示，其中，在两个码字的对应比特的值不同的比特数（即，两个二进制数不同）之后，海明距离是一个数量的海洋距离。如果考题检查重，可以从Simhash计算出各个考题的签名值，然后计算两个考题的签名的海明距离。根据
年的经验，对于第64位的Simhash来说，海明距离3以内的两个问题是相似的。如果您要求64位Simhash在海明距离3以内的所有签名，可以将64位二进制签名分成4个，每块16位。
是根据鸽子窝的原理而知道的。两个签名值的海明距离在3以内的话，一个是一样的。从上面知道。海明距离的计算虽然很简单，但是数据量很大的时候，一个一个进行不同种类的方法是不现实的。例如，
需要对64位Simhash值的所有3位内的组合进行C（63，3）＝41664次查询，或者分配41664倍的存储空间。本文采用的数据为100个选择题、100个填空题、100个主观问题、测试题库为在线教育平台数据库，算法语言采用Python语言，分词系统采用结巴分词技术。
在采用Simhash算法计算测试题的签名值之前，将与重用词无关的词截断，与TF-IDF结合词性、词数计算关键字的权重，计算Simhash签名值，最后进行测试题信息的海明距离计算。根据经验，海明距离3以下的两个问题是重复的。然后留下一个问题，删除剩余的冗余问题。对于
在线教育平台的测试问题库中很多问题重复的现象，本文提出将改进的Simhash算法应用于类似测试问题的测试。通过上述实验，发现结果完全符合要求。通过使用结巴分词技术对测试题文本进行高效接续，导入了TFT-IIDF经典的权数计算技术。同时考虑词性和词长，计算出的Simhash签名值更准确。
使用索引功能的海明距离计算，可以大大减少二进制值的比较次数，使计算过程更高效可靠，搜索速度更快。在今后的研究中，因为在现在的实验中有被错误删除的情况，所以希望能找到更好的方法来降低错误删除率，实现更准确的检索。