论文查重 | 论文文献库 | Simhash算法在试题查重中的应用

随着互联网的普及 ,信息化技术已经与人类的日常生 活息息相关 ,它不仅影响了人类的生活方式 ,还能引起教 育变革 。 我国《义务教育课程标准》明确指出 :“为了给学 生创设良好的学习条件 ,促进学生主动学习 ,更好地理解 和掌握学习内容 ,提高学习效率 ,教育工作者应积极开发 和利用各种课程资源”[1 ] 。 因此 ,在线教育产品成为全球 化发展的趋势和必然 。 在各在线教育平台兴起的同时 ,由 于提供给学生的试题知识点不断增长 ,这无疑会造成在线 教育平台的存储开支问题 。 研究发现 ,在试题库中有大量 相似或相同试题 ,也即是说 ,有相当一部分试题的核心内 容相同 ,试题库中只存储一道此类型的题目即可 。 否则 , 随着时间推移 ,这种相似试题造成的存储成本问题将变得 越来越严重 。 因此 ,试题查重技术的研究将发挥重要作 用 。 通过该查重技术希望可以达到识别冗余数据的目的 , 从而大大降低存储成本 ,缩减不必要的存储开支 。 Simhash 算法是一种用于识别试题题目信息是否相 似的算法 ,可以粗粒度地识别试题库中的冗余部分 。 通过 Simhash 算法识别试题库中存在的重复数据 ,并使用 python 语言删除重复试题信息 ,可实现相同试题只被存储 一次的理想状态 。 一般情况下 ,单个试题的签名值可以通 过哈希函数算出 ,但是不同程度的碰撞问题也随之出现 , 即使试题不同也有可能出现签名值相同的情况 。
针对该问题 ,本文研究了一种改进的 Simhash 算法 , 由于目前 Simhash 算法的关键词权重计算是基于单词出 现的频率 ,并未考虑到词性及词长 ,本文通过引入 TF-IDF 技术以及考虑到关键词的词性与词长等因素 ,计算出关键 词权重 ,从而增加 Simhash 签名值计算的准确性 ,然后通 过使用带有索引功能的海明距离检测试题之间的相似程 度 。 最后通过实验 ,验证了该方案的可行性 。
结巴分词是一个使用 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 语法生成一个词语生成器 ,逐个返回所需的关键词 。 Simhash 算法是通过将文本转化为 n位签名 ,然后通 过比较文本签名值的海明距离计算文本相似度的算法[3 ] 。
本文提出将 Simhash 算法应用于相似试题信息的检测识 别中 ,相似试题信息的检测通常可以分为两个阶段 :单个 试题 Simhash 签名值的计算阶段和试题之间 Simhash 签 名值的匹配阶段 。 在签名值计算的分词阶段 ,本文使用结 巴分词技术 ,选出具有代表性的关键词为 Simhash 签名值 的精确计算作铺垫 。 在关键词的权重计算过程中 ,不仅要 考虑该关键词出现的频率 ,还要综合考虑名词 、动词 、形容 词等重要词性及词长 ,同时把经典的 TF-IDF 计算方式应 用于 Simhash 算法当中 ,通过对关键词权重的考虑改进 Simhash 算法以达到试题精确检测的目的[4] 。 Simhash 算 法工作流程如图 1 所示 。
因此 ,综合试题信息各个关键词的词频 、词性以及词 长 ,能够更加准确地计算出试题关键词的权重 ,全面表示 出试题特征 ,使计算出的 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 倍的存储 空间 。
本文采用的数据为 100 道选择题 、100 道填空题 、100 道主观题 ,试题库为在线教育平台的数据库 ,算法语言采 用 Python 语言 ,分词系统采用结巴分词技术 。 在采用 Simhash 算法计算试题题目的签名值之前 ,采用结巴分词 技术去掉重用词及无关词 ,然后结合 TF-IDF 以及词性 、 词频计算出关键词权重 ,然后进行 Simhash 签名值计算 , 最后进行各试题信息的海明距离计算 。 根据经验认为 ,海 明距离小于等于 3 的两个试题即为重复 ,然后将试题保留 一道 ,删除其余冗余试题 。
针对在线教育平台试题库中大量试题重复的现象 ,本文提出将改进的 Simhash 算法应用到相似试题检测中 。 通过上述实验 ,可以发现结果完全符合要求 。 通过使用结 巴分词技术进行试题文本的高效切词 ,对于关键词权重计 算 ,引入了 TF-IDF 经典的权值计算技术 ,同时考虑词性 与词长 ,使计算的 Simhash 签名值更加精确 。 使用带有索 引功能的海明距离计算方式 ,可大大减少二进制数值的比 较次数 ,使计算过程更加高效可靠 ,查找速率更快 。 在今 后的研究中 ,因为目前实验有时会出现错误删除的情况 , 希望找到更优的方法减少错误删除率 ,使查找精确性更高 。

相关文章:浅谈图书采访订单的查重