匹配算法论文范文

匹配算法论文范文第1篇

关键词：论文 相似度 匹配 算法

1 概述

近年来，随着网络技术的发展与普及，人们通过互联网获得信息更加便捷。而很多专业性的论文也能够在互联网上进行检索。在校学生或社会上的一些工作人员在发表专业论文时，往往通过互联网查阅相关资料，但有些人为了能够尽快直接抄袭或剽窃他人论文。各高校每年有大量的毕业生需要写毕业论文，而社会上每年也会有大量的论文在公开期刊杂志上进行发表。如此多的论文如何检测其是否含有抄袭或剽窃现象呢？单单依靠人们对每一篇论文进行审查肯定是行不通的，这就要借助于现代化的手段以提高相应的审查效率。

设计和开发一种好的论文相似度算法可将待发表的论文与已有论文进行智能比对检查，若发现雷同现象可及时通知发表人员做进一步修改。从而减少甚至避免在社会上出现的专业论文抄袭现象。

2 算法设计

因为每年会产生大量的论文，因而已有论文的数量非常巨大，这就要求比对算法要尽可能的简单，从而达到较高的执行效率。

首先对已有论文进行分类整理，以建立已有论文库。对已有论文按照发表年份、专业类别、出版社进行分类收集和存储。然后将论文库中的论文与待进行逐一比对审查。

待与已有论文进行匹配时，具体算法步骤如下：

2.1 待审查论文文档预处理

首先提取待审查论文的文本内容，将其进行段落划分。段落划分时，要将相邻较小的段落合并为一个较大的段落；过大的段落也要分解为多个较小的段落。如规定有效段落中句子的数量应大于5并小于60，那么论文中如果有两个相邻的段，其中一段仅有4个句子，则该段应与另一段进行合并，从而合并为一个有效段落；但如果论文中有一个段包含了70个句子，则该段应分解为两个有效段落：其中一个有效段落包含30个句子，另一个有效段落包含40个句子。段落划分后，对有效段落进行逐个顺序编号。

2.2 有效段落匹配

将待审查论文中划分好的有效段落与另一篇论文进行一次匹配。匹配时按先后顺序读取有效段落中的句子，从句子中随机抽取一定数量的连续字符，将其与另一篇论文进行完全字符串匹配，如果完全相同则记录该句，然后继续读取下一句，同样随机抽取相同数量的字符串与另一篇论文进行完全字符串匹配，并记录匹配结果。依次进行，直至段落结束，统计该段落中记录下来句子的数量，将其除以段落总的句子数量，得出该段落的匹配相似度。

2.3 论文相似度计算

段落匹配结束后，选出段落相似度最大的两个段落，将这两个段落中记录下来句子的数量，除以这两个段落总的句子的数量，视为该论文的相似度。如果该相似度值较大，则可视为论文中的段落有一定的抄袭现象。需相关人员做进一步审查核实。

3 算法实现

算法采用面向对象的思想，将具体的算法过程与功能封装在相应的类中。主要的类有：

Paper类：表示论文，含有年份、专业类别、出版社、作者名称，文档内容等属性。

PagerList类：用来实现论文的分类整理，含

有add（Pager p）和remove（Pager p）方法可在不同类别中添加或移除论文。

Paragraph类：用于论文段落的划分，其中ListdivideToParagraph（Paper p）方法负责将论文划分成有效段落，各个段落保存在一个字符串列表中。

CheckPager类：用于论文的相似度比较，其中的float check（Paper p1，Paper p2）方法负责将两篇论文进行匹配，匹配结束后返回相似度值。

其具体实现的流程如上图所示：

4 总结

由于每年会有大量的论文得以公开发表，因此已有论文的数量逐年增多，因此在算法设计时应着重考虑系统的审查匹配效率。该算法在论文匹配时主要以有效句为单位进行字符串的完全匹配比较，虽然精度上不是很高但可满足对大量论文进行快速匹配的效率要求，以提供一种简捷的辅助审查手段。在算法实现时还可采用多线程的机制，以能更好的被现今主流的多核CPU所支持，从而进一步提高匹配算法的执行效率和程序运行的稳定性。

参考文献：

[1]巫喜红，凌捷.BM模式匹配算法剖析.计算机工程与设计，第28卷第1期.2007.

[2]娄正良，刘昌平，白洪亮，邹明福.汉字串的模糊匹配算法.微电子学与计算机，第21卷第4期.2004.

[3]潘群娜.基于模式匹配KMP算法的探讨.科技信息（科学教研），第13期.2007.

[4]李容.Visual C# 2008开发技术详解.电子工业出版社，2008.

作者简介：

匹配算法论文范文第2篇

【关键词】深度挖掘匹配算法 毕业论文管理 应用

在毕业论文管理工作不断加强的情况下，注重管理模式的更新和合理选用，提高匹配算法的针对性，才能真正提高高校教务管理水平。因此，对深度挖掘匹配算法在毕业论文管理中的应用有比较全面的了解，才能为高校教务管理工作提供可靠参考依据。

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-），女，江西省南昌市人。工程硕士学位。现为江西交通职业技术学院副教授。研究方向为大数据、系统集成、智能化技术。

作者单位

匹配算法论文范文第3篇

关键词：双目视觉 立体匹配 导航定位 机器人

中图分类号：TP242 文献标识码：A 文章编号：1007-9416(2011)12-0059-02

引言

双目视觉是一种通过两幅图像获取物体三维信息的方法，具有通过二维图像认知物体三维立体信息的能力，其关键技术就是要解决两幅图像中对应点的匹配问题［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］薛长松．基于DM642的双目视觉控制系统研究［D］.河南大学硕士学位论文,2007.

作者简介

匹配算法论文范文第4篇

>> 算法与模型 快速图像匹配算法及其水下导航应用 刍议华帝战略选择与匹配 入侵检测模式匹配算法的研究与改进 论文相似度匹配算法的研究与实现 字符串匹配算法比较与分析 正向最大匹配分词算法的分析与改进 基于模拟退火算法的P2P借贷平台的债权匹配模型 基于轮廓特征点的三维模型相似性匹配算法 一种基于语言学特征的本体匹配改进算法 动作与音乐的节奏特征匹配模型研究 基于SIFT算法与RANSAC算法的X射线图像匹配研究 电影语言与影片风格的匹配问题 基于启发式算法的品牌模型的选择 软件可靠性模型选择的SRMS算法 双目立体视觉区域局部匹配算法的改进及其实现 软件工程过程模型及其选择 混合Copula模型选择及其应用 模式匹配查询算法研究 指纹快速匹配算法研究 常见问题解答 当前所在位置：l 德国

[4]

ZAKI T， ESSAADY Y， MAMMASS D， et al. A hybrid method ngramsTFIDF with radial basis for indexing and classification of Arabic document [J]. International Journal of Software Engineering and Its Applications， 2014， 8（2）： 127-144.

[5]

