匹配算法论文范文
前言：我们精心挑选了数篇优质匹配算法论文文章，供您阅读参考。期待这些文章能为您带来启发，助您在写作的道路上更上一层楼。
第1篇
在毕业论文管理工作不断加强的情况下，注重管理模式的更新和合理选用，提高匹配算法的针对性，才能真正提高高校教务管理水平。因此，对深度挖掘匹配算法在毕业论文管理中的应用有比较全面的了解，才能为高校教务管理工作提供可靠参考依据。
1 深度挖掘匹配算法的相关分析
根据深度挖掘匹配算法在毕业论文管理中的应用情况进行全面分析来看，其主要包括如下两个方面：
1.1 志愿自动匹配算法的相关分析
对学生和课题的选择关系进行合理分析可知，两者的最优、最大匹配，最好是根据学生的实际情况量身定做，才能真正实现课题与学生的最完美匹配。因此，教师提出相关题目时，需要对学生的情况、特性和要求等进行全面分析，才能在学生对课题的特性、关联性等有一定了解的情况下，提高课题与学生的匹配概率，最终让学生选定最合适的课题。在实践过程中，志愿自动匹配算法的合理运用，需要根据毕业论文的管理流程，从教师出题开始。一般情况下，教师应该先提出大题让学生自由选择，在匹配学生确定好以后将大题分成几个小题，从而将每个小题分配给合适的学生。在这种情况下，教师设定的课题需要从修读课程达到的分数、难度、所属类别等多个方面确定，并从教务管理系统中获取学生的成绩和选题积分点等，才能根据分数线来判定学生是否符合相关选题。其中，选题的难度在简单、一般、难、很难和非常难几个等级，对应的成绩是及格、良好、优秀、极好。在实际进行选题时，学生可以根据自己的情况选择三个题目作为志愿，以在系统完成匹配后，自定将题目下发给学生。在实践过程中，初始化志愿显示的是学生的第一志愿，在经过while、if、else、break、continue等流程后，系统会将题目和学生进行适当分类，以确保题目与学生的匹配最合理、最科学。由此可见，志愿自动匹配算法是优先对具有课题相关能力的学生进行匹配的，在学生人数低于匹配数量的情况下，可继续为积分点高、能力稍差的学生进行匹配，对于确保课程成绩与积分点的完美结合有着极大影响。
1.2 调剂学生算法的相关分析
在经过上述算法进行匹配后，根据学生的实际情况进行深层挖掘，可以实现课题与剩余学生的完美调剂。因此，对上述阶段中匹配失败的学生志愿所选的教师、课题类别、难度等因素进行深度挖掘，并将搜索结果作为匹配课题的依据，才能在缩小搜索范围的情况下，找到与剩余学生最合适的课题。如果出现相近课题较多的情况，则需要有学生、工作人员共同协商，以确定最终和最适合学生的课堂。在实践应用中，调剂学生算法的运用需要对需要调剂的学生进行合理分析，并通过if、else、return、while、continue、else等多个流程，才能真正匹配出最适合学生的课题。
2 深度挖掘匹配算法在毕业论文管理中的实际应用
根据深度挖掘匹配算法的实际应用来看，在毕业论文管理中学生可以了解到最适合自己的课题信息，教师可以根据学生的积分点和成绩等确定课题，从而避免选择某一课题的学生过多或过少的情况出现，对于提高第一志愿自动匹配成功率有着极大作用。因此，在实际应用中，注重教师、课题类别、难度的合理设定，确保它们的排序科学，将课堂与学生的匹配关系看作是二分图，并且，每个学生可以选择的课题有三个，系统可以根据学生的实际情况进行自动匹配，最终深度挖掘与学生志愿匹配的课题。例如：志愿自动匹配和调剂学生的总数都为102人，通过深度挖掘匹配算法匹配成功的人数分别为72人和90人，成功率达到了70%、88%。在不使用任何算法进行匹配的情况下，两者的成功率是52%左右。由此可见，在毕业论文管理系统中，深度挖掘匹配算法在科学应用，可以为教务管理工作提供可靠参考依据，对于提高毕业论文管理工作人员的工作效率有着重要影响。
3 结语
综上所述，在深度挖掘匹配算法不断推广的情况下，其在毕业论文管理中的实际应用受到了很多教务管理工作人员的青睐。因此，充分发挥深度挖掘匹配算法的作用，提高深度挖掘匹配算法在毕业论文管理中的应用效果，才能更好的满足学生的选题需求。
参考文献
[1]冯丽慧，冯立智.数据挖掘在毕业论文成绩管理中的应用研究[J].电脑知识与技术，2012，30：7150-7153.
[2]徐章韬.用信息技术深度挖掘课程内容――以数学学科为例[J].教育发展研究，2015，12：29-33.
[3]连伊娜.深度挖掘高校档案文化内涵，更好为教育事业发展服务[J].黑龙江史志，2013，11：104-105.
作者简介
刘冰洁（1983-），女，江西省南昌市人。工程硕士学位。现为江西交通职业技术学院副教授。研究方向为大数据、系统集成、智能化技术。
第2篇
【关键词】藏文分词 匹配算法 哈希表 词典机制
1 引言
藏文信息处理存在着分词的问题，而藏文分词是对藏文词性标注、藏语音合成、机器翻译、大型语料库建设和信息检索等藏文信息处理的基础。藏文分词的效果会对进一步研究的藏文词性标注、藏语音合成、机器翻译、大型语料库建设和信息检索等藏文信息处理软件的性能和效果产生影响。
为了提高分词的准确率，需要有一个足够大的词库，面对足够大的词库，对词库中的词语的搜索技术就显得十分重要，对词库中词语的搜索速度直接关系到分词系统的性能。词库目前主要是采用索引的机制来实现的，一般用到的索引结构的包括线性索引、倒排表、Trie树、二叉树等。线性索引、倒排表都是静态的索引结构，不利于插入、删除等操作。
2 分词
2.1 词典机制算法
本系统采用的是基于Hash索引的分词词典。分词词典机制可以看作包含三个部分：首字Hash表、词索引表、词典正文。词典正文是以词为单位txt文件，匹配过程是一个全词匹配的过程。首先，通过首字Hash表确定该词在词典中的大概位置，然后根据词索引表进行定位，进而找到在词典正文中的具置。该系统是采用Myeclipse10平台，使用Java语言进行实现的，直接调用Java里的hashmap创建函数，找到该词之后，然后进行字符串匹配。
2.2 基于匹配算法分词
主流的分词方法有三种：分别为基于语言学规则的方法、基于大规模语料库的机器学习方法、基于规则与统计相结合的方法，鉴于目前藏文方面还没有超大型的句子语料库。该系统便采用了基于语言学规则的根据词典进行匹配的方法对藏文进行分词。
根据匹配的方向不同，分为正向和逆向两种匹配算法。本系统采用的是正逆向匹配算法相结合的减字匹配法对藏文进行分词的，因为藏文在每个字的结束时，都会以“”作为分界；每个句子会以“”或者“” 作为分界。因此，对藏文进行分词的减字算法首先以藏文的字符“”或者“”切分出句子，如此一来，原文就被分为相应的若干个句子了。接下来，再对每一个句子进行词典的匹配，如果没有匹配成功就根据藏文字符中“”从句末尾减去一个字符，然后再次进行匹配，直到匹配成功为止。对每个句子重复这些流程，直到每个句子全部分解为词为止。逆向最大匹配是从句子的末尾选择计算最大词的长度，从后往前匹配、切分，其基本原理是和正向最大匹配的原理是相同的。
为了提高切分的精度，该系统使用的是正向最大匹配和逆向最大匹配相结合的方法进行分词，先分别采用两种方法分词，然后根据概率比较两种分词结果，选择概率较大的那种匹配算法作为分词结果。
本系统的逆向最大匹配和正向最大匹配均是采用减字匹配算法，减字算法实现简单，切分效果也比较理想，流程如图1所示。
正向最大匹配（MM） 对于文本中的字串 ABCD，ABCD？W，若ABC∈W，并且AB∈W，然后再判别CD是否属于W，若是，则就切分为AB/CD，如果不是，则切分为AB/C/D。其中W 为分词的词典。逆向最大匹配对于文本中的字串 ABCD，ABCD？W，BCD？W，CD∈W，并且AB∈W，其中W为分词的词典，那么就取切分 AB/CD，根据藏文词组最长的为6个字符组成的，所以进行匹配算法的时候，初始化藏文最大字符串长度为6，流程图如图2所示。而逆向最大匹配算法是从句子的末尾开始进行匹配，其核心算法与正向最大匹配算法相同，只不过开始匹配的方向不同而已。
无论是正向匹配（MM）算法还是逆向匹配（RMM）算法都会产生大量的歧义字段。我们很容易举出这样的例子，如：（五十六个民族心连心）这一句藏语，采用正向匹配算法分词的结果为：，采用逆向匹配算法的分词结果为：，在采用逆向匹配的时候，将会被划分为，而（五十六）实际是一个词，不该划分，诸如此类的藏文句子还有很多，例如 等，无论使用正向最大匹配算法或者使用逆向最大匹配算法都会产生歧义，这种歧义称为组合歧义。为了减少这种歧义的影响，本系统使用两种分词方法相结合的方式。首先分别使用两种算法进行分词，然后通过统计的方法消除部分歧义。具体实现为：设正向最大匹配算法所切分的n个词分别为，则这个句子切分的频率则为；设逆向最大匹配算法所切分的n个词分别为，则这个句子切分的频率则为。如果，则选择正向最大匹配算法所切分的结果，反之，则选择逆向最大匹配算法所切分的结果。
3 结果和分析
结合26个大小不同的实验文本，对基于哈希表索引和匹配算法的分词系统的准确率进行了分析，准确率如图3所示。结果显示，该分词系统的准确率在92%以上。由此可得基于哈希表索引和匹配算法的分词系统在准确率上有不错的效果。
参考文献
[1]华却才让.基于树到串藏语机器翻译若干关键技术研究[D].陕西师范大学，2014.
[2]石方夏，邱瑞，张|，任帅.藏文信息隐藏技术综述[J].物联网技术，2014，12：28-32.
[3]王思力，张华平，王斌.双数组Trie树算法优化及其应用研究[J].中文信息学报，2006，05：24-30.
[4]陈硕，桂腾叶，周张颖等.信息检索在论文写作和项目申报中的应用[J].科技展望，2015，13：274-275.
[5]黄昌宁，赵海.中文分词十年回顾[J]. 中文信息学报，2007，03：8-19.
[6]奉国和，郑伟.国内中文自动分词技术研究综述[J].图书情报工作，2011，02：41-45.
[7]贺艳艳.基于词表结构的中文分词算法研究[D].中国地质大学（北京），2007.
[8]戴上静，石春，吴刚.中文分词中的正向增字最大匹配算法研究[J].微型机与应用，2014，17：15-18.
[9]刘遥峰，王志良，王传经.中文分词和词性标注模型[J].计算机工程，2010，04：17-19.
作者简介
陈硕（1995-），男，自治区拉萨市人。本科在读，主研领域为自然语言处理，数学建模及其应用。
周欢欢（1994-），女，湖南省衡阳市人。本科在读，研究方向为数学建模及其应用、交通运输规划与管理。
通讯作者简介
赵栋材（1976-），男，现为大学藏文信息技术研究中心副教授。主要研究方向为藏文信息处理。
作者单位
第3篇
关键词：Rete算法，智能防火墙，规则，快速，匹配
Rete算法是一个快速的模式匹配算法，它通过形成一个Rete网络进行模式匹配，利用基于规则的系统的两个特征，即时间冗余性（Temporalredundancy）和结构相似性（structural similarity），提高系统模式匹配效率。
一、模式匹配的基本概念
1、可满足规则：一个规则称为可满足的，若规则的每一模式均能在当前工作存储器中找到可匹配的事实，且模式之间的同一变量能取得统一的约束值。形式化地说，规则
if P1,P2,…Pmthen A1,A2,…An
称为可满足的，若存在一个通代σ，使得对每一个模式Pi，在工作存储器中有一个元素Wi满足
Piσ=Wii=1,2,3 …m
这里，σ作用在某个模式的结果称为模式实例，σ作用在整个规则的结果称为规则实例。在专家系统中，可满足的规则称为标志规则。
2、冲突集：由全体规则实例构成的集合称为冲突集，也称上程表。免费论文参考网。
3、模式匹配算法的任务是：给定规则库，根据工作存储器的当前状态，通过与规则模式的匹配，把可满足规则送入冲突集，把不可满足的规则从冲突集中删去。
二、Rete算法的依据和基本思想
Rete算法快速匹配的重要依据是：
1、时间冗余性。免费论文参考网。工作存储器中的内容在推理过程中的变化是缓慢的，即在每个执行周期中，增删的事实只占很小的比例，因此，受工作存储器变化而影响的规则也只占很小的比例。由产生式系统的折射性，只要在每个执行周期中记住哪些事实是已经匹配的，需要考虑的就仅仅是修改的事实对匹配过程的影响。
2、结构相似性。许多规则常常包含类似的模式和模式组。
Rete算法的基本思想是：保存过去匹配过程中留下的全部信息，以空间代价来换取产生式系统的执行效率。
三、Rete匹配网络结构与过程
Rete算法的核心是建立Rete匹配网络结构，其由模式网络和连接网络两部分构成。其中，模式网络记录每一模式各域的测试条件，每一测试条件对应于网络的一个域结点，每一模式的所有域结点依次连起来，构成模式网络的一条匹配链。
Rete网络匹配过程由模式网络上的模式匹配和连接网络上的部分匹配构成。在模式网络的机器内部表示中，我们把共享一个父结点的所有结点表示成一条共享链。同时，把每一模式匹配链中的结点表示成一条下拉链，于是，每一结点由共享链和下拉链指向其后继结点，模式网络就是一棵可以使用典型遍历算法进行测试的二叉树。
四、智能防火墙Rete算法设计
Rete快速匹配算法，函数Rete设计为:取IP地址、端口号各部分折叠、异或运算后，以Rete长度取模。免费论文参考网。算法如下(无关或部分无关称为集合A，相关、包含相等和相等的称为集合B):
1、Addr=sa+da sa:源地址 da:目的地址
2、Port=sp+dp sp:源端口号 dp:目的端口号
int Rete(long addr, int port)
{int addrxor,key；\地址折叠异或
addrxor=(addr&～(～0﹤﹤16))∧((addr﹥﹥16)&～(～0﹤﹤16))；
key=addrxor∧port； \与端口异或
return(key % max)； }\max为Rete表长度
防火墙初始化时，首先从规则集A用该散列函数构造Rete表R为
Void Initialization(RULE-SET A){
FOR(r∈A)DO{ \r为每条规则
idx=Rete(r.addr,r.port)；
R[idx]=&r； \R代表规则集合A
}}
因为Rete表的长度有限，但是如果设计太大会浪费存储空间，也降低了查找速度，所以免不了会出现冲突。解决冲突的方法是:如果两条规则经过散列后落到同一位置，则把这两条规则按照插入顺序组成一个链表结构。主要算法如下:
if(R[Rete(r.addr,r.port)]=NULL)\R为Rete表,r为规则
R[Rete(r.addr,r.port)]=&r；\没有冲突，则插入Rete表
Else{J=R[Rete(r.addr,r.port)]；\冲突解决方法
while (j->next!=NULL) {j=j->next；} \插入链表末尾
j->next=&r;}
数据包匹配流程：当防火墙收到一个数据包以后，用算法Match查找规则集(A和B)。
Match(IP-Packet p) { \p为数据包
Int idx=Rete(p.addr,p.port) ； \首先用Rete算法查找A类规则
IF (R[idx].addr≧p.addr&& R[idx].port=p.port) \找到匹配规则
return R[idx] ；
Else {int idex I =halfquery(p.addr) ； \利用折半查找索引表
J=L[indexl] ； \L代表规则集合B
While(j!=NULL){\顺序匹配找到的规则链
IF (Matchrule(p)) return j； \ Matchrule为规则匹配函数
Else j=j->next；
}}
Return(Norulematch)；
}
参考文献：
[1] 闫丽萍，潘正运. RETE算法的改进与实现.微计算机信息，2006 (36）
[2] 庞伟正，金瑞琪，王成武. 一种规则引擎的实现方法.哈尔滨工程大学学报，2005(03)
[3] 江建国，张景中. 基于Rete算法的几何自动推理系统. 四川大学学报（工程科学版）， 2006(03)
第4篇
关键词：入侵检测；免疫原理；r连续位匹配；检测集生成
中图分类号：TP18文献标识码：A文章编号：1009-3044(2012)26-6348-03
Network Intrusion Detection Based on Immune Theory
WU Xiang1, HAN Liang2
(1.Naval Headquarters, Beijing 100841, China; 2.The East China Sea Fleet of Navy, Ningbo 315122, China)
Abstract: After analysis of the immune algorithm characteristics, the metaphor mechanism which is associated with the intrusion detection is extracted and studied in-depth. And then on the basis of artificial immune system, intrusion Detection system based on immune mechanism is built and the definition of system self and system non-self, immune matching rules set, and also the generation and life cycle of the immune detector are explained. Finally, the model is validated by the simulation experiments. The establishment of the immune intrusion detection system and the simulation work is the cornerstone of this research.
Key words: intrusion detection; immune theory; r contiguous bits matching; detector set generation
人体的免疫系统功能是通过大量不同类型的细胞之间的相互作用实现的[1-2]。在这些不同类型的细胞主要作用是区分“自体”和“非自体”。“自体”是指人体自身的细胞，而“非自体”是指病原体、毒性有机物和内源的突变细胞或衰老细胞。淋巴细胞能对“非自体”成分产生应答，以消除它们对机体的危害；但对“自体”成分，则不产生应答，以保持内环境动态稳定，维持机体健康。
可以看出入侵检测系统和免疫系统具有一定程度的相似性。对于一个入侵检测系统，特别是网络入侵检测系统，免疫系统的组成、结构、特征、免疫机理、算法等都为入侵检测系统设计有着重要的借鉴意义。它们要解决的问题都可以被描述为：识别“自体”和“非自体”，并消除“非自体”。
1自体和非自体的定义
计算机安全的免疫系统保护的是计算机系统的数据文件，所以将“自体”定义为计算机中合法的数据，这些数据包括合法用户、授权活动、原始源代码、未被欺诈的数据等；将“非自体”定义为其它一切非法数据，这些数据包括自身遭受非法篡改的数据、病毒感染的数据以及外来数据等。
2免疫匹配规则
在计算机中，所有的数据都是以二进制来表示的，这就表明在进行仿真的过程中，使用免疫匹配规则的对象都应该是针对二进制字符串的，因此需要采用二进制的匹配算法。采用何种二进制字符串的匹配算法，这是一个十分关键的问题，因为只有采用了合适的匹配算法，才能有效的构造免疫检测器集[4]。目前有很多的近似匹配算法，如r连续位的匹配算法、海明距离匹配算法等。r连续位匹配规则能更好地反映抗体绑定的真实提取，即能更真实地反映检测器字符串与被检测字符串的匹配情况，所以它比海明匹配规则更常用，因此文章采用r连续位的匹配算法。
r连续位的匹配规则可以描述如下：对于任意的两个字符串x，y，如果两个字符串x，y在相应位置上至少连续r位相同，那么这两个字符串是r连续位匹配的，即Match(x,y)|r=true。例如，如果设定r=5，字符串x=“10111010”和字符串y=“11011010”，由于它们在相应位置4-8位上都为“11010”，因此这两个字符串是匹配的。
在训练阶段，首先随机生成候选检测器集合，然后让候选检测器与自体集进行匹配，这个过程也叫阴性选择过程。在匹配的过程中，那些与与自体集相匹配的候选检测器就被丢弃，而不与自体集匹配的候选检测器则作为成熟检测器，存储于检测器集合中。
[1] Oscar A,Fabio A G, Fernando N,et al.Search and Optimization：A Solution Concept for Artificial Immune Networks: A Coevo? lutionary Perspective [C].Proceedings of 6th international conference on Artificial Immune systems，Brazil，2007：26-29.
[2] Hofmeyr, S, Forrest, S. Immunity by Design: An Artificial Immune System[C]//Proceedings of the 1999 Genetic and Evolution? ary Computation Conference,1999:1289-1296.
[3]杨进,刘晓洁,李涛,等.人工免疫中匹配算法研究[J].四川大学学报:工程科学版，2008,40(3):126-131.
[4]马莉.基于免疫原理的网络入侵检测器生成算法的研究[D].南京:南京理工大学硕士论文, 2006.
[5]卿斯汉,蒋建春,马恒太,等.入侵检测技术研究综述[J].通信学报,2004,25(7):19-29.
[6]焦李成,杜海峰,刘芳,等.免疫优化计算、学习与识别[M].北京:科学出版社, 2006.
[7] Dasgupta D，Gonzalez F.An Immunity-Based Technique to Characterize Intrusions in, Computer Networks [J].Special Issue on Artificial Immune Systems of the Journal IEEE Transactions on Evolutionary Comput- ation.2002，6(3)：281-291.
第5篇
关键词：入侵检测；KMP算法；BM算法；RK算法；AC算法；AC－BM算法
中图分类号：TP301文献标识码：B
文章编号：1004 373X(2009)02 063 05
Application of Pattern Matching Algorithm in Intrusion Detection Technique
RAN Zhanjun1,YAO Quanzhu2,WANG Xiaofeng1,ZOU Youjiao1
(1.Xi′an University of Technology,Xi′an,710054,China;2.College of Computer Science and Engineering,Xi′an Unversity of Technology,Xi′an,710048,China)
Abstract：Relying solely on traditional passive defense technology has been unable to meet today′s network security needs,IDS based on pattern－matching is becoming a hotspot of research and application,the efficiency of pattern matching determines the performance of this kind of IDS.A survey of the intrusion detection system classic pattern matching algorithm is given in this paper,including single pattern matching algorithm:KMP algorithm,BM algorithm,RK algorithm and multi－pattern matching algorithm －AC algorithm,AC－BM algorithm.Meanwhile,the efficiency of various algorithms is summarized.Through analysis of algorithms,future research directions of this kind of algorithm are advanced.
Keywords：intrusion detection;KMP algorithm;BM algorithm;RK algorithm;AC algorithm;AC－BM algorithm
0 引 言
随着网络技术的发展，各种基于网络的应用层出不穷。面对日益突出的网络安全问题，仅靠传统的被动防御已经不能满足要求，能够主动检测并预防的入侵检测系统应运而生。
根据采用的分析方法，入侵检测分为误用检测和异常检测。误用检测是指：根据己知的攻击方法，预先定义入侵特征，通过判断这此特征是否出现来完成检测任务。异常检测是指：根据用户的行为或资源的使用状况的正常程度来判断是否属于入侵。由于异常检测的误检率和漏检率高，因此目前大多数入侵检测系统产品均主要采用误用检测的方法。误用检测中使用的检测技术主要有: 模式匹配、专家系统、状态转移等，其中模式匹配原理简单，可扩展性好，而且最为常用。据统计，现在大约95%的入侵检测都是特征匹配的入侵检测。
由此可见，模式匹配算法性能的好坏直接影响到入侵检测系统的效率。随着网络传输速度的大幅度提高，入侵检测系统需要处理的数据量越来越大，如果模式匹配算法来不及处理这些实时的大量的数据包，必然会丢弃部分数据包，而这些被丢弃的数据包中很可能就包含有入侵信息，从而造成漏报。在此介绍几种著名的用于入侵检测的模式匹配算法，包括单模式匹配算法和多模式匹配算法，通过对它们进行剖析和实际测试，提出入侵检测系统中模式匹配算法的选择策略和未来的研究方向。
1 单模式匹配算法
1.1 相关定义
模式匹配：是指在给定长度为n的目标串T=T1T2…Tn中查找长度为m的模式串P=P1P2…Pm的首次出现或多次出现的过程。这里Ti(1≤i≤n)，
Pj(1≤j≤m)∈∑(字符集)，若P在T中出现1次或多次，则称匹配成功，否则称匹配失败。
单模式匹配算法：在目标串中1次只能对1个模式串进行匹配的算法。
多模式匹配算法：在目标串中可同时对多个模式串进行匹配的算法。
最简单的模式匹配算法是Brute－Force算法(BF算法)。在BF算法的目标串和模式串的字符比较中，只要有1个字符不相等，而不管前面已有多少个字符相等，就需要把目标串T回退，下次比较时目标串T只后移1个字符。虽然算法简单，但效率低下，不适合用于入侵检测系统中，不做重点介绍。
高效的模式匹配算法都是设法增大不匹配时目标串T或模式串P之间的偏移量，以减少总的比较次数。下面介绍3种经典的快速单模式匹配算法。
1.2 KMP算法
1970年，S.A.Cook从理论上证明了一维模式匹配问题可以在O(m+n)时间内解决［1］。D.E.Knuth，V.R.Pratt和T.H.Morris 在BF算法的基础上提出了一种快速模式匹配算法，称为KMP算法［1］，该算法消除了BF算法的目标串指针在相当多个字符比较相等后，只要有1个字符比较不等便需要回溯的缺点，使算法的效率得到了大幅度提高，时间复杂度达到最理想的O(m+n)，空间复杂度是O(m)。
KMP算法的基本思想是：若某趟匹配过程中Ti和Pj不匹配，而前j-1个字符已经匹配。此时只需右移模式串P，目标串T不动，即指针i不回溯，让Pk与Ti继续比较。移动后重新开始比较的位置k仅与模式串P有关，而与目标串T无关，因此k可以通过下面的next函数事先确定。
定义next［j］函数为：
next［j］=max{k|1＜k＜j且 P1P2…Pk=
Pj-kPj-k+2…Pj-1} ，集合非空
0，其他情况
-1(标记)，j=0时
1.3 BM算法
相对于BF算法，KMP算法虽然消除了主串指针的回溯，在不匹配时能使模式串右滑若干位，但由上述next函数可知：右滑的最大距离不会超过1趟匹配操作所进了的比较次数j，原因在于KMP算法的匹配操作是从左到右进行的。受到KMP算法的启发，R.S.Boyer和J.S.Moore提出一种新的快速字符串匹配算法－BM算法［1－3］。
BM算法基本思想是：开始时将目标串T与模式串P左对齐，自右至左逐个字符进行比较(即首先比较Pm与Tm)；当某趟比较时Ti与模式串的对应字符不匹配，则把模式串右滑d(x)一段距离，执行由Pm与Ti+d(x)起始的自右至左的匹配检查。BM算法采用以下两条规则计算模式串右移的距离：
(3) g是转移函数，该函数定义如下：g(s,a)：从当前状态s开始，沿着边上标签为a的路径所到的状态。假如(u,v )边上的标签为a，那么g ( u,a ) =v；如果根节点上出来的边上的标签没有a，则g(0,a) =0，即如果没有匹配的字符出现，自动机停留在初态；
(4) f(不匹配时自动机的状态转移)也是转移函数，该函数定义如下：
f(s)：当w是L(s)最长真后缀并且w是某个模式的前缀，那么f(s)就是以w为标签的那个节点；
(5) q0∈Q是初态(根节点，标识符为0)；
(6) FQ，是终态集(以模式为标签的节点集)。
这样，在目标串中查找模式的过程转化成在模式树中的查找过程。查找一个串T时从模式树的根节点开始，沿着以T中字符为标签的路径往下走：若自动机能够抵达终态v，则说明T中存在模式L (v)；否则不存在模式。
AC算法模式匹配的时间复杂度是O(n)，并且与模式集中模式串的个数和每个模式串的长度无关。无论模式串P是否出现在目标串T中，T中的每个字符都必须输入状态机中，所以无论是最好情况还是最坏情况，AC算法模式匹配的时间复杂度都是O(n)，包括预处理时间在内，AC算法总时间复杂度是O(M+n)，其中M为所有模式串的长度总和。
2.3 AC－BM算法
对多模式串的匹配而言，虽然AC算法比BM算法高效得多，但AC算法必须逐一查看目标串的每个字符，即必须按顺序输入，不能实现跳跃，而BM算法则能够利用“右滑”跳过目标串中的大段字符，从而提高搜索速度。如果将BM算法的这种启发式搜索技术应用到AC算法中，则可大大提高多模式匹配算法的效率。许多人据此给出了各种改进的算法。Commentz－Walter最先将BM算法和AC算法结合在一起给出了Commentz－Walter算法；Baeza－Yates结合BMP算法和AC算法也给出了多模式匹配改进算法。
AC－BM算法［5］是Jang－Jong在1993年结合AC算法的有限自动机和BM算法的连续跳跃思想提出来的新算法，利用劣势移动表和优势跳转表来实现跳跃式地并行搜索，算法的时间复杂度为O(mn)。
该算法的思想是：首先把要查找的多个模式构成一个关键字树，把相同的前缀作为树的根节点。模式树从目标串的右端向左移动，一旦模式树确定在适当的位置，字符比较从左向右开始进行。模式树移动时同时使用坏字符移动和好前缀移动。坏字符移动的策略为:如果出现不匹配的情况，移动模式树，使得树中其他模式的能与当前目标串正在比较的字符相匹配的那个字符移动到与当前目标串正在比较的字符的相同位置上，如果在当前的深度上，目标字符没有出现在任何模式中，则模式树的偏移量为树中最短模式的长度。好前缀移动的移动策略为：将模式树移动到一个已被发现是另一个模式子串完全前缀的下一个位置，或者移动到作为树中另一个模式后缀能够正确匹配目标串的某个前缀的下一个位置。在模式树的移动过程中，必须确保模式树的偏移量不能大于树中最短的模式长度。
2.4 AC，AC－BM算法改进情况简介
文献［10］中卢汪节等人针对AC算法在构造状态机时空间冗余较大的情况，对状态机各结点进行压缩存储，使空间性能和时间性能都有提高；文献［11］中万国根等人对AC－BM算法的改进借鉴了BMH算法的思想，取消了原算法的好前缀跳转，优化了坏字符跳转，并修改了skip的计算方法，对大字符集的情况在平均情况下具有更优的性能；文献［12］对AC－BM的改进则是通过预处理思想实现的，在进行AC-BM匹配之前首先扫描首和(或)尾字符，确定其位置，再到相应位置进行匹配，相当于把目标串按模式串首、尾字符分成数段，每段进行比较，段间不含首字符的就直接跳过，不用比较，从而提高效率。
3 算法的实际执行效率
上述这些算法究竟哪种算法具有最好的执行效率呢?能不能仅通过时间复杂度来进行衡量呢？时间复杂度仅是一个度量的范围，表示受几个参数的影响，并不代表一个具体的值，还需要在具体的环境中进行测试。
文献［13］测试了包括上述算法在内的多种单模式和多模式匹配算法的性能。测试平台为：硬件：CPU Intel Xeon 3.46 GHz X 2，内存2 GB DDR，硬盘200 GB SCSI；软件：Windows 2003 Server,Intel IXA SDK4.1。单模式匹配测试的规则集，使用随机生成的8，16，32，48，128位具有代表意义的规则，可以对应端口、IP地址，MAC地址、IPv6地址等，对多模式匹配测试采用Snort系统2.4.3规则集。
单模式匹配算法主要测试模式长度与匹配时间、占用空间及预处理时间的变化关系。测试结果表明：各算法的测试指标在规则长度增长的情况下均呈递增趋势，但BM算法的增长速度最为缓慢，在不太在意存储空间的情况下，BM可以作为优先考虑的算法，同时对IPV6地址也更为合适。
多模式匹配算法的测试项目为规则数与单位匹配时间、占用储存单元、单位预处理时间的变化关系。测试结果表明AC－BM算法在上述3项测试中取得了很好的性能平衡。这也是新
版的Snort系统中选用AC－BM算法的重要原因。
4 入侵检测系统中模式匹配算法的研究方向
常用的模式匹配算法所采用的思想主要有基于字符比较、基于自动机、基于hash查找、基于位逻辑运算和基于Tries树型机构搜索。鉴于目前网络的实际状况，多模式匹配算法更加适合于基于模式匹配的入侵检测系统。这里认为应该从下面3个方面着手：一是继续研究和改进精确的模式匹配，将快速的单模式匹配算法和多模式匹配算法相结合，充分借鉴同类算法的先进思想，如：引入Hash函数、引入自动机、对字符串分块等来不断提高多模式匹配算法的性能；二是尝试采用模糊匹配的策略，国外对此已经开始进行相应的研究；三是对网络数据包和入侵特征进行研究，总结出这两类字符串特点，有针对性地对这两类字符串的匹配问题进行研究。
5 结 语
网络带宽的不断增加、日益严重的网络安全状况要求必须尽快提高网络入侵检测系统的性能。虽然入侵检测系统可以采用很多技术，并且这些技术也在不断的研究和发展中，但是目前主流的实用的入侵检测技术仍然是基于模式匹配的。因此如何提高模式匹配的效率成为研究入侵检测系统的一个关键所在。在此对已有的经典模式匹配算法进行了系统综述，并对入侵检测系统中模式匹配算法的未来研究方向给出了观点。
参考文献
［1］庞善臣,王淑栋,蒋昌俊.BM串匹配的一个改进算法［J］.计算机应用,2004,12(12):11－13.
［2］Boyer R S,Moore J S.A Fast String Searching Algorithm ［J］.Communications of ACM,1977,20(10):762－772.
［3］张立航,潘正运,刘海峰.基于改进的KR算法在网闸中的实现［J］.微计算机信息(管控一体化),2008(24):137－138.
［4］Johnson T,Newman－Wolfe R E.A Comparison of Fast and Low Overhead Distributed Priority Locks ［J］.Journal of Parallel and Distributed Computing,1996,32(1):74－89.
［5］Jason C C,Staniford S,McAlemey J.Towards Faster String for Intrusion Detection or Exceeding the Speed of Snort ［EB/OL］./sotfware/acbm/speed－of－snort－03－16－2001.padf,2003.
［6］黄占友,刘悦.对KMP串匹配算法的改进［A］.第四次全国便携计算机学术交流会论文集［C］.北京:科学出版社,1997.
［7］涛,方滨兴,胡铭曾.对BM串匹配算法的一个改进［J］.计算机应用,2003,23(3):6－8.
［8］张国平,徐汶东.字符串模式匹配算法的改进［J］.计算机工程与设计,2007,28(20):4 881－4 884.
［9］蔡晓妍,戴冠中,杨黎斌.一种快速的单模式匹配算法［J］.计算机应用研究,2008,25(1):45－46,81.
［10］卢汪节,鞠时光.入侵检测系统中一种改进的AC算法［J］.计算机工程与应用,2006(15):146－148.
［11］万国根,秦志光.改进的AC－BM字符串匹配算法［J］.电子科技大学学报,2006,35(4):531－533.
［12］周四伟,蔡勇.AC－BM算法的改进及其在入侵检测中的应用［J］.微计算机应用,2007,28(1):27－31.
［13］王琢,赵永哲,姜占华.网络处理模式匹配算法研究［J］.计算机应用研究,2007,24(12):310－312.
作者简介
冉占军 男，1977年出生，陕西西安人，讲师，硕士研究生。主要研究方向为算法、网络安全。
姚全珠 男，1960年出生，博士，教授。主要研究方向为算法、数据库、网络安全。
第6篇
关键词：KMP；改进；模式匹配算法；字符；分析；算法
中图分类号：TP309
随着计算机技术的不断发展，需要处理的数据内容不断呈现出大量化的特点。近年来，在计算机研究领域内模式匹配问题受到了极大的关注。在串处理系统中，子串在主串中的定位操作是一种重要的过程中，称之为串的模式匹配。随着计算机网络搜索引擎技术的发展、病毒技术的进步以及数据压缩方面的不断发展，模式匹配算法在计算机应用系统中得到了广泛的应用。目前主要的匹配算法有BF算法、KMP算法与一些改进的算法，从方式上，可以分为精确匹配、模糊匹配、并行匹配等。本文重点对KMP算法进行分析，另外对于改进的KMP算法进行研究与展望。
1 简单的模式匹配算法
现代计算机技术不断发展，人们的工作、生活与互联网有着密切的联系，同时网络内容也不断丰富，每一个终端几乎都有可能会上传与下载数据，造成网络上的类似相信也非常多，如何能够从大量的信息中进行查找同样的信息，则需要经过一定的算法。[1]这种典型的应用系统将会使用到匹配算法。简单的模式匹配算法主要是一种查找过程，给出一个特定的字符串P，在一大型的文本中进行查找，从而确定出P是否在大型文本中出现过，如果存在，同时给出相应的出现位置。在以上的算法定义中，为了对数学模式进行简单描述，进行以下符号定义。模式串为P，需要匹配的大型文本主串为T，模式串的长度为m，需要匹配的大型文本主串长度为n，在模式串中首字符与末字符分别为P1与Pm，而需要匹配的主串文本首字符与末字符分别为T1与Tn。文本字符串T与模式字符串P分别是由字符组成的一种集合，强行搜索模式实质上就是把模式P与文本T进行自左向右的挨个搜索，如果模式字符串P在某一点的匹配失败，则立即将T向右移动一个字符的位置，继续从模式字符串P的第一位向右来搜索。[2]这种算法基本上是最符合原理的，但同时它的工作量十分巨大，体现出的效率并不高，需要进行m（n-m+1）次的字母匹配运算，往往给过程浪费大量的时间。现代社会是高效社会，一旦在网络搜索中速度过慢，用户将会失去耐心。目前更多的手持设备在应用搜索时一般是即时搜索，对时间的要求较高，运算量太大的低效搜索模式已经不再满足现代需求。每个网站的用户数量都在不断增大，形成的用户名与密码都需要进行数据储存，利用模式匹配法可以对账户与密码进行匹配，从而判断是否可以登入，否则就进行拒绝，有效提高时间，保护网站利用与用户隐私。这是模式算法的典型应用，随着算法的不断进步，将会在多个网络领域内得以广泛应用。[3]
2 KMP算法
KMP算法目前已经经过了多年的发展，最早是由克努特、莫里斯与普照拉特同时发现，是一种改进的字符串匹配算法，在这种算法中，对主串指针回溯进行了消除，利用已经得到的部分匹配结果把模式串右行一段较远的距离，再次进行比较与匹配，从而使算法的效率得到大幅地提升。这主要是因为在前期的匹配过程经验总结中，一旦某字符不符合模式串的匹配要求，在附近的一段文本中也将不会出现匹配的对象。[4]
KMP的算法思想是当Ti与Pj匹配完成时，主串的指针i与模式的串指针j将会分别加1，不断向后面进行再次匹配，如果Ti与Pj匹配不成功时，主串的指针i保持不动，模式的串指针j将不会回到第一个位置，而是回到一个合适的位置，一旦j回到了第一个位置，将有可能会对需要匹配的文本字符进行错过。主串的指针i保持不动时，算法的关键就在于模式的串指针j指回到了哪一个位置。模式的串指针j不可右移太大的距离，避免错过有效匹配，同时也要右移尽可能地大，以提高匹配效率。在某次字符匹配时，一旦不匹配，模式的前j-1个字符能够匹配，则在下一次匹配时，可以把模式串向右移动j-s-1个字符位置，从而使P1与Tj-s对齐，需要从P3+1开始进行匹配情况检查。为了避免遗漏问题，在以上的首字串必须是最长的，自匹配的部分字串是唯一的，与模式自身结构有关。当模式的第j个字条与主串里的该字符进行比较位置时，它的值主要是取决于模式本身，与主串无关。这时关键是要选择模式的适当位置。
3 改进的KMP算法
模式匹配的KMP算法有效地避免了BM算法中频繁回溯的问题，极大地提高了模式匹配的效率，但这种算法并不是最优秀的。经过长时间的探索与分析，KMP算法中的扫描部分仍然可以进一步改进。[5]
在改进的KMP算法中，当某一次匹配失败时，i指针不需要进行回溯，而是使用已经匹配到的结果，查看是否对i的调整进行必要性评估，之后再决定与向右滑动的位置模式进行比较。主串指针i的有效变化可以有效提高匹配的效率。在进行第一次匹配结束时，j=6处，无法进行匹配时，i指针将会定为6，j指针为6，当模式串向右移动三个位置时，开始进行第二次的匹配，i的指针为9，而j的指针值为3，也就是说从主串的第九位开始进行比较，i值的不断增加也就加快了模式匹配的进度，提高了工作效率。
4 利用改进算法进行多次模式匹配
与单模式匹配算法相比，多模式匹配算法的优势在于一趟遍历可以对多个模式进行匹配，从而大大提高了匹配效率。对于单模式匹配算法，如果要匹配多个模式，那么有几个模式就需要几趟遍历。当然多模式匹配算法也适用于单模式的情况。在入侵检测系统中，一条入侵特征可能匹配或部分匹配很多条规则，如果采用单模式匹配，在匹配每条规则时都需要重新运行匹配算法，效率很低。然而，日益增多的网络攻击使得入侵检测的规则数目仍在不断增长。
在实际的应用中，模式串与主串一般需要多次的匹配，才能找到主串中是否有多次存在相同的子串，如在数据库中进行查找。[6]通过多次模式的匹配可以实现多个子串在文本中的位置，同时可以进行标记，有利于现代计算机庞大数据量的数理与分析。我国人口众多，网民数量庞大，姓名与用户名很可能会出现重复的情况，所以需要提前在数据库中进行查找，以确定是否可用，另外对匹配但其他特性不符的对象进行排除。
5 结束语
随着现代计算机技术的不断发展，越来越多的新技术得以应用与改进。网络安全发展形势也要求提高网络入侵检测系统的性能。模式匹配的效率问题引起了足够的重视。通过对传统的KMP模式匹配算法与其发展状况进行分析，明确未来发展思路，为其实践应用奠定理论基础。
参考文献：
[1]李桂玲.一种改进的KMP模式匹配算法[J].吉林工程技术师范学院学报，2009（10）：75-77.
[2]杨战海.KMP模式匹配算法的研究分析[J].计算机与数字工程，2010（05）：38-41.
[3]陈冬文，张帆，王斌，周启海.模式匹配算法――KMP算法的改进[A].2008中国信息技术与应用学术论坛论文集（一）[C].成都：西南财经大学信息技术应用研究所，2008.
[4]明廷堂.BF与KMP模式匹配算法的实现与应用[J].电脑编程技巧与维护，2013（23）：24-28+34.
[5]范洪博.快速精确字符串匹配算法研究[D].哈尔滨：哈尔滨工程大学，2011.
[6]赵森严，黄伟，李阳铭.一种改进的KMP入侵检测的模式匹配算法[J].井冈山大学学报（自然科学版），2013（01）：55-57.
第7篇
Abstract： With the rapid development of the city， the increasing number of cars， the city faces increasing traffic pressure， intelligent transportation system is one of the effective ways to solve the traffic congestion currently accepted， but to provide a reliable source of data for intelligent transportation systems an important issue in building intelligent transportation systems， floating car technology as newly
developed a traffic information collection methods， the practice has proved capable of reliable data source for intelligent transportation
systems. In order to grasp the macroscopic properties of the urban road traffic， the paper uses data preprocessing， coordinate conversion， map matching， statistical analysis and a more in-depth analysis of floating car data comparison， intuitive access to relevant features of the urban transport， urban transport planning and management decisions and people travel has some practical value.
关键词： 城市道路交通；GPS浮动车；宏观特征
Key words： Urban Road Traffic；GPS Floating Car；Macroscopic Characteristics
中图分类号：U496 文献标识码：A 文章编号：1006-4311（2013）03-0036-03
0 引言
随着城市化进程的不断加快，更多的人进入城市，交通拥挤日益成为城市发展的瓶颈，据公安部消息，截至2012年6月底，我国机动车保有量达2.33亿辆，汽车保有量达1.14亿辆，大中城市中汽车保有量达到100万辆以
上的城市数量达17个，私家车保有量达到8613万量，占
汽车保有量的75.62%[1]。发展智能交通系统对于城市交通诱导、缓解交通拥堵已成为国内外认可的有效方式之一，随着科技的发展进步，浮动车技术因其在交通信息采集方面建设周期短，投资少，覆盖范围广，数据精度高，实时性强受天气影响小等特点[2]越来越受到智能交通建设和研究领域的重视。浮动车技术在国外起步比较早，取得了一定的研究进展：英国的浮动车数据系统FVD，主要用于交通信息的采集与分析，预测道路形成时间及时向用户[3]；德国的浮动车数据系统FCD，主要采集车辆的位置、速度、时间等信息，提取和分析交通信息，判断交通状态，及时向公众，为公众出行规划提供参考依据[4]；美国的ADVANCE系统，该系统是浮动车与检测线圈相融合，预测旅行时间，为出行者提供实时的动态路线诱导信息[5]；日本VICS系统，该系统能够提供多种信息，为旅行者出行规划提供参考[6]；韩国KORTIC，该系统结合浮动车、环形线圈、闭路电视监控进行交通信息采集，把数据融合后提取交通信息，判断交通状态[7]。
浮动车技术在国内的研究起步比较晚，开始于2002年的北京交通大学利用少量的出租车进行的北京市路网分析评介，但是目前发展比较快，在北京、上海、杭州、宁波等城市利用现有的出租车建立起了浮动车系统，实时采集路网的交通信息。论文采用的数据为昆明市GPS浮动车数据。
1 数据采集及预处理
1.1 数据格式 浮动车就是在城市道路行驶的车辆（主要是公交车、出租车）上安装具有位置信息采集功能的GPS设备，在车辆的运行过车中通过无线网络（GPRS、WIFI等）实时向控制中心传回车辆的位置、时间、瞬时速度、车辆运行方向、设备终端编号等信息的车辆。
1.2 浮动车数据预处理
①剔除研究范围之外的数据：研究用的数据时间范围为：2010年12月01日00时00分00秒-2011年3月31日23时59分59秒的共计26984135条数据，研究的地理范围为东经102.647O-102.828O，北纬24.914O-25.117O的范围，数据分析之前，剔除研究范围之外的数据。
②剔除速度大于120km/h的数据：根据相关规定的道路的设计最高速度不得超过120km/h，包括高速公路，考虑到有绕城高速和二环快速路，删除速度高于120km/h的数据。
③剔除前后时间间隔超出数据回传时间间隔的数据：采用的数据回传的时间间隔为15s，如果某一条数据与前后数据的之间的时间间隔超出15s则需要对该数据进行剔除处理，算法如下：
Ti-Ti-1>15s且Ti+1-Ti>15s
则删除数据i。
Ti为浮动车传回的第i条数据记录的时刻。
1.3 坐标转换 浮动车数据采用的坐标为WGS-84大地坐标系，而昆明市道路网数据采用的是北京1954平面坐标系，为了能将浮动车数据准确的匹配到城市道路网上，必须对浮动车数据进行坐标转换，使浮动车数据坐标的坐标系与道路网电子地图数据坐标保持一致。
1.4 地图匹配 由于受GPS定位误差及建筑物遮挡等因素的影响，GPS浮动车数据并不完全准确的定位于道路网电子地图相应的道路上，而是存在一定的偏差，为了准确的研究城市道路交通的宏观特征，需要把GPS浮动车数据准确匹配到城市道路网上，实现这一过程的算法称之为地图匹配算法。目前地图匹配算法主要有点到点匹配算法、点到线匹配算法、线到线地图匹配算法。
单独的点到线的匹配算法只是采用投影距离大小比较确认匹配点，没有考虑到浮动车行驶轨迹的连贯性，因而在交叉口和“Y”字口等地点会出现错误匹配。考虑到行驶轨迹的连贯性，采用点到线匹配结合历史轨迹数据匹配算法。具体算法如下：
①GPS浮动车数据点P（x，y），匹配算法为求点到线的最近点距离来确定匹配的路段，设道路L1和L2的方程为A1x+B1y+C1＝0和A2x+B2y+C2＝0，与点P到两条道路的距离为：
d■=■（1）
d■=■（2）
如果d■＞d■则点P匹配到道路L1上。但是点到线的匹配算法存在缺陷，如图1所示，点P4会被错误匹配到L2上而不是匹配到L1上。
②此缺陷可以通过完成点到线的最近距离匹配之后，采用统计分析的方法，依据浮动车数据的设备终端好及时间顺序，判别P4点与前后各点同为一辆浮动车的数据同时时间间隔不超过阀值，则可确定P4点在道路L2上。
2 交通宏观特征分析
2.1 浮动车不同速度区间比例分析 本论文为了便于研究选取2010年12月1日00时00分00秒至2010年12月31日00时59分59秒之间的浮动车数据作为研究对象，进行分析研究，其中分别选取工作日（星期一），周末（星期日）的数据进行分析，研究之前删除了数据中速度为零的数据，时间间隔为30分钟，时间段为00时00分-23时00分。
从图2中可以看出各阶段速度的比例在一天当中都是不断变化的，这反映了道路交通的动态特性。
①周日的浮动车数据量比例低速区域（15>speed>=0）在7：30之前保持在10%左右7：30之后开始平缓的增加，到15：00左右达到20%左右，高速区（speed>=30）的比例从7：30开始有70%左右下降达到50%左右持平，中速区（30>speed>=15）也出现了一定程度的增加，这反映了周末人们7：30出行的不开始不断增多导致交通状况发生变化，车辆运行速度开始减缓；
②周一的浮动车数据量比例低速区域（15>speed>=0）在6：30之前保持在10%左右6：30之后开始急剧增加，8：30达到20%左右，之后出现小幅波动，高速区（speed>=30）的比例从6：30开始有71%急剧下降达到50%左右持平，中速区（30>speed>=15）也出现了一定程度的上升，这反映了人们从6：30开始上班出行不断增多导致交通运行减缓。
③图中可以看出周日的低速区增加、高速区下降要比周一缓慢，同时周一由于人们上下班时间相对固定，基本集中在8时30分到9时00分的原因，早上出行时间主要集中在6：30到8：30之间形成早高峰，下午下班的时间集中在17时00分到18时00分之间，因而17：00到19：00之间形成晚高峰，而周日则反映出人们出行的时段比较分散，早晚高峰不是很明显。
④从晚上20时00分开始中速区和低速区的比例开始下降，高速区的比例开始升高，反映出了人们出行的减少，道路交通处于比较畅通的状态。
2.2 全路网一星期七天交通状况分析 通过对处理好的数据进行分析获取了一星期的昆明市研究区域全路网的不同时间段的速度分布特征如图3所示。
通过对趋势图进行分析，可以知道昆明市全路网的交通有以下特征：
①工作日与周末的交通状况有明显的不同，星期六和星期天从早上7：30才开始速度不断下降进入早高峰时段，全路网速度持续减慢到9：30左右速度开始低于30km/h，而且一直持续到12：30左右出现小幅的回升，之后几乎保持小幅波动，变化不是很大，到下午17：20左右速度又开始持续下降，回身保稳定的时间为下午19：00整，这一时段为晚高峰，之后速度有小幅波动，同时由于出行人数和车辆的减少，速度加快。
②工作日的速度从早上6：30开始持续降低，到8：30左右达到最低形成早高峰，之后基本保持稳定，没有出现大幅波动，持续到12：20左右之后速度出现小幅替提升，中午13：30左右速度因为下午上班出行等因素的影响速度再次出现降低，之后基本保持稳定，到下午17：20左右又再一次降低持续至18：40，形成晚高峰，之后速度出现小幅波动，并持续回升。
③从图中可以看出，不论是周末还是工作日，凌晨4：40-6：50之间的速度是最高的，速度接近于35km/h，说明在这一时段出行的人数及车辆都比较少，交通运行顺畅。
④工作日的早高峰要比周末的早高峰提前40分钟左右，同时工作日的早高峰形成快于周末，而且速度下降较快，另外工作日的晚高峰形成时间基本一致，保持稳定的趋势一致。
第8篇
关键词:点云数据;配准;ICP算法
中图分类号:TP391.7 文献标识码:A
The Research of Cloud Data Alignment
CHEN San-qing
(School of Computer, Panzhihua University, Sichuan Panzhihua 617000)
Key words: cloud data; alignment;ICP algorithm
为了得到物体真实的三维模型,人们需要获得三维物体表面的真实数据。但是,由于受到测量设备和环境的限制,物体表面完整测量数据的获得往往需要通过多次测量完成。点云(三维数据)就是使用各种三维数据采集仪采集得到的密集数据,它记录了有限体表面在离散点上的各种物理参量。三维曲面的重建就是依据这种密集的点云数据来恢复原始曲面,进而实现三维模型的真实重现的目的。
由于每次测量得到的点云数据往往只覆盖物体部分表面,并且可能出现平移错位和旋转错位,为了得到物体完整表面的点云数据,需要对这些局部点云数据进行整合和配准。因此,在得到点云数据之后,为了得到三维模型的原始曲面,必须要将不同角度,不同位置扫描得到的大容量三维空间数据点集转换到一个统一的坐标系中,该技术称之为数据缝合,即三维点云数据的配准。点云配准是点云数据获取后的第一步处理,也是所有后续处理的基础。因此,配准的精度将直接关系到建模精度。
1 点云数据配准算法的研究进展
一般情况下点云都是以高密度形态存在,为了有效处理各种形式的点云,根据点云的分布特征(如排列方式、密度等)可以把点云分为[1]:散乱点云,即测量点没有明显的几何分布特征,呈散乱无序状态;扫描线点云,即点云由一组扫描线组成,扫描线上的所有点位于扫描平面内;网格化点云,即点云中所有点都与参数域中一个均匀网格的顶点对应;多边形点云,即测量点分布在一系列平行平面内,用小线段将同一平面内距离最小的若干相邻点依次连接可形成一组有嵌套的平面多边形。
针对上述各种形式的点云数据,在20世纪80年代中期,很多学者对其配准进行了大量研究。1987年,Horn、Arun等人用四元数法提出点集对点集配准方法。这种点集与点集坐标系匹配算法通过实践证明是一个解决复杂配准问题的关键方法。1992年,计算计视觉研究者Besl和Mckay[2]介绍了一种高层次的基于自由形态曲面的配准方法,也称为迭代最近点法ICP(Iterative Closest Point),并在此基础上产生了许多的变种算法。ICP主要用于解决基于自由形态曲面的配准问题。但ICP算法对两个点云相对的初始位置要求比较高,点云之间初始位置不能相差太大,并且要求两个匹配点集中的一个点集是另外一个点集的子集。当条件不满足,或相差太大时,会影响ICP算法的收敛结果,使得配准变的不可靠。
Chen等运用两个曲面在法矢方向的距离来代替某一点到其最近点的距离,并将其作为匹配的目标评价函数。这一设想最初是由Potmesil于1983年提出的,它被推广为最优加权的最小二乘方法。Masuda等对点集进行随机采样,用最小中值平方误差作为度量准则,该方法在每次迭代后都需要进行重新采样。Johnson等使用特征提取策略去除没有启发信息的平面点来提高配准速度,在点云数据法矢连续、突变比较少的情况下,其速度没有明显的提高。也有一些学者通过引入参考点的方法来实现三维点云数据的配准,这些参考点实际也是一种标签,需要在测量前粘贴在被测物体上。此外,G.Barequet等人在几何哈希技术基础上采用投票机制实现了部分曲面匹配算法。还有使用卡尔曼估计子的三角片曲面匹配方法等。
2 ICP点云数据配准算法及其改进算法
ICP算法最初由Besl和McKay,提出来的时候,其原意是迭代最近点(IterativeClosestpoint)匹配算法,后来被广泛理解为迭代对应点(IterativeCorrespondingpoint)匹配算法。ICP法实质上是基于最小二乘法的最优匹配方法,它重复进行“确定对应关系点集并计算最优刚体变换”的过程,直到某个表示正确匹配的收敛准则得到了满足。目前,ICP算法在点云数据配准中应用相当广泛,并且得到了许多学者的进一步研究和扩充。基于ICP算法点云数据配准过程如图1所示:
2.1Beslhe和Mckay提出的原始ICP算法[2]
设扫描匹配过程中的参考扫描模型为Sr,待匹配的当前扫描模型为Sc,模型中的数据点个数为N。参考扫描模型和当前扫描模型间的变换矩阵为P=(p0,pl,p2,p3,p4,p5,p6)T 其中,PR=(p0,p1,p2,p3)T四元组表示旋转偏移量,可转化为3×3的旋转矩阵R(PR),PT =(p4,p5,p6)T表示平移偏移量。这样,模型间的变换矩阵可以表示为P=( PR | PT )T 。ICP算法在进行点对匹配时采用的是比较点间欧式距离的方法,而扫描模型间的变换矩阵是通过最小化欧式距离平方函数得到。
整个ICP算法描述如下:
第一步:初始化迭代,P0=( l,0,0,0,0,0,0 )T,迭代次数k,设置欧式距离均方差阀值r以及最大迭代次数Kmax 。
第二步:迭代步骤:
(1)对待匹配扫描模型中的每个点搜索其在参考扫描模型中欧式距离最近的点,生成整个扫描模型的邻近点对集合Yk。
(2)由参考模型中的扫描点和匹配点对集合计算扫描模型间的变换矩阵Pk=(PR k | PT k )T和匹配点对间的欧式距离误差dk。
(3)根据变换矩阵Pk=( PR k | PT k )T变换当前扫描模型Sr中的所有扫描点位置。
(4)计算变换后,参考扫描模型与当前扫描模型间的对应点对间的欧式距离误差dk+1,并计算第k和k+1次迭代中误差变化量。当该变化量小于欧式距离均方差阀值r或迭代次数k大于k max时,停止迭代。
ICP算法是一种迭代算法,具有很高的匹配精度。但由算法描述可知,它存在计算量较大且迭代过程可能无法收敛到全局最优解的缺陷。ICP算法最耗费时间的步骤是求解邻近点对的过程,因为它采用的是全局搜索。为适应不同的环境并克服ICP算法自身的部分缺陷,许多研究人员对其进行了改进。
2.2ICP的改进算法
为了提高基本ICP方法的可靠性和鲁棒性,从匹配点的选择到最小二乘度量目标函数的选取等ICP匹配算法中的各个阶段,许多研究者都提出了各种的优化方法,形成了相应的ICP变型算法。ICP算法的各个阶段划分如下[3]:
(1)匹配模型中进行匹配的数据点的选取采样;
(2)两模型中有对应关系的匹配点对的选择;
(3)匹配点对的适当权值赋予;
(4)过滤某些错误的匹配点对;
(5)度量准则的选取;
(6)最优化方法的确定。
对ICP算法的改进主要集中在如下四点[4]:
(1)点集的不同选取方法。一般情况下点集的选取方法包含如下五种情况,分别是选取所有可用点作为点集;随机选取抽样点作为点集;采用平均抽样方法进行点集选取;根据点的特征信息(如梯度信息等)进行点集选取;选取边缘点作为点集。
(2)点的对应方法。点的对应方法主要有二种,一种是搜索最近点作为对应点;另一种是采用投影求交的方法确定对应点。
(3)点对的拒绝。点对拒绝的实现主要有以下三种情况:对于边缘点的拒绝;对于对应点对中距离过大的点对的拒绝;考虑法向量的点对的拒绝。
(4)加速迭代。主要采用减少迭代次数或使用非迭代的方法来实现,作用是减少运算量,提高计算速度。
Chen和Medioni两位学者在Besl和Mckay的经典ICP算法的基础上进行了改进,该算法的不同之处在于改进后算法的目标函数中的距离是点到对应点出的切平面的距离。事实上,因为一开始的匹配点对通常都是不精确的,这种方法认为在这种不精确的意义下,严格地极小化匹配点对之间的距离平方和不能达到快速的收敛,因此它选取了到匹配点处的切平面的距离来代替点到点的距离。这种方法的好处是一开始就可以使迭代误差很快地减小,也就是快速的收敛,但是因为它用切平面来代替真正的曲面,也就是忽略了目标函数的Hessian中的二次项信息,所以这种方法有时候会不收敛,尤其当目标物体表面曲率变化明显时,这时,二次项信息在目标函数种占有更多的比重。事实上,这种方法是一种Gauss-Newton法,它不保证收敛,但是如果收敛,速度会比较快,是二次收敛。后来有研究者对这种方法提出了改进,加上了步长控制[5](Levenberg-Marquart方法),这样可以保证该方法收敛,而且如果步长选取地合适,并不影响收敛速度,仍然二次收敛。此外,Mitra等引入平方距离(Squared Distance)的概念。把Chen和Medioni的改进中所忽略的二阶信息做了一个理想的近似加入了迭代中,因此能保证更好的收敛性。这种方法在满足标准假设的情况下,是一种准牛顿方法。准牛顿方法是收敛的,而且是二次收敛的。
3 结束语
近年来随着三维扫描技术的发展,特别是三维激光扫描技术的出现,高效、快速、准确的获取真实场景的高精度三维点云数据变得较为容易。利用这些点云数据可以恢复重建具有准确几何信息和真实感的原始物体。本文对点云数据处理中的配准方法进行了论述。本文首先总结分析了点云数据配准算法的研究现状,然后对其中比较具有代表性的ICP算法及其改进算法进行了具体的探讨。目前,对ICP算法研究的主要集中在如何提高ICP算法的稳定性、收敛性和可靠性等方面上,通过改进搜索最近点以及计算的收敛性,来提高ICP算法的配准精度和配准速度。
参考文献:
[1]张舜德,朱东波,卢秉恒.反求工程中三维几何形状测量及数据预处理[J].机电工程技术,2001,30(l):7-10.
[2]Besl P J, MeKay N D. A method for registration of3-D shapes.IEEE Trans onPattern Analysis and Maehine Intelligenee ,1992 ,14(2): 239-256.
[3]潘小林.三维曲面匹配技术研究[D].南京航空航天大学硕士论文,2004.
第9篇
【摘要】 颈动脉超声图像中的运动信息能够间接地反应颈动脉弹性等状况，结合颈动脉内中膜厚度(CIMT)能够为心脑血管疾病诊断提供定性与定量的依据。我们将改进后的金字塔快速匹配算法(modified block sum pyramid，MBSP)应用于颈动脉超声波图像斑点跟踪获得运动信息。理论和实验结果都表明，改进后的金字塔块匹配算法能有效地减少运动跟踪的运算量，并且有着和改进前的金字塔块匹配算法相同的准确度。运动跟踪结果能够为医生诊断心脑血管疾病起到一定的辅助作用。
【关键词】 颈动脉;斑点跟踪;金字塔算法;运动分析;平均绝对差函数
Abstract：The motion information in the carotid ultrasound image can reflect the condition of carotid whether it has hardened， expanded and contracted in the right way. Then it can help doctor to diagnose cardio cerebral vascular diseases together with the carotid intima-medial thickness(CIMT).We used the modified block sum pyramid (MBSP) algorithm to analyze the motion of carotid ultrasound images. The result shows that the modified algorithm effectively reduced the computation while speckle tracking. Besides that， the MBSP algorithm has the same accuracy with the block sum pyramid. The tracking result can assist the doctor to evaluate the disk of cardio cerebral vascular diseases to a certain degree.
Key words：Carotid; Speckle tracking; Block sum pyramid; Motion analysis; Mean absolute difference
1 引 言
心脑血管疾病与颈动脉内中膜厚度及其运动特征等有着密切的相关性[1]。对于超声波图像而言，可以通过斑点跟踪的方法获得运动信息。斑点作为噪声不可避免地存在于超声波图像中。虽然斑点噪声影响超声波图像质量，但是根据斑点噪声的形成原理，可以通过跟踪斑点来获取图像中相关目标的运动信息。为研究组织的运动特征和弹性信息，进而辅助评估心脑血管疾病提供了一种可能。斑点跟踪算法一般包括两个方面：匹配和搜索。匹配的准则有许多种，常用的准则有归一化相关函数(NCCF)，平均均方误差函数(MSD)以及平均绝对差函数(MAD)等。因MAD不涉及乘法等复杂运算，所以较为常用，本研究也采用该匹配准则。搜索方法也有好多种，有全搜索法[2]，十字搜索法[3]，菱形搜索法[4]等。此外，在这些算法基础上发展出了许多快速算法，如金字塔算法[5]，连续淘汰法[6]，改进的自适应2BIT变换法[7]等。临床实践中医生除了用肉眼定性地去观察颈动脉的运动特征，有时需要定量测量出感兴趣的颈动脉某一目标的运动信息(如：短轴切面轮廓在一个心动周期内收缩和扩张的运动状况)。这样就能够更加可靠地评估心脑血管疾病和风险。由于辅助诊断对运动跟踪的实时性要求不是很高，而对运动跟踪的准确性要求较高。故我们选择能达到全局最优的全搜索法和金字塔快速匹配算法的组合进行斑点运动跟踪，并且对金字塔快速匹配算法进行了改进，将其应用于颈动脉运动分析，高效准确地跟踪出目标兴趣点运动的相关信息。
2 原理与方法
2.1 金字塔块匹配算法
设有块X和Y，块大小均为：2M×2M，对块X和Y均建立 M+1层的金字塔。从塔顶往下依次为第0，1，…，M层。X，Y的金字塔的第m 层分别记为Xm，Ym。第m-1层和第m层关系如方程(1)所示：
Xm-1(i，j)=Xm(2i-1，2j-1)+
Xm(2i-1，2j)+Xm(2i，2j-1)+Xm(2i，2j)(1)
令：MADm(X，Y)=∑2mi=1∑2mj=1|Xm(i，j)-Ym(i，j)|(2)
可以得出结论(3)：
MAD0(X，Y)≤MAD1(X，Y)≤MAD2(X，Y)…≤MADm(X，Y)…≤MADm(X，Y)(3)
两个块在生成了各自的金字塔之后，从顶层往下逐层计算MADm(X，Y)。如果发现其大于或者等于最新的MADmin时，说明本候选块一定不是最优块，舍弃该候选块继续搜索下一个候选块，如果比较到最底层，仍然比最新的MADmin还小时，将MADmin更新为当前候选块与参考块的MADm(X，Y)。直到所有的候选块均搜索完后，最小的MADmin的候选块相对于参考块的偏移量即为所要求解的运动向量。 金字塔匹配算法就是通过尽快地舍弃那些不是最优的候选块而减少运算量的。虽然建立金字塔会增加额外的计算量，但是由于大部分的块在比较时就被舍弃了，所以总的运算量还是大幅地减少。
2.2 改进的金字塔匹配算法
金字塔块匹配算法从顶层开始往下逐层比较时，层与层间的MAD值相差很大。当层数较大时，最后一层与倒数第二层的MAD值相差更大，因此，比较时仍有不少的计算冗余。为此，希望在现在的金字塔基础上不改变运算量，在层与层之间新增一些阈值，能够尽早地舍弃那些不是最优的块。为了叙述方便，以下讨论均以在最后一层(第M层)与倒数第二层(第M-1层)之间增加阈值为例。
两个要比较的块分别记为X，Y，块X和Y的金字塔的第M-1层分别记为：XM-1，YM-1。设SM-1为第M-1层塔的所有像素点空间。将XM-1，YM-1按照相同的方式均分割为N个区域：S1M-1，S2M-1，S3M-1，SkM-1，…，SNM-1，1≤k≤N，见图1。具体的分割方法还需要根据实际情况进行合理的选择。分割出的N个区域要满足以下两个约束关系：
∑Nk=1SM-1k=SM-1(4)
SM-1k∩SM-1l=，1≤k≠l≤N(5)
图1 像素空间分割方法
Fig 1 Pixels partition method
图2 实验所采取的分割方法
Fig 2 Experiment′s method
同时对块X，Y的金字塔的第M层也划分为N个区域SM1，SM2，SM3，SMk，…，SMN，1≤k≤N。也要满足约束关系：
∑Nk=1SMk=SM和SMk∩SMl=，1≤k≠l≤N。
SM-1k区域中的每一个点对应于SMk区域中的4个点，此对应关系和构建金字塔时从M层到M-1层的4个点累加成1个点的对应关系一致。
构造如下函数表达式：(0≤n≤N)
MADM-1n(X，Y)=MADM-1(X，Y)-∑nk=1∑(i，j)∈SM-1k
|XM-1(i，j)YM-1(i，j)|+∑nk=1∑(i，j)∈SMk |XM(i，j)YM(i，j)|(6)
根据层间区域关系式(1)，上式又可以写成(7)式：
MADM-1n(X，Y)=MADM-1(X，Y)-f(n)(7)
其中f(n)可写成(8)式:
f(n)=∑nk=1∑(i，j)∈SM-1k|XM-1(i，j)YM-1(i，j)|-
[|XM(2i-1，2j-1)YM(2i-1，2j-1)|+
|XM(2i-1，2j)YM(2i-1，2j)|+
|XM(2i，2j-1)YM(2i，2j-1)|+
|XM(2i，2j)YM(2i，2j)|](8)
又据三角不等式及上下层点的对应关系知：
f(n)≤0，且f(n)随着n的增大单调递减，据此得出(9)、(10)、(11)的3个结论：
MADM-1(X，Y)=MADM-10(X，Y)(9)
MADM-1N(X，Y)=MADM(X，Y)(10)
MADM-10(X，Y)≤MADM-11(X，Y)
≤…MADM-1n(X，Y)≤…MADM-1N(X，Y)(11)
如果将SM-1像素空间一列一列依次从左往右分割时，所得到的有关结论则和文献[8]是一致的。文献[8]中所提到的逐行更新算法可看作是本研究改进算法的特例。现将改进的金字塔匹配算法(以在两帧中跟踪一个兴趣点为例)归纳如下：
记前后两帧图像分别为fi(x，y)，fi+1(x，y)，被跟踪点坐标为(a，b)，前一帧图像点(a，b)所对应的块称为参考块，搜索范围为A。
(1)计算相对于参考块运动位移为(0，0)的候选块与参考块两者的MAD值作为MADmin，并且确定后一帧图像中的起始候选块。MAD计算公式如(12)式所示：
MADmin=∑2M-1-1x=-2M-1 ∑2M-1-1y=-2M-1|fi(a+x，b+y)
-fi+1(a+x，b+y)|(12)
(2)依据金字塔算法构建当前候选块和参考块各自的金字塔。金字塔总共假设有M+1层。沿金字塔至上而下逐层进行比较，因为这里只考虑在M-1层和M层间新增阈值，所以前M-1层的比较和原金字塔块匹配算法一样。当M-1层比较完后，发现MADM-1(X，Y)仍然小于最新的MADmin。此时则需要按照构造函数表达式生成一个新的中间阈值，再进行比较，其间发现新生成的阈值大于或者等于MADmin时，舍弃，直接进入步骤(3)进行下一个候选块的匹配。否则一直进行到最后一层为止。如果其结果仍然小于MADmin时，更新MADmin。
(3)按照选取的搜索算法(如全搜索法)，确认下一点被候选点及相应的候选块。重复步骤(2)，直到A所有需要搜索的点搜索完为止。
(4)最后，对应于MADmin值最小的候选块即为最优候选块，其相对于参考块的偏移量，即为所要跟踪的运动矢量。
2.3 利用MBSP算法分析颈动脉图像
(1)取颈动脉短轴切面一个心动周期的图像序列。在第一帧图像中，沿颈动脉短轴轮廓，手动大致均匀地选取出若干个兴趣点，兴趣点应尽量选取在整个运动序列图像中亮度较为平稳且肉眼观察较为明显的斑点噪声颗粒。
(2)利用改进的金字塔跟踪算法(MBSP)逐帧地跟踪所有兴趣点，得到各个兴趣点在各帧中的运动矢量，再将各帧上各点的运动矢量按照适合人眼观看的比例显示在各帧图像上。最后以动态的方式播放附有运动矢量的颈动脉图像序列，医生可以根据播放视频中的运动矢量定性地掌握兴趣点运动大小、方向、扭转、是否出现异常等情况，做出一些如是否可能出现斑块硬化等初步诊断。
(3)最后给出各个兴趣点的收缩扩张曲线，每条曲线给出每个点随时间的运动速度变化。设第j帧图像中跟踪到的N个点的分别为坐标(X1，Y1)，…，(Xi，Yi)，…，(XN，YN)。其均值为(X，Y)。记Vi=(Xi，Yi)-(X，Y)，1
3 实验与结果
3.1 实验结果
实验数据由合肥105医院超声科提供，为一个心动周期的颈动脉短轴切片序列图像，共25帧。第1、11、22帧图像分别见图3、4、5。图3中小白框即为我们要跟踪的6个兴趣点，左上角为1号点，按顺时针依次排列。为了表述方便，这里只选取了6个兴趣点为例。
分别用BSP和MBSP算法对该颈动脉序列图像进行斑点运动跟踪，其中MBSP算法在第3层和第4层增加了3个新的阈值。将第3层的像素空间从左到右依次分割成4个相同的区域，见图2。实验中块大小取为16×16，搜索范围为8×8。图4附上了第11帧图像上各兴趣点的运动矢量图，两个算法跟踪出来的结果一样。图6给出了各个兴趣点(从左往右，从上至下依次为1到6)随时间变化的扩张收缩运动速度图。从图中我们可以看出，兴趣点2、3、4的运动表现出较为一致的运动规律，在一个心动周期内经历一个明显的扩张和之后的收缩过程。但是观察兴趣点1、5、6的运动速度曲线，发现其运动起伏相对来说没有这些规律，从而可以认为1、5、6附近区域可能出现一些病变。这和医生的诊断结果：本试验者颈动脉左下部区域内膜形成了较为明显的斑块，而斑块区域收缩运动常出现紊乱是相互吻合的。
3.2 性能分析
(1)准确性。分析改进后的算法和改进前的金字塔匹配算法(BSP)，容易得出前后算法运动跟踪结果应该是一致的，差异只在于计算量上。实际跟踪的结果也证明了这一点。图7、8给出了前后两种算法的跟踪兴趣点1的运动轨迹图，图中横轴、纵轴分别对应于图像的X轴和Y轴坐标轴。
(2)效率。表1给出了改进前后算法在上述实验过程中需要计算的各MAD值统计次数。计算第m层的MADm值所需要运算量(含加减法及绝对值)可以公式化[9]为：3.22m-1，计算MADmn运算量约为：5n·(3·22m+2-1)/16。以第4层为例，如果直接采用表1 金字塔算法改进前后各MAD次数
原来的金字塔算法，需要计算总次数为821 457;但采用改进后的算法需要的计算量仅为721 747。可见因为第3层与第4层3个新增阈值的引入，第4层判决过程的总体运算就减少12.11%，可以考虑将区域进行更细划分，但是要权衡因为阈值增加而造成的比较运算量。如果在第3层等层也引入同样机制的话，运算量将进一步减少。
4 总结
本研究将改进后的金字塔匹配算法应用于斑点运动跟踪，实验结果表明该算法能准确而更加有效地跟踪出运动矢量。并且将该方法应用于颈动脉运动分析，结合颈动脉的自身特点，给出有利于辅助医生诊断的扩张与收缩曲线等依据，为颈动脉的进一步分析奠定了一定基础。
参考文献
[1]胡玮，张军，孔国喜，等. 超声检测颈内动脉内-中膜厚度及其形态结构与相关心脑血管疾病的关系[J]. 第四军医大学学报 ，2007，28(15):1431-1433.
[2]Brünig M， Niehsen W. Fast full-search block matching[J]. IEEE Trans Circuits Syst Video Technol，2001，11(2): 241-247.
[3]Ghanbari M. The cross-search algorithm for motion estimation[J]. IEEE Trans Commun，1990， 38(7): 950-953.
[4]Zhu S，Ma K-K.A new diamond search algorithm for fast block-matching motion estimation[J].IEEE Trans Image Processing，2000，9(2):287-290.
[5]Lee C H， Chen L H. A fast motion estimation algorithm based on the block sum pyramid [J]. IEEE Trans Image Processing， 1997，6(11):1587-1591.
[6]Li W， Salari E. Successive elimination algorithm for motion estimation [J]. IEEE Trans Image processing， 1995，4(1): 105-107.
[7]Demir B， Ertu¨rk S. Block motion estimation using adaptive modified two-bit transform[J]. IET Image Process， 2007，1(2):215-222.
第10篇
关键词：车牌识别；人脸检测；VC++；OpenCV
中图分类号：TP311.52
1 引言
随着社会科技的进步和经济的迅猛发展，医院的业务也日渐增多，如何为医院提供一种安全、舒适、方便、快捷和开放的信息化生活空间，是本文重点讨论的问题。下文中，依托先进的科学技术，实现医院内部管理的高效、互动和快捷。对医院的出入口进行实时智能监控，达到维护治安和防止破坏的作用，及时的把一切可能发生的或即将发生的案件制止，以及对进出医院的可疑人物及车辆进行信息采集，把安全隐患降低到最小，对确保医院安全具有十分重要的作用。本论文工作，是基于VC++和openCV设计开发了一款实用的医院车辆及人员进出管理系统。能够对来访车辆进行自动车牌识别，根据车辆的数据库信息查询，实现门禁系统的自动控制；同时系统还包含人脸检测模块，能够对每天来访的人员进行人数统计。
2 系统总体设计
本系统功能主要分为两大模块：监控管理和数据库信息管理。具体功能图如下所示：
3 系统详细设计
打开和关闭摄像头：通过调用opencv中的函数cvCaptureFromCAM（）；初始化从摄像头中获取视频，获得每一帧的图像，并显示在窗口的图片控件上。通过调用opencv中的函数cvReleaseCapture（）；释放资源，并将视频窗口销毁，实现关闭摄像头的功能。
实时信息采集：通过函数cvSaveImage（）；将图片保存，并进行命名，可将当前摄像头所捕捉到的状况进行采集，可对进出医院的可疑人员和车辆进行抓拍。
人脸检测：在opencv中含有根据人脸模板训练的人脸分类haarcascade_frontalface_alt2.xml。通过加载分类器，可以对当前帧的图像中出现的人脸进行识别，并通过cvCircle（）将人脸圈出，实现人脸检测功能。通过检测出来的人脸可以知道今天目前为止该医院共进出了多少人次，并将信息通过定时器定时刷新信息，反馈给保安人员。
车牌识别：车辆检测可以采用埋地线圈检测、红外检测、雷达检测技术、视频检测等多种方式。采用视频检测可以避免破坏路面、不必附加外部检测设备、不需矫正触发位置、节省开支，而且更适合移动式、便携式应用的要求。
系统进行视频车辆检测，需要具备很高的处理速度并采用优秀的算法，在基本不丢帧的情况下实现图像采集、处理。若处理速度慢，则导致丢帧，使系统无法检测到行驶速度较快的车辆，同时也难以保证在有利于识别的位置开始识别处理，影响系统识别率。因此，将视频车辆检测与牌照自动识别相结合具备一定的技术难度。
车牌识别流程如图2所示：
图2 车牌识别流程
车牌图像处理：对于车牌图像，由实时监控录像进行实时保存，在进入车牌识别过程时打开。用dlg.GetPathName（）得到图片的路径，将图片打开。因为保存的图片是倒着的，所以将图片显示在图片控件前需要将图片进行旋转。利用函数cvCreateImage（）将图片转化为二值化时的大小，用函数cvCvtColor（）转化为灰度图，并用cvSmooth（）进行高斯滤波，为图片二值化做准备。
图片二值化：所有灰度大于或等于阈值的像素被判定为属于特定物体，其灰度值为255表示，否则这些像素点被排除在物体区域以外，灰度值为0，表示背景或者例外的物体区域。程序中没有用opencv函数库中的cvAdaptiveThreshold（）和cvThreshold（）进行二值化，而是通过调用AdaptiveThreshold（）获得第一个阈值，将最大像素的*0.7作为第二个阈值，进行图片二值化，并将这两个阈值用来做边缘检测函数cvCanny（）的参数。
牌照定位：本程序中通过对二值化的图像进行边缘检测后，在对得到的图片进行垂直和水平扫描，在对水平方向从左往右扫描的过程中，对最大信息量的区域圈出，然后进行垂直分割，将得到的区域即为车牌区域，之后再用cvResize（）将得到的图片变为统一的大小。也就是车牌定位的过程为：水平分割、垂直分割、二值化牌照字符分割。完成牌照区域的定位后，再将牌照区域分割成单个字符，然后进行识别。字符分割一般采用垂直投影法。由于字符在垂直方向上的投影必然在字符间或字符内的间隙处取得局部最小值的附近，并且这个位置应满足牌照的字符书写格式、字符、尺寸限制和一些其他条件。利用垂直投影法对复杂环境下的汽车图像中的字符分割有较好的效果。
牌照字符识别：字符识别方法主要有基于模板匹配算法和基于人工神经网络算法。基于模板匹配算法首先将分割后的字符二值化并将其尺寸大小缩放为字符数据库中模板的大小，然后与所有的模板进行匹配，选择最佳匹配作为结果。基于人工神经网络的算法有两种：一种是先对字符进行特征提取，然后用所获得特征来训练神经网络分配器；另一种方法是直接把图像输入网络，由网络自动实现特征提取直至识别出结果。
是否放行：在识别车牌号之后，将得到的车牌号的字符串与数据库中的车牌号的字符串进行对比，如果数据库中有该车牌则是医院的车，放行，否则不放行。
4 论文下一步的工作
本系统基本实现了医院车辆进出的自动化管理，以及进出人员的人次统计。但是目前系统只实现了一个摄像头的视频监控，这还不能满足目前医院多个监控摄像头同时工作的现状。因此，论文下一步的改进工作，是实现医院内多个监控摄像头的同时调取与管理。
参考文献：
[1]钟志光，卢君，刘伟荣.Visual C++.NET 数字图象处理实例与解析[M].北京：清华大学出版社，2003，6.
[2]何斌，马天予，王运坚，朱红莲.Visual C++ 数字图象处理第二版[M].北京：人民邮电出版社，2002.
[3]夏良正.数字图象处理[M].南京：东南大学出版社，1999，9.
[4]葛亮.Visual C++从入门到实践[M].北京：清华大学出版社，2009.
[5]康晓林，袁建州.Visual C++6.0实用教程[M].北京：电子工业出版社，2008.
第11篇
关键词：SIFT；相似性度量；图像匹配
引言
在计算机视觉领域，图像匹配仍然是当前研究的热点问题。基于特征的匹配方法[1]，因为根据图像中趋于稳定的少量特征进行匹配，使得运算速度快、匹配效果好，所以成为目前研究最多、应用最广泛的一种方法。但是，这种方法需要在图像间进行遍历性的匹配运算，存在计算量大，且精度不高的问题。
1999年，Lowe提出了SIFT（Scale Invariant Feature Transform）算法[2]，该算法利用高斯差分在图像的多尺度空间中快速求解高斯拉普拉斯空间中的极值点，加快了特征提取的速度，提取的SIFT特征对于图像平移、缩放、旋转具有不变性，并且对于仿射变换、视觉变化、光照变化有较强的稳定性和很好的匹配鲁棒性，所以被广泛应用于计算机视觉的图像匹配、图像检索和模式识别等方面[3，5]。虽然SIFT 算法具有上述的优点，但该算法首先要将彩色图像灰度化，仅利用图像的灰度信息和特征点的局部邻域信息，忽略了图像的颜色信息，导致不能识别图像内具有相似结构的特征点。
文章提出基于SIFT的多特征相似性度量算法，首先对彩色壁画图像提取SIFT特征点与特征向量，然后对每个特征点提取HSI彩色特征，最后按定义的相似性度量公式计算两个特征点之间的距离，确定二者是否匹配。
1 特征提取
1.1 SIFT特征提取
尺度空间极值点的检测采用DOG方法，将一个像素点与它相邻的26个点相比较，如果是最大值或最小值，就作为图像中的一个特征点。以特征点为中心，在16×16的邻域内，将采样点与特征点的相对方向通过高斯加权后，分别归入8个方向的梯度方向直方图，最后获得4×4×8的128维特征向量来描述一个SIFT特征点。
SIFT算法的两个关键步骤是关键点检测和关键点描述。在关键点检测阶段，大多是利用两种不同的方法，即尺度不变检测和致密采样。文章采用致密采样进行特征检测，理由如下。一方面，尺度不变检测器在描绘均匀信息时是低效的，而壁画图像中包含着这样的信息。另一方面，在特征匹配时，通过致密采样得到的关键点优于随机抽样和尺度不变的探测器[6]。
SIFT算法首先将彩色图像灰度化，提取的特征关注图像的梯度信息，忽视了图像的彩色信息。文章对彩色图像提取特征，实验发现图像的误匹配点中，存在着彩色信息不一致的问题。因此，文章对图像既提取SIFT特征，又提取颜色特征，对多特征融合设计相似性度量方案，可以减少误匹配率，提高匹配效果。
1.2 颜色特征提取
为了解决误匹配中存在的SIFT梯度信息一致，彩色信息不一致的问题，我们在对特征点提取SIFT特征后，再次提取其颜色特征。由于RGB颜色模型只考虑图像的亮度信息，而HSI颜色模型全面考虑图像的亮度和颜色信息，因而在开发基于彩色描述的图像处理算法中，HSI模型更为有用[7]，文章提取HSI彩色特征。
HSI颜色模型中，H表示色调，指的是人的感官对不同颜色的感受，描述纯色的属性；S表示饱和度，描述的是颜色的纯度；I表示强度，描述的是颜色的明亮程度。
常用的最近邻方法原理是，对于基准图像中的每个特征点，在待匹配图像中寻找距离最近的特征点，然后形成一组匹配对。因为最近邻获得的匹配对中存在大量的误匹配，所以Lowe在论文[8]中对于基准图像中的每个特征点，在待匹配图像中寻找距离最近和次近的两个特征点，当这两个距离的比值小于预设的阈值时，才认为找到了一组正确的匹配对，这样消除了大量的误匹配，取得了不错的匹配效果。文章设阈值为thr，且0
3 实验结果及分析
为了观察算法性能，我们从互联网上寻找了两张有重叠部分的壁画图片进行了实验。图像如图1所示。采用Matlab7.7.0编程，运行在AMD A6-3400M CPU 1.4GHZ和4G内存的PC机上，Windows 7.0操作系统。
实验首先寻找图像的SIFT特征点，然后提取特征点的SIFT特征和HSI特征，再对图1a和图1b按公式（9）进行相似性度量，再分别用欧式距离和卡方距离作为相似性度量，并且thr分别选用0.5，0.6，0.7，0.8进行特征对提纯。结果表明，匹配过程在使用同样的阈值时，三种相似性度量方法中，所得到的匹配正确率相同，而匹配时间不同，按公式（9）计算的距离稍快一些。随着thr值的增大，所得匹配对数减少，当thr取值为0.6时，具有较好的匹配结果。图2为thr取值为0.6时的匹配结果。
另外，实验同时表明，对于图像分别提取SIFT特征和HSI特征，如果仅按SIFT特征或HSI特征计算相似性，所得到的匹配正确率都低于两个特征按公式（9）计算相似性的情况。
因此，对图像提取SIFT特征和HSI特征，按我们定义的相似性度量计算方法，确实提高了图像匹配的效率。
4 结束语
文章采用的算法对彩色壁画图像同时提取SIFT特征和HIS彩色特征，有效地去除了梯度信息一致而彩色信息不一致产生的误匹配。通过定义的相似性度量公式，在计算两个特征点之间是否匹配时，速度更快一些。由于SIFT 算法计算量大，算法复杂，提高图像匹配的实时性，将是下一步的研究工作。
参考文献
[1]ZHU Q，WU B，XU Z.Seed point selection method for triangle constrained image matching propagation[J].IEEE Geoscience and Remote Sensing Letters，2006，3（2）：207-211.
[2]LOWE D G.Object recognition from local scale-invariant feature[C]// Proc.the Seventh IEEE International Conference on Computer Vision.Corfu，Greece： IEEE Press，1999：1150-1157.
[3]张书真，宋海龙，向晓燕，等.采用快速SIFT算法实现目标识别[J].计算机系统应用，2010，19（6）：82-85.
[4]王瑞瑞，马建文，陈雪.多传感器影像配准中基于虚拟匹配窗口的SIFT算法[J].武汉大学学报（信息科学版），2011，36（2）：163-166.
[5]钟金琴，檀结庆，李莹莹，等.基于二阶矩的SIFT特征匹配算法[J].计算机应用，2011，31（1）：29-32.
[6]K.Mikolajczyk，C.Schmid. A performance evaluation of local descriptors [J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27（10）：1615-1630.
[7]何川.高压输电线路视频监控技术研究[D].北京：北京交通大学，2012.
第12篇
关键词：数字图像取证；图像区域复制粘贴篡改
中图分类号：TP391.41文献标识码：A文章编号：1007-9599 (2011) 16-0000-01
Comparative Study of Ddigital Image Copy Paste Tamper Forensics Technology
Han Min,Sun Jinguo
(Chinese People's Public Security University,Beijing102623,China)
Abstract:This article describes several algorithms aiming at a common copy-paste forgery in the research field of digital image forensics,compared?the performance of?various methods.Different of kinds of tamper detection methods have been analyzed and discussed.It also prospects the future of copy-paste forgery in the research field of digital image forensics.
Keywords:Digital image forensics;Image area copy paste tamper
一、引言
近年来随着电子技术的发展传统的“胶卷相机”已经几乎被数码相机所代替，这为人们省去了很多传统相机使用上的不变，但伴随着数字图像处理软件的发展，数字图像的非法篡改给人们的生活以及社会带来很多负面的影响，数字媒体的信息安全无法得到保障。复制粘贴篡改是一种常见的篡改手法，它利用同幅图片内各种统计参数比较相近，从一个区域复制一个图块粘贴到另一区域上，以达到掩盖图像真实内容的目的。
二、数字图像被动取证技术
数字图像被动取证技术，要求只给出待检测图像就可以鉴别真伪，即在不依赖任何预签名提取或预嵌入信息的前提下，对图像内容的真伪和来源进行鉴别和取证的技术，因此这类取证技术也叫数字图像盲取证技术。
数字图像被动取证技术实现的可行性基于这样一个事实：任何来源的数字图像都有自身的统计特征，而任何对数字图像的篡改都会不可避免地引起图像统计特征上的变化。因此，可以通过检测图像统计特征的变化，来判断图像的原始性、真实性和完整性。
三、取证算法
目前的取证算法大体上可以分为两类，即基于单个像素的穷举搜索和基于图像块的检测方法。块匹配算法共同的特点就是对输入的图像数据进行分块处理。得到这些块之后，从这些块中提取相应的特征值构成特征向量，不同的基于块匹配的算法的实质区别就在于选取的特征值各不相同。下面就各种方法进行比较：
（一）穷举搜索。基于单个像素点的穷举法原理很简单，但计算复杂度很高，将之应用于大幅图像的篡改检测显然是不可行的，与此同时，此算法也不能够抵抗外来的一些干扰操作，如加噪、模糊等。算法本身受条件的约束性较强。一般我们只用于对较小尺寸的篡改图像的检测。
（二）简单块匹配。最基本的块匹配检测算法是将得到的b2大小的块展开，每个方形块按行优先顺序被展为一行，存入一个矩阵中，这样所有的行向量组成了一个二维矩阵X，其中列数为b2，行数为（Mb+1）（Nb+1）。为了减少算法的计算量，按照字典排序的方法对X阵中的行进行排列。最后根据判断是否存在等同的行向量来确定篡改结果。这种算法在图像遭到了复制粘贴篡改后没用进行其他篡改的情况下显示出了良好的性能，但是当篡改图像经过如压缩等后续操作时，检测的正确率明显降低，这是由于块与块之间不再是精确的相似，检测效果大打折扣。
Fridrich等人对此进行了改进，先对图像进行块离散余弦变换（BDCT）变换，采取经过量化后各块的BDCT系数进行对比分析。由于是在DCT域上做分析，算法具有一定的鲁棒性。但是当处理的图像比较大时，由于计算量太大，往往需要很长的时间来实现篡改定位，这个时间很可能无法令人接受。
骆伟祺等人提出了一种鲁棒的检测算法，这种算法也是基于图像块匹配的。假定问题图像为彩色图像（大小为MxN），首先对其进行分块处理，分块的方式同前面一样，在得到了（M-b+1）x（N-b+1）个图像块之后，对每个图像块提取可以代表其内容的七个特征值，并以向量的形式来表示，前三个分量a1、a2、a3分别是b2大小的彩色图像块RGB通道的均值。若为灰度图，只需记录像素点的灰度值即可，a4、a5、a6、a7则是由图像块内各像素点的亮度分量Y组成的阵列经过四种分解方式整合处理后得到的特征。此算法具有一定的鲁棒性能，能够抵抗一定程度的后处理操作，如模糊、压缩等。但如果被复制的区域发生了形变，则容易造成误判，甚至失效。
（三）基于不变矩的检测算法。不变矩方法是一种经典的特征提取方法，目前已经广泛应用于图像分析与模式识别领域中。Hu提出的7个矩不变量，不但具有平移不变性，而且还具有旋转不变性，适合用于表示图像的特征。但Hu矩的方法对模糊和加噪操作没有明显效果。
Zernike矩是一组正交矩，也具有旋转不变性，即旋转目标并不改变其模值。由于Zernike矩能构造出任意高阶矩，而高阶矩包含更多的图像信息，所以Zernike矩的识别效果优于其他方法。何坤等人提出了一种方法，将尺寸较大的篡改图像运用小波变换得到低频子图像，再把低频子图像分割为图像子块，对其子块序列图像分别进行Zernike矩分析判断是否存在复制篡改，该方法克服了噪声和几何变换对取证的影响。
（四）基于SVD的检测算法。奇异值分解（SVD），是一种图像特征分析方法。它的目的在于消除图像数据各分量间相关性，是基于信号二阶统计特性的一种方法。国防科技大学吴琼等人提出了一种基于SVD的图像复制区域检测算法。利用奇异值分解变换来处理图像块数据，并对图像块进行相似性匹配检验。这种方法对图像羽化或边缘模糊等处理具有鲁棒性。
四、结语
目前主流算法对于相对简单的复制粘贴篡改检测效果较好，但伪造者为了使篡改图像更加可信，除了采用简单的平移、旋转外，还可能会根据实际情况对篡改内容进行缩放、模糊等操作，这样传统的块匹配算法将会失效。因此，在保证算法健壮性与检测准确率的前提下，我们要设计出能够同时抵抗平移、旋转、缩放、模糊等各种操作的取证算法，这是我们今后努力的方向。
参考文献：
[1]周琳娜.王东明数字图像取证技术[M].北京:北京邮电大学出版社,2008:69-70
[2]骆伟祺,黄继武,丘国平.鲁棒的区域复制图像篡改检测技术[J].计算机学报,2007,11
第13篇
关键词：记事本系统 桌面平台 C#
中图分类号：TP393 文献标识码：A 文章编号：1003-9082（2015）12-0013-01
引言
早期的记事本系统只提供最基本的功能，例如文字查找功能。较新版本的Windows所搭载的新版记事本可以支持查找及替换功能，记事本亦集成了一个简单的日志功能，每一次打开文件，都可以记下一个新的时间标签。
但随着计算机操作体验的不断提高，传统记事本系统已经完全不能满足人们的日常生活需要。本论文开发的这套记事本系统，集成了备忘录模块、登录模块、分类存储模块等多个模块，满足了人们在记事本功能上的诸多要求[1]。
如今信息技术发展飞速，特别是C#技术，因为它有着很好的交互性、灵活性、安全性和扩展性，让此技术在应用中越来越广泛，因此也必然的进入到了文字编辑软件的开发中[2]。此系统的主要目的是让文字编辑存储更加方便，让日常生活记录笔记的过程更快速、方便和科学，使用本系统用户可以根据自己的需要来存储备忘录，不会耽误重要的事情，反之亦然，大大方便了用户的日常生活。
一、系统总体介绍
整个记事本系统分为五大模块，分别是登录模块、主界面模块、文字搜索模块、文字替换模块、字体设置模块。记事本系统五大组成模块如图1所示：
图1 记事本系统组成模块
二、模块设计
1.登录模块
登录时需要输入用户名和密码，然后才能登录。在用户登录时，要判断用户是否存在，若存在，判断用户输入的用户名和密码是否能够匹配成功，如果正确匹配，关闭登录窗口，进入系统主窗体。如果用户存在，但是用户名和密码不匹配，那么提示用户输入的密码错误。记录用户输入密码错误的次数，如果输错超过3次，则窗体自动关闭，登录失败。本系统采用SQL Server数据库，登录模块数据表如表1所示：
表1 登录模块数据表
2.主界面模块
本系统的系统主界面包括一个菜单栏和文本栏。菜单栏包含本系统的所有功能的菜单，包括新建记事本、删除记事本、分类管理、文字搜索、文字替换、字体设置、关于CHENE记事本等多个功能。而多行文本框是用来显示和编辑记事本内容的。主界面模块所用的数据表如表2所示：
表2 记事本信息表
3.文字搜索模块
本模块的功能类似于操作系统中的Ctrl+F功能，在文档中根据关键字查找调用内置的查询功能，输入关键字，点击确定，如果搜索到关键字，就会出现搜索结果，并统计出共有几个相匹配的关键字，并且会以高亮显示。这一点在日常文字编辑中非常的实用，无论是字词定位还是寻找线索都是非常有用的。
4.文字替换模块
本模块的功能类似于操作系统中的Ctrl+H功能，在使用过程中会有非常多的技巧。有时编辑的文本有很多空格和空行还有一些相同或重复的文字，删除和处理这些文字相当麻烦。因此只需要使用左侧菜单栏里的“文字替换”功能， 输入需要替换或者删除的文字就可以完成自动替换功能。
三、系统实现
1.登录界面的实现
界面采用当今最为流行的扁平化设计，当用户输入用户名和密码之后，还可以按En回车键登录系统，实现的原理是：在输入密码的文本框的KeyPress事件下，判断是否按了回车键，如果按了就会激发“登录”按钮的Click事件。
2.主界面的实现
使用文本框来显示和编辑记事本内容。整体界面依旧采用扁平化设计，界面整洁清晰。分类管理主要利用了TreeView控件显示所有的日志分类和日志标题，当单击某个日志标题时，右侧文本框将从数据库取出并显示出该日志的内容。
3.文字搜索/替换模块的实现
本模块的实现主要采用串的模式匹配的KMP算法[3]，该算法较一般串的模式匹配算法有较大的改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。
本系统的开发主要实现了以下目标：（1）灵活的新增记事本功能。（2）由于使用这套系统的普通用户在计算机的操作水平上可能不太够，因此本系统具有比较方便实用的人机界面（3）对于已经存档的记事本，能够高效的分类显示。（4）在使用过程中能够方便的使用文字查找和替换功能。（5）由于不同用户的不同需要，编辑文本的同时能够更改显示的字体。
参考文献
[1]谷震离， 胡付田. 记事本应用程序的开发与设计[J]. 许昌学院学报.2003（2）
[2]程文玮. 数据库管理[J]. 广州大学学报（自然科学版） [J].2005（2）
第14篇
[关键词]模糊匹配 模糊查找 位置匹配 C语言算法
[中图分类号]TP391.41 [文献标识码]A [文章编号]1009-5349（2013）02-0061-01
引言
为了提升用户拨号的快捷性，要求用户在输入号码的时候，对用户已输入号码进行模糊匹配，并以列表的形式呈现给用户，供用户选择。用户使用手机键盘拨号速度最快不超过100毫秒，这就要求手机必须在100毫秒以内查找结束并把结果呈现给用户。而手机号码、SIM卡号码、最近通讯录号码总和在3000个左右。利用传统的字符串查找已不能满足要求。
本论文仅阐述核心算法部分。
一、算法实现
本算法使用以空间换取时间的办法，通过记录不同数字所在的位置，并通过移位操作来实现模糊查找。此算法复杂度仅仅和用户输入的字符串长度有关，而和实际的字符串长度无关。因此，不同于常规的字符串查找算法。
（一）字符映射
首先，把手机号码中存在的字符映射成16个字符，方法为：把字符“0”-“9”转换成数字0～9；把“*”“#”“+”“p”“w”分别转换成数字10、11、12、13、14；把可能存在的字符“-”或其他字符转换成数字15。
（二）数据结构定义
用元素来定义电话号码的存储结构，一个元素存储一个号码。格式可以如下：
typedef struct
{tCellType nData[16]；
}tElement；
其中tCellType可以为unsigned short或unsigned long。前者代表可容纳电话号码的最大长度为16，后者代表可容纳的最大长度为32（32位机器下）。
（三）数据结构建立
把一个电话号码放到一个元素中去，保证：元素中nData[0]记录数字0所在的位置，nData[1]记录数字1所在的位置，依次类推，nData[15]记录数字15所在的位置。
添加一个电话号码到号码映射中。方法如下：（1）从字符串中取第一个字符，并根据字符映射规则映射为数字。（2）以映射成的数字为索引（index），并记录字符所在的位置为（i），位置从0开始计数。（3）取元素中索引为index的变量，并把位置为i的位设为1。即：nData[index] |=0x01
举例：假如电话号码为“13511051123”，则在nData[1]的0、3、4、7、8的位置1，nData[2]的9的位置1，nData[3]的1、10的位置1，nData[5]的2、6的位置1， nData[0]的5的位置1。
（四）查询方法
假如用户仅仅输入一个字符则只需要一次判断即可。算法复杂度为O（1）。假如用户输入n个字符，则需要：首先判断第0个字符对应元素中的值是否为真，如果是则继续。接着取第1个字符对应的元素值并右移1次，和第0个元素相与得结果tm，如果tm为真则继续。然后取第2个字符对应的元素值并右移2次，和上一次得到的结果相与得到新的tm，如果tm为真则继续。依次执行直到字符串结束。
算法复杂度分析：最好情况下一次判断即可获取结果，即用户输入的第一个字符对应的元素值为0；最坏情况下需要：n-1次移位操作，n-1次与运算，及n次判断操作。但一般用户输入的待查找字符串长度n远远小于原始字符串的长度。
算法示例：取临时变量tm，list为用户输入的待查找字符串通过字符映射得到的数组，n为字符串长度。
tCellType tm = nData[list[0]]；
for（i = 1； tm&&i
{tm&=nData[list[i]] >>（i）；}
if（tm） {//处理找到的记录}
举例：假如电话号码为“13511051123”，如果用户输入的待查找字符串为“105”，则需要判断nData[1]| （nData[0]>>1）|（nData[5]>>2）显然nData[1]在第4位上为1；nData[0]在第5位上为1，右移一位变成第四位；nData[5]在第6位上为1，右移二位变成第四位；相与后仍然为真。
假如用户输入的为“15”，而nData[5]仅仅在2、6的位置上为1，右移一位变成第1、5位，显然nData[1]在1、5位上均为0，相与后仍然为0。
其他说明：实际应用中可以通过一定的方法记录结果，新的查找基于上一次的查找结果进行查找，而没有必要对所有记录重新查找。
第15篇
关于树叶质量的建模与分析
封锁嫌疑犯的数学建模方法
正倒向随机微分方程理论及应用
数学建模与数学实验课程调查报告
基于肤色模型法的人脸定位技术研究
生猪养殖场的经营管理策略研究
从数学建模到问题驱动的应用数学
大学篮球教练能力评价的机理模型
基于WSD算法的水资源调度综合策略
关于地球健康的双层耦合网络模型
多属性决策中几种主要方法的比较
塑化剂迁移量测定和迁移模型研究进展
基于信息熵的n人合作博弈效益分配模型
混合动力公交车能量控制策略的优化模型
垃圾减量分类中社会及个体因素的量化分析
随机过程在农业自然灾害保险方案中的应用
“公共自行车服务系统”研究与大数据处理
天然气消费量的偏最小二乘支持向量机预测
微积分与概率统计——生命动力学的建模
美国大学生数学建模竞赛数据及评阅分析
微积分与概率统计——生命动力学的建模
在微积分教学中融入数学建模的思想和方法
2015“深圳杯”数学建模夏令营题目简述
字符串匹配算法在DNA序列比对中的应用
差分形式的Gompertz模型及相关问题研究
小样本球面地面条件下的三维无源定位算法
数学建模思想渗入代数课程教学的试验研究
基于贝叶斯信息更新的失事飞机发现概率模型
基于人体营养健康角度的中国果蔬发展建模
关于数学成为独立科学形式的历史与哲学成因探讨
深入开展数学建模活动,培养学生的综合应用素质
完善数学建模课程体系,提高学生自主创新能力
利用动态贝叶斯网构建基因调控网络的研究进展
地方本科院校扩大数学建模竞赛受益面的探索
城镇化进程中洛阳市人口发展的数学建模探讨
基于TSP规划模型的碎纸片拼接复原问题研究
卓越现场工程师综合素质的AHP评价体系研究
基于Logistic映射和超混沌系统的图像加密方案
嫦娥三号软着陆轨道设计与控制策略问题评析
嫦娥三号软着陆轨道设计与控制策略的优化模型
微生物发酵非线性系统辨识、控制及并行优化研究
含多抽水蓄能电站的电网多目标运行优化研究
连接我们的呼吸:全球环境模型的互联神经网络方法
垃圾焚烧厂周边污染物浓度的传播模型和监测方案
以数学建模竞赛为切入点,强化学生创新能力培养
一种新的基于PageRank算法的学术论文影响力评价方法
基于视频数据的道路实际通行能力和车辆排队过程分析