基于局部最大相似设想的串匹配算法-论文.pdf

《基于局部最大相似设想的串匹配算法-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第22卷第l4期电子设计工程2014年7月V01．22NO．14ElectronicDesignEngineeringJu1．2014基才局部最大相似设想的串匹配算法刘鹰(西安文理学院陕西西安710065)摘要：在设计盲打机考自动判卷系统时，需要一种有效的文本相似度判别算法。为此提出了一种基于局部最大相似设想的串匹配算法来解决此类问题，通过分别比较错误发生部位局部子字符串在插入片段、漏打片段或错打片段的的得分并选取失分最小者，实现了精确判定考生得分的目的。该算法无回溯，效率高，已应用于自动机考系统中。关键词：字符串比较；最大相似度；自动判

2、卷；智能化考试系统中图分类号：TP312文献标识码：A文章编号：1674—6236(2014)14—0040—03StringcomparisonalgorithmbasedonlocalmaximumsimilarityhypothesisLIUYing(Xi'anUniversityofArtsandScienc~'all710065，China)Abstract：Comparisonoftextsandstringsarethetasksfrequentlyappearedinthedevelopmentoftheapplicati

3、onsystemslikeautomaticgradingsystemandevaluationofthequalityofdatatransmissionsystem．Obviouslyitcannotbeperformedjustthroughcomparetwosourcestringscharacterbycharacter．Astringcomparisonalgorithmbasedonlocalmaximumsimilarityhypothesisisdescribedhereandwhichisimplementedina

4、nautomaticgradingsystem．Keywords：stringcompare；mostsimilarity；automaticgradinintelligentexamsystem在机考自动判卷系统中，如何判断考生输入答案与范文的原串(s)转换到目标串(t)所需要的最少的插入、删除和替相似程度是一个核心问题，这可以归结为文本比较算法的设计。换数目。列文斯顿距离亦称编辑距离(PhraseEditDistance)，比较两个文本的相似程度，常用的算法有模糊哈希(Fuzzy最早由俄国数学家列文斯顿(VladimirLevensh

5、tein)提出，在Hashing)算法、列文斯顿距离(LevenshteinDistance)算法等。自然语言处理(NaturalLanguageProcessing，NLP)中应用比较模糊哈希算法主要用于文件的相似性比较，又称基于内广泛。容分割的分片哈希算法(ContextTriggeredPiecewiseHashing，列文斯顿距离算法可以看作一个动态规划，其思路是从两CTPH)。个字符串的左边开始比较，记录已经比较过的子串相似度(即2006年，JesseKornblumⅢ提出了模糊哈希算法并给出了距离)，然后进一步得到下一个字符位

6、置时的相似度。一个算法实例。随后，JasonSherman又开发了一个名为ssdeep其他文本比较算法还有KMP算法(Knuth—Morris—Pratt)的工具软件以实现这一算法。该算法最初用于计算机取证，后和BM(Boyer-Moore)算法。这两个算法主要用于精确查找。来又被用于恶意代码检测，最近又有用于开源软件漏洞挖掘等。国内也有一些对文本或字符串比较算法的研究，如北京交模糊哈希算法的主要原理是使用一个弱哈希函数计算文件通大学的王艳清等[51和武汉大学信息资源研究中心的李刚等嘲，局部内容，在特定条件下对文件进行分片，然后使用一个强

7、哈分别讨论了具体应用环境下的文本或字符串比较算法。希函数对文件的每个片段计算哈希值，取这些值的一部分并连虽然上述算法都是成熟的文本比较算法，也都有广泛的应接起来，与分片条件一起构成一个模糊哈希结果。使用一个字用，但就盲打机考机考系统的具体问题，都还存在各种具体问符串相似性对比算法判断两个模糊哈希值的相似度有多少，从题，如模糊哈希算法主要用于文件比较，列文斯顿距离算法用而判断两个文件的相似程度。于盲打机考判分时结果不够直观等，对于盲打机考评判这一任对文件的部分变化(包括在多处修改、增加、删除部分内务，尚无特别有效的算法可供选择。容)，使用模

8、糊哈希均能发现其与源文件的相似关系，是目前因此，在本文引入了最大相似程度的概念，其出发点是认判断相似性较好的一种方法。为考生在做打字测试时总是力图犯最少的错误，从而争取更高列文斯顿距离(Lev