SIDOROV G， VELASQUEZ F， STAMATATOS E， et al. Syntactic dependencybased ngrams as classification features [C]// MICAI 2012： Proceedings of the 11th Mexican International Conference on Artificial Intelligence， LNCS 7630. Berlin： Springer， 2013： 1-11.

[6]

YI Y， GUAN J， ZHOU S. Effective clustering of microRNA sequences by ngrams and feature weighting [C] // Proceedings of the 2012 IEEE 6th International Conference on Systems Biology. Piscataway： IEEE， 2012： 203-210.

[7]

BOURAS C， TSOGKAS V. Enhancing news articles clustering using word ngrams [C] // DATA 2013： Proceedings of the 2nd International Conference on Data Technologies and Applications. London： dblp Computer Science Bibliography， 2013： 53-60.

[8]

GHANNAY S， BARRAULT L. Using hypothesis selection based features for confusion network MT system combination [C] // EACL 2014： Proceedings of the 3rd Workshop on Hybrid Approaches to Translation （HyTra）. Stroudsburg： Association for Computational Linguistics， 2014： 2-6.

[9]

SIDOROV G， VELASQUEZ F， STAMATAOS E， et al. Syntactic ngrams as machine learning features for natural language processing [J]. Expert Systems with Applications， 2014， 41（3）： 853-860.

[10]

HAN Q， GUO J， SCHTZE H. CodeX： combining an SVM classifier and character ngram language models for sentiment analysis on Twitter text [C]// SemEval 2013： Proceedings of the Second Joint Conference on Lexical and Computational Semantics （*SEM）， Volume 2： Proceedings of the Seventh International Workshop on Semantic Evaluation. Stroudsburg： Association for Computational Linguistics， 2013： 520-524.

http：//p.nus.edu.sg/～antho/S/S13/S13-2086.pdf

[11]

BESPALOY D， BAI B， QI Y， et al. Sentiment classification based on supervised latent ngram analysis [C] // CIKM 11： Proceedings of the 20th ACM International Conference on Information and Knowledge Management. New York： ACM， 2011： 375-382.

[12]

MILLER Z， DICKINSON B， HU W. Gender prediction on Twitter using stream algorithms with ngram character features [J]. International Journal of Intelligence Science， 2012， 2（4A）： 143-148.

[13]

WRIGHT J， LLOYDTHOMAS H. A robust language model incorporating a substring parser and extended ngrams [C] // ICASSP 1994： Proceedings of the 1994 IEEE International Conference on Acoustics， Speech， and Signal Processing. Washington， DC： IEEE Computer Society， 1994： 361-364.

[14]

HACIOGLU K， WARD W. Dialogcontext dependent language modeling combining ngrams and stochastic contextfree grammars [C] // ICASSP 2001： Proceedings of the 2001 IEEE International Conference on Acoustics， Speech， and Signal Processing. Washington， DC： IEEE Computer Society， 2001， 1： 537-540.

[15]

SIU M， OSTENDORF M. Variable ngrams and extensions for conversational speech language modeling [J]. Speech and Audio Processing， 2000， 1（8）： 63-75.

[16]

ZHOU S， GUAN J， HU Y， et al. A Chinese document categorization system without dictionary support and segmentation processing [J]. Journal of Computer Research and Development， 2001， 38（7）： 839-844. （周水庚，关佶红，胡运发，等.一个无需词典支持和切词处理的中文文档分类系统[J].计算机研究与发展，2001，38（7）：839-844）

[17]

GAO Z， LI X. Feature extraction method based on sliding window application in text classification[J]. Science & Technology Information， 2008（34）： 23-24. （高振峰，李锡祚.基于滑动窗口的特征提取方法在文本分类中的应用[J].科技信息：学术版，2008（34）：23-24.）

[18]

