一种答案匹配算法.pdfVIP

2005耳第4期 信 息技 术 锄 ． 一 种 答 案 匹 配 算 法 俞经善，陈宝学 (哈尔滨工程大学汁算机科学与技术学院，哈尔滨 150001) 摘 要：对于给定两个串S1(标准答案)和S2(实际答案)，长分别m和n，给出了一个找出两 串间最大匹配的算法。通过该算法，可以比较两个串S1和 s2的相似程度，从而可以断定实际答 案与标准答案的匹配程度，进而可以对试卷打分。 关键词：答案；模式匹配；串的最大匹配；算法 中图分类号：TIll1 文献标识码：A 文章编号：1009—2552(2005)04—0037—03 Analgorithm foranswermatching YUJing-shan，CHENBao．xue (Insti~teofComputer~ienceandT~ ology，HarbmEngin~ringUmversi~，HarbM150001，China) Abs~act：Giventwos n罢；sS1oflengthmandS2oflengthn，thepaperpresen~anM~fithrnwhichCna fmd themaximM matchingofthem．Thealgorithm Cna beusedtocomparethesimilari~ oftheⅢos~ngsS1nad S2．Thenitcanbe usedtocomparethesimilari~ofthestandardal~wernadthestudents’answe~，nad6ve them sco~s． Keywords：naswer；pattern ma tchnig；maximalma tchnigofstrin~；algorithm l 赵 的描 述 时，应给予相应的分值。 在试卷评阅中，对于客观题，如选择题，可以很 2 问题的定义 轻易地通过读卡器来判别正误。而对于主观问答 设∑为任意有限集，其元为字符。∑ 为∑ 题，则很难实现自动评阅。下面，就对试卷的主观题 上的有限字符串集合，那么对任意S1，s2E∑ ，设 的自动评阅方面做一下尝试，并给出相应的算法。 字符串的模式匹配，就是给定两个字符串sl和 S1= a1a2a3…a ，S2=b1b2b3…b，m，n0。记 s2，长度分别为m和n，找出s2中出现的一个或多个 m= {1，2，…，m}，n= {1，2，…，n}，贝0称 或所有的S1。它主要用于文本处理，例如文本编辑、 {(i，)IiEm，JEn，a=6}为S1与S2 文本数据的存储(文本压缩)和数据检索系统。显然， 的匹配关系集，记作 M(s1，s2)。若对任意(i，)， 这不能完全用在答案的匹配上，可以想象，不可能存 (i，)E ，①ii，当且仅当J／，②i=i当 在一个和标准答案S1完全一致的学生试卷，或者说， 且仅当 =／，称 cM为s1与s2的一个匹配。若 在学生回答的答案中，也不可能完全包含S1。所以， C(i，)为m ×n矩阵，且满足： 必须对模式匹配方法进行改进，以适应需要。 ／． ．、 f0，若(i，) M(S1，s2) ’ 11，若(i，)E (S1，s2) 显然，试卷评阅不要求标准答案与实际答案的完 全匹配，而是看两者间的匹配程度。如果能找出两者 则称矩阵C为串s1与s2的匹配关系阵。于是求串s1 的最大匹配，即它俩的相似程度。再根据预先设计好 与s2的最大匹配 ，等价于求C中的一个最