引论：我们为您整理了13篇匹配算法论文范文，供您借鉴以丰富您的创作。它们是您写作时的宝贵资源，期望它们能够激发您的创作灵感，让您的文章更具深度。
篇1
1KMP算法
最简单的朴素串匹配算法(BF算法)是从主串的第一个字符和模式串的第一个字符进行比较，若相等则继续逐个比较后续字符，否则从主串的第二个字符起再重新和模式串的第一个字符进行比较。依次类推，直至模式串和主串中的一个子串相等，此时称为匹配成功，否则称为匹配失败。朴素模式匹配算法匹配失败重新比较时只能向前移一个字符，若主串中存在和模式串只有部分匹配的多个子串，匹配指针将多次回溯，而回溯次数越多算法的效率越低，它的时间复杂度一般情况下为O((n-m+1)m)（注：n和m分别为主串和模式串的长度），最坏的情况下为O(m*n)，最好的情况下为O(m+n)。KMP模式匹配算法正是针对上述算法的不足做了实质性的改进。其基本思想是：当一趟匹配过程中出现失配时，不需回溯主串，而是充分利用已经得到的部分匹配所隐含的若干个字符，过滤掉那些多余的比较，将模式串向右“滑动”尽可能远的一段距离后，继续进行比较，从而提高模式匹配的效率，该算法的时间复杂度为O(m+n)。
那么如何确定哪些是多余的比较？在KMP算法中通过引入前缀函数f(x)来确定每次匹配不需要比较的字符，保证了匹配始终向前进行，无须回溯。假设主串为s1s2，sn.，模式串为t1t2，tm.，其中m≦n，从si+1开始的子串遇到一个不完全的匹配，使得：
(1.1)
如果我们能确定一个最小的整数，使得：
(1.2)
其中，所以确定i''''等价于确定k，这里的k值就是我们要求的前缀函数f(x)。由式1.1和1.2中K值与主串s无关，只与给定的模式串t中与主串匹配的q有关，即k=f(q)，
f(q)=max{i|0iq且t[1..i]是t[1..q]的后缀}(1.3)
确定KMP前缀函数的算法如下：
#defineMAXSIZE100
Typedefunsignedcharstring[MAXSIZE+1];//0号单元用来存放串的长度
voidf(sstringt,int*array)
{
m=t[0];//m为当前模式串的长度
array=(int*)malloc((m+1)*sizeof(int));//0号元不用
array[1]=0;k=0;
for(q=2;q<=m;q++)
{while(k>0&&t[k+1]!=t[q])k=array[k];
if(t[k+1]==t[q])k=k+1;
array[q]=k;
}
}
关于KMP算法的前缀函数f(x)的示例见表1。
当模式串中有i个字符串匹配成功，第i+1个字符不匹配时，则从i-f(i)个字符重新开始比较，这样不仅无须回溯，而且一次可以向前滑动i-f(i)个字符，大大提高了模式匹配的效率。下面给出朴素匹配算法和KMP匹配算法的比较，见表2。
表2朴素匹配算法和KMP匹配算法比较表
朴素算法KMP算法
时间复杂度O((n-m+1)m)O(m+n)
向前移动字符个数1q-f(q)
回溯次数q-1无
其中：n为主串长度，m为模式串长度，q为匹配成功的字符个数
2KMP算法的改进
在KMP算法的实际应用中，发现该算法也存在着不足，结合下面的表一来论述KMP模式匹配算法的改进。假设模式串前4个字符与主串的第i+1..i+4匹配成功，第5个字符匹配失败，此时前缀函数f(4)=1，下一次匹配将从第i+4开始，并直接将模式串中的第2个字符与主串中的第i+5个字符进行比较，从表1中可知，匹配必将失败，此次比较是多余的。这说明此时的前缀函数f(x)并不是最优，需要对前缀函数进行改进。实质上，所谓对KMP算法的改进就是对其前缀函数的改进。
4结语
本文给出的算法较朴素匹配算法在效率上有了较大的提高，尤其是对重复字符出现较少的数据段进行模式匹配可取得较高的查找效率。应用于大型数据库的数据查询，会更加有效地缩短查找时间。
参考文献
[1]严蔚敏，吴伟民.数据结构[M].清华大学出版社，2001
篇2
引言
双目视觉是一种通过两幅图像获取物体三维信息的方法，具有通过二维图像认知物体三维立体信息的能力，其关键技术就是要解决两幅图像中对应点的匹配问题［1］。立体匹配一直都是机器视觉领域中的难点和热点，论文根据结合变电站及巡检机器人双目视觉系统的特点，运用匹配辅助区域匹配算法实现立体匹配，获得密集准确的深度图。
1、立体匹配原理
立体匹配基于视差原理，如图1所示。其中基线距B=两摄像机的投影中心连线的距离；摄像机焦距为f。设两摄像机在同一时刻观看空间物体的同一特征点，分别在“左眼”和“右眼”上获取了点的图像，它们的图像像素坐标分别为
采用平行摄像机模型，两摄像机的图像在同一个平面上，并且特征点p的图像坐标y坐标在左右图像平面上相同，
可以得到：
要想根据左右图像对完成立体匹配任务，就把只需计算左右图像对的立体视差，立体视差是景物点在左右图像中图像像素的横坐标之差，即：
从而就可以建立立体视差图(又称深度图)。所建立的立体视差图可以细分为两个子区域，零视差子区域和非零视差子区域，零视差子区域为机器人可以自由行走的无障碍平坦区域；非零视差子区域为平坦区域上的凸出区域，可能是障碍物存在的区域。
根据式(3)及立体视差原理，可以方便地计算世界坐标下的特征点在摄像机坐标系下的三维坐标：
左摄像机像面上的任意一点只要能在右摄像机像面上找到对应的匹配点，就可以确定出该点的三维坐标。这种方法是完全的点对点运算，像面上所有点只要存在相应的匹配点，就可以根据式(5)计算出对应的三维坐标。
2、立体匹配设计
经过图像预处理，可以为立体匹配提供较理想立体图像对，降低了匹配算法的难度。论文结合变电站、检机器人双目视觉系统的特点，运用特征辅助区域匹配算法实现立体匹配，该算法结合特征匹配算法及区域匹配算法的优点，可以在计算量不大的情况下，生成密集准确的立体视差图。
算法的总体上分三步：
2.1 匹配初始化阶段
匹配初始化阶段需要完成以下工作：对双目摄像机参数的标定；对摄像机所采用的图像运用高斯―拉普拉斯模板进行图像预处理；对预处理的图像运用加速主成分分析法实现图像的特征提取；这些过程都是为后面的立体匹配做准备，为之提供较理想的立体图像对。
2.2 特征匹配阶段
根据各种匹配准则缩小匹配点的搜索范围，利用特征匹配算法确定正确的匹配点。
2.3 区域匹配阶段
由于前面特征提取算法限制，不可能把景物所有特征点全部提取到，所以特征点匹配完成后，还存在一些有价值的非特征点未被匹配。但是这些未被匹配点被已匹配点限制在较小的范围内，对这些小范围点的匹配就是区域匹配算法的工作。
对多个可能的候选匹配点比较时，可能使用的依据有灰度、曲率、拉普拉斯变换、梯度等。结合变电站实际环境，运用连续性约束准则和灰度、x方向的灰度梯度、梯度方向唯一确定匹配点［2］。思路如下：
①┍算视觉连续性约束相关系数
其中d为已匹配点的视差均值，d为当前候选匹配点的视差。若，1为预先设定视觉连续性约束相关系数阈值，排除此候选匹配点，重复执行此步直到时，执行第2步；否则直接执行第2步执行。
②计算候选匹配点与待匹配点的灰度相关值Vcorr、x方向的灰度梯度接近程度系数Kgard_r、梯度方向相关系数式(7)-(8)中，K_gard_x、K_gard_y为基准图像上特征点x和y方向的梯度，Rgrad_x、Rgrad_y为候选匹配点x和y方向的梯度，fl、fr为左右图像的灰度函数，、为特征点和候选匹配点在窗口(2N+2M+1)中灰度均、为两点在窗口中灰度标准差。若有Vcorr
③计算总判断依据
计算出所有候选匹配点的Iall值，其Iall值最大者即认为是最佳候选匹配点，即特征点Pleft在右图像中的匹配点。
要匹配固定大小的图像窗口中的像素，相似约束准则是两幅图像在窗口中的相关性度量，当被搜索区域的点与待匹配点间相似约束准则最大化时，认为搜索区域的点是待匹配点的匹配点［3］。
设有立体图像对IMG1、IMGr，Pl、Pr为两幅图像中的像素点，相关窗口大小为，为图像IMGl中像素点Pl在图像3、实验与结果
图2中左右两图像，是左右摄像机对同一景物拍摄所得。
根据上图的左右两图，运用立体匹配算法求得立体视差图。实验结果如图3所示，其中左图像素深度图，右图是对左图经median处理后的效果图，看起来对左图清晰了不少，但不能显示真实图像视差关系。此算法消耗较长时间，将在以后工作中改进。
参考文献
［1］杨俊,贾秀芳.变电站防火防盗图像识别的研究.中国高等学校电力系统及其自动化专业第20届学术年会，2004.7.
［2］林琳.机器人双目视觉定位技术研究［D］．西安电子科技大学硕士学位论文,2009.
篇3
1 引言
在现有的毕业论文选题系统中，一个学生只能选择一个题目作为自己最终的题目，同样，一个题目只能分配给一个学生。如果最后题目由学生自己确定，那就会出现先选的学生具有更大的选择余地，后选的学生由于不能再选已经选定的题目，所以其可选择的题目会越来越少，这对很多学生来说很不公平。如果学生选择自己的志愿，最终题目由老师来定，这不但加大了老师的工作量，而且还是不能保证每位同学的公平性。如何采用计算机智能辅助选题，设计最优匹配算法实现学生与题目的整体最优匹配，会大大提高选题的效率。
汤颖曾在《毕业设计立项与选题管理及其支持系统》中提出，采用模糊匹配技术进行学生-题目的自动匹配；潘志方在《一种改进的Ford-Fulkenson算法在选题系统中的应用研究》中将题目与学生的匹配抽象为二分图的匹配，并采用改进的Ford-Fulkenson算法实现题目与学生的自动匹配。以上两种方法只考虑了学生与题目之间的最大匹配值，并没有考虑学生的整体满意度最优的情况。
本文将通过采用最优匹配算法（KM）确定一种匹配方案，使得学生的整体满意度最高。具体方法概括如下：学生预选多个题目，并根据自己对题目的满意度由高到底排序，这样，满意度成为二分图的一分值，如图1所示：
2 系统功能模块设计
根据前期的可行性分析，本系统主要进行以下模块的设计：系统管理员模块、专业负责人管理模块、指导教师管理模块和学生选题模块。
系统管理员模块主要负责对系统参数的设置及用户的管理。主要实现以下功能：
（1）系统设置：对系统标题、毕业生、选题参数设置；
（2）学院及专业设置：完成学院、专业的添加、删除、修改操作；
（3）数据字典的维护：教师信息、选题难度、选题方向灯信息的维护；
（4）教师和学生的管理：完成教师、学生信息的添加、删除和修改操作；
（5）文件文化建设管理：日志文件查看、上传文件的管理。
专业负责人管理模块与系统管理员权限相似，但操作的数据只能针对于指定专业，无法浏览及操作整个学院的课题及学生信息。最重要的功能是实现题目的审核。
导师管理模块主要用于选题以及选择自己选题学生的审核确认。
（1）个人中心管理：如信息修改及密码重置；
（2）选题管理：选题的增加、修改、删除以及选题类型的设置；
（3）学生选题查询及审核。
学生模块主要实现学生选题的选择及确认。
（1）学生个人信息的修改；
（2）学生选题及确认信息查询；
（3）学生留言及咨询。
3 KM算法在系统中的实现
KM算法由Kuhn和Munkras分别提出来，这是一种问题。经典的算法。该算法由通过每个顶点一个顶标（A[i][j]）来求最大权匹配的问题转化为不断寻找增广道路以使二分图的匹配数达到最大的完备匹配。KM算法的关键在于不断寻找二分图中的可增广道路。如果找到一条可增广道路，就可以额将属于和不属于相等子图的边取相反，从而相等子图里就是增加一条边，一直到所有的顶点都进入相等子图为止。
KM算法可以很好地解决选题系统中，题目与学生最优匹配的问题。下面以国际商学院09级本科学生选题为例。
在匹配过程中，设学生的集合为X={X1，X2，X3……Xn}，选题的集合设置为Y={Y1，Y2，Y3……Yn}，学生对自己选题的满意度为二维矩阵Z[m][n]，其他题目规定权值为0。系统规定学生最多可预选3个题目，并按照满意度分别设置0.9，0.7，0.5。以下表1是对国际经济与贸易专业使用不同算法得出的学生满意程度。
下面对以上数据进行说明。如采用手工分配的方式，使得681名学生中414名同学分的了题目，满意度为60.82%；如果采用最大匹配算法进行分配，可以使分配数达到最大，有517名学生分得题目，满意度上升为79.99%；最有用最有匹配算法进行分配，使总体满意度达到78.24%，533人。需要说明的一点是，KM算法只是找到了整体最优匹配而不是最大数匹配，如果整体最优情况下匹配数和最大匹配数相差得太大的话，那么整体最优方案显得不太可取。所以，最好的情况就是同时考虑最优匹配和最大匹配来同时控制两者的大小。
4 结语
本系统实现了毕业论文选系统工作的各个管理功能，通过实现教师与学生的双向选择，使用KM算法，提高选题的质量和效率，为学院充分利用网络完成毕业论文选题工作提供了便利的平台。
参考文献：
[1]汤颖.毕业设计立项与选题管理及支持系统[J].合肥工业大学学报，2006，29（5）.
篇4
1 引言
突发公共卫生事件应急系统的建立对于保障公共安全，建设社会主义和谐社会具有特殊重要的现实意义。目前国内外在应急响应领域已经取得了很大的进步，但对应急预案系统的研究才刚刚处于起步阶段。作为整个系统中最为基础和根本的一环，应急预案对于应急响应的实施具有重要作用。
本文通过对现有应急预案和应急响应过程的分析，通过框架技术对应急预案的知识进行表示，研究了预案的匹配算法，给出了预案相似度以及价值评估的计算方法。
2 智能预案匹配
应急预案是应急事件处置的领域知识来源。应急预案管理系统可以在对处置预案、资源分布转台、事件处置状态自动初步生成事件处置方案。再经过处置人员对初步方案进行调整，经过认可后即可作为高效地应急响应处理的指导方案。
2.1 基于框架的匹配
预案采用框架的智能化存储结构表示，预案的智能匹配自然和框架体系的匹配息息相关。基于框架体系的匹配系统一般由两大部分组成：
（1）由框架及其相互关联构成的知识库。提供求解问题所需要的知识；
（2）由一组解释程序构成的框架推理机。针对用户提出的问题，通过运用知识库中的相关知识完成求解问题的任务，给出问题的解；
2.2 匹配过程及算法
3.2 数据相似度研究
预案是介于数据与知识之间的一种知识存在形式，存储预案的框架结构具有不同数据类型的槽和侧面属性。计算不同数据类型属性的相似度，首先要讨论属性即槽值和侧面值的数据类型。一般来说，属性的数据类型分为以下三个大类。针对以上三大类型，分别来讨论其相似度算法。
4 结论
本文主要论述了智能预案框架表示与预案知识匹配机制。通过对现有应急预案和应急响应过程的分析，提出一个对应急预案的描述方法。利用框架结构完整的描述预案实体单元，依据各框架间的纵向联系和横向联系，从而形成框架网络。利用框架知识表示，研究了预案的智能匹配与相似度比对。最后讨论了预案相似度算法，给出了预案相似度以及价值评估的计算方法，讨论了预案框架中不同数据类型属性的相似度算法，重点研究了数值类型和文本类型的属性相似度算法。
参考文献
[1]Nilsson NJ. Artificial Intelligence： A New Synthesis[M].Copyrighted Matenal，2000.
[2]Sui YF，Gro Y， Cao CG.Ontologies， Frames and Logical Theories in NKI[J].Journal of Software，2005，16（12）.
[3]李晨阳，曹忠升，冯玉才.一种基于框架和中间件模型的知识库系统[J].计算机应用，2000（12）：1298-1300.
[4]张荣梅.基于CBR与MAS的智能决策支持系统研究及应用[D]：[硕士学位论文].北京：北京科技大学，2001.
[5]刘义刚.基于预案库的快速智能决策支持系统的研究[D]：[硕士学位论文].北京：北京理工大学，2001.
[6]杨健，赵秦怡.基于案例的推理技术研究进展及应用[J].计算机工程与设计，2008，29（3）：710.
篇5
摘要：分析了毕业论文选题系统的特点，引入了学生及指导教师对选题结果的满意度，建立了一个以总体满意度最大为目标的毕业论文选题系统模型，并在此基础上设计实现了基于web的本科毕业论文选题系统。实际应用表明，该系统可以有效的提高毕业论文选题的总体满意度及选题质量。
Abstract: The thesis analyzed the characteristics of graduation projects' selection system, introduced the satisfaction of student and instructor with the results on the topics, established a model of graduation projects' selection system which took the overall satisfaction as the goal, and on this basis, designed and implemented graduation projects' selection system for undergraduates based on web. The application showed that this system could effectively improve the overall satisfaction of thesis topics and the quality.
关键词：满意度 毕业设计 选题系统 web
Key words: satisfaction；graduation project；selection systems；web
中图分类号：TP39 文献标识码：A文章编号：1006-4311（2011）29-0147-02
0引言
毕业设计（论文）是高校培养学生的重要环节，随着高校的扩招，毕业论文选题的工作量也越来越大，以往的手工选题的方式已经远远不能满足高校毕业论文选题的需求。一个有效的方法是采用计算机智能选题系统，在毕业论文选题系统中，一个学生只能选择一个题目作为自己的最终论文题目；同样，一个题目也只能分配给一个学生。如果最终题目由学生自己确定，那么就会出现这样的情况：先选的学生具有更大的选择余地，后选的学生由于不能再选已经选定的题目，所以其可选择的题目会越来越少，这对很多学生来说是很不公平的。如果学生选择自己的志愿，而最终题目由老师来定，这不但加大了老师的工作量，而且还是不能保证每位同学的公平性。如果采用计算机智能辅助选题，设计最优匹配算法实现学生与题目的整体最优匹配，无疑将大大提高选题的效率。
一些学者曾对题目的智能化匹配作过比较深入的研究，如汤颖采用模糊匹配技术进行学生一题目的自动匹配[1]；潘志方将题目与学生的匹配抽象为二分图的匹配，并采用改进的Ford-Fulkenson算法实现了题目与学生的自动匹配[2]；杨胜超等将学生的满意度引入到了毕业论文选题中[3]。但是，他们只是考虑了题目与学生的最大匹配数，并没有同时考虑学生和教师整体满意度最优的情况，而教师的满意度往往对选题质量的控制起着关键作用。
本文在毕业论文选题系统中引入了学生和教师的满意度，建立了在最有匹配基础上的以满意度最大为目标的选题系统模型，给出了算法实现并将其应用到了本科毕业论文选题系统的设计中，最后给出了毕业论文选题系统的具体实现，并进行了实际测试。测试结果表明，该选题的应用可以提高选题的总体满意度和选题质量。
1选题系统最大满意度模型
设S为学生的集合，有sm属于S，m属于[1，M]，其中M为学生数。设T为题目的集合，有tn属于T，n属于[1，N]，其中N为论文题目总数。那么对于所有的选题情况有集合Anm，对于某一具体选题，学生满意度Xnm，教师满意度Ynm，那么Xnm+Ynm有最大值，max(Xnm+Ynm)。因此，该问题变成了求解满意度最大值问题，并能确定在取得最大值情况下Anm的集合，也就是具体的每一个学生的对应的唯一的选题。
2毕业论文选题系统的设计实现
2.1 系统用例该系统的用户主要有三类，分别是系统管理员、普通教师和学生，系统用例说明如表1所示。
2.2系统流程设计基于最大满意度的毕业设计选题系统，充分考虑了学生确定自己论文题目的自由性：学生可以自主命题由老师来审核，如果审核通过则可作为自己的最终论文题目，如果未通过审核还可以反过来参加预选或者再次自主命题（有最大自主命题数限制）。同时将教师对选题情况的评价引入，更加合理。同时还优化了题目预选的匹配：通过管理员启动最大满意度匹配算法，确定出学生与题目的最优匹配方案，这样便大大减轻了老师的工作量，提高了选题的效率。最后，如果通过以上两个步骤还有学生没有定题，就只有通过老师手动确定学生的最终题目。
2.3 系统数据库设计基于前边的分析设计，我们需要设计到下列各表，这些表之间相互关联，共同存储着系统所需要的数据。在设计数据库表的过程中，应遵循以下几条原则，数据库设计一个表最好值存储一个实体或对象的相关信息，不同的实体最好存储在不同的数据表中，如果实体还可以再分，实体的划分原则是最好能够比当前系统要开发的实体的颗粒度要小，数据表的信息结构一定要合适的，表的字段的数量一定不要过多，扩充信息和动态变化的信息一定要分开在不同的表里，对于多对多这样的表关系系统尽量不出现。该系统中主要的数据表如表2-表5。
普通教师参数表保存的是用户参数，UserID是用户注册时输入的，作为该表的主键，表中记录的用户编号是不会相同的，这要求在用户注册时检查欲注册的用户名是否已经被注册过，这是必要的一步。（故部分系统在注册时要求用个人Email地址作为用户ID，这样重复的几率非常低，但也是需要检查的。）且UserID在其他表中也会用到。（表2）
学生参数表保存的是用户参数，StID是用户注册时输入的，作为该表的主键，表中记录的用户编号是不会相同的，这要求在用户注册时检查欲注册的用户名是否已经被注册过，这是必要的一步。（表3）管理员参数表是管理员的一些注册信息，其中Adminid是管理员编号，是该表的主键。其余各字段与普通教师参数表中的字段意义相同。（表4）
题目信息参数表是信息的各种参数，包括题目的编号（系统自动生成），是该表的主键。题目的详细内容是对该题目的简单介绍，题目类别根据需要进行设置。（表5）
2.4 系统实现最后，系统采用asp+access进行了实现，具体实现过程由于篇幅所限，不再赘述。
3系统测试
该系统设计完成后，在榆林学院信息工程学院2010届本科毕业生的毕业论文选题过程中进行了实际的测试，测试数据如表6。
在此次测试中，共有学生96人，题目107个，从表中可以看出，采用手工分配方案，只有74个学生可以分得选题，而采用智能最大满意度方案，有91人分得了选题（其余学生采用手工分配）；在满意度方面，采用最大满意度方案后，学生的整体满意度和教师的整体满意度均有较大提高。
4结束语
按照以上描述的设计思路和算法，采用Asp技术+Access后台数据库实现了毕业论文选题系统。该系统将选题结果学生和教师整体满意度最大作为目标，不但大大降低了整个选题过程的工作量，而且大大提高了学生及教师对选题结果的整体满意度，从而提高了选题质量。该系统在榆林学院信息工程学院2010届计算机科学与技术专业本科毕业生的毕业论文选题中进行了应用，取得了良好的效果。
参考文献：
篇6
Research of the Text Subjective Question's Auto Remarking Algorithm Based on Word Segmentation Algorithm &VSM
LI Xue-jun
(Southwest University of Science and Technology, Mianyang 621010, China)
Abstract: The paper makes use of the studied results(such as Vector Space Model (VSM), Word Segmentation algorithm and so on) of the native language understanding, and applys them in processing the text subjective question's answer (including the standard answer and the student's answer), and then it used the text_charactered vector matching algorithm to auto remark those student's examining paper by the computer system. According to the experiment, the algorithm has accuracy of remarking and some valuable domains of application.
Key words: Auto-remarking; Word Segmentation algorithm; Vector Space Model (VSM); Text character matched
随着计算机技术和互联网技术迅猛发展，传统教育模式发生了变化，越来越多的课程提出了在线考试的需求。计算机可以很好地完成客观题（如选择题、判断题）的判分工作，其判分策略、关键技术及其应用实例详见文献[1]至文献[3]。亦即把考生作答的结果和题目标准答案进行精确匹配从而得到考生的得分。文献[4]提出了一种近似串匹配算法来对文本录入题的自动评分算法，其本质还是进行文本的比较，与客观题的判分原理基本是相同的。
计算机自动评分是指利用计算机程序来模拟人工评分的标准和内部过程。对客观题的评分是通过把试题的标准答案与考生的答案做一个精确比较，并据此作为是否给学生相应的题目分值；对于主观题，目前一般是让考生把其作答的结果形成一个文件（答案文件），再通过网络把考生的答案文件上传到考试服务器中的专用目录中，科任教师在考试结束后对考生的答案文件进行人工评判来进行给分；最后把考生客观题的计算机自动评分结果和主观题的人工评分结果累加起来作为考生的最终成绩。对于客观题可以完全不要人工干预，而主观题就必须在人工干预下才能完成。
因此本文就此提出将人工智能的自然语言理解技术（主要是分词算法）、文本的空间向量模型表示和知识的框架表示内容应用到网络考试系统中的主观题的自动评分过程中。
1 文本主观题自动评分原理
对于在线考试系统来说，其自动评分是在特定范围内的，不需要让其理解所有的自然语言，只需要理解标准答案即可。因此，应该使用某种算法使标准答案转化成机器能够理解的形式，将考生答案也按照一定的规则转化成计算机可以理解的形式，然后再将其和标准答案进行匹配并评分。其关键是如何将评分规则转化为可以被机器理解的知识库。主观题的自动评分原理如图1所示。
2 自动分词算法简介
2.1 最大匹配分词算法
匹配分词法是按照一定的策略将待切分的汉字串与一个“充分大的”机器词典（如金山词霸等）中的词条进行匹配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配。按照不同长度优先匹配的情况，可以分为最大（最长）匹配和最小（最短）匹配。最大匹配分词法即先确定一个最大的词的长度，然后从左（正向）或从右（逆向）取该长度的词串，将词串与词典中的词条匹配，如果没有该词则去掉一个字符继续匹配，以此类推，直到达到匹配或剩下一个单字为止。
2.2 最大概率分词算法
最大概率分词算法的基本思想是：假设一个待切分的汉字串可能包含多种分词结果，将其中概率最大的那个作为该字串的分词结果。例如，有一个句子S＝“有意见分歧”，第一种分词路径W1＝“有/意见/分歧/”，第二种分词路径W2＝“有意/见/分歧/”，如图2所示。到底应该选择哪一种为最后的分词结果呢？
根据概率分词算法的基本思想，需要计算每一种方法出现的选取概率的作为最后结果，即计算Max(P(W1|S), P(W2|S))。概率计算方法如图3所示。
每一个词汇出现的概率P(wi) 可以在带词频的词典中查出。通过查词典可以得到每个词的概率为：P(有)=0.0180，P(有意)=0.0005，P(意见)=,0.0010，P(见) =0.0002，P(分歧)=0.0001。
对于第一种分词方法：P(w1) = P(有) * P(意见) * P(分歧) = 1.8×10-9；
对于第二种分词方法：P(w2) = P(有意) * P(见) * P(分歧) = 1×10-11；
由上所示，P(w1) > P(w2)，所以取第一种方法作为分词结果。
3 文本矢量特征匹配算法
主观试题的答案以文本方式存储，经过分词后的文本如何表示才能更加容易地被计算机处理关系到文本处理的准确性，因此文本表示方法是自动评分算法的一个关键问题。近年来，在Web文本信息特征获取算法的研究中，矢量空间模型(Vector Space Model，VSM )[5-6]是应用较多且效果较好的方法之一，本算法借鉴了该模型的思想。在矢量空间模型中，文本被看作由一组正交词条所生成的矢量空间。根据这个思想，同时考虑到考试评分中经常将试题答案分为几个要点，因此提出主观题成绩评判模型为：
首先，答案文本是由一些要点组成，如果把答案文本（Answer text 用A来表示）看成一个由n个要点（Pi）组成的集合，则可以这样表示答案：A={P1,P2,…,Pi,…,Pn}；设每个要点Pi的分值为Mi，则该答案的总分M为：；按照VSM思想，将标准答案每一个要点Pi被看成是由Ki个特征词（wj）组成的向量P：；设每个特征词的权重是wj（由经验丰富的任课教师人工设置），则其归一化权重为：；设考生答案的每一个要点Pi'也被看成是由Ki'个特征词（wj'）组成的向量P'：；通过计算考生答案和标准答案的向量间的距离并据此计算考生可得到到该要点的分值，即：(如果向量间的距离为0，则说明考生答案和标准答案完全匹配，考生可以拿到该要点的所有分值)；考生所得总分M'为：。
4 算法测试及结论
本论文采用oracle作为后台数据库管理系统（因为系统所用的词典数据库都比较大），基于B/S模式设计了基于文本的主观题自动评分测试软件。通过对不同名词解释题目（答案长度及复杂度不同）的评测，再将本算法评得的分数与人工评分相比，分数的容差在（－0.5～＋0.5），可以测得其评分的准确度在86.93％。通过实际的数据测试可以看出，答案越复杂，要点越多，评分的准确性越差；相反，要点越少，答案越简单，评分的准确性越好。而且人工设置关键词和权重也有利有弊，人工设置固然增强了系统的准确程度，但是其前提是设置人必须是有经验的老师，如果是没有经验的老师设置，则给算法增加了人为的误差。该算法具有一定的实用性，但还有待进一步的完善。
参考文献：
[1] 华蕊. 自动组卷及评分系统的设计[J]. 中国电化教育.2002,(2):84-85.
[2] 朱映辉, 江玉珍.计算机自动评卷策略分析与研究[J]. 电脑知识与技术,2005,(35):30-32.
[3] 李丁. 计算机考试系统中自动评分策略的研究与实现[J]. 广东广播电视大学学报,2002,11(4):30-32.
篇7
Key words: immune theory clonal selection antibodies circulating complement
一、引言
人工免疫系统是一个新兴的计算智能研究领域。近年来,人工免疫系统及其应用已逐渐成为了智能信息系统中的研究热点。生物免疫系统的免疫识别过程能在较短的时间内利用数量相对有限的抗体去识别近乎无限多的抗原,从信息处理的角度看,这是在资源受限条件下的一整套高效问题求解机制。克隆选择学说的基因重组、亲和度成熟、受体编辑等机制较好地从个体层次上阐述了这种高效问题求解能力的形成,因而成为多种人工免疫系统模型和算法的重要思想来源,免疫算法就是一种借鉴该系统特性而形成的启发式搜索算法.它具有保持种群分布多样性的特性,避免陷入局部最优解的优点。
二、克隆选择原理
克隆选择是生物免疫系统理论的重要学说,其原理(如下图1所示)的基本思想是只有那些能够识别抗原的细胞才进行扩增,只有这些细胞才能被选择并保留下来,而那些不能识别抗原的细胞则不选择,也不进行扩增。骨髓中微小的“休眠”的B细胞每一个都载有一个不同的抗体类型。这些细胞载有对于抗原特异的受体,扩增分化成浆细胞和记忆细胞。
免疫系统在成长的克隆中也是自适应的,同时也呈现了一种变异机制,在对抗体特异编码的基因中产生极高频率点变异。该机制(体细胞高频变异)与为改进抗原结合而进行的选择,共同导致细胞与抗原具有极高的亲和力匹配。
根据免疫系统中的克隆选择学说的思想,该算法在抗体种群和抗体优秀决定基中进行克隆选择操作,全面的模拟了生物免疫系统克隆选择的过程,很好的保持了抗体种群的多样性。
三、克隆选择算法
3.1 抗体/抗原匹配算法
要确定一个B细胞对象与提呈的抗原结合得有多好,在抗原上任何点开始匹配;匹配算法计算每一位,在抗原与抗体之间以互补的方式进行匹配,得出匹配值,再从匹配分值得到结合值,根据抗体的结合值的大小可以看出抗体和抗原是否结合的完美,并且可以判定出结合完美的抗体中哪些决定基起到了关键的作用。
对于一个抗体结合一个抗原,结合必须是稳定的,也就是匹配分值在匹配发生之前必须超过一定的阈值。该设定阈值为抗体大小的一半。该方法是Hightower的匹配算法的修改,只是多种伪生物匹配的一种。
抗体/抗原匹配算法的描述:
(1)初始化抗体群,针对抗体与抗原的决定基逐位进行异或操作,若抗体和抗原相对应的决定基相同为0,不同为1,结果统记为c;
(2)将抗体与抗原的决定基逐位进行异或操作结果的累积和记为(公式一);
(3)对由两个或者更多个1组成的每一区域记录长度为l;
(4)记抗体的结合度为(公式二);
(5)定义阈值为
(6)抗体Ab 移位一位。
3.2 克隆选择算法的实现
克隆选择算法的实质是在进化过程中,在每一代最优解的附近,根据亲和度的大小进行克隆,产生一个变异解的群体,从而扩大了搜索范围(即增加了抗体的多样性),有助于防止进化的早熟和搜索限于局部极小值,同时通过克隆选择来加快收敛速度。其基本思想为:随机生成N个抗体组成的抗体群,对这些抗体进行一些操作后,选出抗体中优秀的决定基片段,针对这些优秀的决定基片段进行克隆操作,从而形成子抗体。克隆选择操作只是在优秀的抗体决定基中进行,而不是在抗体的所有决定基中。
克隆选择算法是根据克隆选择原理和亲和度的成熟发展而来的,其主要考虑了免疫方面的如下几个方面:
(1)保持功能性的细胞从指令系统中分离;
(2)受刺激最强的个体进行选择和克隆;
(3)为受刺激的细胞死亡;
(4)亲和力度较好的克隆个体重新选择;
(5)多样化的产生和保持。
克隆选择算法的实现步骤(流程图如图2所示):
(1)初始化。随机产生初始的抗体群(P);
(2)计算抗体与抗原的结合度。本文采用的抗体和抗原是否完美结合的匹配算法,是由Hightower提出的,对抗体和抗原逐位进行异或操作,即抗体和抗原的决定基位相同记为0,不同记为1,若抗体和抗原结合,则其为1,根据公式一得出该抗体的匹配值,然后根据公式二可得到该组抗体和抗原的结合强度值(M);
(3)挖掘一个抗体中优秀的决定基片段。根据抗体和抗原的结合的匹配程度,我们可以看出抗体与抗原能够结合上的决定基位,算法中提到必须是两个或者更多个连续结合的决定基片段才进行挖掘提取(Pm)。
(4)对选择出抗体的优秀决定基的片段进行克隆操作,产生一个暂时的克隆群体(C);
(5)随机生成新的编码融合进暂时的克隆群体中,形成新的抗体群(Pn)。
3.3 抗体的循环补充
生物免疫系统中为了保持抗体的多样性,每天都会产生大量的新的抗体注入到免疫系
统中,其中大多数抗体决定基的片段会因为结合度太低而遭受到抑制,但仍有少数的抗体片段跟抗原具有很好的结合,获得了克隆扩增机会。为了模拟这一抗体循环补充机制,我们在每次对优秀抗体决定基片段的提取之后,再随机产生的抗体决定基注入到提取出来的优秀抗体决定基片段中,形成新的抗体进入到克隆扩增以及结合度成熟的过程中,以提高抗体的多样性,实现全局范围内的搜索优化,避免陷入局部最优解。
四、克隆选择算法运行结果
图3(a)中我们可以清楚的看到抗原与抗体是怎样结合的,并找到了能够完美结合的抗体中优秀的决定基片段,根据算法的运行可得出抗体与抗原的结合度为156。图3(b)中可以看出算法能够对这些优秀决定基片段进行了挖掘。图3(c)中算法实现克隆。图3
(d)中随机生成新的编码融合进暂时的克隆群体中,形成新的抗体群。
五、结束语
借鉴了生物免疫系统中的克隆选择原理,从而设计了本算法。在文中详细阐述了算法的实现步骤,并且该算法通过调试能正确的完成其功能输出。但是该算法还没有通过实例验证,在接下来的工作中,将本算法应用到实例中,来判定算法的性能。
参考文献:
[1]韦巍,张国宏.人工免疫系统及其在控制系统中的应用.控制理论与应用,2002,19 (2):157-160
[2]莫宏伟.人工免疫系统原理与应用.哈尔滨工业大学出版社.2003.1390
篇8
1、积相关算法概述
以图像匹配为基础的电视跟踪方法,习惯上称为电视图像相关跟踪,简称为相关跟踪。积相关算法是常见的相关算法中的一种,也叫归一化相关算法:
相似性度量(x0,y0)的表达式为:
n~(x0,y0)=m-1X=0m-1y=0f(x,y)t(x+x0,y+y0)m-1X=0m-1y=0f2(x,y)m-1X=0m-1y=0t2(x+x0,y+y0)
其中,0≤x0≤n-m, 0≤y0≤n-m。如果把f(x,y)和t(x,y)分别看作两个欧式空间里的矢量,那么积相关算法的度量值表达式正是这两个矢量在欧式空间里夹角的余弦。这是一个非常有用的性质,它的实际意义是,当环境光强发生变换时。应用积相关算法可以不受干扰。
2、跟踪稳定性的研究
所谓跟踪的稳定性是指匹配点的位置是否能够唯一确定或者在一个极小的范围内滑动。研究系统跟踪的稳定性具有十分重要的意义。
2.1图像预处理对跟踪稳定性的影响
在智能电视跟踪系统中实现积相关算法时,采取必要的图像预处理是非常必要和有益的。对模板和实时图像进行灰度均衡,使相关峰变得尖锐,从而提高跟踪性能;增大图像的对比度,也可以使相关峰变得尖锐,从而提高跟踪性能;对图像进行灰度最小化处理,使相关峰变得尖锐,提高跟踪性能。
2.2模板选取对跟踪稳定性的影响
积相关跟踪算法的模板需要人工在视场范围内进行锁定,这个初始的第一个模板对跟踪效果也是有影响的。为了得到良好的跟踪效果,相关峰应当尽量选择在图像比较复杂并且没有规律的区域内。
2.3奇偶场对跟踪稳定性的影响
系统采用的摄像头是按照PAL-D制式进行隔行扫描按照奇偶场产生图像的。对一幅静止的图像如果采用隔场匹配,那么一个模板始终与奇数场或者偶数场的实时图像进行匹配,此时跟踪点就始终是稳定的。对于动态的、连续的图像,应该在算法中加入一些处理措施,比如对模板进行刷新,否则可能造成跟踪不稳定。
3、简化的快速积相关图像匹配算法
基于前面给出的简化归一化积相关度量方法,为了进一步减少匹配算法匹配时间,提高匹配效率,且同时保证一定的匹配精度与匹配概率,设计了先粗后精的分层匹配控制策略。
3.1先粗后精的分层匹配控制策略
下图中给出了匹配控制策略的设计框图。
这种匹配控制策略首先是进行粗匹配,确定匹配点的大概位置或候选位置,接着进行精匹配,确定匹配点的精确位置或最佳位置。精匹配是在粗匹配的结果---候选匹配子图中完成的,因而搜索范围大大减少,提高了匹配速度。
对于本文算法,使用该方案需要注意以下三点。
(1) 粗匹配阶段,为了保证精匹配阶段的有效性,必须确保粗筛选后所保留的预选点包含有匹配点。
(2) 门限法实现起来难度较大,多数是靠大量实验及经验获取,且仅在特定的情况下可以采用。实际中,可以考虑采用3~5点筛选法,即直接取粗匹配阶段度量值最优的3~5个匹配点作为精匹配基准点。
(3) 图像的预处理是指对匹配图像的灰度数据进行一定的压缩或特征提取。在粗匹配阶段,可以考虑隔像素取值且隔像素搜索。而在精匹配阶段,像素值及搜索范围均要适当扩展。
3.2算法设计
结合简化的度量方法及前面给出的先粗后精的分层匹配控制方案,设计了简化的快速归一化积相关图像匹配算法。
(1) 粗匹配阶段
计算总的匹配搜索次数(如对于大小分别为m×m和n×n的基准图与实时图,则总的搜索次数为(m-n+1)×(m-n+1),进行循环递推匹配。匹配准则如下。
①每隔n1像素从基准图左上角开始扫描获取各个基准子图,并在实时图及所选的基准子图中隔n2个像素取其灭度值,组成用于相关匹配的维数较小的灰度矢量。
②利用简化的归一化积相关度量方法比较基准子图与实时图灰度矢量的相似性。
③采用递归比较的方法得到3~5个最优的匹配点,对应的基准子图作为候选配子图。
(2) 精匹配阶段
在粗匹配阶段得到的各个匹配点周围适当展开进行搜索匹配(若粗匹配阶段是隔n1像素进行搜索的,则在各匹配点周围展开的幅值为应在n1/2到n1的范围内)。
①利用简化的积相关度量方法逐一取候选子图,并在其扩展的范围内进行灰度匹配。
②所有度量值中,Rs(u,v)值最大的匹配位置便是最终的匹配结果。
4、提高跟踪实时性
经过大量的实验,采用快速的简化积相关算法进行匹配仿真实验可得出如下结论:
第一是积相关及本文简化快速积相关算法在智能电视跟踪系统中出项的稳定性干扰以及较小的几何畸变具有良好的抑制作用,且实时图像越大,其抑制能力越好。
第二是对未经选定的图像,可以考虑对匹配数据及搜索方案进行适当调整以获得满意的匹配效率。对于经过选定的图像,采用本文提出简化的积相关度量方法及先粗后精的分层匹配控制策略,有效地提高了匹配效率。
第三是减少匹配次数。在匹配时,进行一次粗匹配和二次精匹配。一次粗匹配时将步长设为2个像素,这样可以使计算量减少为原来的1/4。需要指出的是,采取上述的参数进行积相关处理时,一次粗匹配的过程中,可能会遗漏实际的最佳匹配点,但是最佳匹配区域不会被遗漏,也就是说,最佳匹配点可以在二次精匹配中找回。
总之,通过上述方法可以在有限的硬件条件下,有效地提高了系统跟踪的稳定和实时性。
参考文献:
[1] Franz Matthias O, Bernhard. Scene-based homing by image matching[J].Biol. Cybern,1998:191-202.
[2]刘扬,赵峰伟,等.景像匹配区选择方法研究[J].红外与激光工程, 2001, 30(3): 168-170.
[3]任仙怡,廖云涛,张桂林等.一种新的相关跟踪方法研究[J].中国图象图形学报(A版),2002,7(6):553~557.
[4]刘嘉.应用随机过程[M].北京:科学出版社,2002:12~13.
[5]彭架雄,雷达图像匹配制导技术,华中理工大学.
[6]孔丹,李介谷.亚像元精度的图像匹配技术[J].红外与激光工程,1999,27(1): 29-32.
[7]李尊民.电视图像自动跟踪的基本原理.国防工业出版社.1998.
[8]齐文宁.导弹上图象处理机的研制及边缘提取算法的研究.东南大学硕士学位论文.1997.
篇9
影像匹配实际上就是两幅（或者多幅）影像之间识别同名点，它是计算机视觉及数字摄影测量的核心问题。我们知道要匹配的点的同名像点肯定在其同名核线上。在进行最小二乘影像匹配之前，需要先进行粗匹配。然后在粗匹配的基础上用最小二乘法进行精匹配。我们这次讨论的是利用一维搜索的方法来进行粗匹配。这就是利用同名核线来进行同名像点的粗匹配。这相对于二维匹配来说速度更快。
1.1基于数字影像几何纠正法提取核线，利用共面条件来确定同名核线
我们知道，核线在航空摄影测量上是相互不平行的，它们相交于一点---核点。但是如果将影像上的核线投影（或者称为纠正）到一对“相对水平”-------平行于摄影基线的影像对上后，则核线相互平行。正是由于“水平”的像片具有这么一特性，我们就有可能在“水平”像片上建立规则的格网，它的行就是核线，核线上像元素（坐标为xt、yt）的灰度可由它对应的实际像片的像元素的坐标为x，y的灰度求的 ，即g（xt，yt）=g（x，y）。
根据前边的共线方程，同一摄站点摄取的水平像片与倾斜像片，其水平和倾斜像片的坐标之间的关系为：
(1-1-1)
(1-1-2)
上边的式子中a1,a2…,c3为左片的九个方向余弦，是该像片的外方位角素的函数，f为像片主距。显然在水平像片上，当yt为常数的时候，则为核线,将yt=c代入（1-1-1）和（1-1-2）式经整理，得：
（1-1-3）
其中：
e3=d3
若在“水平”像片上以等间隔获取一系列xt值 ，(k+1)*,(k+2)*…,可以得到一系列的像片坐标（x1，y1），（x2，y2），（x3，y3），…，这些点就位于倾斜像片p的核线上。
同样以yt=c 代入右边的共线方程：
(1-1-4)
(1-1-5)
其中， ， ，… 右方像片的对于单独像对像空间辅助坐标的角方位元素的函数，由此可得右片上的同名核线。
1.2核线的重排列（重新采样）
已知原始的影像的灰度序列，为求待定的平行于基线的“水平”影像。这就需要进行核线的灰度重采样。按照式（1-1-1）和（1-1-2）将“水平”像片上的坐标u，v反算到原始影像上的x，y。但是由于所求得的像点不一定恰好都落在原始影像采样的像元中心，这就必须进行灰度的内插-----重采样。通常所用到的是双线形插值法，取临近的四个像元点的灰度的数值进行待求点的灰度的计算。
图1-2-1双线形重采样
本公式中y1代P点到g1，g4连线的距离，x1代表P点到g3,g2连线的距离的大小
1.3数字影像匹配的基本算法
本论文讲述的相关系数法主要是对于一维影像相关的。
如图1-3-1所示是一维影像相关的目标区和搜索区（这里取m=n）。设g代表目标区内的点组的灰度值，g’代表搜索区内相应点组的灰度值，则每个点组共取得了n个点的灰度值的均值为
图1-3-1一维相关目标和搜索区域
，（i=0，1，2…n） （1-3-1）
两个点组的方差 ， 分别为：
， （1-3-2）
两个点组的协方差 为：
（1-3-3）
则两个点组的相关系数 为：
（0,1,… -n） （1-3-4）
在搜索区内沿核线寻找同名像点，每次移动一个像素，按照（1-3-4）来依次相关系数 ，取其中的最大的数值，其对应的相关窗口的中心像素就被认为是目标点的同名像点。
1.4用相关系数的抛物线拟合来提高相关精度
为了把同名点求的更为准确一些，可以把相关系数的最大点i点左右若干点（一般取左右个两个点）联系起来，从而将其函数的最大值k处的作为寻求的同名点的位置，结果会更好一些。
图1-4-1抛物线拟合
如图1-4-1所示设有相邻像元素系处的5个相关系数，用一个二次抛物线方程式来拟合，取用的抛物线方程，代表相应S位置处灰度的数值。
（1-4-1）
式中的参数A，B，C用间接平差方法求的。此时抛物线顶点k处的位置为：
（1-4-2）
由相关系数抛物线拟合可以使相关精度提高到0.15-0.2个子像素（当信噪比较高的时候），但是相关精度和信噪比近似成反比例关系。当信噪比比较小的时候，采用相关系数抛物线拟合也不能提高相关精度。
2仅考虑相对位移的一维最小二乘影像匹配
2.1一维最小二乘影像匹配原理
在本次仅仅考虑相对位移的一维最小二乘影像相关。在一维影像相关中是在倾斜影像相对应的水平影像坐标系中沿x轴方向寻求同名点，若在最小二乘算法中把搜索区像点移动的位移量作为一个几何参数引入，就可以直接解算像点的位移。
设有两个一维灰度函数 ， ，除了随机噪声 ， 外， 相对于 存在位移量 。如图4-3-1所示，则
（2-1-1）
则（2-1-2）
图 2-1-1 仅考虑相对位移的一维最小二乘影像相关
为了解求相对位移量，需要对（2-1-2）式子进行线性化：
（2-1-3）
对离散的数字影像，灰度函数的导数 可以由差分 代替，即
（2-1-4）
其中 采样间隔。令 ，则误差方程式可以写为；
（2-1-5）
为了解求 ，取一个窗口，对窗口内的每个像元素都可以列出一个误差方程式，按照的原则，则可以求得影像的相对位移的量 ：
（2-1-6）
因为解算都是线性化的结果得到的，因此，解算需要迭代进行。解得 后，对 进行重新采样，各迭代计算时，系数 以及常数项 均采用重新采样后的灰度值进行计算。
2.2计算最佳的匹配点位
我们知道，影像匹配的目的是为了寻求获得同名点。通常以待定的目标点建立一个目标窗口，窗口的中心点就是目标点。但是，在高精度影像相关中，必须考虑目标窗口的中心点是否是最佳的匹配点。根据最小二乘法影像匹配的精度理论可以知道：影像匹配中的精度取决于影像灰度的梯度 ， 。因此，可以用梯度的平方为权，在左方影像窗口中内对坐标做加权平均：
（2-2-1）
以它作为目标点坐标，它的同名点坐标可以由最小二乘法影像匹配所求得的几何变换参数求得；
（2-2-2）
随着以最小二乘法为基础的高精度数字影像匹配算法的发展，为了近一步提高起可靠性与精度，摄影测量工作者进而有提出了各种带有约束条件的最小二乘影像匹配的算法。例如，附带有共线条件的最小二乘相关以及与VLL法相结合的最小二乘影像匹配方法都得到了广泛的应用和研究。
3 最小二乘影像匹配的精度分析
篇10
键，在分布式环境下加速后缀数组的构造需要充分考虑到通信对算法性能的影响。串匹配问题是计算机科学中研究得最广泛的问题之一，在文字编辑与处理、图像处理、信息检索、分子生物学等领域都有很广泛的应用。本文解决的是分布式存储环境下的精确串匹配问题。在串匹配的许多实际应用中一个确定的文本常常被查询很多次(比如对非常长的基因序列的查询)。针对这种情况，Manber.U和E.W.Myers提出建立后缀数组(suffixarrays)〔1〕来提高查询的性能论文，而后缀数组最大的不足是它的构造时间过长。因此一直以来，如何快速有效地构造后缀数组成了提高基于后缀数组的串匹配算法性能的关
2USAA算法
假设N，M为文本串和模式串的长度，P为处理器数，算法设计思路如下:
(1)将长为N的文本串A均匀划分成互不重盛的P段，分布于处理器。~(P一l)中，且使相邻的文本段分布在相邻的处理器中，显然每个处理器中局部文本段的长度为〔N/P〕。
(2)除了处理器O外，其它每个处理器利用KMP算法计算分配到自己的文本串的头个字符与模式串，基金项目:国家自然科学基金重点项目(60533020)的匹配信息。如果存在匹配情况，就向相邻的前一个处理器发送最大匹配后缀长度Maxsuffixlen，否则就发送一个负数。每个处理器可独立地计算和发送该值，所以这一步的计算复杂度为O(M)，通信复杂度为O(1)。
(3)处理器1~(P-l)接收前一个处理器的信息。
(4)利用Manber.U和E.W.Myers在文献〔〔1〕中的算法各处理器并行地构造局部文本段的后缀数组。
(5)利用Manber.U和E.W.Myers在文献〔1〕中的算法各处理器并行地进行模式申的匹配。算法的计算复杂度为O((N/P(109109(N/P)))，通信复杂度为0(1)，大大降低了通信复杂度。
3实验结果及分析
我们在基于分布存储的32节点HPRX2600高性能机群系统上测试了上述算法，比较了USAA和目前理论值最好的MMsortlz〕算法之间的性能，其计算复杂度为，通信复杂度为。
图1给出了当M一16、P~2时，N的取值对算法执行时间的影响。从图中看出当时，由于N、P的取值成了影响算法复杂度的主项，因此在实际应用中USAA算法比MMsort算法表现要好。
图2给出了当N变大时，USAA算法和MMsort算法的通信时间比较。可以看出，随着文本串的规模变大，由于处理器间需要进行的通信量增加，MMsort算法的通信时间有明显的上升，而USAA算法的上升幅度要显著小于MMsort。
4结论
本文提出的USAA算法通过采取均匀的后缀分配方式来降低处理段间匹配时的通信消耗，在(N/P)M的情况下使算法在保持计算复杂度的同时大大降低了通信复杂度。通过实验结果可以看到，USAA算法很好地解决了在分布式存储环境下降低后级数组构造中的通信复杂度的问题。
参考文献
篇11
Components Based Graduation Design Managing Information System
YANG Zu-qiao1, LIU Gui-mei2
(1.College of Mathematics & Computer Science, HuangGang Normal University, Huanggang 438000, China; 2.Educational Technology Center, HuangGang Normal University，Huanggang 438000 , China)
Abstract: According to construction status of digital campus and the actual demands of graduation design management in our school, the basic modules of the projection management system is designed based on the Java Web Component technology. To achieve the functions of user registration, teacher questions, student topics, upload documents, download information, tutoring etc., and selected theme matching algorithm and system security are discussed mainly. Application the system can regulate the graduation designs selection and management process, improve work efficiency, economize the human resources and management costs, improve the management level of graduate de? sign.
Key words: Java Web component；management information system; graduate design；matching algorithm; Workflow
长期以来，毕业设计管理全过程基本上是手工或计算机辅助打印等方式完成，这种管理方式效率较低，容易出错，不能适应高校信息化的要求。因此需要一个针对此流程进行管理的系统，使得此过程更加方便，更加透明，更加高效，以节省更多的人力和不必要的工作。现在有许多高校已经设计并开发了毕业设计管理系统，方便了学生和教师，提高了管理效率，但是，部分系统还是没有从根本上改变毕业设计管理工作的总体流程和管理理念，存在信息孤立、交互方式单调等问题，也还有以下几个待改进的方面：1）过多关注于毕业设计的选题管理，对毕业设计的过程管理的重视不够；2）部分系统在可维护性、执行效率和可扩展性等方面还存在一些问题[1]；3）系统信息的安全性有待进一步提高[2]。
作为J2EE体系中的重要一环，JSP为创建高度动态的Web应用提供了一个独特的开发环境[3]。JSP设计目标是为了使动态页面编写更容易，更简单。到处可执行，JSP技术完全与平台无关的设计，包含它的动态网页和底层Server元件设计，加强元件功能，更容易建立动态网页。由于Java Web组件技术具有以下优点：
1）可重复使用跨平台的组件(如：JavaBean或Enterprise JavaBean组件)来执行更复杂的运算、数据处理；
2）组件可以跨平台使用；
3）组件是基于二进制代码编码，运行效率高，安全性好。
该文利用Java Web组件技术开发一个适合地方计算机类专业的毕业设计管理系统，实现毕业设计全过程的信息化管理。
1系统设计
软件体系结构的设计是整个软件开发过程中的关键点。B/S架构在客户端使用浏览器就可以访问到系统，大大简化了客户端载荷，减轻了系统维护与升级的成本和工作量，降低了用户的总体成本。系统总体任务是对学生和指导教师进行管理，在仔细分析管理流程和已有系统的特色基础上，本系统采用三层B/S架构，包括浏览器、Web服器和数据库服务器，如图1所示。
第二个问题是系统的安全性问题。本系统中采用随机登录验证码机制防止恶意注册和MD5加密机制保护用户的密码，可以实现对消息完整性的保护。这两种安全措施可以有效保证用户的密码安全，从而提高系统的安全性能。
实现高校毕业设计及论文管理网络化，为教师、学生以及学校管理都提供了极大便利，本系统有较强的针对性及实用性，能够解决本校论文管理存在一系列问题，在投入使用后，为教师、学生和管理人员提供了交流沟通的平台，实现管理人员、教师和学生的交流与互动，有效解决高校毕业设计中存在的一些问题，规范毕业设计流程，提高毕业设计的质量。系统在具体使用过程中，肯定还会出现这样那样一些问题，但随着新技术不断发展以及设计者对软件体系不断更新与完善，相信随着本系统日渐成熟，给学校的教学管理及发展带来方便。
[1]张敬普,娄鹏宇.工作流技术在毕业设计系统中的应用[J].数字技术与应用,2010 (8):35-35.
[2]曾小平,吴暾华.本科毕业设计管理系统的设计与实现[J].微型机与应用, 2011 ,30(18):83-85.
篇12
1 绪论
图像拼接技术有悠久的研究历史。早期用于航空遥感照片合成，在20世纪90年代Heung——Yeung Shum研究了同心圆拼图(柱面全景图)， 20世纪90年代中期，微软研究院的Szeliski教授提出基于运动的全景图像拼接模型，将8参数减低为4参数，2003年M.Brown发表了全自动的图像拼接算法的文章，使用捆绑调整技术，同时，鱼眼镜头拍摄图像生成球面全景图的绘制技术也得到广泛研究。
2 全景图像拼接技术的概述
2.1 全景图的模式分类
全景图根据图像投影方式的不同，存在几种全景图像：一种是球面全景图像，一种是多面体全景图像，还有一种是最常用的柱面全景图像。柱面全景处理起来比球面全景与多面体全景简单得多，因而应用面比较广。
2.2 全景图的生成流程
全景图的声称流程如下：图像的采集，图像的预处理，图像的变换，图像匹配，图像的平滑处理。
3 基于特征匹配的柱面全景图拼接技术的研究
3.1 原始图像的采集和几何校正
3.1.1 拍摄方法和原则
照相机拍摄时一般有三种情况：
1.旋转照相机拍摄
在这种情况下，放置照相机的三脚架在拍摄过程中一直在同一位置。照相机绕垂直轴旋转，每旋转一定的角度，拍摄一张照片。拍摄得到一系列照片中相邻两张必须有部分重叠。建议相邻图像之间重叠比例达到50%。重叠比例越大，拼接就越容易。
2.平移照相机拍摄
平移照相机指的是照相机在一个平行于成像平面的方向上平移。这种情况的缺点：拍摄的相片在一个平面上，拍摄的三维感觉不如旋转拍摄的。科技论文。
3.手持照相机拍摄
这种方法比较容易做到，手持照相机原地旋转拍摄。但是，拼接手持照相机拍摄的照片是很困难的，因为在拍摄过程中，照相机的运动非常复杂。可以增加重叠比例，使照相机旋转角度、平移减小，因而减小相邻图像之间的不连续程度。
用照相机拍摄全景图像，要取得较好的效果，必须注意以下几个方面的原则：
3.2 图像的变换
将一幅图像与另一幅图像匹配，常需要对一幅图像进行一系列的变换，这些变换可分为刚体变换、仿射变换、投影变换和非线性变换。
3.3 图像的匹配
3.3.1图像拼接算法的原理
一般情况下，经过柱面投影变换得到的具有重叠区域的柱面全景图中相邻的两幅待拼接图像间的重叠[2]范围大约在30%-50%之间。为了减少在特征区域提取时候的盲目性，我们可以先对灰度图像进行图像轮廓的提取，尽量的让选择的特征区域包含独特的信息，容易识别。
在图像匹配过程中，希望匹配点要准确，即关峰尖锐，定位精度高，因此在实验过程中用边缘检测的方法提取图像的边缘从而使图像的轮廓更为清晰，这样有利于提高匹配的精度和降低伪匹配的可能性。
3.3.2 基于特征区域的提取和匹配算法的实现
本文采用Moravec[3]算子进行特征区域的提取，窗口的大小可以采用55到2121。窗口越大，抗噪声能力越强，同时运算量也越大。
特征区域的匹配过程步骤如下：
1.将匹配图像重叠部分的像素灰度值和位置信息读入数据矩阵B，矩阵B读入的是匹配图像重叠部分的数据。
2.设置一个或者多个二维循环，通过对循环条件的设置或者分段设置循环，使搜索路径可以沿着预处理之后提取的轮廓边沿进行，将整个图像的重叠区域全部搜索一遍。科技论文。
3.沿着搜索的路径提取矩阵B的55，并且对矩阵内部的元素进行运算，分别计算该矩阵和单位矩阵的元素的均方差和灰度差的绝对值之和，分别把它们赋给两个变量。
4.将记录的当时搜索区域和单位矩阵的均方差和灰度差的绝对值之和跟之前的记录值作比较（记录值的初值的均方差为0，灰度值的绝对值之和为10），记录均方差的最大值和灰度值的绝对值之和的最小值，并且分别记录它们的坐标位置。科技论文。
5.搜索矩阵下移，再次重复步骤2和步骤3。
6.搜索结束，就得到了在矩阵B中令均方差最小且灰度值的绝对值之和最大的区域，记录该区域的位置和中心点的坐标位置。
在本课题的实现过程中，待拼接的图像已经经过了预处理和轮廓提取，所以在拼接的过程中，只需要将算子的中心沿着重叠部分图像的轮廓进行就可以了。
3.4图像的平滑处理
在拍摄柱面全景图时，周围环境和相机本身引起的最大问题就是相邻图像之间的光照变化较大，会出现带状痕，为了消除这种拼接区域带状痕影响，提出了一种直方图处理方法：
1.对于24位色图，首先将RGB图像转换成HIS类型图像，针对其I分量进行处理，等同于对灰度图像的灰度值进行处理。
2.将两幅图像的1/3公共部分作为重叠区域，注意要保证两个重叠区域像素数目一致。
3.分别计算左、右两边重叠区域的I分量或灰度图像灰度值的和sum1与sum2。
4.Differ=sum1/sum2，将图像2的每一个像素的I分量或者灰度图像2的每一个像素的值与参数Differ相乘加权。这样做的目的是将两幅图像的亮度均值统一，使得重叠区域在拼接时能够平滑过渡。
4 总结与展望
随着虚拟现实技术的不断发展，虚拟现实技术开始走向大众化，并应用于网上购物、网上旅游、网上教育和在线游戏等领域，虚拟现实系统将会成为未来世界一个不可缺少的重要组成部分。
【参考文献】
[1]王玉珍.基于特征区域的图像拼接技术.兰州大学硕士学位论文，2001：
3-10
[2]兰培真,马越,邱志雄,金一垂.不同视点重叠图像自动拼接算法.中国航海，2001，(2)：41-45
篇13
〔中图分类号〕TP391 〔文献标识码〕A 〔文章编号〕1008-0821（2016）02-0140-05
〔Abstract〕Text mining is an important aspect of data mining technology.According to the features of syntactic rules，the paper uses the text mining technology，and puts forward the design model based on the syntactic rules text knowledge mining.It analyzes the working principles of the data preparation，the syntactic rules knowledge structure，the text preprocessing，the text mining and the evaluation of mining results.Meanwhile it expounds the process of the construction of the syntax rules.At last，the paper identifies the model after some physical experiments.All in all，the design has certain research significance and application value to implement the intelligent of the text knowledge mining.
〔Key words〕text mining；syntactic rules；pattern matching；text pretreatment
随着信息技术、网络技术和各种数字化资源的建设，人们正面临着海量、快速增长的文本数据资源，传统的搜索引擎和查找技术已远远不能满足人们的需求。如何从大量原始的、未经处理的文本数据集合中挖掘出潜在未知的知识，满足人们获取各种信息和知识的需要，已成为一个重要的研究课题。
1 文本挖掘及句法规则概述
文本挖掘（Text Mining，TM）是在数据挖掘的基础上发展起来的一个分支，它以文本数据作为挖掘对象，主要任务是对隐藏于海量文本中没有检测到的非结构化知识进行提取的过程[1]。文本挖掘处理的对象是由多数据源组成的大量文本文档，包括新闻文章、研究论文、书籍期刊、报告会议、档案文献、Internet网络信息等半结构化或者高度非结构化的数据[2]。
汉语句子的结构非常自由，但其蕴含的基本规则相对稳定，句法规则是从汉语本身的属性特点出发，将构成句子的词或词组按一定的语法关系和句子结构，组合成能够表达完整意思的规则[3]，如词语的分类、句式结构的确定、句法描述体系和句法构成元素的建立等，它是对句子结构的抽象概括，通过组合和聚合关系造出无数合格的句子，是对句子分析的一种总结结果。
2 基于句法规则的文本知识挖掘技术的分析与设计
本文采用句法规则构造实现文本知识挖掘，主要设计如下：首先，根据知识的表示和用户的不同需求，构造出能全面准确表达文本内容的句法规则；其次，针对多源文本数据的特点和存在的问题进行预处理操作，为核心挖掘提供干净、准确、简洁的目标数据；再次，基于模式匹配算法，执行句法规则与目标文本数据的匹配，得出满足句法规则条件的挖掘结果；最后，通过一定的指标对挖掘结果进行评价，将满足用户需求的知识可视化表达到用户界面，供其选择和使用，具体过程如图1所示：
2.1 数据准备
数据准备主要是多源文本数据的获取，它通过多种数据源获取用于文本知识挖掘的数据，并存储在本地硬盘中[4]。文本数据的获取有多种途径，主要来源是Internet网络信息、研究成果、各种专题数据，以及其他文献资料。选择文本数据的数据源需要遵循以下原则：一是能为对象提供详细、准确数据；二是要考虑数据的可整合性、可挖掘性和现势性。文本知识的挖掘是一种基于句法规则的集中式挖掘，务必要求多源文本数据在结构上能够整合到同一平台框架下，并且保持一定的现势性，从而简化挖掘操作，提高知识获取的准确度。
2.2 句法规则构造
句法规则构造是根据知识的表示方法和汉语的句法组成结构，通过对表达语料库的的详细分析，将知识规则化，为核心挖掘提供模式匹配的基础条件。它主要分为3个层次：模板元素、句法规则、规则库。建立用于构造句法规则和约束文本分词、词性标注的模板元素，构造出用于模式匹配的句法规则，构建相应的规则树。从模板元素建立到句法规则构造，再到规则库的构建带有明显的层次性和结构性。
句法规则构造过程分为以下几步：一是收集并提炼出资料中的模板元素并建立相应的模板元素库；二是根据语法要求和句法结构将模板元素组合成句法规则；三是把句法规则存放入规则库。
2.2.1 句法规则的模板元素
模板元素是用户作为约束文本预处理结果的一种扩充词典，各个模板元素之间相互作用、相互影响构成了表达文本内容的句法规则。在这里借鉴汉语句法结构组成和本体概念的构建方法，将构成规则的每个〈词语〉抽象为词性，每种词性下面包含了能够反映该词性性质的元素，称为模板元素，规则中的每个模板元素都是该事件的参与者，一个句法规则看作是一个句子的语义的某种抽象化表示[5]，用模板元素表示该句子的语义，具体表示为：
从式（1）可以看出，多个模板元素根据汉语句子的语法要求和句法结构组合，即可构成能够表示特定文本知识的规则，我们称这种表示知识的规则为句法规则。因此，本文的句法规则是以模板元素为基本单位，根据人们表达习惯将多个模板元素按照语法关系组合成能够表达知识的句子。模板元素作为句法规则的组成，是一种类似本体的表达类型，可表示为属性（内容1，内容2，…，内容n），其中属性抽象为能够表达该领域知识的任意一种词性，如“词性：名词”，内容则表示该模板元素范围内包含的所有词的集合。
本文在采用中科院ICTCLAS分词系统汉语词性标记统计的基础上，提出了多个属性类别选项以描述模板元素，具体如表1所示：
然后，对各词类内容进行具体划分，如以谓词表为例：
2.2.2 句法规则构造
句法规则是模式匹配的逻辑核心，是知识表示内容的形式化概要，起到把要挖掘的知识内容类型化和结构化的作用。一条句法规则通常指出模板元素之间的关系，当句法规则与目标文本进行匹配时，必须合理约束各模板元素之间的语法关系和句法结构，严格按照每个模板元素在句法规则中的出现顺序对其进行匹配[4]。例如：北京是中国的首都，与天津市相邻，它的句法化表达为：〈主语〉+〈谓词〉+〈地名〉，〈连词〉+〈地名〉+〈谓词〉，它的句法规则为：n/v/ns/f/w2/cc/ns/v。
2.2.3 规则库
规则库是用户需求与目标文本之间进行问题求解的基础，用于描述相应领域内知识概要的产生式集合[6]，它包含了所有能反应和表达实体文本知识的方法和表现形式，能够为用户提供不同的抽象描述，形成不同的推理链，得出不同的挖掘结果。本文规则库采用规则树结构存储，如图2所示：
图2中，规则库作为树的根结点，共包含24个子结点，分别代表本文构造的24条句法规则。按照结点所在层次由高到低分别定义为一级、二级、三级和四级规则。该规则树构建的基本策略是：
（1）将所有的句法规则置于一个集合中，即规则库作为规则树的根结点；
（2）根据句法规则的组成结构对其进行划分，将相互独立并且不被包含的句法规则按编号顺序（从A到X）依次作为第二层的子结点，定义为一级规则；
（3）将其余句法规则根据包含与被包含的关系，依次划分到相应子结点下面，并分别定义为二级、三级和四级规则。
采用以上树结构存储句法规则，结构清晰，便于执行与目标文本的匹配，减少部分句法规则与目标文本之间不必要的匹配。
2.3 文本预处理
文本预处理是文本挖掘的基础，主要对目标对象的多源文本数据进行操作，将多数据源中获取的文本数据进行处理，为下一步的文本知识挖掘提供比较“满意”的目标数据。预处理主要包括文本快速整合、文本分词和词性标注、目标文本存储等，本文采用中科院的开源ICTCLAS分词系统对文本进行分词和词性标注。
文本预处理主要分为3个步骤：
（1）多源文本数据快速整合。将目标对象的多源文本数据集成到同一文本文档中。
（2）中文分词和词性标注。将经过整合的目标对象文本数据分词、标注词性。
（3）目标文本存储。将目标文本以段为单位编码并索引标记，建立两个二维表分开存储目标文本分词结果和目标文本词性标注结果。例如，对于预处理之后的目标文本：南京/n位于/v江苏省/ns中部/f，我们采用表3和表4所示存储：
2.4 文本知识挖掘
文本预处理完成以后，即可进行文本挖掘操作。文本知识挖掘是采用模式匹配算法，将规则库中的句法规则和目标文本执行精确匹配，得出符合规则条件的文本结果，并将其保存。它的主要任务是通过各种算法挖掘出用户需要的信息，主要包括特征提取、文本分类、文本聚类、文本提取、关联分析等[7]。本文采用KMP（Knuth-Morris-Pratt）算法进行模式匹配，基本思想是：当匹配过程中出现字符比较不相等时，模式串利用已经得到的“部分匹配”结果将模式串向右“滑动”，重新开始下一趟的匹配。例如对于主串“acabaabaabcac”，模式串“abaabcac”，利用KMP算法进行匹配的过程如下：
具体挖掘流程如图3：
基于句法规则的模式匹配的执行步骤为：
（1）读取句法规则库，输入目标文本词性和目标文本分词，启动基于句法规则的模式匹配。
（2）对规则库中的句法规则按照由高到低级别依次和所有编码的目标文本词性执行匹配。采用匹配算法遍历目标文本词性执行精确匹配，直到所有句法规则与目标文本词性执行完匹配，输出所有句法规则匹配结果。若无句法规则匹配结果，则匹配失败，结束整个模式匹配。
（3）将所有句法规则匹配结果转换为对应文本字符。根据二维表编码关联返回到对应目标文本分词中，根据索引标记将句法规则匹配结果转换成相对应的文本字符，该文本字符即为文本知识挖掘结果。
（4）输出所有基于句法规则的挖掘结果，匹配结束。
2.5 挖掘结果评价和知识表达
评价是指通过一定的评价标准对挖掘结果进行评估，把符合条件的结果返回到可视化模块。知识表达是将评价后的结果表达到用户界面，供用户选择使用，最终经过可视化表达的结果即为用户期待已久的知识。文本挖掘质量评估是对挖掘结果的整体衡量，若挖掘结果满足评价指标，则挖掘完成，否则重新挖掘。
3 实验结果验证
下面我们以郑州市地理信息文本知识的挖掘为例，利用VisualStudio 2010作为开发平台，介绍整个挖掘实现过程。
3.1 数据选取
打开数据源接口，通过Internet搜索引擎选取30篇郑州市地理信息数据，并保存到“F：＼郑州市地理信息文本数据”中。
3.2 文本预处理
对以上选取的文本数据进行预处理。在ICTCLAS分词系统上进行设置，通过选择文本、添加用户词典、分词并标注词性、结果保存，实现文本快速整合、分词和词性标注。对预处理后的目标文本设置过滤功能，将对应的目标文本分词和目标文本词性以段为单位编码同时用索引标记，分开存储。存储结果如下图所示：
3.3 文本知识挖掘
文本知识挖掘是在本文2.2句法规则构造的基础上进行，主要分为3个过程：匹配条件提交、匹配实现和结果转换。匹配条件提交指读取规则库、输入目标文本词性和目标文本分词，匹配实现通过执行模式匹配算法代码来实现，结果转换利用句法规则匹配结果的编码和索引标记将其转换为对应的目标文本分词字符，实现挖掘结果。挖掘结果分别如图6所示：
3.4 评价和表达
在完成文本知识挖掘以后，便对挖掘结果进行评价，并按相对优劣次序将地理位置文本知识可视化表达，并可导出为常用的EXCEL、WORD等文档格式，如图7所示：
通过以上实例可以看出，采用基于句法规则的文本挖掘方法，能够为用户在挖掘结果中得到比较满意的信息，从而较好的达到设计的目的。
4 结束语
随着文本数据资源的不断增长，仅仅通过简单的搜索引擎和数据筛选功能已经无法满足人们对信息和知识的需求，迫切需要高效率的信息分析方法。采用基于句法规则的文本知识挖掘设计方案，能够从句法规则设计入手，利用现有文本挖掘技术，从众多文本数据中快速地获取用户需求的知识，对实现文本知识智能化挖掘具有一定的借鉴意义。
参考文献
[1]Antonis Spinakis.Text Mining A Powerful Tool for Knowledge Management[EB/OL].http：∥/articles/TextMining.pdf，2010，（7）.
[2]张雯雯，许鑫.文本挖掘工具述评[J].图书情报工作，2012，（4）：26.
[3]杨晖.言语实践中的句法认知[J].吉林师范大学学报：人文社会科学版，2007，（4）：64-66.
[4]马绍龙.基于句法规则的地理位置文本知识挖掘[C].郑州：信息工程大学论文集，2014（4）：170-173.