PENG H， LONG F， DING C. Feature selection based on mutual information： criteria of maxdependency， maxrelevance， and minredundancy [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2005， 27（8）： 1226-1238.

[19]

匹配算法论文范文第5篇

关键词： 模式匹配; 跳转距离; BM算法; BMH算法; BMHS算法; DBMHS算法

中图分类号：TP393 文献标志码：A 文章编号：1006-8228（2015）01-08-04

An improved pattern matching algorithm of BMHS

Zhang Huan， Hu Yong

（School of Electronic and Information Engineering， Sichuan University， Chengdu， Sichuan 610065， China）

Abstract： Pattern matching plays an important role in computer application. By analyzing BM， BMH， BMHS algorithm and their corresponding improved algorithms， a new improved algorithm（called DBMHS） based on BMHS is proposed. DBMHS takes full advantages of two ends string characters of pattern string， through comparing two ends character jump distance of pattern matching， jump distance is increased. The experiment results show that the improved algorithm significantly increases the jump distance of matching window， effectively improving the matching efficiency.

Key words： pattern matching; jump distance; BM algorithm; BMH algorithms; BMHS algorithm; DBMHS algorithm

0 引言

随着网络技术的高速发展，网络资源呈爆炸式增长。如何在网络数据中找到需要的信息，已经成为人们研究的热点问题。模式匹配算法在很多领域得到了较为广泛的应用，如入侵检测、计算机病毒特征匹配[1]、搜索引擎、文本挖掘等。目前关于模式匹配的算法有很多，其中最著名的是BM算法[2]。BM算法发展的过程中，1980年Horspol发表了改进与简化BM算法的论文，即Boyer Moore Horspoo（BMH）算法[3]，随后Sunday在1990年在BMH算法的基础上又进行了改进，提出了BMHS算法[4]。本文对现有几种典型模式算法进行分析，在BMHS算法的基础上进行改进，并进行试验和结果分析。

1 典型算法

1.1 BM算法

BM算法是由Boyer和Moore在1977提出的单模式匹配算法。它是目前实际应用中效率较高的单模式匹配算法之一。BM算法采用从右向左比较的方法，同时应用到了两种启发式规则，即坏字符规则和好后缀规则，来决定向右跳跃的距离。BM 算法中坏字符跳跃表和好后缀跳跃表的设计对提高BM算法效率有至关重要的作用。设文本T（长度为n），模式串P（长度为m）。

⑴ 坏字符跳跃表：当Pk≠Ti，即不匹配情况发生时，若此时Pk是P的末字符且Ti在模式串P中不出现，则下一次比较可以将匹配窗口直接移动m个位置后继续匹配;若Ti在模式串P中出现，则找到Ti在模式串P中出现的最右边的位置j（1≤j≤m-1），匹配窗口移动的距离为m-j（如图1所示）。

<E：＼方正创艺5.1＼Fit201412＼图＼zh图1.tif>

图1 坏字符规则

⑵ 好后缀跳跃表： 当Pk≠Ti（k<m）时，子串Pk+1Pk+2…Pm与Ti+1Ti+2…Ti+m-k是匹配的。若在模式串P的k位置左边有与Pk+1Pk+2…Pm相同的子串P1P2…Pm-s或Pk+1Pk+2…Pm的某个后缀Ps+1Ps+2…Pm与P的某前缀P1P2…Pm-s相同，即移动匹配窗口s位使Ti位置与该子串对应位置对齐，算法继续匹配（如图2所示）。

<E：＼方正创艺5.1＼Fit201412＼图＼zh图2.tif>

图2 好后缀规则

在匹配过程中，模式串P与文本T从右向左开始匹配，一旦发现不匹配，取好字符跳转和坏字符跳转之间较大的值作为模式串P的向右跳转距离。最理想的情况是每次匹配时文本T中第一个匹配的字符不存在于模式串P中，此时BM的算法的时间复杂度为O（n/m）;最坏的情况是文本T中有多个重复的字符，并且模式串P由m-1个相同的字符前加一个不同的字符组成，在这种情况下，BM算法的时间复杂度为O（mn）。

1.2 BMH算法

Horspool提出的BMH算法相对于BM算法更容易实现。BMH算法在预处理阶段只使用了坏字符跳跃表，无论文本中哪个字符造成了匹配失败，都将依据坏字符跳转表向右移动。BMH算法的基本思想是：①搜索文本时，从头到尾搜索，匹配时从右向左匹配。首先比较文本指针所指字符和模式串的最后一个字符，如果相等，再比较其余m-1个字符，无论文本中哪个字符造成了匹配失败，都将由文本中和模式串最后一个位置对应的字符来启发模式串向右移动，即当匹配开始比较TiTi+1…Ti+m-1和P0P1…Pm-1时，一旦发生不匹配，计算跳转距离skip（Ti+m-1），跳转后将模式串和文本对齐后重新匹配。②如果与P完全匹配，返回在T中对应的位置;③如果搜索完T仍然找不到完全匹配的位置，则查找失败[3]（如图3所示）。坏字符跳转计算公式：

<E：＼方正创艺5.1＼Fit201412＼图＼zh图3.tif>

图3 BMH算法

如图3所示，当文本中的与T2（‘d’）与模式串P中的P2（‘c’）发生不匹配时，计算跳转距离skip（T4），可以看出P1与T4相等，模式串P向右移动3个字符，即skip（T4）等于3，然后将P1与T4对齐后重新匹配。

BMH算法简化了初始化过程，匹配过程中的判断过程也作了简化，因为BMH算法只采用了BM算法的坏字符移动规则，并且将失配情况与偏移量的计算独立，不关心文本串中哪个字符造成了失配，只考虑用于模式串最右端对齐的文本字符来决定偏移量。该算法的理论时间复杂度与BM算法一致，但实际使用情况下较BM算法效率高。

1.3 BMHS算法

BMHS算法在BMH算法的基础上作了进一步改进，该算法的主要思想是：当开始匹配TiTi+1…Ti+m-1和P0P1…Pm-1时，若发生不匹配，考虑下一个字节的情况，即利用下一个字符Ti+m决定右移量。当下一个字符Ti+m不在模式串P中出现时，它的右移量比BMH算法的右移量大，跳过m+1个字符。通常情况下，BMHS算法比BMH算法快，但当Ti+m-1不在模式中出现，而Ti+m出现在模式串中时， BMHS算法[4]的效果就不如BMH算法[3]。匹配过程如图4。BMHS算法的跳转距离计算公式为：

<E：＼方正创艺5.1＼Fit201412＼图＼zh图4.tif>

图4 BMHS算法

如图4所示，当Ti+m出现在模式串P中时，如图4（a），将模式串P中的字符‘e’与Ti+m对齐;当Ti+m不存在于模式串P中时，如图4（b）所示，模式串P向右移动m+1个字符;而图4（c）中当Ti+m存在于模式串P中，而Ti+m-1不存在于模式串P中时，skip（Ti+m-1）等于5，而skip（Ti+m）等于1，Ti+m-1的跳转距离大于Ti+m的跳转距离，若还使用Ti+m为标准，则会降低匹配效率。在BMHS算法中最理想的时间复杂度为O（n/m+1）。

1.4 对各算法的已有改进

在模式匹配中存在两个基本定理：任何字符串匹配算法的最坏情况下必须检查至少n-m+1个文本中的字符;任何字符串匹配算法至少检查n/m个字符[5]。因此，没有一个算法比BM算法有更好的计算复杂度，但是我们可以通过改进来减少比较次数，提高匹配的平均性能。

基于以上三种模式匹配算法，近些年已经有多种改进算法。例如，利用统计字符在模式串中出现的频率来实现跳转[6];利用双字节计算偏移量[7-9];通过模式串P和文本T之间的关系来实现跳转[10];利用已匹配成功的字符串来进行跳转[11]，以及从模式串两端向中间匹配的方式[12]来改进模式匹配算法等。以上算法虽然减小了匹配次数，但相应增加了匹配的时间。接下来详细介绍一种通过双字节来计算偏移量的模式匹配改进算法。

2012年袁静波提出了一种改进的BMHS模式匹配算法[8]。该算法在BMHS算法的基础上利用文本T中与模式串P最后一个字符对应的字符Ti+m-1，以及Ti+m和Ti+m+1来实现跳转，模式串P和文本T从右向左匹配。以下是具体匹配过程。

第一步：当文本T和模式串P发生失配时，首先判断Ti+m是否在模式串中，若不存在直接跳过m+1的距离，如图5所示，文本T中的T4（‘d’）不在模式串P中，则模式串P向右移动m+1个字符。

<E：＼方正创艺5.1＼Fit201412＼图＼zh图5.tif>

图5 Ti+m不在模式串P中

第二步：当Ti+m在模式串中时，判断子串Ti+m Ti+m+1是否在模式串P中，若不存在，则跳过m+2的距离，如图6，子串“be”不在模式串P中，则模式串向右跳转m+2个字符。

<E：＼方正创艺5.1＼Fit201412＼图＼zh图6.tif>

图6 Ti+m Ti+m+1不在模式串P中

第三步：若模式串包含Ti+m Ti+m+1，则比较子串Ti+m-1Ti+m是否存在于模式串P中，不存在的话跳转m+1个字符，如图7，子串Ti+m Ti+m+1（“be”）存在与模式串P中，而子串Ti+m-1 Ti+m（“gb”）不存在与模式串P中，则模式串P向右跳转m+1个字符。

<E：＼方正创艺5.1＼Fit201412＼图＼zh图7.tif>

图7 Ti+m-1 Ti+m不在模式串P中

第四步：若Ti+m Ti+m+1和Ti+m-1 Ti+m都存在于模式串中，则取两者之间匹配的最大值进行跳转，如图8，可以看出，子串Ti+m Ti+m+1（“ea”）的跳转距离为2，子串Ti+m-1 Ti+m（“ae”）的跳转距离为3，取跳转距离较大的值，则模式串P应向右跳转3个字符。

<E：＼方正创艺5.1＼Fit201412＼图＼zh图8.tif>

图8 比较得到较大值进行跳转

在该改进算法中，模式串P最大的跳转距离为m+2，在理想的情况下该算法的时间复杂度为O（n/m+2）。

2 DBMHS算法

2.1 基本思想

通过观察BM，BMH和BMHS算法的匹配过程可以发现，这些算法在匹配窗口的首字符匹配均失败时效率最优。本文提出的DBMHS算法通过比较模式串P的第一个字符P0的跳转距离jump（P1）和在T中与模式串P最后一个字符对应的后一个字符Ti+m的跳转距离jump（Ti+m）来移动模式串P。跳转距离公式如下：

jump（P1）={k|Ti+k=P1，1≤k≤m}

jump（Ti+m+1）=m-k+1 k=Max{k|Pk=Ti+m+1，1≤k≤m}

2.2 匹配算法

显然，提高首字符匹配失败的概率是提高算法效率的关键之一。改进的DBMHS算法结合了BMHS算法特点，首先模式串P与文本T左端对齐，从右向左开始匹配，先检测T中与模式串最后一个字符相对应的字符Ti+m-1是否在模式串P中，若Ti+m-1不在模式串P中出现，则检测后一个字节Ti+m是否存在于模式串P中，若Ti+m不在模式串P中出现，则模式串P可以向右移动最大的距离m+1，否则移动距离为m。如图9、图10所示。

<E：＼方正创艺5.1＼Fit201412＼图＼zh图9.tif>

图9 Ti+m不存在于模式串P中

<E：＼方正创艺5.1＼Fit201412＼图＼zh图10.tif>

图10 Ti+m存在于模式串P中

若Ti+m-1与模式串P中对应的字符相匹配，则接着匹配余下的字符，一旦发生不匹配的情况，则检测Ti+m是否存在于模式串P中，若不存在，则模式串P直接向右移动m+1的距离，若存在则计算Ti+m的跳转距离，然后计算模式串P中第一个字符P0的跳转距离，比较这两个跳转距离，选择较大的跳转距离作为模式串P的实际跳转距离。从图11可以看出，若使用Ti+m进行跳转，则模式串P的跳转距离为1，若使用模式串P的第一个字符P0进行跳转，则模式串的跳转距离为2，通过比较，使用P0的跳转距离可以使模式串P尽量的向右移动。需要注意的是，若模式串P或文本T中同一个字符出现多次，在计算跳转距离时，需分情况处理，例如，若匹配Ti+m时，P中出现多个与Ti+m相同的字符，则选择最右端的字符与Ti+m对齐;若是在匹配P0时出现这种情况，则选择T中靠左的字符进行对齐。

<E：＼方正创艺5.1＼Fit201412＼图＼zh图11.tif>

图11 P1跳转距离大于Ti+m

若算法在匹配时自右向左均匹配成功，则此时找到一次完全匹配，算法结束。DBMHS匹配算法伪代码描述如表1。

表1 DBMHS匹配算法伪代码

[输入：文本串T，模式串P

输出：文本串T中是否存在子串P＼&While i≤T

Do If Ti+m-1 Pm

If Ti+m-1P

If Ti+mP Then MOVE m;

Else MOVE m+1;

Else

If Ti+mP Then MOVE m+1;

Else MOVE max（jump（P0），jump（Ti+m））;

Else If Ti+kPk

If Ti+mP Then MOVE m+1;

Else MOVE max（jump（P0），jump（Ti+m））;

Else If Ti。。。i+m-1= P0。。。m-1 Then Return true;

Return false;＼&]

2.3 算法分析

从BMHS算法的匹配算法可以看出，BMHS算法在比较时利用下一个字符Ti+m决定右移量，当Ti+m不在模式串P中出现时会跳转最大的距离m+1，但当Ti+m出现在模式串P中时，由于多进行了一次匹配，BMHS匹配算法的效果就不如BMH算法。因此，DBMHS匹配算法通过模式串两端的字符来充分利用Ti+m。当Ti+m出现在模式串P中时，计算Ti+m的跳转距离，并计算第一个字符P0的跳转距离，通过比较这两个字符的跳转距离来实现更大的跳转，这样不仅提高了Ti+m的利用率，而且获得了更高的匹配效率。

3 算法性能测试

本实验使用的计算机硬件平台为IntelPentium G2020处理器，4G内存，软件平台为Windows 7操作系统，Microsoft Visual Studio 2010集成开发环境。在此环境下分别对BMHS算法、IBMHS算法和DBMHS算法进行测试，IBMHS匹配算法为文献[8]中提出的对BMHS匹配算法的改进算法。

实验随机选取4个不同长度的文本串，实验文本字符集由大小写字母，数字和空格组成。模式串从文本串中随机提取。分别执行BMHS算法、IBMHS算法和DBMHS算法程序，统计不同长度文本串，不同模式串的情况下，算法的执行时间和匹配窗口的移动次数。每个算法分别执行10000次，运行时间取平均值。得到的数据如表2和表3。

表2 匹配窗口移动次数

[文本长度＼&模式串长度＼&BMHS＼&IBMHS＼&DBMHS＼&匹配次数＼&匹配次数＼&匹配次数＼&2481＼&12＼&259＼&183＼&202＼&1138＼&10＼&114＼&90＼&95＼&555＼&14＼&44＼&32＼&35＼&225＼&12＼&16＼&13＼&14＼&]

表3 匹配时间

[文本长度＼&模式串长度＼&BMHS＼&IBMHS＼&DBMHS＼&匹配时间＼&匹配时间＼&匹配时间＼&2481＼&12＼&0.218＼&1.482＼&0.218＼&1138＼&10＼&0.094＼&0.671＼&0.094＼&555＼&14＼&0.031＼&0.218＼&0.031＼&225＼&12＼&0.016＼&0.094＼&0.016＼&]

由表2和表3可以看出，本文提出的算法相比传统的BMHS算法有较大的改进。例如第一次匹配，DBMHS匹配次数较BMHS减少了约28%，并且文本长度越长，减少的匹配次数就会越多。此外，DBMHS在匹配用时上与传统的BMHS算法比较接近。虽然IBMHS算法的匹配次数少于DBMHS算法，但是匹配时间几乎是DBMHS算法的7倍。从效率上来说，DBMHS算法要优于其他算法。

4 结束语

本文通过分析BM，BMH和BMHS模式匹配算法，提出了一种改进的算法DBMHS。由于DBMHS算法充分利用了模式串两端字符，通过实验可以证明，该算法的匹配效率得到了显著提升。下一步的研究将考虑该算法应用在多模式匹配中，并利用语言学中的知识，如模式串与文本结构，使其性能更加优越。

参考文献：

[1] Yang Wang and Hidetsune Kobayashi. High Performance Pattern

Matching Algorithm for Network Security. IJCSNS International Journal of Computer Science and Network Security，2006.6（10）：83-87

[2] Boyer R S，Moore J S.A Fast String Searching Algorithm[J].

Communications of the ACM，1977.20：762-772

[3] Horspool N R. Practical Fast Searching in Strings[J]. Software

Practice and Experience，1980.10（6）：5012506

[4] Sunday D M. A very fast substring search algorithm[J].

Communication of the ACM，1990.33（8）：132-142

[5] 李雪莹，刘宝旭等.字符串匹配技术研究[J].计算机工程，2004.30

（22）：24226

[6] 刘胜飞，张云泉.一种改进的BMH模式匹配算法[J].计算机科学，

2008.35（11）：164-165

[7] 姚保峰，王磊.一种改进的BMH模式匹配算法[J].湖南工程学院学报：

自然科学版，2011.3：40-42

[8] Yuan J， Yang J， Ding S. An Improved Pattern Matching Algorithm

Based on BMHS[C]//Distributed Computing and Applications to Business， Engineering & Science （DCABES）， 2012 11th International Symposium on. IEEE，2012：441-445

[9] 王浩，张霖.基于坏字符序检测的快速模式匹配算法[J].计算机应用

与软件，2012.29（5）：114-116

[10] Shrivastava G， Jain A. A Review of Intrusion Detection Method

Based On Automatic Pattern Matching[J]. Computer Engineering，2012.1（1）：88-90

[11] Chen Q， Niu Y， Wang Z， et al. Improved BM Pattern Matching

Algorithm for Intrusion Detection[C]//Computational Science and Optimization （CSO）， 2010 Third International Joint Conference on. IEEE，2010.1：440-444

[12] Chao Y. A deterministic finite automata based on improved BM

匹配算法论文范文第6篇

关键词：入侵检测；免疫原理；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.

[8] Cantu-Paz E. Feature subset selection, class separability, and genetic algorithms[C]//Proceedings of the Genetic and Evolution? ary Computation Conf, 2004:959-970.

匹配算法论文范文第7篇

关键词：入侵检测；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年出生，博士，教授。主要研究方向为算法、数据库、网络安全。

王晓峰 女，1966年出生，博士，副教授。主要研究方向为信息安全。

匹配算法论文范文第8篇

关键词：模式匹配；藏文音节；BM算法

中图分类号：TP393.08

藏文网络舆情是当前必须关注的舆论涌现与信息传播现象。近几年藏文网络舆情的数量呈现递增的增长趋势，网络信息的传播途径也呈现出多样化和复杂化。由于藏文网络的这些显著的特点，藏文信息处理相对滞后于英文和中文等，短时间内迅速的获取大量信息则不容易。另，目前藏文网站大量的涌现，网页数量巨大，处理起来速度相对慢，以往藏文网络舆情页面的统计都是基于手工统计实现的，效率低，很难对网络舆情的变化做出快速响应。模式匹配技术是内容过滤的核心技术，是计算机信息技术领域研究的基础问题之一，研究敏感词作为模式串的藏文模式匹配算法具有重要的研究意义。

BM算法是Boyer和Moore提出的一种字符串快速匹配算法。其基本思想是从右向左的把模式字符串同文本做比较。开始时仍是P的最左边与T的最左边对齐，当在某一趟比较中出现不匹配时，计算模式串右移的距离，把模式串向右移动该距离，再进行从右至左的匹配，同时应用到了两种启发式规则，即坏字符规则和好后缀规则，来决定向右跳跃的距离。

1 BM算法在藏文中的改进

藏文字符匹配中应用BM算法时，必须结合藏文文字特征，对BM算法进行改进以符合藏文的特点，提高匹配效率。

1.1 藏文文字结构及编码特点

藏文是由多个基本字符通过纵向叠加组成的字符串，构成一个完整藏文词素的基本单位是由藏文中的“音节分割符tsheg bar”来确定。一个或多个音节构成一个藏文词。音节，则是由音节分割符（音节点）或者其他藏文标点符号来划分的。一个音节中基字符是不能被省略的，其余相关构件都可以减少掉一个或几个这样仍然可以成一个音节（藏字）。七个构件中辅音字母在各部位依据藏文语法要求都有一定限制并不是所有的辅音字母都能够做前加字或者后加字等。

藏文在计算机中进行编码时一个音节需要用多个编码来表示，长度是不定的，这使得藏文在信息系统中的实现非常的麻烦。

（1）国内的几种藏文处理系统将藏文作为整字给予编码。将藏文垂直组合的部分作为一个处理单元编码（预先进行垂直组合，称为垂直预组合，垂直预组合后的字符称为藏文字丁），比如北大方正的报刊排版系统、华光藏文排版和同元藏文处理系统、激光照排系统等，这几个系统都有各自的编码方案这类编码采用双字节进行编码。这样，具有完整构件组合的藏字（即一个音节最多由4个字丁组成）。因此，国内的这几种编码方式一个音节就最多有4个编码。国家标准的扩A和扩B编码方案采用的是也是整字编码方案。

（2）国外的几种藏文编码方式也是采用整字编码方案，但是将带元音的字丁与元音分离后分别进行了编码。一个藏文音节最多就由5个字丁组成，即一个藏文音节由5个编码组成。

（3）ISO/IEC 10646藏文基本集是国际标准的编码方案，它完全将藏文视做拼音文字，字丁则是通过字母的动态组合实现的。即将一个藏文音节拆分成不同构件的独立的部分，对每一个构件都单独进行编码。采用国际标准后一个藏文音节最多由7个编码组成。基于不同编码的方式使得一个音节的编码个数不同，即使具有相同编码个数的同一种编码方案，由于编码范围不同编码值也将不一致。1997年，我国的藏文基本字符集被收入了国际标准ISO/IEC 10646《信息技术通用多八位编码字符集》。藏文编码标准得到了统一。故本匹配算法以小字符集国际编码标准（ISO/IEC 10646）编码进行讨论。

依据藏文采用小字符集编码中音节字的特点：

（1）具有完整构件的音节具有7个编码且每个编码都是两个字节，则对一个藏文音节字的表示则最多需要14个字节，最少也需要两个字节。匹配过程中只有在一个音节的所有字节都相等的情况下，一个藏文音节才匹配成功。

（2）藏文音节与音节之间由音节点分割，在小字符集中该音节点为0X0F0B。

1.2 基于藏字特征改进的BM算法

改进后的BM模式匹配算法的具体思路：

（1）用模式串P的尾字符与文本串T进行比较，结果失配，且文本串字符不为音节点，则模式串P右移到下一个出现的音节点处在新的位置继续比较。

（2）用模式串P的尾字符与文本串T进行比较，结果匹配，再把模式串第一个字符与文本串T比较，结果匹配。则将模式串与文本串T由右向左依次比较。当所有字符都能匹配上时，则找到字符串返回查找结果并结束；如果模式串第一个字符与文本串T比较，结果不匹配，则：

求move（o）=First（OT）-First（OP），将模式串移动move（o）个字符。

其中First（OT）：表示文本串T出现的第一个音节点；First（OP）：表示模式串P出现的第一个音节点。move（o）：距离差值；

（3）用模式串P的尾字符与文本串T进行比较，结果匹配，再把模式串第一个字符与文本串T比较，结果匹配。则将模式串与文本串T由右向左依次比较。如果在模式串P的某一字符x失配，则转4；

（4）如果失配的字符x在模式P中没有出现，则：

求：First（x）：从x起始的字符到第一个出现的音节点的距离。那么从字符x开始的m（模式串的长度）+First（x）个文本显然不可能与P匹配成功，直接全部跳过该区域即可，则模式串移位m+First（x）个位置；

（5）如果失配的字符x在模式P中出现，则：以该字符进行对齐。设move（x）为P右移的距离，m为模式串P的长度，max（x）为字符x在P中最右位置。作模式串移位：[m-max（x）]+First（x）。

通过上对面算法的分析，我们可以看出，改进后的BM算法可以减少比较的次数，提高匹配的速度。

2 结束语

越来越多的藏文出版作品在以数字化方式存储，网络上的藏文资料也日益增多，改进针对西文以及中文的搜索算法，寻找适合藏文文字特点的字符查找算法是值得研究的。改进的BM模式匹配算法就是利用藏文字符构字特征以及编码特点，改变了BM算法的比对方式，从而提高匹配的效率。

参考文献：

[1]江涛，于洪志.基于藏文文本的网络舆情监控系统研究[A].全国计算机安全学术交流会论文集[C]，2006.

[2]闵联营，赵婷婷.BM算法的研究与改进[J].武汉理工大学学报，2006（03）：528-530.

[3]殷丽华，张冬艳，方滨兴.面向入侵检测的单模式匹配算法性能分析[J].计算机工程与应用，2004（24）：46-47.

[4]扎西加，珠杰.面向信息处理的藏文分词规范研究[J].中文信息学报，2009（04）：113-117.

[5]严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，1999.

作者简介：春燕（1977-），女，藏族，讲师，硕士研究生，主要研究方向：藏文信息处理、数据挖掘。

作者单位：大学藏文信息技术研究中心，拉萨 850012

匹配算法论文范文第9篇

【关键词】嵌入式；Linux；指纹识别；MiniGUI

0.引言

计算机的发展使指纹识别技术得到高速发展。目前指纹识别系统的发展以嵌入式系统为主，嵌入式指纹识别系统需要构建可靠的嵌入式平台，而且由于资源有限，对指纹识别算法要求较高。嵌入式指纹识别系统体积小、灵活性高、操作简单，能够很好的满足实际需要。与其它生物识别技术相比，指纹具有较高的稳定性、独特性。指纹绝对可以通过每个指纹的细节特征进行区分。

1.指纹识别系统设计方案

本系统以S3C2410微处理器为核心，扩展了SDRAM、RAM芯片、FLASH芯片、RTL8019AS网卡芯片。S3C2410的通用IO口与液晶显示屏、键盘相连，完成与用户的交互操作，构成了了本系统的硬件开发板。指纹采集模块采用的是Veridicom公司的FPS200指纹传感器模块，并通过USB接口与开发板相连，实现数据指令的传送，从而在开发板上完成指纹的获取、预处理、提取特征值、特征值对比等功能。系统机构框架见图1。

操作系统启动后对FPS200指纹模块进行初始化，然后通过USB将采集到的指纹图像传送到ARM开发板上，应用程序对读入的指纹图像进行处理并，最后进行指纹的匹配。

2.嵌入式linux开发平台搭建与实现

2.1嵌入式系统概述

嵌入式操作系统（Embedded Operating System，简称EOS）负责嵌入式系统的全部资源的分配和调度工作，管理任务和并发操作，为开发人员提供统一的接口和硬件抽象。嵌入式操作系统除具备任务调度、中断处理、文件操作等一般操作系统所具有的最基本功能外，还具有小巧、稳定可靠、可移植性好、可扩展性好、具有强大的网络功能及硬件支持等优点。

2.2嵌入式Linux交叉编译环境的搭建

交叉编译需要一个高性能的宿主机，用来编译应用开发的源程序，然后可以生成目标平台的可执行程序。建立交叉编译环境需要完成两件事：宿主机的选择和交叉编译环境的建立。

2.2.1宿主机的选择

嵌入式Linux开发的宿主机可以选择安装Linux操作系统的主机或是装有Linux虚拟机的主机。本文选择Fedora12作为宿主机的操作系统，Linux宿主机与目标机通过两种方式进行连接：（1）网络方式，通过TFTP和NFS服务；（2）串口方式minicom。

2.2.2交叉编译环境的建立

交叉编译就是在一个平台上编译生成可在另一个平台上执行的程序。平台是指体系结构（Architecture）和操作系统（Operating System）。为了Linux的应用程序的开发，构建一个多体系结构的交叉编译环境是非常必要的。

2.5设备驱动程序移植

在Linux系统下将设备分为三类：字符设备，块设备和网络设备。字符设备驱动程序与访问普通文件一样，需要至少实现open、close、read和write等方法，但是普通文件可以前后移动的访问，字符设备通常只能顺序访问。块设备与字符设备类似，块设备上可以容纳文件系统。但是块设备和字符设备在内核中数据的管理方式不同，内核与驱动程序之间的软件接口也不同。

Linux设备驱动的移植分为两种，一种是内核已经支持的硬件，这些设备驱动移植比较简单，只需在内核配置时加入该设备，并添加相应的初始化代码即可。另一种是内核不支持的硬件，首先要编写相应的驱动程序，然后通过交叉编译生成驱动模块文件，在应用程序使用该驱动时加载驱动模块。与U-Boot的移植一样，Linux内核也需要对K9F1208U0B NAND Flash、RTL8019AS网卡进行驱动的移植，而且内核中还要加入LCD、触摸屏和USB驱动的移植。

2.6根文件系统的设计

嵌入式Linux可以支持的多种文件系统，最常用的是Cramfs、YAFFS、JFFS等。

3.指纹识别算法研究

指纹识别算法是将采集到的指纹与指纹模板进行对比，判断它们是否为同一枚手指。目前的指纹识别过程如图3所示。系统从指纹传感器获得原始指纹图像，首先要对采集的图像进行预处理，将噪声等无用信息去除，并且将有用信息加强。其次对处理后的图像提取特征，获得能够区分指纹的唯一性特征。注册指纹是把得到的指纹加入到指纹库中。最后对指纹匹配，通常为了节省查找时间，会将指纹数据库分类。

3.1指纹图像预处理

指纹模块采集到的指纹图像是灰度图像，这些灰度图像中通常包含有噪声等无用信息，而这些无用信息严重影响到指纹识别系统的准确性，为了提高系统的性能需要对指纹图像进行预处理。指纹图像预处理包括提取指纹图像中指纹的有效区域，去除有效区域中的噪声，加强指纹有效信息，为指纹特征提取和最终的识别提供好的条件。

3.1.1归一化

归一化的算法描述如下：假设指纹图像大小为N×N，G（i，j）为像素点（i，j）的灰度值，N（i，j）为归一化后像素点（i，j）的灰度值，对指纹图像中的像素点依次应用公式（1）实现归一化。归一化处理调整图像灰度值的均值和方差到一个希望的范围内，保证采集到的指纹图像的灰度值能够在同一个级别上，为以后的处理算法提供一个好的条件。

3.1.2分割

指纹模块采集到的指纹图像包括指纹和背景两部分，所以在预处理时需要将背景分割出去，只留下指纹部分。分割操作就是将指纹图像的有效指纹区域保留下来进行后续的预处理操作。

3.1.3基于点方向的二值化

通常在对指纹图像进行二值化之前要先完成滤波去噪，如卷积法、Gabor等，但是这些算法运算量较大，不适宜在嵌入式应用系统中使用，所以本文中采用将滤波和二值化合并的算法，即基于点方向的二值化，能够在较小的运算代价下去除一定的粘连和连接断文等。二值化操作就是将255级灰度图像转化为只显示黑和白两种颜色的指纹图像。

3.1.4去噪

虽然二值化能够消除一些噪声干扰，但是可能会引入新的噪声，而且指纹纹线上可能会存在少数气泡噪声，指纹图像边缘上也会有部分毛刺存在。这些噪声会对后面的指纹特征提取造成影响，所以在完成二值化操作后需要进行一步去噪的操作，删除指纹图像边缘的毛刺和对指纹纹线上的气泡进行填充。

3.1.5细化

经过上面几步的处理，基本得到了指纹纹线，但是纹线的宽度却是不均匀的，原因可能是采集指纹图像时手指压力大小不同或是手指不干净等噪声影响，纹线不均匀会给指纹特征提取带来比较大的误差。对图像进行细化的算法有很多，常用算法有：Hitditcb算法、E.S.Deutsch算法和OPTA算法。

3.2指纹特征提取

在进行指纹特征提取前会利用纹线跟踪算法对指纹图像中纹线进行修复，修复后的指纹图像会提高指纹特征提取的效果和效率，但是如果指纹图像噪声干扰严重时，指纹修复就是一件非常困难的任务，对于不同的指纹图像，指纹修复算法效果差别会很大，从而影响到指纹识别算法。还有一种处理方法是，对细化后的指纹图像直接进行指纹特征提取，当然提取的特征中会包含大量的伪特征，但是这样的提取过程简单，简化了算法的复杂度；然后再根据实际中真实特征点和伪特征点的特点，对提取的特征进行筛选，删除伪特征，最终得到真实有用的特征点集。

3.3指纹特征匹配

指纹匹配是指纹识别系统非常关键的一步，目前已经做了大量的研究，常见的匹配算法有基于点模式的指纹匹配算法，基于纹理结构的匹配算法，基于纹线的匹配算法等。点模式匹配算法因其不高的时间和空间复杂度，非常适合在嵌入式环境下使用。本文就采用基于二维群集的点模式匹配算法进行指纹匹配。

4.结束语

本设计在S3C2410实验箱平台上实现基于Linux操作系统的指纹识别系统的设计与实现，采用先进的FPS200指纹采集模块，设计了良好的图形交互界面。本文对基于嵌入式linux的指纹识别系统进行了深入研究，硬件平台采用基于ARM9架构的S3C2410嵌入式平台。对指纹识别算法进行了深入的研究，选择和改进后的算法更适用于嵌入式平台，算法主要分为三个部分：指纹图像预处理、特征值提取和指纹匹配。 [科]

【参考文献】

[1]颜永龙.嵌入式自动指纹识别系统若干问题的研究[D].重庆：重庆大学硕士学位论文，2008.

[2]陈梁.嵌入式指纹识别系统研究与实现[D].南京：南京航空航天大学硕士学位论文，2007.

[3]丁飞.基于的指纹识别系统的研究与实现[D].广州：华南理工大学硕士学位论文，2007.

匹配算法论文范文第10篇

关键词：浮动车；GPS；地图匹配；轨迹点

引言

建立城市交通综合信息平台，通过对庞大的城市交通网络中的实时交通信息进行深入分析，为改善城市交通信息服务水平，提高决策科学性，缓解城市交通拥堵提供了基础。交通综合信息平台的数据支撑来源于交通基础信息的实时采集，科学决策的依据在于数据分析的快速、准确。

GPS浮动车是获取道路实时车速便捷有效的方法，可以通过车载GPS定位信息获取道路实时车速及运行状态（拥堵、畅通、缓行），其作为一种便捷廉价、可操作性高的车速采集手段已经被各城市普遍采用，特别是公交车与出租车安装车载GPS设备最为常见。通过对公交车及出租车的GPS返回数据与城市道路网的匹配、分析来获取道路的实时车速，进而实现对道路状态的有效判断。因此确保GPS浮动车轨迹点数据与信息平台电子地图快速、准确匹配是管理决策的基础，研究准确适用的GPS浮动车轨迹点数据的地图匹配算法是非常重要的。

1 GPS数据的地图匹配原理

地图匹配（Map-Match）简称MM技术，就是利用电子地图的路网信息和GPS数据来实行对车辆行驶准确位置的确定，它是一种定位误差修正技术。

浮动车所上报的GPS数据中包含有经纬度等地理信息，但这些GPS坐标只能反映车辆位置情况，而不能与实际路网路段直接相关联。因此，车辆在路网中行驶的情况，必须要依赖于地图匹配算法来完成车辆位置信息与路网位置的关联。

地图匹配算法的直接目的是将GPS测得的车辆位置或行驶轨迹，与现有的电子地图道路路段数据进行比较，继而找到车辆所处的道路，计算出浮动车辆在道路上所处的位置。一般地图匹配过程有以下几个步骤：

（1）通过对获取的GPS数据的预处理及匹配模板的分析、描述，提取出点和道路的轨迹特征。

（2）根据对地图匹配规则的制定，计算出GPS样本和匹配模板两者的相似度、匹配度。

（3）选取待匹配点距离最近或者是轨迹相似度、匹配度最高的道路曲线模板，可更正匹配样本的位置或轨迹，作为匹配结果[1]。

图1 地图匹配原理图

地图匹配原理一般可分成两个过程来表达：即寻找GPS待匹配点最可能归属的道路，并将GPS浮动点投影到这条它所归属的道路上面。

以上两个过程的关键在于需找GPS待匹配点最可能归属的道路，基本的思想即是在GPS点四周一定范围内搜索所有的可匹配点，然后根据匹配度计算，淘汰匹配度较低的点，选出最优点。并将此最优点作为GPS浮动车车辆的当前行驶路线。这样，寻找最优点成为算法性能优劣的关键所在，如果搜索范围过大，需对周围各条道路一一筛选，增加了算法计算量，导致匹配速度缓慢。反之，如果搜索范围过小，则有可能未能准确寻找到最佳匹配点，出现匹配错误，降低匹配的准确率。

2 基于GPS轨迹点的浮动车地图匹配算法

可实现地图匹配的算法很多，在GPS数据量极大，且算法应用的场景为实时车速展示，需要选择一个合适的方法，保证匹配的准确性和匹配速度。因此文章提出的地图匹配算法是基于GPS点到校正点的匹配，并且利用连续几个GPS点的轨迹确定结果，最终获取较为正确的路网匹配结果。

2.1 网格匹配

Step1：计算GPS点所归属网格。

当在系统中导入GPS数据信息后，可从这些原始数据中提取出坐标信息。可设为（x，y）。然后对该GPS坐标信息进行可信度检测，首先取网格划分中最大和最小的两个坐标点，其中最大的坐标点位于地图的右上角，假设为（xm，ym），最小的坐标点则位于地图的左下角，假设为（xn，yn）。如果待匹配点坐标（x，y）满足以下条件：

则认为该GPS点在研究坐标范围之内，转到下一步计算。

Step2：搜寻所在网格匹配

根据该GPS点的坐标信息，在网格列表中搜寻其所属的网格。假设网格编号为G0，若

（x，y）∈{G0}

则判定该点位于G0网格内。

在搜寻到所在网格后，将所在网格G0中的所有校正点加入到待匹配集合。但在该匹配中需要注意的是当GPS点与网格边距离小于1/3时，则需要将其相邻网格（G1……G8）所包含的校正点一并加入待匹配集合，进行匹配度计算。（见图2）

2.2 节点匹配

Step1：计算GPS与路段的距离和方向差

在网格匹配中搜寻出的校正点集合被称为待匹配集合。需要将GPS点与带匹配集合中的各个校正点进行匹配，找寻出最佳匹配点。

计算GPS点与各待匹配校正点之间的距离。设GPS点坐标为（x，y），GIS校正点坐标为（xr，yr），由于两点距离较近，两点接近于平面，则可根据平面距离公式

得出GPS点与各校正点之间的距离d。

计算GPS点与路段各校正点之间的夹角。取GPS数据的角度为？渍0，再与网格内的GIS路段校正点的切线方向角度？渍r（取正北方向为0°）求差值。可得出GPS点与路段方向的夹角α。

Step2：匹配度计算

匹配度是判断校正点优劣的重要标准，是描述GPS点与一条道路的匹配程度，用实际算法所求得的数值进行量化，匹配度越大，就认为发出这个GPS数据的浮动车越有可能位于这条道路。对于匹配度的计算，主要考虑的是GPS与路段的距离及其与路段的夹角。

图3 GPS点匹配

Step3：Confidence Point（CP点）判断

针对GPS浮动车地图匹配的特殊性，本文提出了Confidence Point判断。所谓Confidence Point，就是可信点[8]。判断是否为CP点，主要判断其所有匹配点是否位于同一路段。

由于浮动车地图匹配的最终目的是为城市各条道路得到路段平均速度提供起点、终点以及时间信息，而当车辆距离路口（包括城市立交路口、普通平面交叉路口、主辅路的出入口等）比较近时，由于GPS浮动车减速、并线等驾驶行为导致GPS数据中的方向信息等变化较大、准确性降低，使得系统比较难以确定车辆的准确位置。 但是考虑到GPS浮动车地图匹配的一个最终目的是获取路况实时信息，因此，如果无论车辆当前在哪条道路上行驶，只要能确定车辆必定通过或者必定离开某个路口，就可以根据GPS浮动车辆的下一个GPS定位数据确定其这一段时间的行驶轨迹。

因此当GPS数据处于路口节点或分合流点附近时，它所对应的匹配点并不在同一路段上，系统将这样的数据判定为非CP点，作为延迟匹配点，利用行驶路径进行匹配。反之，若GPS数据所对应的匹配点位于同一路段，则系统将其判定为CP可信点，对其各匹配点进行匹配度计算。

其中对于CP可信点，系统按照step3中匹配度计算中所确定的方法进行匹配度计算。取匹配度最大的点为最佳匹配点。对于非CP点，则转入下一步。

Step4：延迟匹配

对于上一步所提到的非CP点，并无法通过单一的GPS数据匹配来确定浮动车的确切位置，这时就需要通过相同浮动车的多个GPS数据来联合判断车辆的行驶路线轨迹。

图5 非CP点延迟匹配示意图

假设某浮动车连续的n个GPS数据组成的序列Pn（n=1，2，3，……，k），满足以下条件：

（1）P1点为CP点，P2为非CP点，且k小于延迟匹配的允许最大值；（2）Pk为已经确定的CP点，并能按照地图匹配方法正确寻找到最佳匹配点。

则可利用前后两个CP点P1和Pk，寻找这相邻两个CP点的最短路径L。再利用最短路径L对P2，P3，Pn-1进行匹配，去掉不属于L的匹配点，再取最大匹配度点作为最佳匹配点。

3 结束语

文章所使用的地图匹配方法通过获取GPS浮动车数据，利用GPS坐标信息，通过比对电子地图各条路段的地理信息，将浮动车位置关联到路网上。

研究表明，该匹配算法具有以下优缺点：

（1）匹配速度快。由于将电子地图网格化，避免了将GPS数据坐标与地图中所有节点坐标的一一进行计算，而是仅选取了比较小范围的节点进行匹配。提高了运算、匹配的效率。

（2）匹配精度较高。由于在匹配方法上采取了多种方法进行联合使用，针对不同位置的GPS数据点运用不同的匹配方法，保证了每个GPS数据点匹配的准确性。特别是基于连续GPS点轨迹来判断位置，使得匹配的结果更为准确。

重庆市政府在2011年开展“重庆市交通综合信息平台”建设，信息平台对重庆城区的干路网交通信息进行采集与汇聚。文章的研究依托交通信息平台的基础数据，研究成果应用于重庆市主城区路网运行情况的评估与监控，经过实测对比，验证了该算法的良好精度和适用性。

参考文献

[1]张其善，吴金培，杨康凯.智能车辆定位导航系统及应用[M].北京：科学出版社，2002.

[2]肖锋.面向道路交通状态监测的GPS与GIS数据预处理关键技术研究[D].重庆大学硕士毕业论文，2008.

[3]重庆市交通综合信息平台试点工程技术报告[R].2012.

[4]孙棣华，等.基于预处理的城市路网拓扑结构构建算法[J].计算机工程与应用，2008（08）.

[5]车莉娜.车辆导航定位中的关键技术研究[D].辽宁工程技术大学硕士论文，2008.

[6]Weiliang ZENG， Zhaocheng HE and Xiwei SHE. Data Repair Method for Real Time Urban Link Speed Estimation，ASCE2011.

[7]王华.GIS城市道路最短路径算法研究[J].测绘科学，2010.

[8]章威，等.基于大规模浮动车数据的地图匹配算法[J].交通运输系统工程与信息，2007（4）.

[9]程志华，刘小勇.基于GIS 的城市路网拓扑关系的自动建立及最短路径分析[J].新疆农业大学学报，2007.