（控制科学与工程专业论文）c语言在线考试系统的设计与实现.pdf

p i ， l ， _ 学位论文数据集 中图分类号 t p 3 1 1 5 2 学科分类号 5 2 0 4 0 3 0 论文编号 1 0 0 1 0 2 0 1 1 0 8 3 2 密级公开 学位授予单位代码 l 0 0 1 0 学位授予单位名称北京化工大学 作者姓名彭巍学号 2 0 0 8 0 0 0 8 3 2 获学位专业名称控制科学与工程获学位专业代码 0 8 1 l 课题来源其他研究方向控制科学与工程 论文题目c 语言在线考试系统的设计与实现 关键词 c 语言，在线考试，评阅，程序理解，编译原理，沙箱 论文答辩日期 2 0 1 1 5 2 6 论文类型应用研究 学位论文评阅及答辩委员会情况 姓名职称 工作单位学科专长 指导教师夏涛副教授北京化工大学c a e 和m i s 系统 评阅人l 王建林 教授 北京化工大学 智能检测技术 评阅人2赵众教授北京化工大学 控制理论和控制工程 评阅人3 评阅人4 评阅人5 答辩委员会拂 王建林 教授北京化工大学智能检测技术 答辩委员1 赵众 教授北京化工大学控制理论和控制工程 答辩委员2林伟国教授北京化工大学检测技术及自动化装置 答辩委员3 王颖副教授北京化工大学光电检测技术 答辩委员4祝海江副教授北京化工大学模式识别与智能系统 答辩委员5 注：一 四 论文类型：1 基础研究2 应用研究3 开发研究4 其它 中图分类号在中国图书资料分类法查询。 学科分类号在中华人民共和国国家标准( g b t1 3 7 4 5 9 ) 学科分类与代码中 查询。 论文编号由单位代码和年份及学号的后四位组成 6jj_8舢77哪8引iiy 摘要 c 语言在线考试系统的设计与实现 摘要 随着我国信息化建设的推进，计算机应用能力的培训得到了迅猛的发 展，开设了c 语言程序设计相关课程的学校和培训机构越来越多，同时c 语言课程的计算机在线考试也成为了一个热门的研究课题。在线考试是网 络教学系统功能之一，它涉及到多项关键技术，如大规模题库的建立与维 护、自动组卷、大规模的并发访问、自动阅卷等。其中，自动阅卷技术能 够在快速准确得到评分结果的同时节省大量的人工劳动时间。 目前自动阅卷已经能很好地完成对常见客观试题的自动批阅工作，但 是对于一些主观性很强的问题，尤其是程序设计题型，还没有很好的解决 方案。本课题就是在这样的背景下提出的，目的是实现c 语言课程的完 全无纸化考试，减少阅卷工作量，提高评阅过程的公正性和准确性。本文 对该系统的指导思想、实现策略以及所用技术等进行了系统的阐述。 本课题对考试系统中的自动组卷、试题考试及自动评分系统分别进行 了研究设计，重点对程序题的评分方法进行了研究，在比较结果的评分方 法基础上，设计了动态评阅与静态评阅相结合的方法，评分结果更加公正、 准确。对于只有少量错误的考生程序，应用编译原理中的分析方法，通过 动态找错及改错，使其在系统监控下运行，从而可根据结果信息及错误信 息进行评分，解决了多数考生因编程中的很小失误而导致大量丢分的问 题。而对于错误严重或结果不正确的程序，通过静态检查，可根据程序中 北京化- t 大学硕上学位论文 的关键语句数给出相应分数，使评分结果更加接近于人工阅卷。同时为了 保证系统不被恶意代码所攻击，所有编译成功的可执行文件均在沙箱环境 下运行。 系统设计成功后，初步实验结果证明自动评分模块运行稳定，评分标 准能够统一。 关键词：c 语言，在线考试，评阅，程序理解，编译原理，沙箱 t h ed e s i g na n di m p l e m e n to f o n l i n e e x a m i n a t i o ns y s t e mo f cp r o g r a m m i n gl a n g u a g e a b s t r a c t w i t ht h ed e v e l o p m e n to fi n f o m a t i o n i z a t i o ni nc h i n a ，t h e r ei sar 印i d d e v e l o p m e n ti nc o m p u t e rs l ( i l l st r a i n i n g m o r ea n dm o r es c h 0 0 1 sa n dt r a i n i n g i n s t i t u t i o n sh a ds e tu pt h ecp r o g r a m m i n gl a n g u a g er e l a t e dc o u r s e s ，a tt h e s a m et i m e ，o n l i n ee x a m i n a t i o no fcl a n g u a g eh a sa l s ob e c o m ea nh o t r e s e a r c ht o p i c 0 n l i n ee x a mi so n eo ft h e 如n c t i o n so fn e 帆o r kt e a c h i n g s y s t e m ，w h i c hi n v 0 1 v e s an u m b e ro fk e y t e c h n o l o g i e s ， s u c ha st h e e s t a b l i s h m e n ta n dm a i m e n a n c eo f1 a 玛e - s c a l ed a t a b a s e ，a u t o m a t i cg e n e r a t i o n o ft h ee x 锄i n a t i o np 印e r s ，1 a 玛e - s c a l ec o n c u r r e ma c c e s s ，a u t o m a t i cs c o r i n g a n ds oo n a m o n gm e m ，t h ea u t o m a t i cs c o r i n gt e c l 1 i q u e sc a ns c o r et h er e s u l t s q u i c k l ya n da c c u r a t e l ya n dm a y s a v eal o to fm a n u a l l a b o rt i m e n o wt h ea u t o m a t i cs c o r i n gs y s t e mw o r k sw e no nt h ec o m m o n o b je c t i v e q u e s t i o n s ， b u tf o rs o m e h i g h l ys u b je c t i v eq u e s t i o n s ， e s p e c i a l l y t h e p r o g r a m m i n gq u e s t i o n s ，t h e r ea r en og o o ds o l u t i o n s t h i st o p i ci sp r e s e n t e di n t h i s c o n t e x t ，t h ea i mi s t oa c h i e v et h e 如l l 如n c t i o n a lcl a n g u a g eo n l i n e e x a m i n i n gs y s t e mt or e d u c et h es c o r i n gw o r h o a da n di m p r o v et h ef a i m e s s a n da c c u r a c yi nt h ep r o c e d u r e t h ist h e s i sg i v e sas y s t e m a t i ce x p o s i t i o no ft h e 北京化t 大学硕十学位论文 p r i n c i p l ei m p l e m e n t a t i o ns t r a t e g ya n d t h eu s eo f t e c h n o l o g yo f t h es y s t e m t h i ss u b j e c tc 枷e do u tm er e s e a r c ho na u t o m a t i cp a p e r g e n e r a t i o n ， o n l i n ee x a m i n a t i o na n da u t o m a t i cs c o r i n gs y s t e mi nt h es y s t e m ，f o c u s i n go n s c o r i n gp r o c e d u r e so ft h ep r o g r a m m i n gq u e s t i o n s d e s i g n e dam e t h o dw h i c h c h e c k sm es o u r c ec o d eb a s e do nt h eo r d i n a 巧m e t h o do fc o m p a r i n gt h er e s u l t s ， t h i sc o u l dm a k es c o r i n gm o r ef a i ra n da c c u r a t e f o rt h es o u r c ec o d et h a th a s o n l yaf e wf i a u l t s ，w eu s et h ea n a l y z i n gm e t h o n di nt h ec o m p i l e rt h e o 拶t of i n d o u ta n dc o n e c tt h ef a u l t sd y l l a m i c l yu n d e rt h es u p e r v i s i o no fi t so p e r a t i o ni n t h e s y s t e m ， s ow ec o u l ds c o r et h es o u r c ec o d eb yt h er e s u l ta n de m r i n f o n i l a t i o n ，s 0 1 v i n gt h ep r o b l e mt h a tm o s to ft h es t u d e n tl o s t1 a r g em l m b e ro f p o i n t sb e c a u s eo ft h et h e1 i t t l em i s t a k e si nm es o u r c ec o d e t h r o u g hs o u r c e c o d ec h e c 王( i n g ，w ec o u l dg i v et h ep o i n t sa c c o r d i n gt ot h ek e ys t a t e m e n ti nt h e c o d ew h i c hh a sf a t a le r r o r s o re r r o rr e s u l t st om a k et h es c o r i n gr e s u l tm o r e s i m i l a rw i t ht h em a n u a ls c o r i n g m e a n w h i l e ，i no r d e rt oe n s u r et h a tt h es y s t e m w i l ln o tb ea t t a c k e db ym a l i c i o u sc o d e ，a l lt h ee x e c u t a b l ef i l e sw e r em ni nt h e s a n db o xe n v i r o n m e n t s a r e rt h es u c c e s so fs y s t e md e s i g n ，p r e l i m i n a qe x p e r i m e n t a lr e s u l t s s h o wt h a tt h ea u t o m a t i cs c o r i n gm o d u l ew o r k ss t a b l ya n dt h em a r k i n gc a nb e u n i 矗e d k e yw o r d s ：c l a n g u a g e ， o n l i n e e x a m i n a t i o n s ，s c o r e ，p r o g r a m u n d e r s t a n d i n g ，c o m p i l e rt h e o r y ，s a n d b o x i v 目录 目录 第一章绪论l 1 1 课题背景1 1 2 论文选题的目的和意义2 1 3 国内外研究状况一2 1 4 本课题的主要研究内容及方法3 第二章相关技术介绍5 2 1 常用匹配算法简介5 2 1 1k m p ( k n u t h m o r r i s p r a t t ) 算法5 2 1 2h o r s p o o l 算法7 2 1 3b m ( b o y e 卜m o o r e ) 算法8 2 1 4s h i r a n d 算法l o 2 2l d i s t a l l c e 算法1l 2 3 编译原理1 4 2 3 1 编译基础1 4 2 3 2 词法分析1 5 2 3 3 语法分析1 5 第三章编程题的计算机评阅1 7 3 1 引言1 7 3 2 源代码的程序理解1 8 3 3 中间表达形式的抽象语法树表示1 9 3 3 1g c c 编译器与抽象语法树1 9 3 3 2a s t 的遍历2 2 3 3 3a s t 的冗余信息消除2 4 3 3 4a s t 的匹配一2 8 3 4 对c 源代码的错误检测与修改2 9 v 北京化工大学硕十学位论文 3 4 1c 语言的特点和常见错误2 9 3 4 2c 语言常见错误的处理3 2 3 5 按评分点匹配3 3 第四章系统架构与实现3 5 4 1 系统需求3 5 4 2 系统架构3 5 4 3 沙箱及其实现3 8 4 4 数据库设计4 5 4 5 教师端模块的设计4 8 4 5 1 题库维护模块4 8 4 5 2 组考模块5 2 4 5 3 成绩管理模块5 7 4 6 学生端模块设计6 0 4 7 评阅模块设计6 5 4 7 1 选择题与填空题评阅模块6 5 4 7 2 编程题评阅模块6 6 第五章总结与展望7 3 参考文献7 5 致谢7 7 研究成果及发表的学术论文7 9 作者和导师简介8 1 c o n t e n t s c h a p t e r 1i n t r o d u c t i o n l 1 1t o p i cb a c k g r o 吼d l 1 2t h es e n s eo fm et o p i c 2 1 3d o m e s t i ca n di n t e r n a t i o n a lr e s e a 】r c hs t a t u s 2 1 4m a i nt a s k s ：3 c h a p t e r 2b a s i ct h e r o yo fr e l a t e dt e c h n i q u e s 5 2 11 1 1 t r o d u c t i o nt oc o m m o nm a t c ha l g o r i t m “5 2 1 1k m p ( 1 ( n u t h m o r r i s - p r a t t ) a l g o r i t h m ”5 2 1 2h o r s p o o la l g o r i t h m 一7 2 。1 3b m ( b o y e r - m o o r e ) a l g o r i t h m _ 8 2 1 4s h i r a n da l g o r i t h m 1 o 2 2l d i s t a n c ea l 星r o n t h n l 1 1 2 3c o m p i l i n gp r i n c i p l e ”1 4 2 3 1t h eb a s i ct h e r o yo fc o m p i l i n g 1 4 2 3 2l e x i c a la 1 1 a l v s i s 。1 5 2 3 3s y n t a xa i l a l y s i s 1 5 c h a p t e r 3c o m p u t e rs c o r i n go f t h ep r o g r a n l m i n gq u e s t i o n s 1 7 3 1i i l t i d d u c t i o n 1 7 3 2t h ep r o 伊锄c o m p r e h e n s i o no fm es o u r c ec o d e 1 8 3 3a s t p r e s 铡i t a “o no f m e i n t e r m e d i a t ee x p r e s s i o n 1 9 3 3 1g c cc o m p i l i e ra n da s t 1 9 3 3 21 r a v e 髑a lo f a s t 2 2 3 3 3r e d u n ( 1 锄t l yi n f o r m a t i o nr e m o v e m e n to f m ea s t 2 4 3 3 4a s tm a t c h i n g 2 8 3 4e n 0 rd e t e c i n ga n dc o n e c t i n go fc s o u r c ec o d e 2 9 v h ! ! 皇垡三查兰堡主堂垡笙奎一 3 4 1t h ef e a t u r ea l l dc o m m o ne 啪r so fc1 a 1 1 9 u a g e 一2 9 3 4 21 h eh a n d l i n go fm ec o n l i i l o ne n - o r so fcl 姐g u a g e 3 2 3 5m a t c ：i l i n gb yt h es c o r i n gp o i n t s 3 3 c h a p t e r 4s y s t e ma r c h i t e c t l l r ea n di m p l e m e n t a t i o n 3 5 4 1s y s t e h lr e q u i r e i i l e n t s 3 5 4 2s y s t e ma r c l l i t e c t u r e 3 5 4 3s 肌d b o x 锄di m p l 锄e n t a t i o n 3 8 4 4d a ta _ b a s ed e s i g n “4 5 4 5t e a c h e rm o d u l ed e s i 印4 8 4 5 1q u e s t i o nd a t a b a s ed e s i g n 4 8 4 5 2e x 锄a r r a n 百n gm o d u l e 5 2 4 5 3s c o r em a l l a 百n gm o d u l e 5 7 4 6s t l l d e n tm o d u l ed e s i g i l ”6 0 4 7s c o d n gm o d u l ed e s i g n 6 5 4 7 1c h o o s i n ga 1 1 df i l l i n gq u e s i t o n sm o d u l e 6 5 4 7 2p r o 伊距皿i n gq u e s t i o nm o d u i e 6 6 c h a p t e r 5c o n c l u s i o na n de x p e c t a t i o n 一7 3 r e f b r e n c e 7 5 a c k n o w l e d g e m e n t 7 7 r e s e a r c ha c h i e v e m e n ta n dp a p e rp u b l i s h e d 7 9 b r i e fi n t r o d u c t i o no fa u t h o ra n da d v i s e r 8 1 v i l i 第一章绪论 1 1 课题背景 第一章绪论 当今高校教学中，考试是一个很重要的环节，教学改革的一个重要方面就是研究 如何利用计算机提升考试效率、把握考试质量，同时能够将教师从繁琐的考试相关工 作，包括组卷、组考、阅卷、统分、结果分析等工作中解放出来；由于近年来各高校 纷纷扩招，许多高校的师资力量相对而言比较匾乏，如果教师被考试相关工作占用了 较多时间和精力，那么教师对于课程教学本身所投入的精力势必减少，这样对于提高 教学质量和效率是非常不利的，因此将在线考试系统在高校投入运行是势在必行的 【l 】【2 】 o 在线考试涉及到了多项关键技术，包括题库的创建与维护技术、自动组卷技术以 及自动阅卷技术等【3 】。其中，自动组卷技术可根据学生的实际情况对难度系数进行调 整，同时随机生成试卷；自动评改技术可以有效地节约时间，并且能够快速而准确 地得到评分结果。 c 语言是一种在国际上广泛流行的计算机高级程序设计语言，在各类高等院校的 计算机及相关专业中，c 语言均被列为一门必修的基础课；学习c 语言，除了需要对 理论知识的掌握之外，更不容忽视的一个重点就是培养实践应用能力【4 1 。目前国内也 有很多有关c 语言的上机考试系统，大多设计有选择题及填空题，可很好地实现对理 论知识的考核，而且自动评分技术也较成熟；但对实践能力的考核程序设计题，由 于其自动评分很难实现，一些考试系统干脆取消了该类试题；也有一些考试系统中设 计有程序设计题，但对该类试题的评分方法却并不完善，评分结果也不尽如人意【5 】。 例如全国计算机等级二级c 语言的上机考试系统中包含程序设计题型，但评分时并不 查看考生源代码内容，只是机械地按照程序运行结果给出相应分数，这样，源代码中 一个小小的错误就有可能导致一段几近j 下确的源代码无法通过编译或无法给出正确 结果( 如源代码某行句尾中漏写了分号“：”) ，按照这样的评分方法，由于运行结果不 j 下确，考生将无法得分。这明显违背了传统人工阅卷中所采用的评分原则，因此考生 的真实水平也无法通过这样的评分结果反映出来。 北京化工大学硕十学位论文 1 2 论文选题的目的和意义 传统考试方法是教师出卷，学生在纸质试卷上作答，考试完成后教师还要对纸质 试卷进行逐份阅卷、统分并登记成绩才能得到一份成绩单，同时传统考试模式中学生 作弊的事例时有发生，且在阅卷过程中，尤其是主观题阅卷过程中会带入较强的教师 主观性。 c 语言在线考试系统具有自动组卷、自动组考和自动阅卷这三大核心功能，它简 化了了考试流程，节约了教师宝贵的时间，同时还能有效避免作弊情况的发生，而且 阅卷时不带有任何主观倾向，能够得出学生的真实成绩，也有利于教师掌握学生的真 实学习情况，这样教师可以根据考试的反馈情况有针对性的在自己的日常教学中做出 改进。 在线考试系统的研究、推广和应用可以显著提高考试的科学性和公平性，将极大 的加快教育信息化的步伐。 1 3 国内外研究状况 目前，国内外已存在有较多在线的考试系统【6 】 7 】【8 】【9 】【l o 】，这些系统多半具有自动组 卷、计算机考试以及自动评阅等功能，并且组卷和考试功能也都比较成熟，在实际工 作中已经应用了较长时间【1 1 】。但对于自动评阅功能而言，它的实现受到了题型的制约， 一般而言，对于客观题的评阅，如选择题和判断题等，现有的系统都已经能很好地完 成评阅工作，但是对于一些主观性较强的问题，尤其是编程题的评阅，目前而言，在 实际应用中暂时还没有见到比较完善和成熟的解决方案n 2 1 。 对于组卷和考试功能而言，现有系统都有较成熟的技术，既有基于c s 架构的 1 3 】， 也有基于b s 结构的【l4 1 。对于评阅功能而言，一般来说是根据题型的不同采用不同的 评阅方案。对于客观题的评阅，如选择题和判断题等，只需要简单地将学生答案和标 准答案相对比，若二者一致则给满分，否则给零分。对于简单的主观题，如填空题或 程序改错题等，一般是采用模式匹配的方案，按题目性质将学生答案与标准答案进行 精确或模糊匹配，若匹配成功则给满分，否则给零分。对于编程题而言，目前现有系 统中常见做法有两种： 1 结果评分法。 2 第一章绪论 系统将考生源代码编译后执行生成的可执行文件，然后将可执行文件的输入 与标准答案提供的输出进行比较，若二者一致，则考生可得满分，否则考生 得零分。这种评分方法在阅卷时只关注考生源代码最终编译执行后输出的结 果，对考生的源代码本身并不关注。 2 机器和人工结合评分法。 系统提供一个教师阅卷功能，在该功能内，系统将考生源码显示在屏幕上， 由教师在计算机上给分，最后系统自动计算出总分。 目前而言，这两种评分方法都不是很完善，第一种方法的缺点在于过分重视了结 果而因此忽略了过程，如果一个考生的源代码基本正确，仅仅是因为输入时的一些小 疏忽( 如漏写了分号“；”等) ，就有可能丧失全部的得分，这是不公平的，也是不合 理的，同时这样的评分结果无法反映考生的真实水平，对于教师教学的改进也没有任 何帮助作用；它的优点在于可以实现无需人工干预的全自动阅卷。而第二种方法本质 上而言还是人工阅卷，虽然考生的最后得分会比较合理，但这种方法需要人工全程干 预，本质上而言并没有减轻教师的工作量，而且教师人工阅卷时还是带有一定的主观 倾向性，因此成绩的客观性还是难以保证的。 1 4 本课题的主要研究内容及方法 本课题研究和设计的是一个应用于c 语言在线考试的系统，它能实现从组卷、组 考开始到考试结束后的阅卷、统分等一系列完整考试流程；同时该套系统也应适用于 学生的日常在线练习。 首先针对自动组卷的需求对系统题库进行了设计，根据各种不同类型题目的特 点，系统实现了一套较为完善的试题存储模式并在数据库中应用，以便于组卷模块能 够自动生成试卷。 对于考试环节而言，系统基于b s 架构实现了在线考试的功能，使考生可以以简 单易用的方式与系统进行交互，并在服务器上保存学生的原始答案。 对于自动阅卷环节而言，评阅客观题和简单主观题的算法均比较成熟，在这一环 节系统研究的重点是编程题的自动评阅，通过分析，主要有以下几方面的问题： 1 对程序结果而言，如何判定其正确性? 3 北京化工大学顾十学位论文 2 对无法通过编译或无法给出结果的程序，如何对其给出合理的评价和分数? 3 如何检查程序逻辑的j 下确性7 4 对于正确的程序结果而言，如何判定源代码的实现是否符合题意? 本文采用了模拟人工阅卷的方式来对编程题进行计算机的自动评阅。首先检查编 译和执行结果的正确性，在通过的前提下检查表其与标准解法的相似度，若相似度过 低则进行扣分，这一做法的目的是为了确保考生的实现是符合题意的，比如教师在讲 授完s w i t c h 语句后进行随堂考试，自然要求题目必须用s w i t c h 语句来实现，如果学生用 了i f 语句来完成，虽然结果也一样正确，但是明显背离了考核的目的，这种情况下自 然不能得分。如果考生源代码无法通过编译或输出结果不正确，那么就需要按照评分 点给分。 4 第二章相关技术介绍 2 1 常用匹配算法简介 第二章相关技术介绍 模式匹配是串的基本运算之一【”j 。有两个字符串t 和s ，字符串t 称为正文，字 符串s 成为模式，要求找出模式s 在j 下文t 中首次出现的位置，一旦模式s 在正文t 中找到，就说发生一次匹配。有些应用可能会要求找出所有的匹配位置。在实际工作 中，字符串匹配技术在众多领域中都得到了广泛的应用，它包括精确匹配和近似匹配 两种。这里将对字符串匹配算法进行简要分析和总结。 2 1 1k m p ( k n u t h m o r ris p r a t t ) 算法 1 9 7 0 年，m o r r i s 和p 船n 提出了k m p 算法的原始思想【1 6 】，k n u t h 对此进行了改进， 使得l p 算法在搜索阶段的最坏时间复杂度和平均时间复杂度都是o ( n ) 【1 7 】，它实质 上是一个在长串中匹配一个短串的一种无回溯算法，即在整个匹配过程中，指向长串 的指针是不需要回溯的，这个特性使得它很适合处理数据仓库中的大量文本，可以在 读取的同时进行匹配工作。 l 洲p 典型算法可分为两部分：计算n e x t 值和按n e x t 值进行匹配，它的c + + 语言 描述如下： 计算n e x t 值 v o i dg e t - p e x t v a l ( c o n s td l a r 卑t ，i n tn e x t v a l 玎) i n ti = 0 ： n e x t v a l 【o 】= 一1 ； i n t j = - l ； w h i l e ( i s t r l e n ( t ) - 1 ) i f ( j 一- 1l lt 【i 】一t 啪) i + + ； j + + ； 5 北京化丁大学硕 ：学位论文 ) e l s e i f ( t i 】! = t d ) n e x t v a l 【i 】= j ； ) e l s e n e x t v a l 【i 】= n e x t 、，a l j ； ) j = n e x t v a l d 】； 根据计算出来的n e x t 值进行匹配 i n tk m p ( c o n s tc h a r 宰s ，c o n s tc h a r 宰t ，i n tn e x t ) i n ti = o ； i n t j = o ； i n ts l e n = s t r l e n ( s ) ；如果下面写成i s t r l e n ( t ) ，如果i 是负数，那么i 会比s t e l e n 的结果大 i n tt l e n = s t r l e l l ( t ) ； w h i l e ( i 劬】加一1 ： 2 1 2h o r s p o oi 算法 h o r s p o o l 算法原理与和l 洲p 算法相反，它采用后缀搜索方法进行匹配。h o r s p o o l 算法可以说是b m 算法的简化版本。如果在后缀匹配时发现有不匹配字符的存在，那 么模式将需要向右移动18 1 。假设模式最后一个元素是字符c ，h o r s p o o l 算法由c 的情 况而确定。实际上，通过最大安全移动距离来减少匹配的次数就是h o r s p o o l 算法的核 心思想。 h o r s p o o l 算法的c + + 语言描述如下： 缸 h o r s p o o l _ m a t c h ( c o n s tc h a r 奉s o u r c e ，c o n s tc h a r 宰m o d a l ，i n tp o s ) i n t s j e i l = s t r l e n ( s o u r c e ) i n t m j e i l = s t r l e n ( m o d a l ) ； i n t m i - m j e n - l ，s 仁p o s + m i ； i f 【( s j e i l - p o s ) 一1 ) ( s i w h i l e ( ( s 【s i 】! = m 【m i ) i i ( m i 一1 ) ) ； m i _ m _ 1 e i l 一1 ； s i + - m j c i l - 1 ； 城s i e l s e r d h m l l ： ) 2 1 3b m ( b o y e r m o o r e ) 算法 b m 算法采用后缀搜索的方法进行匹配：预先计算出三个函数值d 1 、d 2 、d 3 ，它 们分别对应三种不同的情形；当进行后缀匹配的时候，如果模式最右边的字符和文本 中相应的字符比较失败，则算法和h o r s p o o l 算法的操作完全一致；当遇到不匹配的字 第一二章相关技术介绍 符并非模式最后字符时，则算法有所不同1 9 1 。b m 算法的c h 语言描述如下： 撒l e 6 n em i n ( a ，b ) ( ( ( a ) = p ) i f ( 宰p p c ) r e t l l m1 e n 舢一c 0 u n t 一1 ； ) p p 一； c o u 】= l t + + ； ) r c 咖一1 ； ) b m 算法的匹配 i n tb m j n d e x ( c h a r 毒t ，c h a r 宰p ) i n t n = s t r l e n ( t ) ； i n tm = s t r l e n ( p ) ； i n ti = m 一1 ，j = m 一1 ； w h i l e ( i = n 1 ) i f ( t 【i ：一p d 】) 9 北京化t 大学硕：十：学位论文 i f ( j 一0 ) r e t 啪i ； ) e l s e i 一； j 一； ) ) e l s e 往后跳，取决于最后一次匹配的字符的位置 i = i + m - m i n ( j ，1 + l a s t ( p ，t i ) ) ； j = m - l ； ) ) r e 帆l m 一1 ； 2 1 4s hi f t a n d 算法 s h i r a n d 算法比k m p 算法简单，它的特点就在于为了提高程序运行效率，运用 了位并行技术。首先需要构造一个表b 以记录字符集中每个字符的位掩码。然后通过 计算公式的运算，在每读取一个文本字符的时候获取新的位向量【2 0 1 。因为要预处理计 算b ，如果字符集很大的话，并不划算。如果模式串m 很长的话( 大于机器字长) ， 也很不方便。所以这种算法适用于字符集较小，模式串小于机器字长的情况。s h i r a n d 算法的c + + 语言描述如下，这里假设字符集的大小为1 2 8 ： i n ts h i j f i a 1 1 d ( c h a r 宰s ，i n tl e ns ，c h a r 木p ，i n tl e np ) l o 第二章相关技术介绍 定义字符集表 i n tb 1 2 8 】； m 锄s e t ( b ，0 ，s i z e o f 【b ) ) ； 计算字符集中每个字符在字符集表中的掩码 i n ti ； 五”( i _ o ；i l 饥_ p ；i + + ) b 【p i 】 l _ 1 i ； ) 按字符集表进行匹配 i n td = o ； f o r ( i _ o ；i l e n ；i + + ) d = ( ( d 1 ) i1 ) & b s i 】； i f ( d & ( 1 ( 1 e i l - p 1 ) ) ) r e t l l mi l e np + 1 ； ) ) r c 炯】r n 一1 ； 2 2l dis t a n c e 算法 一个字符串可以通过增加一个字符，删除一个字符，替换一个字符得到另外一个 字符串，假设我们把从字符串s 转换成字符串t ，前面3 种操作所执行的最少次数就 北京化工大学硕士学位论文 称为s t 的相似度；如”a b c ”与”a d c ”度为1 ，”a b a b a b a b a 与”b a b a b a b a b ”度为2 ，”a b c d f t 与 a c d b ”度为2 。 计算两个字符串s 和t 之间的相似度s ( s ，t ) 可以使用l e v e i l s l l t e i n