模式匹配算法

模式匹配算法（通用11篇）

模式匹配算法 篇1

摘要：在长度为N的主串S中查找是否存在长度为M的模式串T, 叫模式匹配问题。对于N和M均非常大的情况, 概率算法求解此问题的效率比朴素算法和KMP算法要高。通过比较两个长度均为M的串的关联数是否相同, 来确定这两个串是否相同。如果某它们的关联数不同, 则这两个串一定不同;如果它们的关联数相同, 则它们不同的概率很小, 可忽略认为它们相同, 也可将它们按位比较以便准确判断它们是否相同。本文计算长度为M的串的关联数的算法复杂度为O (1) 。

关键词：概率算法,模式匹配,关联数,主串,模式串,时间复杂度

1 前言

给定的符号模式是否出现在是一个很长的文本中, 通常将此问题称为模式匹配。分析DNA序列和其他各种基因相关项目的结果, 涉及的算法学上的核心问题是模式匹配问题。求解模式匹配问题的常用算法有朴素算法和KMP算法。朴素算法的效率很低, 时间复杂度为O (n*m) [1,2,3,4,5]。KMP算法仅当主串与模式间存在许多“部分匹配”的情况下才能显示出它的高效率O (n+m) [1,2,3,4,5]。本文使用概率算法求解模式匹配问题, 此算法特别适用于模式串非常长的情形。

2 模式匹配问题的概率算法

2.1 算法的基本思想

模式匹配问题具体描述为, 在长度为N的主串S中查找是否存在长度为M的模式串T。概率算法求解模式匹配问题的基本思想是, 将主串S中每个长度为M的符号串关联一个数, 然后随着算法穿过S, 依次考虑每M个符号的块所关联的数与模式串T所关联的数是否相同。若某相邻M个符号所关联的数与模式串T所关联的数不相同, 则它们一定不同;如果它们所关联的数相同, 则它们不相同的概率很小, 完全可将其忽略, 认为它们是相同的。[6]为了使概率算法的时间复杂度尽可能小, 每M个符号的块所关联的数必须满足以下条

件: (1) 要比M短, 理想情况下为logM。 (2) 计算这个数所需的时间不能超过O (M) , 理想情况下为常量时间。可见, 简单地将M个符号的块翻译成数字是不能满足这两个条件的。

我们可以随机产生一个长度为logM的素数Prim, 用M个符号的块直接翻译成的数字除以Prim, 所得的余数就是M个符号的块所关联的数。可以看出, 这样所求的关联数满足上述条件 (1) , 因为M个符号的块直接翻译成的数字除以素数Prim的余数位于0到Prim-1之间, 所以它的长度不超过Prim的长度logM。下面重点看一下它是否满足上述条件 (2) 。

假定主串S和模式串T都是由26个英文字母组成的, 将它们分别看作一个很长的二十六进制数, 每位数的可能取值分别A、B、…、Z, 其中A相当于数值0、Z相当于数值25。一般情况下, 计算M位数除以某个素数Prim的余数所需的时间, 和M有关。但是, 可以利用已计算出余数的M位数, 来计算下一个M位数除以Prim的余数。为此, 需从主串S的最后一个字符开始, 即首次取出的M位数是S的倒数第M到倒数第1个字符组成的, 第2次取出的M位数是S的倒数第 (M+1) 到倒数第2个字符组成的。例如, 考虑S=“A C E F S D S E C W U YTWVBNMCCXZDEFRGGLKPOIU…..”, 令T的长度M=8, 假设我们已经到达第5个位置, 数SDSECWUY除以随机产生的素数prim的余数已经计算出来, 接下来要计算FSDSECWU除以prim的余数。因为FSDSECWU=FAAAAAAA+ (SDSECWUY-Y) ÷26, 所以FSDSECWU除以Prim的余数可通过FAAAAAAA除以Prim的余数和SDSECWU除以Prim的余数经过简单加减运算而求得。FAAAAAAA中的实际上是F×267, 这样的数共有25个, 所以可提前将它们除以P r i m的余数计算出来并存放在一个数组中。而SDSECWU除以Prim的余数可通过SDSECWUY除以prim的余数、此余数的最后一位数字及商的最后一位数字经过简单算术计算而求得。可见, 计算M个数字的数除以Prim的余数可在常数时间内完成。

总上所述, 随机产生一个长度为LogM的素数, 将每M个字符的块直接翻译成一个数, 然后用这个数除以素数所得余数, 就是M个字符的块所关联的数。而且此关联数的计算可在常数时间内完成。

2.2 算法的具体步骤

根据2.1中概率算法的基本思想, 这里给出概率算法的具体实现过程。

在长度为N的主串S中查找是否存在长度为M的模式串T的概率算法的具体步骤如下: (1) 随机产生一个含LogM位数字的二十六进制素数, 将其按位存放在数组prim中;

(2) 计算模式串T直接翻译成的数除以prim的余数, 并存放于数组tmod中;

(3) 定义整型变量s_location, 并令s_location=N-M+1;

(4) 事先计算出A×26M-1, B×26M-1, C×26M-1, ……, Z×26M-1除以prim的余数, 并存放于二维数数组mid (26行M列) 中;

(5) 将主串S的第s_location至第s_location+M-1个符号取出, 存放于字符串ss中;并计算ss直接翻译成的二十六进制数除以prim的余数, 存放于数组smod中;

(6) 判断smod与tmod是否相同, 如果不同, 转7) ;否则, 按位比较字符串ss和T, 判断ss和T是否相同, 如果相同, 说明在S中找到了T, 算法结束, 否则转7) ;

(7) s_location=s_location-1;

(8) 如果s_location等于0, 说明在S中不存在模式串T, 算法结束;否则转9) ;

(9) 取出主串S的第s_location个字符, 并将其赋给变量num;

(10) 如果主串S的第s_location+M个字符大于数组smod的最后一个元素, 则将它们的差赋给变量x;否则将它们的差加26赋给变量x;

(11) 根据x的值和prim的最后一个元素的值, 可得出前面的M个字符直接翻译成的数除以prim的商的最后一位数y;

(12) 将y*prim+smod按位赋给数组remain;并将remain的最后一位删除掉;

(13) 如果mid[num-‘A’]+remain>prim, smod=mid[num-‘A’]+remain-prim;否则smod=mid[num-‘A’]+remain;转6) 。

上述算法中的加减运算均在26进制下进行。

注意, 上述算法的前提条件是, 主串和模式串均由二十六个字母组成, 所以每M个符号所关联的数是一个二十六进制数。如果主串与模式串中的字符不止有26个可能的取值, 是一个比较大的数, 则本文的算法就不再方便了;如果主串与模式串中的字符不足26种, 例如是10种, 那么随机产生的素数就是十进制数, 而且每M个字符的块所关联的数也是十进制数了。比如, DNA序列中只有T、G、C、A四种字符, 所以如果模式匹配的是DNA序列, 每M个符号的块所关联的数就可以是四进制数。

其实, 算法中的运算均是按位进行的。所以, 是几进制数关系并不大。

3 概率算法与朴素算法比较

朴素算法的基本运算是比较。使用朴素算法最坏情况下需比较 (N-M+1) *M次。如果M非常大, 如为十亿, 则朴素算法的执行速度会非常慢。概率算法的基本运算是算术加或减。概率算法的一个核心操作是计算M个字符所关联的数, 即将M个字符直接翻译成某进制数, 并求此数除以随机素数的余数。此核心操作最坏情况下需进行算术加或减C*logM* (M-logM+1) 次, 这里C是常数, 表示数制。此核心操作在整个概率算法中最多进行C+1次, 一次是求模式串所关联的数;一次是求主串的最后M个字符所关联的数;其余是求形如“常数×CM-1”的数除以那个素数的余数。概率算法余下的操作是根据已求得的M个字符所关联的数来计算下一个M个字符的块所关联的数, 此操作最多进行N-M次, 每次需进行基本算术运算最多4* (logM+1) 次。[1,2,3,4,5]

从上面的分析可以看出, 如果M和N不很大, 本文的概率算法没有朴素算法有效;但是M和N越大, 本文的概率算法的使用价值越大。

参考文献

[1]鲁宏伟, 魏凯, 等.一种改进的KMP高效模式匹配算法[J].华中科技大学学报 (自然科学版) , 2006, 34 (10) :41-43.

[2]张治, 施鹏飞.一种有效的贪婪模式匹配算法[J].计算机研究与发展, 2007, 44 (11) :1903-1911.

[3]THATHOO R, VIRMANI A, et al.A fast exact pattern matching al-gorithm for biological sequences[J].Current Scence, 2006, 91 (1) :47-53

[4]Sheik S S, Aggarwal S K, et al.A fast pattern matching algorithm[J].Journal Chemical Information and Computer Science, 2004, 44 (4) :1251-1256.

[5]许峰, 满振梅, 等.数据集成领域中的模式匹配技术研究[J].计算机工程, 2006, 32 (6) :40-41.

[6]朱起定.有限元概率算法的基本理论[J].湘潭大学自然科学学报, 2001, 23 (2) :121-133.

模式匹配算法 篇2

利用新时期的航空影像和旧时期的DEM,基于正射影像匹配的相关理论,提出了地形变化检测和数据更新的自动化算法,该算法能够利用两个时期的未变化信息进行控制,避免了传统的定向过程,极大减少了人工编辑,能够同时得到变化检测的结果、更新后的.DEM和DOM.实验结果证明了该算法的实用性和高效性.

作 者：李德仁 夏松 江万寿 LI De-ren XIA Song JIANG Wan-shou 作者单位：李德仁,江万寿,LI De-ren,JIANG Wan-shou(武汉大学测绘遥感信息工程国家重点实验室,湖北,武汉,430079)

夏松,XIA Song(中南财经政法大学信息学院,湖北,武汉,430060)

双目立体匹配算法的FPGA实现 篇3

摘要：针对区域匹配算法在灰度变化比较大区域精度不高的问题，提出一种改进的匹配算法，利用sobel算子计算各像素点的梯度值，根据梯度幅度直方图获得自适应阈值，动态建立支持窗口，改进传统的Census变换，用窗口内所有像素均值代替中心像素进行Census变换，在左右图像中寻找最佳匹配点获得视差图，利用FPGA并行处理和硬件实现的优点，对大数据量实时地进行处理，提高运算效率，实验结果表明：改进的立体匹配算法和硬件结构能够获得精度较高的视差图，处理640×480的图像对只需32.4 ms，

关键词：立体匹配；Sobel算子；自适应阀值；Census变换；现场可编程门阵列

DOI：10.15938/j.jhust.2016.04.005

中图分类号：TP391

文献标志码：A

文章编号：1007-2683（2016）04-0025-05

0引言双目立体视觉是计算机视觉技术研究领域的热点问题，立体匹配是实现立体视觉的重要环节，匹配结果的精度则是制约立体视觉技术发展的瓶颈，立体匹配的算法大致可以分为全局匹配算法和局部匹配算法，其中区域匹配算法由于能够直接获取视差信息，算法复杂度也相对较低，因而广泛地应用在实时立体视觉系统的设计中，

区域匹配算法的性能很大程度上依赖匹配窗口的建立和相似性测度函数的选择，文根据分割区域动态选择窗口的形状和大小的方法得到了较好效果，但对于复杂纹理图像，无法做到较精确的色彩分割，Yoon和Kweon 利用像素间光度学和几何学关系调配窗口中像素的权值，本质上类似于分割的思想，但却回避了分割难题，此方法不依赖初始视差估计，同时在深度不连续和连续区域得到精确匹配，但其高时间计算复杂度问题有待解决，常用的相似性测度函数有像素灰度差的绝对值和（sumof absolute differences，SAD）、及像素灰度差的平方和（sum of squared differences，SSD）、以及非参数化方法的Rank变换和Census变换SSD、SDA算法容易受光照不均及遮挡问题的影响导致匹配误差增大，Rank变换的思想类似滤波器，通过待匹配点与特征窗内各点灰度差，定义灰度等级Zabih把等级变换算法推广到Census变换，通过编码像素间的等级信息保留其空间分布，用加权平均编码信息匹配图像，由于这种方法依据灰度排序方式，提高了算法的鲁棒性，但同时增加了窗口图像信息的维度，计算更加复杂。

虽然上述算法已经能够极大改善区域匹配的性能，但是对于存在灰度变化比较大区域的图像会出现视差图过渡平滑的现象，而且算法复杂度都比较高，难以满足立体视觉系统高速、实时的要求，本文结合边缘检测，利用Sobel梯度算子、梯度幅度直方图和Census变换改进基于传统Census变换的区域匹配算法，并且借助现场可编程门阵列（field pro—grammable gate arrays，FPGA）开发专用的硬件并行处理系统实现该算法，

1.算法描述

1.1梯度幅值计算

Sobel是一阶导数边缘检测算子，是一种有效的梯度计算方法，具体方法是通过3×3模板作为核与图像中的每个像素点做卷积和运算。

利用Sobel算子计算图像中一点的梯度幅值，需要以该像素点为中心建立一个3×3的窗口，然后将窗口内所有像素分别与两个核做卷积获得水平分量G_x和垂直分量G_y如式（1）～（4），

1.2自适应匹配窗口

匹配窗口尺寸的选取对于立体匹配至关重要，窗口太小，包括的图像信息过少，不足以表达出区域的特征，导致误匹配；窗口太大，则违背了匹配窗口内的像素的视差值是一致的假设，无法区分场景中物体和其背景，同时匹配速度也降低在实际匹配中，匹配窗口的大小需要随着图像像素灰度的变化而改变，以提高匹配的精度，

一般在像素灰度变化比较大的区域，对应的像素梯度值变化也比较剧烈，视差变化也不连续，匹配窗口大小应该设置得比较小；而对于梯度值较小的区域，往往是低纹理区域，此处匹配窗口应该设置得比较大，因此需要动态调节匹配窗口的大小，本文采用双阈值确定匹配窗口的大小：选定两个梯度幅值阈值，一个较高G_h另一个较低G_l；设定匹配窗口的尺寸标准分别为D₁、D₂、D₃（D₁>D₂>D₃）；当梯度幅值G（x，y）>G_l时，匹配窗口的大小为D₁×D₂；当梯度幅值G（x，y）3×D₃；其他情况时，匹配窗口大小为D₂×D₂

分析梯度直方图得出阈值的计算方法，自适应地动态生成阈值，克服人为设定阈值的不足，

根据梯度直方图可知，阈值的选择问题实际上即为在梯度幅值直方图中找出灰度变化平稳的区域的尖峰与第一个灰度变化较大区域的尖峰之间的平滑区域，阈值可以选取为此区域内任意一像素的梯度幅值，为了找到这段区域，对梯度幅值的相邻两点作差分，即

1.3改进的Census变换

Census变换属于非参数相似测度因子，基本思想是用一个矩形窗口遍历图像，把窗口内中心像素的灰度值作为参考值，将窗口内其余像素依次与参考值比较，灰度值小于参考值的像素点记为1，大于或等于参考值的像素点记为O，然后按位连接输出一串二进制代码。

式中：W（p）为以像素点P为中心的匹配窗口；I（p）为像素点P的灰度值，，（p）为W（p）内除像素点P以外任意一点的灰度值；表示按位连接，矩形窗口W（P）的尺寸是根据中心像素点的梯度幅值和梯度阈值比较之后确定的，函数E（X，y）定义为

但是传统的Census变换过于依赖中心像素，当图像受到干扰，中心像素发生畸变，就会增大误匹配的几率，本文用矩形窗口内所有像素值的平均值替代中心像素值，仍然按照式（8）、（9）进行变换，这样增强了Census变换的抗干扰能力，

将两幅图像的匹配窗口中的所有像素进行改进的Census变换得到两串01代码，利用Hamming距离公式计算两比特串之间的差异，Hamming距离越小则说明两点的匹配代价越小，两个像素点越相似匹配代价计算如下：式中：（x，y），）表示像素点的坐标值；w表示以点（x，y）为心中的邻域；I_r（x，y）表示在左图中像素点（x，y）的灰度值；I_r表示右图像素的灰度值；XOR表示异或运算；d表示视差，

2.算法描述

FPGA完成图像数据的存取、梯度计算、自适应阈值的计算和立体匹配，算法模块的RTL视图如图1所示，

2.1缓存窗口设计

使用QuartusⅡ软件中基于RAM的移位寄存器宏模块ahshift_taps来实现缓存窗口的设计，宏模块altshift_taps是一个可配置的、具有抽头（Taps）输出的移位寄存器，每个抽头在移位寄存器链的指定位置输出数据，例如，对于256×256的图像，ahshifltaps模块参数设置为8bit输入、8bit输出、3抽头，相邻的两个抽头相距256个寄存器，如图2所示，其中相邻两个抽头间的距离是根据图像大小来设定的，

在工程实际中，3×3的窗口是经常用到的，Shift—RAM中存储2行数据，同时输入数据组成3行阵列，接着输入row3_data数据，机构Shift_RAM移位存储后就可以得到3×3的窗口数据阵列，移位寄存器仿真波形如图3所示，

2.2Sobel梯度鼻子

Sobel梯度算子的硬件实现可以分为图像数据缓存模块和梯度结合模块，其中，图像数据缓存模块采用移位寄存器（shift register）实现，梯度结合模块采用可编程宏模块和Verilog HDL语言相结合的方法实现，

根据卷积运算公式，可以使用QuartusⅡ软件中的可编程加法器altmult_add模块以及可编程多路并行加法器parallel add模块来实现卷积运算，将运算得到的垂直方向和水平方向的梯度值求平方和G_x2+G_y2，利用QuaausⅡ中的宏模块ALTSQRT求解

2.3自适应阈值

自适应阈值的选择是基于梯度直方图进行的，因此首先需要对经过非极大值抑制后的图像进行直方图统计，自适应阈值的产生电路如图5所示，

这些寄存器用于存储不同梯度值像素点的个数，梯度值作为寄存器组的地址，在每幅图像开始时，对这些寄存器清零，梯度值输入后，通过地址选择器，相应地址的寄存器的内容被取出来送人累加器1，加l后再写入该寄存器，直到整幅图像的所有像素点统计完毕，在时钟保持有效期内，每个时钟到来累加器2的内容自加1，累加的结果作为寄存器组的地址，相应地址寄存器的内容以及下一个地址寄存器的内容分别送人寄存器1和寄存器2，对寄存器1和寄存器2的内容按式（6）进行差分，比较器比较差分的结果是否为0，若为0则发出停止累加信号，停止累加器2的累加，此时累加器2的值即为高阈值G_h，G_h右移一位（即除以2）得到低阈值G₁。

2.4立体匹配

为了提高系统的实时性，Census模块的设计采用了以资源换取时间的并行优化方法，例如，对于7×7的局部变换窗口，Census变换模块如图6所示，将移位寄存器组扩展为8行，每一列读入8个像素数据，在窗口水平移动中，每隔8个时钟周期对Census变换窗口的数据更新一次，当Census变换窗口移至每行末尾时，便获得了相邻两行像素的Census局部变换，从资源方面分析，并行后比较器的数量增加了1倍，但移位寄存器的数量只增加了1/7，优化结果却使Census局部变换的速度提高了近1倍，运算频率由1/7（像素/周期）提高到1/5（像素/周期），

3.实验结果与分析

为了验证本文算法的有效性，将实验结果上传到Middlebury网站平台进行评估，本文算法的支持窗口分别设置为D₁=7、D₂=5、D₃=3，为了分析匹配精度，选择Middlebury网站上一些相近的算法进行比较，匹配精度比较结果如表1所示，

通过比较，ADCensus算法能够达到很低的误点率，但算法较为复杂，本文算法与SSD+ASW、Cen—BUS+ASW算法相比误匹配率要低，对比而言本文提出的算法综合考虑了算法匹配精度与实时性，达到了较好的效果。

另外，在Pc和FPGA上实现本文算法，计算两者处理同一帧640×480像素图像所用时间，比较结果如表2所示，

选择Middlebury平台中的Teddy图像作为参考图像，比较SSD+ASW、Census+ASW和本文算法的匹配结果，

由图7（b）可以看出本文算法得到的视差图较Census+ASW和SSD+ASW算法更为清晰，能够比较准确地反应图像的深度信息，

4.结论

一种大容量模式匹配算法 篇4

随着模式匹配技术在入侵检测、病毒扫描和网络内容过滤方面的广泛应用,模式匹配算法的研究逐步成为深度包检测研究的重点。但随着网络技术的飞速发展,模式匹配技术也面临着巨大的挑战。10 Gb/s级网络速率的到来要求模式匹配算法必须实现网络数据的线速处理。同时,网络中病毒、蠕虫、木马等网络攻击的不断增多,要求模式匹配算法能够支持更多规模的模式集。深度包检测需要对网络数据包负载进行搜索,匹配位置的不确定性增加了算法的复杂度,并已成为制约网络内容检测系统发展的瓶颈。三态内容可寻址寄存器(TCAM)是一类能够对存储内容进行并行查找,并在较短的确定时间内给出结果的高速存储器。深度包检测领域已有一些基于TCAM模式匹配算法的研究[1,2,3]。由于TCAM存储资源有限,因此,压缩存储表项是基于TCAM模式匹配算法的一个研究重点。

1 现有算法的不足

TCAM利用并行比较的方法实现存储内容的快速搜索,但TCAM存在表项位宽限制,长模式需要切割为多个短模式进行存储。TCAM与一般CAM的区别在于其存储内容可以有“0”,“1”或“-”(无关项)三种形式,因此,对于长度小于TCAM位宽的表项可以用无关项填充,搜索时,无关项将对应位置掩掉进行比较。长模式切法为多个短模式后只有连续命中子串序列才能匹配该长模式。Fang Yu等人提出了一种“TCAM+SRAM”的实现方案[1],TCAM匹配输入字符串,SRAM存储命中表项信息,通过在搜索过程中不断更新已匹配信息实现长模式匹配。然而,该方案在一个TCAM查询周期内移动一个字符,造成命中列表极为庞大,增加了很多不必要的计算量。文献[2]将模式进行移位存储,实现搜索一个周期内移动若干字节,但是算法资源利用率低,前后两次查表存在依赖性,流水实现时需要使用多级TCAM。两级TCAM模式匹配算法[3]利用利用第一级TCAM匹配字符串,第二级TCAM匹配命中表项编号序列,从而实现长模式匹配,但算法每次搜索只能向前移动一个字节。文献[4]通过第一个子串的移位存储实现周期内多个字节的移动,但该算法在匹配后续子串失败时,必然回溯若干字节确定模式的开始位置。文献[5,6]利用TCAM的掩码特性在包分类中合并多条相似表项从而提高资源利用率,但模式匹配需要动态地确定所有可能发生的匹配,从而产生大量的交叉转移。

2 基于TCAM的模式匹配算法

2.1 算法思想

设置TCAM位宽为w字节,基于TCAM的模式匹配算法先将模式移位,然后按w字节将移位的模式切分为若干个子串。存储时,所有子串存入第一级TCAM中,位宽小于w字节则进行填充,第二级TCAM存储所有合法的编号序列。搜索模式时,第二级TCAM根据前端命中表项的编号序列组成输入编号,并输出命中表项对应的长模式,算法的硬件结构图如图1所示。

2.2 表项存储与模式搜索

为了匹配到出现在数据任何位置的模式串,算法先将模式进行进行w次右移。然后按w字节切分模式,共产生3类子串,即第一个子串、若干中间子串和最后一个子串,分别称为头串、中间串和尾串。头串和尾串的长度可能不足w字节,且两类子串的无关项位置不同,从而造成两者之间的表项冲突,头串是一个模式的开始,可能出现在数据的任何位置,而中间串和尾串只能出现在头串之后。同时,TCAM的分片功能可以限制查表区域。因此,存储字符串时,将头串单独存入高地址分区,中间串和尾串按字符串长度存入低地址的分区,同时,利用TCAM的分块特性,将头串与中间串、尾串分块存储。算法从头串开始每次移动w字节,直至一次匹配过程结束,同时由于尾串长度不足w字节,因此,命中尾串表项后的移动距离应该尾串长度。SRAM表项信息包括命中表项是否为短串、下次搜索的移动距离和表项编号三部分。表项存储时,按照最长匹配原则进行存储,将长字符串存在低地址。

当TCAM位宽w=4 B时,模式“ABABAD”的切分和存储情况如图2所示,首先按4 B切分模式,然后将头串存入块2,中间串和尾串存入块1。头串用于确定模式的起始位置,所以块2为默认匹配区域,当后缀搜索失败时,利用块2再次确定模式位置。

模式匹配时,按如下过程进行搜索:

(1) 向块2输入长度为w字节的字符串,若命中表项,则移动w字节执行(2),否则,移动w字节后继续执行(1);

(2) 输入下一个w字节,搜索块1和块2,若命中表项,移动相应距离然后执行(2),否则,移动相应距离,然后执行(1)。

TCAM_2存储所有可能的编号序列,通过匹配输入编号搜索长模式。第一级TCAM匹配之后,向第二级TCAM输入匹配表项编号,TCAM_2将合法编号序列连接起来,从而实现长模式匹配。如果TCAM_1没有表项命中,则输出一个约定的无效标识。

2.3 表项压缩

在第一级TCAM中,子串长度从一个字节到w字节不等,因此,表项之间存在大量的包含关系,从而造成TCAM_2匹配一个长模式可能需要大量的表项,大大地限制了算法支持的模式集规模。中间串长度为w字节,不存在包含关系,因此,头串和尾串编号的包含关系造成TCAM_2存储表项数目的膨胀。利用TCAM的掩码特性,将TCAM_2的头串和尾串编号掩掉若干位,存储编号空间,查表时,只要编号属于该区间,则命中该表项。

TCAM_2中 w字节的子串编号为一个确定值,而长度小于w字节的子串用编号段代替,因此,应按子串长度和包含关系分配子串编号。一个w字节的子串可能同时与头串和尾串具有包含关系,且比较位置不同,因此,这类具有双重包含关系的子串应分配两个编号,一个作为头串编号,一个作为后缀编号。由于第二级TCAM匹配时,只有第一个编号才是头串编号,所有子串只有处于编号序列头部是才使用头串编号,其他时候使用后缀编号。子串集合划分时,按相同方向逐字节比较,具有相同字符的子串划分为同一集合,编码过程如图3所示。图3为头串编号编码过程,具有相同前缀的子串为同一集合,并采用统一的编码,相应地,尾串编号编码时比较字符从后向前移动。编码过程实质是集合切分过程,子串长度越短,则编号范围越大,应作为集合切分的父集;相应地,子串长度于越长,则编号范围越小,应作为集合切分的子集。编码之后,TCAM_2采用“0--”便可以表示“---A”,并将三条表项压缩为一条表项。

3 算法性能分析

由于存储空间资源昂贵,模式集规模大,空间复杂度是衡量基于TCAM的模式匹配算法性能的重要指标,空间复杂度越低意味着算法占用存储空间越少,利用率越高。TCAM_1位宽为w字节,模式规模为N,模式平均长度为m,经i次移位后,产生子串的数目为:

$C{}_i=\left|\frac{m+i}{w}\right|$

去除相同表项,TCAM_1的总表项数:

${\rm N}{}_1\le {\rm N}{\displaystyle \sum _{i=0}^{w-1}\left|\frac{m+i}{w}\right|}$

因此,TCAM_1的空间消耗:

$\begin{array}{l}{\rm M}{}_1\le {\rm N}w{\displaystyle \sum _{i=0}^{w-1}\left|\frac{m+i}{w}\right|}\approx {\rm N}{\displaystyle \sum _{i=0}^{w-1}(}m+i)\\ ={\rm N}w\left(\frac{w-1}{2}+m\right)\end{array}$

最长模式为L字节,则编号序列的长度:

${\rm N}{}_{\text{C}}=\left|\frac{L+w-1}{w}\right|$

每个编号占用n比特,则TCAM_2位宽的字节数:

$w{}_{\text{b}}=n{\rm N}{}_{\text{C}}/8$

随着w的增加,第一级TCAM的表项数增加,而编号序列的长度减小;随着跳跃距离w的增加,模式移位次数增加,两级TCAM的表项数均会随之增加。因此,两级TCAM的空间利用率将随着w的增加而降低。

传统模式匹配算法只能逐字节移动,对模式移位操作后,算法的单次最大安全移动距离为w字节。搜索过程中,若命中头串和中间串,则可以安全移动w字节;若命中尾串,搜索指针只能移动到字符串结束位置。因此,算法的移动距离与命中情况直接相关。

4 实验仿真

仿真实验中,匹配模式来自2008年1月的Snort[7]规则库的2 247个单模式,数据来源于互联网数据分析协会及美国应用网络研究国家实验室[8]。

4.1 编码压缩性能仿真

算法提出了一种编码压缩方法,将具有包含关系的表项压缩到一段连续的编号空间,压缩第二级TCAM表项数目。在不同的TCAM位宽下,对模式集的压缩性能仿真如图4所示。

从图4可以看出:在不同位宽条件下,对TCAM_1的表项编码后,TCAM_2表项规模存在明显下降。同时,虽然随着表项规模的增大,压缩后的表项数目也有所增加,但表项规模越大压缩性能越好。

4.2 空间复杂度实验仿真

算法采用两级TCAM匹配的方式,存储资源消耗分为两部分,实验在不同位宽条件下,对算法的空间消耗仿真如图5所示。

从结果中可以看出:算法的两级TCAM空间消耗均随位宽的增大而增加,但TCAM_1比TCAM_2的空间消耗增加更为明显,且呈阶段性增加趋势,这是由模式长度分布和不同位宽条件下划分子串的相关性决定的。

4.3 搜索速率实验仿真

算法每次的移动距离根据前一次匹配结果而定,采用实验数据得到搜索速率仿真结果如图6所示。

从仿真结果可以看出:随TCAM位宽的增加,搜索速率也逐步增加,但提升幅度逐渐减小。

5 结 语

本文针对现有模式匹配算法的不足,提出了两级TCAM的模式匹配算法并利用移位存储实现快速匹配。该算法利用TCAM特性提出一种子串编码方法,压缩第二级TCAM表项。通过分析和仿真, 表明算法具有较高搜索速率的同时也提高了空间利用率。

参考文献

[1] YU Fang, KATZ Randy H, LAKSHMAN T V. Gigabit rate packet pattern-matching using TCAM [C]. Berlin: Proceedings of the 12th IEEE International Conference on Network Protocols, 2004.

[2] SUNG Jung-Sik, KANG Seok-Min, LEE Young-Seok, et al. A multi-gigabit rate deep packet inspection algorithm using TCAM [C]. St.Louis Mo: GLOBECOM 2005-IEEE Global Telecommunications Conference, 2005.

[3]GAO Ming,ZHANG Kenong,LU Jia-hua.Efficient packetmatching for gigabit network intrusion detection usingTCAMs[C].Vienna:Proceedings of the 20th InternationalConference on Advanced Information Networking and Appli-cations,2006.

[4]Alicherry,MUTHUPRASANNA M,KUMAR M.Highspeed pattern matching for network IDS/IPS[C].Califor-nia,USA:The 14th IEEE International Conference on Net-work Protocols(ICNP),2006.

[5] MEINERS C R, LIU A X, TORNG E. TCAM Razor: a systematic approach towards minimizing packet classifiers in TCAMs [C]// Proc. ICNP. Beijing: IEEE, 2007: 266-275.

Perl中的模式匹配学习笔记 篇5

一、简介

模式指在字符串中寻找的特定序列的字符，由反斜线包含：/def/即模式def，其用法如结合函数split将字符串用某模式分成多个单词：@array = split(/ /, $line);

二、匹配操作符 =~、!~

=~检验匹配是否成功：$result = $var =~ /abc/;若在该字符串中找到了该模式，则返回非零值，即true，不匹配则返回0，即false。!~则相反。这两个操作符适于条件控制中，如：

代码如下:

if ($question =~ /please/) {

print (“Thank you for being polite!n”);

}

else {

print (“That was not very polite!n”);

}

三、模式中的特殊字符

PERL在模式中支持一些特殊字符，可以起到一些特殊的作用。

1、字符 +

+意味着一个或多个相同的字符，如：/de+f/指def、deef、deeeeef等。它尽量匹配尽可能多的相同字符，如/ab+/在字符串abbc中匹配的将是abb，而不是ab。当一行中各单词间的空格多于一个时，可以如下分割：@array = split (/ +/, $line);

注：split函数每次遇到分割模式，总是开始一个新单词，因此若$line以空格打头，则@array的第一个元素即为空元素。但其可以区分是否真有单词，如若$line中只有空格，则@array则为空数组。且上例中TAB字符被当作一个单词。注意修正。

2、字符 []和[^]

[]意味着匹配一组字符中的一个，如/a[0123456789]c/将匹配a加数字加c的字符串。与+联合使用例：/d[eE]+f/匹配def、 dEf、deef、dEef、dEEEeeeEef等。^表示除其之外的所有字符，如：/d[^deE]f/匹配d加非e字符加f的字符串。

3、字符 *和?

它们与+类似，区别在于*匹配0个、1个或多个相同字符，?匹配0个或1个该字符。如/de*f/匹配df、def、deeeef等;/de?f/匹配df或def。

4、转义字符

如果你想在模式中包含通常被看作特殊意义的字符，须在其前加斜线“”。如：/*+/中*即表示字符*，而不是上面提到的一个或多个字符的含义。斜线的表示为//。在PERL5中可用字符对Q和E来转义。

5、匹配任意字母或数字

上面提到模式/a[0123456789]c/匹配字母a加任意数字加c的字符串，另一种表示方法为：/a[0-9]c/，类似的，[a-z]表示任意小写字母，[A-Z]表示任意大写字母。任意大小写字母、数字的表示方法为：/[0-9a-zA-Z]/。

6、锚模式

锚 描述

^ 或 A 仅匹配串首

$ 或 Z 仅匹配串尾

b 匹配单词边界

B 单词内部匹配

例1：/^def/只匹配以def打头的字符串，/$def/只匹配以def结尾的字符串，结合起来的/^def$/只匹配字符串def(?)。A和Z在多行匹配时与^和$不同。

例2：检验变量名的类型：

代码如下:

if ($varname =~ /^$[A-Za-z][_0-9a-zA-Z]*$/) {

print (“$varname is a legal scalar variablen”);

} elsif ($varname =~ /^@[A-Za-z][_0-9a-zA-Z]*$/) {

print (“$varname is a legal array variablen”);

} elsif ($varname =~ /^[A-Za-z][_0-9a-zA-Z]*$/) {

print (“$varname is a legal file variablen”);

} else {

print (“I don‘t understand what $varname is.n”);

}

例3：b在单词边界匹配：/bdef/匹配def和defghi等以def打头的单词，但不匹配abcdef。/defb/匹配def和 abcdef等以def结尾的单词，但不匹配defghi，/bdefb/只匹配字符串def。注意：/bdef/可匹配$defghi，因为$并不被看作是单词的部分。

例4：B在单词内部匹配：/Bdef/匹配abcdef等，但不匹配def;/defB/匹配defghi等;/BdefB/匹配cdefg、abcdefghi等，但不匹配def,defghi,abcdef。

7、模式中的变量替换

将句子分成单词：

$pattern = “[t ]+”;

@words = split(/$pattern/, $line);

8、字符范围转义

转义字符 描述 范围

d 任意数字 [0-9]

D 除数字外的任意字符[^0-9]

w 任意单词字符 [_0-9a-zA-Z]

W 任意非单词字符 [^_0-9a-zA-Z]

s 空白 [ rtnf]

S 非空白 [^ rtnf]

例：/[da-z]/匹配任意数字或小写字母。

9、匹配任意字符

字符“.”匹配除换行外的所有字符，通常与*合用。

10、匹配指定数目的字符

字符对{}指定所匹配字符的出现次数。如：/de{1,3}f/匹配def,deef和deeef;/de{3}f/匹配deeef;/de{3,}f/匹配不少于3个e在d和f之间;/de{0,3}f/匹配不多于3个e在d和f之间。

11、指定选项

字符“|”指定两个或多个选择来匹配模式。如：/def|ghi/匹配def或ghi。

例：检验数字表示合法性

if ($number =~ /^-?d+$|^-?0[xX][da-fa-F]+$/) {

print (“$number is a legal integer.n”);

} else {

print (“$number is not a legal integer.n”);

}

其中 ^-?d+$ 匹配十进制数字，^-?0[xX][da-fa-F]+$ 匹配十六进制数字。

12、模式的部分重用

当模式中匹配相同的部分出现多次时，可用括号括起来，用n来多次引用，以简化表达式：/d{2}([W])d{2}1d{2}/ 匹配：

12-05-92

26.11.87

07 04 92等

注意：/d{2}([W])d{2}1d{2}/ 不同于/(d{2})([W])121/ ，后者只匹配形如17-17-17的字符串，而不匹配17-05-91等。

13、转义和特定字符的执行次序

象操作符一样，转义和特定字符也有执行次序：

特殊字符 描述

模式内存

+ * ? {} 出现次数

^ $ b B 锚

| 选项

14、指定模式定界符

缺省的，模式定界符为反斜线/，但其可用字母m自行指定，如：

m!/u/jqpublic/perl/prog1! 等价于//u/jqpublic/perl/prog1/

注：当用字母‘作为定界符时，不做变量替换;当用特殊字符作为定界符时，其转义功能或特殊功能即不能使用。

15、模式次序变量

在模式匹配后调用重用部分的结果可用变量$n，全部的结果用变量$&。

代码如下:

$string = “This string contains the number 25.11.”;

$string =~ /-?(d+).?(d+)/; # 匹配结果为25.11

$integerpart = $1; # now $integerpart = 25

$decimalpart = $2; # now $decimalpart = 11

$totalpart = $&; # now totalpart = 25.11

四、模式匹配选项

选项 描述

g 匹配所有可能的模式

i 忽略大小写

m 将串视为多行

o 只赋值一次

s 将串视为单行

x 忽略模式中的空白

1、匹配所有可能的模式(g选项)

代码如下:

@matches = “balata” =~ /.a/g; # now @matches = (“ba”, “la”, “ta”)

匹配的循环：

while (“balata” =~ /.a/g) {

$match = $&;

print (“$matchn”);

}

结果为：

代码如下:

ba

la

ta

当使用了选项g时，可用函数pos来控制下次匹配的偏移：

代码如下:

$offset = pos($string);

pos($string) = $newoffset;

2、忽略大小写(i选项)例

/de/i 匹配de,dE,De和DE。

3、将字符串看作多行(m选项)

在此情况下，^符号匹配字符串的起始或新的一行的起始;$符号匹配任意行的末尾。

4、只执行一次变量替换例

代码如下:

$var = 1;

$line = ;

while ($var < 10) {

$result = $line =~ /$var/o;

$line = ;

$var++;

}

每次均匹配/1/。

5、将字符串看作单行例

/a.*bc/s匹配字符串axxxxx nxxxxbc，但/a.*bc/则不匹配该字符串。

6、在模式中忽略空格

/d{2} ([W]) d{2} 1 d{2}/x等价于/d{2}([W])d{2}1d{2}/。

五、替换操作符

语法为s/pattern/replacement/，其效果为将字符串中与pattern匹配的部分换成replacement。如：

代码如下:

$string = “abc123def”;

$string =~ s/123/456/; # now $string = “abc456def”;

在替换部分可使用模式次序变量$n，如s/(d+)/[$1]/，但在替换部分不支持模式的特殊字符，如{},*,+等，如s/abc/[def]/将把abc替换为[def]，

替换操作符的选项如下表：

选项 描述

g 改变模式中的所有匹配

i 忽略模式中的大小写

e 替换字符串作为表达式

m 将待匹配串视为多行

o 仅赋值一次

s 将待匹配串视为单行

x 忽略模式中的空白

注：e选项把替换部分的字符串看作表达式，在替换之前先计算其值，如：

代码如下:

$string = “0abc1”;

$string =~ s/[a-zA-Z]+/$& x 2/e; # now $string = “0abcabc1”

六、翻译操作符

这是另一种替换方式，语法如：tr/string1/string2/。同样，string2为替换部分，但其效果是把string1中的第一个字符替换为string2中的第一个字符，把string1中的第二个字符替换为string2中的第二个字符，依此类推。如：

$string = “abcdefghicba”;

$string =~ tr/abc/def/; # now string = “defdefghifed”

当string1比string2长时，其多余字符替换为string2的最后一个字符;当string1中同一个字符出现多次时，将使用第一个替换字符。

翻译操作符的选项如下：

选项 描述

c 翻译所有未指定字符

d 删除所有指定字符

s 把多个相同的输出字符缩成一个

如$string =~ tr/d/ /c;把所有非数字字符替换为空格。$string =~ tr/t //d;删除tab和空格;$string =~ tr/0-9/ /cs;把数字间的其它字符替换为一个空格。

七、扩展模式匹配

PERL支持PERL4和标准UNIX模式匹配操作所没有的一些模式匹配能力。其语法为：(?pattern)，其中c是一个字符，pattern是起作用的模式或子模式。

1、不存贮括号内的匹配内容

在PERL的模式中，括号内的子模式将存贮在内存中，此功能即取消存贮该括号内的匹配内容，如/(?:a|b|c)(d|e)f1/中的1表示已匹配的d或e，而不是a或b或c。

2、内嵌模式选项

通常模式选项置于其后，有四个选项：i、m、s、x可以内嵌使用，语法为：/(?option)pattern/，等价于/pattern/option。

3、肯定的和否定的预见匹配

肯定的预见匹配语法为/pattern(?=string)/，其意义为匹配后面为string的模式，相反的，(?!string)意义为匹配后面非string的模式，如：

代码如下:

$string = “25abc8”;

$string =~ /abc(?=[0-9])/;

$matched = $&; # $&为已匹配的模式，此处为abc，而不是abc8

4、模式注释

PERL5中可以在模式中用?#来加注释，如：

代码如下:

if ($string =~ /(?i)[a-z]{2,3}(?# match two or three alphabetic characters)/ {

...

}

现以简表总结如下：

一 文字处理模式中,/pattern/常用到的语法

/pattern/

结果

.

除了换行字符n外,找寻只有一个字符的字符串

x?

找寻0个或是1个x字符

x*

找寻0个或是0个以上的x字符

.*

找寻0个或是0个以上的任何字符

x+

找寻0个或是1个以上的x字符

.+

找寻1个或是1个以上的任何字符

{m}

找寻刚好是m个个数指定的字符

{m,n}

找寻在m个数个数以上,n个个数以下指定的字符

{m,}

找寻m个个数以上指定的字符

[]

找寻符合[]内的字符

[^]

找寻不符合[]内的字符

[0-9]

找寻符合0到9的任何一个字符

[a-z]

找寻符合a到z的任何一个字符

[^0-9]

找寻不符合0到9的任何一个字符

[^a-z]

找寻不符合a到z的任何一个字符

^

找寻字符开头的字符

$

找寻字符结尾的字符

d

找寻一个digit(数字)的字符,和[0-9]语法一样

d+

找寻一个digit(数字)以上的字符串,和[0-9]+语法一样

D

找寻一个non-digit(非数字)的字符,和[^0-9]语法一样

D+

找寻一个non-digit(非数字)以上的字符,和[^0-9]+语法一样

w

找寻一个英文字母或是数值的字符,和[a-zA-Z0-9]语法一样

w+

找寻一个以上英文字母或是数值的字符,和[a-zA-Z0-9]+语法一样

W

找寻一个非英文字母,数值的字符,和[^a-zA-Z0-9]语法一样

W+

找寻一个以上非英文字母,数值的字符,和[^a-zA-Z0-9]+语法一样

s

找寻一个空白的字符,和[ntrf]一样

s+

找寻一个以上空白的字符,和[ntrf]+一样

S

找寻一个非空白的字符,和[^ntrf]一样

S+

找寻一个以上非空白的字符,和[^ntrf]+一样

b

找寻一个不以英文字母,数值为边界的字符串

B

找寻一个以英文字母,数值为边界的字符串

a|b|c

找到符合a字符或是b字符或是c字符的字符串

abc

找到一个含有abc的字符串

(pattern)

()这个符号是会记忆所找寻到的字符,是一个很实用的语法

第一个()内所找到的字符串变成$1这个变量或是1变量

第二个()内所找到的字符串变成$2这个变量或是2变量

以此类推,笔者会在下一小节中详细介绍它的用法

/pattern/i

i这个参数是代表忽略英文大小写的意思,也就是在找寻字符 串的时候,不会去考虑英文的大小写

如果要在pattern模式中找寻一个有特殊的意义的字符,要在 这个字符前加上这个符号,这样才会让这个特殊字符失效

二 文字处理模式(Regular Expression)的简单范例

看了上一小节文字处理模(Regular Expression)之的,初学者对于这个语法的应用可能还不是很清楚,所以笔者会在这一小节中,举出一些在文字处理模式中常用的范例给大家看看:

范例

说明

/perl/

找到含有perl的字符串

/^perl/

找到开头是perl的字符串

/perl$/

找到结尾是perl的字符串

/c|g|i/

找到含有c或g或i的字符串

/cg{2,4}i/

找到c后面跟着2个到4个g,再跟着i的字符串

/cg{2,}i/

找到c后面跟着2个以上g,再跟着i的字符串

/cg{2}i/

找到c后面跟着2个g,再跟着i的字符串

/cg*i/

找到c后面跟着0个或多个g,再跟着i的字符串,如同/cg{0,1}i/

/cg+i/

找到c后面跟着一个以上g,再跟着c的字符串,如同/cg{1,}i/

/cg?i/

找到c后面跟着0个或是一个g,再跟着c的字符串,如同/cg{0,1}i/

/c.i/

找到c后面跟着一个任意字符,再跟着i的字符串

/c..i/

找到c后面跟着二个任意字符,再跟着i的字符串

/[cgi]/

找到符合有这三个字符任意一个的字符串

/[^cgi]/

找到没有这三个字符中任意一个的字符串

/d/

找寻符合数值的字符串

可以使用/d+/来表示一个或是多个数值的字符串

/D/

找寻符合不是数值的字符串

可以使用/D+/来表示一个或是更多个非数值的字符串

/w/

找寻符合英文字母,数值的字符串

可以使用/w+/来表示一个或是更多个英文字母,数值的字符串

/W/

找寻符合非英文字母,数值字符的字符串

可以使用/W+/来表示一个或是更多个非英文字母,数值的字符串

/s/

找寻符合空白的字符串

可以使用/s+/来表示一个或是更多个空白字符的字符串

/S/

找寻符合不是空白的字符串

可以使用/S+/来表示一个或是更多不是空白的字符的字符串

/*/

找寻符合*这个符号的字符串,因为*在文字处理模式中有它的特殊意思,所以要在这个特殊符号前加上这个符号,这样才会让这个特殊字符失效

/abc/i

找寻符合abc的字符串而且不考虑这些符合字符串的大小写

三 文字处理模式(Regular Expresion)相关的运算符及函数

模式匹配算法 篇6

收稿日期： 20130927

摘要： 特征点匹配在图像检索、三维测量、模式识别等技术中起着重要的作用。使用MATLAB软件剪切图像并细化线结构光光线条纹。经理论分析SURF算法优缺点,提出了一种基于SURF算法特征点提取的改进算法。用C语言编写改进后的特征提取算法,通过MATLAB软件实验对比两种算法的特征点提取结果并且编写程序实现后期的特征匹配。实验表明:该算法基本满足双目视觉立体匹配的要求,对于线结构光三维测量技术具有重要的理论意义和实用价值。

关键词： 结构光; 双目视觉; 立体匹配算法

中图分类号： TP 391文献标志码： Adoi： 10.3969/j.issn.10055630.2014.02.015

Research on matching algorithm based on

structured light binocular vision feature

LIU Yu, LIU Chanlao, SU Hai

(School of Optoelectronic Engineering, Xi’an Technological University, Xi’an 710032, China)

Abstract： Matching feature points play an important role in image retrieval, dimensional measurement and pattern recognition technology. By using the MATLAB software shear thinning line structured light image and light stripes, and through theoretical analysis of the advantages and disadvantages of SURF algorithm, this article proposes the SURF algorithm which based on feature points extraction algorithm. Through C language improved feature extraction algorithm, MATLAB software experimental comparison of the two algorithms feature point extraction results and preparation program features the late match. Experiments show that the algorithm basically meets the requirements of binocular vision stereo matching, and linear structured light for threedimensional measurement technique has important theoretical significance and practical value.

Key words： structured light; binocular vision; stereo matching algorithm

引言双目立体视觉是利用双目摄像机模拟生物的视觉特征,获取物体表面的三维信息,从而还原物体外表面的几何形貌。如今,基于双目立体视觉的技术,结构光三维测量技术作为一种快速、便携、高精度的三维测量技术,在工业设计、航空等领域均得到了广泛的应用,已成为一种成熟的三维数据获取和质量评价与控制手段［1］。在结构光双目视觉技术中,由于不同视觉所获取信息的不完备性和不同应用中的复杂性,立体匹配成为立体视觉技术中最重要也是最难以处理的问题之一［2］。现今,立体匹配方法有多种。特征的选取跟图像的内容有关,对结构光匹配目前常用的是相位匹配方法,但是相位匹配一般是针对核线平行而言,虽然将空间域转化为时间域,可同样存在邻域奇异性,匹配误差较大［3］。基于区域立体匹配方法,可以得到稠密的视差图,其缺点是在低纹理区域或纹理相似区域容易造成大量的误匹配,边界模糊,视差图效果不理想［46］,计算量大,运算时间较长。基于特征点的立体匹配方法,能够精确的匹配,视差效果明显,但是只能获得稀疏的匹配点,所以仅能勾勒物体的大致轮廓,不能呈现物体的细节部分,也不能得到稠密的视差图［7］。针对特征匹配只能得到稀疏点数的缺点,本文提出了一种改进的特征点提取算法,在不影响匹配速度的情况下,匹配更多的特征点对,并且有效地减少了误匹配率。光学仪器第36卷

第2期刘瑜，等：一种基于结构光双目视觉的特征匹配算法研究

1立体匹配关键技术双目立体匹配的方法是从左右视角两个摄像机拍摄同一物体的两幅图像中找出被测元件表面同一点在不同图像中的对应点,进而求出各个点对应的视差,再由视差信息和投影模型还原出原始物体形貌的深度信息［89］,最终得到三维表面形貌。因此,图像的立体匹配是三维重建的关键环节,也是立体视觉尤其是三维重建的重要研究内容。关于立体匹配方法研究重点具体有两方面:算法鲁棒性和计算速度。(1)算法鲁棒性:三维重建过程与投影过程是互逆的,图像经三维投影到二维空间,三维的深度信息丢失。从二维图像恢复至三维模型,对应匹配点可能会出现一对一或多对一的情况,导致唯一性失效,此外成像过程中如噪声、遮挡、光照变化等干扰都会造成匹配误差。可以通过对原有算法改进或引入新算法来提高准确性。(2)计算速度:立体匹配是在左、右两幅图像中搜索对应点对的过程。所以,提高计算速度需要解决搜索策略问题如极线约束［10］的使用可以将二维搜索降到一维搜索;视差约束也可以通过降低搜索范围方式提高计算速度。2特征点匹配算法的改进特征匹配分为特征点的提取和特征点的匹配两个过程。首先对两幅图像分别提取特征点,根据特征点的相似程度匹配特征点对,并根据各自点的灰度信息得到匹配视差图。因此,特征点提取的准确程度和数量直接影响后期的匹配,从而影响整个立体匹配的精度和效率。所以,如何快速有效地提取特征点是本文重点解决的问题。根据本实验采集5组图片(任选一组左右视图如图1所示),将三线激光器投影到被测物体表面,CCD采集得到左右两幅图像。本文通过对图像进行预处理,减少图像噪声以及测量环境对光条中心提取的不良影响。(1)图像剪切:首先为了确保图像处理速度,在进行结构光光条图像处理时,只剪切包含光条在内的一小部分图像进行处理,而不是对整幅图像都进行处理,如此可以大大地减少运算量,提高检测效率。(2)图像滤波:为了抑制噪声、改善图像质量,要对图像进行滤波处理。本文采用中值滤波能较好地去除孤立噪声点，如图2所示。

2.1基于SURF算子的特征点提取常用的特征点检测方法有Harris角点检测,SUSANA,HessianLaplace,强角点检测等。但是它们缺点是不能适应图像的尺度变化,对于不同尺度的图像,无法建立相应特征点的关系。SURF是一种尺度不变和旋转不变的特征点检测算法,具有速度快,鲁棒性好的特点,针对特征点对的提取数量较少这一不足,本文通过算法上的改进,来提高匹配效率。

nlc202309040401

图1原始图像对

Fig.1Untreated images图2图像预处理

Fig.2Preprocessed image

SURF算法就是利用积分图像的加减运算来实现图像与高斯二阶微分模板的卷积运算,积分图像是由Viola和Jones［11］提出,很大程度上简化了计算时间。积分图像中任一点(i,j)的值ii(i,j),用原图像左上角的任一点(i,j)相应的对角线区域灰度值的和表示,ii(i,j)=∑i′≤i,j′≤jp(i′,j′)(1)图3SURF算子提取效果图

Fig.3SURF operator extraction effect image式中,p(i′,j′)表示原始图像点(i′,j′)的灰度值,ii(i,j)可以用如下迭代式计算得到,S(i,j)=S(i,j－1)+p(i,j)(2)

ii(i,j)=ii(i－1,j)+S(i,j)(3)式中,S(i,j)表示一列的积分,并且S(i,-1)=0,ii(-1,j)=0。需要积分图像时,只需对原始图像的所有像素扫描一遍。用MATLAB软件对滤波后的图像进行处理,结果如图3所示。

2.2基于SURF算法的改进由于结构光光学条纹能实现图像对的立体匹配、还原三维结构,因此需要快速地提取结构光条纹,才能提高立体匹配的匹配速率。通过对图像的剪切和中线条纹提取,可在很大程度上降低后期立体匹配时间,进而提高匹配效率。(1)均衡化与二值化由于结构光光条图像正是属于待测对象(结构光光条),与背景有较强对比度的图像,所以二值化对结构光光条图像是特别有效的,它能有效地分离光条目标区域与背景区域,减少计算量,提高处理速率。在二值化之前需要突出感兴趣的部分,因此提前进行直方图均衡化,将灰度值低的感兴趣部分显现出来,提高处理精度。得到图像对如图3所示。(2)细化与骨架提取利用MATLAB函数库中的细化函数对图像进行细化与骨骼提取,得到单像素的细线条纹,为后期匹配减少了运算量,缩短了匹配时间,提高匹配速率。经过图像预处理后得到立体图像对,对图像二值化结果如图4所示,使得对比度得到明显改善,再通过细化后得到的图像对能够较好地满足后期立体匹配的要求,如图5所示。

2.2.1约束条件由于立体匹配是寻求同一空间景点在不同视角下投影图像的像素间的一一对应关系,因此立体匹配的实质就是在某一匹配准则下的最佳搜索。由于同一物体在不同视角下的图像会有差异,而且场景中的很多因素,如光照条件,物体几何形状和物理特性、噪声干扰等,都被综合成单一的图像中的灰度值。为解决这一问题,通常引入各种约束,将匹配限制在平滑解空间范围内。其约束条件如下:(1)极限约束:当给定一点,它的匹配点一定出现在所对应的极线上。如图6所示,L1为点P2对应的极线,L2为点P1对应的极线,L1和L2互为极线。

图4二值化后立体图像对

Fig.4Binarized stereo image pair图5条纹细化后立体图像对

Fig.5Thinning stripe stereo image pair

图6双摄像机成像模型

Fig.6Dualcamera imaging model(2)唯一性约束:指左图像中的任何点在右图像中最多一个点与之匹配,也就是说,无论是参考图像还是目标图像,任何点都不能同时匹配两个点。(3)顺序约束:对于相似深度的表面,对应的特征点一般以相同的次序落在极线上。(4)最大视差约束:视差范围约束指参考图像某个点的对应点只能在一定的范围内搜索,也就是说,两个匹配点横坐标相差必须小于某个最大视差阈值。

2.2.2算法描述本文基于SURF特征点提取过程,首先选取3个正确的匹配点对,下一步的改进提取算法如下:(1)对左右两幅图像分别取第i个基准点(xi,yi);(2)对左右两幅图像分别取第i个基准点(xi,yi);(3)得到新的基准点(xi,yi+3);(4)对两点(xi-10,yi+3),(xi+10,yi+3)间所有像素点进行遍历,判断该像素点灰度值是否大于200,若是,则提取该特征点坐标(xj,yi+3),保存该特征点并将该特征点作为新的基准点;(5)重复执行(2)(3)步,直到左右图像都遍历结束;(6)对得到的左右图像特征点点集合进行逐个对比,若同时满足xi左-xj右≤3且yi左-yj右≤3则匹配成功,则得到的(xi左,yi左),(xj右,yj右)为匹配成功的特征点对。根据上述改进算法,编写C程序,对图像处理,提取到34个特征点对,由于此方法提取得到的是特征点相对于原始图像的坐标,因此,其坐标数据显示结果如图7所示。图7改进SURF算法的特征点提取坐标示意图

Fig.7The diagram of the improved SURF algorithm coordinates of the feature point extraction图8W窗口内像素灰度和的计算

Fig.8W window pixel grayscale and calculations

图9特征点匹配算法流程图

Fig.9Feature point matching algorithm flowchart

图10改进SURF算法的特征匹配视差图

Fig.10Feature point matching algorithm floechart

2.3特征点的匹配根据这几个约束条件根据选取映射函数,对映射值取值,再判断映射点是否满足条件,满足后,根据双线性插值对图像进行插值,将插值之后和原始图像进行组合,得到匹配视差图。求窗口W内的像素灰度值时,W的大小可通过积分图像的4个相应点(i1,j1)、(i2,j2)、(i3,j3)、(i4,j4)的值计算得到,如图8所示,即窗口的像素灰度和与窗口尺寸无关。窗口W内的像素灰度和为:∑w=ii(i4,j4)－ii(i2,j2)－

ii(i3,j3)+ii(i1,j1)(4)通过该算法,结合改进的SURF算法提取到的特征点对,设置匹配算法流程如图9所示,在MATLAB图形处理软件中,采用C语言编程实现。处理得到特征匹配的视差图,如图10所示。3实验及结果分析结合MATLAB软件,对经过预处理得到的图像进行SURF特征点提取匹配得到29对特征点,再选取其中匹配正确的特征点对10对设为基准,再根据匹配约束条件共选取得到34对特征点,并与相应的SURF测量结果比较(见表1)。从测量结果可以看出,改进后的SURF特征点提取算法运行时间较SURF特征点提取匹配时间增加了0.12 s。 但是误匹配率却降低了约36.5%,匹配成功率得到了明显改善。通过对多幅图像对试验验证,匹配时间增加为0.2 s左右,而误匹配率均降低为40%左右,因此该方案具有可行性。由于前期对图像的剪切和结构光线细化结果中,大量减少了特征提取图像的像素数,从而缩短了整体匹配的运行时间。因此,本文对于匹配算法的改进中,又进一步完善了基于改进SURF算子的特征匹配算法。表1特征点提取算法实验结果比较

Tab.1Feature point extraction algorithm experimental results

特征点提取方法提取特征点对数误匹配对数误匹配率/%匹配时间/sSURF特征点提取291862.072.19SURF算法的改进34926.472.23

nlc202309040401

4结论本文基于线结构光双目视觉立体匹配技术,分析了特征匹配算法的优缺点,通过实验验证了SURF算子匹配方法对于线结构光的适用性,并且在特征匹配过程中,针对SURF特征点提取算法存在的缺陷做了进一步的改进,提高了匹配的精确性。通过对原始采集到的图像进行试验,表明了本文的方法基本可以达到预期匹配结果的要求,从误匹配率和匹配时间上都得到了较好的改善,对三维测量系统,具有重要的理论意义和较高的使用价值。参考文献：

［1］史玉升,李中伟,钟凯,等.结构光三维测量技术在模具设计与制造过程中的应用［J］.航空制造技术,2009,48(20):4850.

［2］桑瑞娟,张华,胡旭,等.一种改进的区域双目立体匹配方法［J］.传感器与微系统,2012,31(8):5859.

［3］穆绵,刘缠牢.一种光学元件面形三维重建的算法研究［J］.光学仪器,2013,35(2):4651.

［4］王月梅.双目立体视觉中图像匹配算法的研究［D］.西安:西安电子科技大学,2009:3355.

［5］李云飞.双目立体视觉中的稠密匹配算法研究［D］.杭州:浙江大学,2011:3144.

［6］郭铁芹.双目视觉立体匹配致密匹配算法的研究［D］.西安:西安电子科技大学,2010:3545.

［7］周秀芝.面向深度提取和形状识别的图像匹配［D］.长沙:国防科技大学,2006:1437.

［8］BRADSKI G,KAEBLER A.学习OpenCV［M］.于仕琪,刘瑞祯,译.北京:清华大学出版社,2009:129132.

［9］CONZALEZ R C,WOODS R E.Digital image processing［M］.2nd ed.New Jersey:Pearson Prentice Hall,2008:280300.

［10］SONKA M,HLAVAC V,BOY R.图像处理、分析与机器视觉［M］.北京:人民邮电出版社,2003:1453.

［11］VIOLA P,JONES M.Rapid object detection using a boosted cascade of simple features［C］∥ Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Kauai:IEEE,2001:38.

一种改进的单模式匹配算法 篇7

日前，绝大多数网络入侵检测系统都依旧是采用精确的模式匹配技术[1]，据公安部计算机信息系统安全产品质量监督检测中心的报告，国内送检的入侵检测产品95%是属于基于入侵规则模式匹配的特征检测产品[5]。当使用轻量级网络入侵检测系统snort 1.6.3对87, 000, 000数据包约超过1G byte的网络数据进行测试时，其测试结果表明，模式匹配过程是系统运行过程中代价最昂贵的部分，约占整个系统的31%[4]。显然，模式匹配在网络入侵检测系统中占有相当重要的地位，也极易成为系统性能瓶颈。

本文在分析BM、BMH算法的基础上，从概率论角度提出了改进的单模式匹配算法I-BMH (Improved-BMH) ，从整体上提高滑动窗口的最大平均值，从而提高匹配效率。

2. 背景知识简述

堪称经典之作的单模式匹配算法是BM (Boyer-Moore) [2]和BMH (Boyer-Moore-Horspool) [3]。

BM算法是首先使模式串Pat和主串Text的左端对齐，然后从右至左逐个匹配，若失配，根据启发策略操作，尽可能使模式串右移，使得Text失配字符与Pat中最右的相应字符对齐。

根据算法BM启发策略的不同，可将其分为坏字符移动和好后缀移动。坏字符移动是指，若该策略匹配过程中在Text[i]处匹配失败，如果存在最右的Pat[j]=Text[i]，将Pat[j]和Text[i]对齐，否则，使Pat[1]和Text[i+1]对齐，然后，继续下一轮比较；好后缀移动是指为充分利用失配时已成功匹配的字符串u，右移Pat使得Pat的某一最大子串v等于u的最大后缀u'，并且Pat[v]之前的字符不等于Pat[u']之前的字符。

算法BMH是利用算法BM的坏字符移动启发策略，当失配时，无论失配位置在何处，都以Pat最后一个字符所对应的当时Text的字符Text[i]为参考字符，Pat右移使得存在最右的与Text[i]相等Pat[j]同Text[i]对齐，否则，右移Pat使得Pat[1]同Text[i+1]对齐。

3. 单模式匹配算法的改进

为方便论述，本文设Pat=a1a2…aL为匹配的模式串，Text=b1b2…bn为匹配的文本串，Pat长度为L, Text长度为n, shift为模式匹配失配时Text指针右移距离，定义delta1 (char) 为[2]：

3.1 I-BMH (Improved-BMH) 算法

在采用坏字符启发策略时，无论是算法BM还是BMH，发生失配时每次右移距离均取决于失配时所选参考点Text中字符对应的delta1值。为了提高匹配效率，须尽量保证每次右移的shift值最大且尽量降低选取max{delta1}的比较次数，从而获得更佳的匹配效率。

从概率论的角度看，为获取最大平均右移距离，应降低失配参考字符/串S在Pat中出现的概率。|S|值越大S串出现在Pa中概率越小，但在实际应用中，为统一公式必须选取合适的|S值。

因此，本文提出了改进的算法I-BMH，并且选取|S|=2。下面论证公式的统一性、求法与|S|=2的必要性。

（Ⅰ）公式的统一性及求法

(1) 当delta1 (Text[i]) ∈[1, L-1]时，字串符Text[i]Text[i+1]须在下一次匹配过程中与Pat中某字符比较。若该字符串]出现在Pa中，则找出delta3 (Text[i]Text[i+1]) ，使得Text失配字符与Pat中最右的相应字符对齐。显然，若Text[i]≠Text[i+1]，delta3 (Text[i]Tex[i+1]) =delta1 (Text[i]) ，否则，delta3 (Text[i]Text[i+1]) =delta1 (Text[i]) +1;

(2) 当delta1 (Text[i]) =L时，字符串Text[i]Text[i+1]中的Text[i将不出现在下一次匹配过程中，此时Text[i]Text[i+1]也一定不出现在Pat中。显然，delta3 (Text[i]Text[i+1]) =L=delta1 (Text[i]) ；

由 (1) (2) 可知，当取|S|=2时，I-BMH算法的delta3 (Pat[i]Pat[i+1]) 取值情况为：若Pat[i]≠Pat[i+1]，delta3 (Pat[i]Pat[i+1]) =delta1 (Pat[i]) ，否则，delta3 (Pat[i]Pat[i+1]) =delta1 (Pat[i]) +1。与此同时，所有未出现在模式Pat中的排列Text[j]Text[k]对应的delta3值均为L。显然，满足公式统一且仅与模式串Pat本身相关。

（Ⅱ）|S|=2的必要性

为保障（Ⅰ）公式的统一性，须选取|S|=2。若取|S|=n, (L>n≥3) 则函数delta3必出现断点，因存在漏配现象的可能性而无法使公式统一。

因此，应选取|S|=2。

图1是I-BMH的一个匹配实例:

3.2 I-BMH算法优越性

因失配时决定主、从串右移距离的算法I-BMH总不小于BMH。所以，I-BMH平均性能优于BMH。

文献[5]采用改良的坏字符启发策略，文献[6]仅从数学平均期望值的角度获取算法BM和BMH中取值较大的为失配时的右移距离。文献[5]、[6]做法存在以下不足：

(1) 失配时多次查询匹配

文献[5]首先看Text[fail]与Pat关系，其次看Text[i-1]与Pa关系以及当Text[i-1]=Pat[j]时Pat[j-1]与Pat[fail]的关系，额外增加多次比较开销；文献[6]若要避免shift=max{delta1＿BM[Pat[i]], delta1＿BMH[Pat[i]]}选取比较开销，需要提前计算出相应的shift值，显然，此时的计算量要稍大于I-BMH的相应工作；

(2) 期待失配字符不在Pat中最大移动距离的平均概率偏低

设字符集∑长度为|∑|，从平均概率的角度看，Text[i]不出现在Pat中的概率为1-L/|∑|，而Text[i]Text[i+1]不出现在Pat的概率变为1-L/|∑|2。显然，若选取Text[i]Text[i+1]为shift值决定字符，Pat移动距离为L的概率比Text[i]或Text[i+1]大 (1-L/|∑|2) - (1-L/|∑|) =L* (|∑|-1) /|∑|2。

因此，算法I-BMH平均性能优于BMH以及文献[5]、[6]中阐述的两种坏字符启发策略。

4. 算法时间复杂度分析与实验结论

4.1算法时间复杂度分析

时间复杂度包括右移动次数shiftn和每次回溯比较次数cmpn，总比较次数即为shiftn*cmpn。

若每一轮比较已开始便失败且shift右滑模式长度L，算法I-BMH获最好性能，时间复杂度为O (n/L) ；若每一轮比较直至匹配完整个模式长度L的最后一个字符失败且shift右滑长度为1，算法I-BMH获最坏性能，时间复杂度为O (n*L) 。那么，它的平均性能时间复杂度如何呢?

对于主串Text的任一字符bi，要么出现或要么不出现在模式串Pat中。所以，失配时平均右移距离为：

而

因此，匹配过程中shift向右平均移动总次数为n/shift＿aver。每次右移前发现失配情况出现需要进行的平均比较次数为cmp＿aver= (1+L) /2。所以，算法I-BMH总的平均比较次数total为：

4.2 实验及结论

本文实验机配置：Pentinum (R) 4 CPU 2.66GHZ，内存512MB，硬盘80G，操作系统Redhat9.0, Linux C；根据参考文献[2][3]及本文实现算法，选取RFC2461.txt (约223KB) 的IPv6邻居发现协议作为测试数据源，以ASCII字符集为模式串构造源随机构造模式规则数，统计总时间，实验结果如右表所示。

结果表明，算法I-BMH平均匹配效率得到一定程度提高。

5. 小结

本文在分析单模式匹配算法BM及BMH的基础上，从概率论的角度论述了如何最大限度的保障匹配失配时，模式串向右滑动距离总和的平均值最大，以及如何选取恰当的参考模式串长度。实验结果表明，改进后的算法平均匹配效率得到一定程度的提高。

摘要：本文在分析单模式匹配算法BM和BMH的基础上, 从概率论的角度分析了如何保障匹配失效时最大限度的滑动模式串, 以及如何选取参考滑动模式串的长度, 提出了改进的单模式匹配算法I-BMH。实验结果表明, 改进后的模式匹配算法平均效率得到一定程度的提高。

关键词：模式匹配,BM,BMH,I-BMH

参考文献

[1]CHEN Xun-xun, FANG Bin-xing.Optimizing of large-number-pat-terns string matching algorithms based on definite-state automata[J].Journalof Harbin Institute of Technology, 2007, 14 (2) :236-239.

[2].Boyer RS, Moore JS.A fast string searching algorithm[J].Communicationof the ACM.1997, 20 (10) :762-772

[3].R.Nigel Horspool.Practical fast searching in strings.Software Practiceand Experience.1980, 10 (6) :501-506

[4].Mike fisk, George Varghese, Fast content-based packet handling for in-trusion detection[R].UCSD Technical Report CS2001-0670.2001-05

[5].宋明秋等.IDS中新的快速多模式匹配算法及其设计[J].计算机工程与应用.2005 (21) :159~162

一种改进的多模式匹配算法 篇8

近期研究表明，在宽带网络环境下的网络入侵检测系统面着高临丢包率带来高漏检率的问题。如何提高入侵检测系统性能，降低丢包率，是当今宽带网络入侵检测系统面临的一难点。

目前，绝大多数网络入侵检测系统是采用精确的模式匹配技术[1]，据公安部计算机信息系统安全产品质量监督检测中心的报告，国内送检的入侵检测产品95%是属于基于入侵规则模式匹配的特征检测产品[7]。使用轻量级网络入侵检测系统snort 1.6.3对87, 000, 000数据包约超过1G byte的网络数据进行测试，其测试结果表明，模式匹配过程是系统运行过程中代价最昂贵的部分，约占整个系统的31%[6]。显然，模式匹配在宽带网络入侵检测系统中占有相当重要的地位。

因此，本文对网络入侵检测系统模式匹配算法做了较为深入的研究，提出了改进的多模式匹配算法AC＿I-BMH。

2. 背景知识简述

模式匹配算法主要分单/多模两类。堪称经典之作的BM[2]和BMH[3]属于单模式匹配算法，AC[4]和AC＿B M[5]属于多模式匹配算法。

BM算法是首先使模式串Pat和主串Text的左端对齐，然后从右至左逐个匹配，若失配，根据启发策略操作，尽可能使模式串右移，使得Text失配字符与Pat中最右的相应字符对齐。根据算法BM启发策略的不同，可将其分为坏字符移动和好后缀移动。BMH算法是利用BM算法的坏字符启发策略，当失配时，无论失配位置在何处，都以Pat最后一个字符所对应的当时Text的字符Text[i]为参考字符。

AC算法开创性的解决了多模式匹配问题，一定程度上弥补了单模式匹配算法在面临多模式匹配需要进行多次循环匹配的缺点。AC利用自动机可以组合模式集Keyset中存在的不相关的模式串，比单独多次使用BM及其变种算法实现多模式匹配速度快。AC＿BM算法是AC算法的一种改进，能够实现跳跃式匹配，跳过Text中无需比较的字符，速度较AC算法好。

3. 多模匹配算法的改进

为方便论述，本文设Pat=a1a2…aL为匹配的模式串，Text=b1b2…bn为匹配的文本串，Pat长度为L, Text长度为n, shift为模式匹配失配时Text指针右移距离，定义delta1 (char) 为[2]：

3.1 模式匹配算法剖析

实质上，对于单模式匹配算法，无论是BM还是BMH，在采用坏字符启发策略时，发生失配的每次右移距离均取决于失配时所选参考点Text中字符对应的delta1值。为了提高匹配效率，须尽量保证每次右移shift值最大且降低选取max{delta1}比较次数，从而获得更佳的匹配效率。

对于多模式匹配算法，算法AC融入了KMP思想，致使无法跳过无须匹配的文本串字符，匹配速度不及AC＿BM；算法AC＿BM，虽然弥补了算法AC存在的不足，但算法AC＿BM构造的规则树必须要求Keyset各模式串相关，无法实现一次匹配含有不相关模式的模式集。

因此，本文从概率论及模式集相关性的角度出发，提出了一种改进的多模式匹配算法AC＿I-BMH，既提高了多模式匹配效率，又允许模式间存在不相关性。

3.2 AC＿I-BMH算法

对于采用坏字符启发策略的算法BM及BMH，从概率论角度看，为获取最大平均右移距离，应降低失配参考字符/串S在Pat中出现的概率。虽然|S|值越大这种概率越小，能够获得更佳的平均右移距离，但是，在实际应用中，为统一公式应选取合适的|S|值。经研究证明，应取|S|=2，即失配时选取参考字符Text[i]Text[i+1]决定Pat右移距离shift，其shift值delta3的计算方法为：

本文将这种模式匹配算法简称为I-BMH (ImprovedBMH），图1是I-BMH的一个匹配实例：

AC＿I-BMH算法是利用了AC算法自动机的机制和I-BMH算法的高效性，抛弃了AC＿BM算法构成模式树的模式相关性要求与从Text尾部开始匹配的做法，以自动机方式实现自左至右的快速匹配，既允许模式集存在不相关性，又能跳过Text中无须比较的字符，进一步加速了匹配效率。

假设模式集Keyset={he, she, his, hers}，文本串Text="...herushersmehh…"，图2 (a) 显示了构造的自动机变迁的GOTO函数[4]，构造方式不同于AC，采用逆向模式串读取方法，使匹配过程类似于BM等同类算法；图2 (b) 是自动机的输出函数Output[4]，图2 (c) 是模式串集各字符的delta1函数值，而图2 (d) 是I-BMH算法所需的delta3函数。其中，对于最短模式长度为min＿L的模式集Keyset={k1, k2, …, kk}delta1的求法是，将所有模式串逆序右对齐，先找出各个模式中各字符的delta1值，最后求得最终delta1值，即

图2 (e) 是AC＿I-BMH的匹配实例。首先，从文本Text左端起跳过模式集中最小模式长度个字符。然后，从该字符起自右至左读入字符输入自动机进行匹配，比如，首先使Text的指针shift指向e，然后读入e、h使自动机从状态0跳变至2，产生Output (2) ={he}，匹配成功一个模式，此时的右移参考字符delta3[er]=2，而r属于模式集，Text指针右移shift=2个位置至u。最后，从u向左读入字符进行匹配，如此循环，直至结束。

4. 算法时间复杂度分析与实验结论

4.1 算法时间复杂度分析

时间复杂度包括右移动次数shiftn和每次回溯比较次数cmpn，总比较次数即为shiftn*cmpn。若每一轮比较已开始便失败且shift右滑最小模式长度min＿L，算法AC＿I-BMH获最好性能，时间复杂度为O (n/min＿L) ；若每一轮比较直至匹配完最大模式长度max＿L后失败且shift右滑长度1，算法AC＿I-BMH获最坏性能，时间复杂度为O (n*max＿L) 。那么，它的平均性能时间复杂度如何呢?

对于主串Text的任一字符串bibi+1，要么出现或要么不出现在模式串Pat中。所以，失配时平均右移距离为：

而

因此，匹配过程中shift向右平均移动总次数等于n/shift＿aver。每次右移前发现失配情况出现需要进行的平均比较次数为

所以，总的平均比较次数total为：

4.2 实验及结论

本文实验机配置Pentinum (R) 4 CPU 2.66GHZ，内存512MB，硬盘80G，操作系统Redhat9.0, Linux C。根据文献[4,5]以及本文实现算法，从Snort2.4.5规则集中选取600条规则作为测试模式集，选取MIT Lincon Lab提供的1999年入侵检测第四周第一天数据outside.tupdump (约206MB、1, 279, 543packets的tcpdump文件, http://www.ll.mit.edu/IST/ideval/data/data＿index html) 作为多模式测试数据源，利用Tcpreplay (http:/tcpreplay.synfin.net) 回放该数据源，统计平均每个网络包的平均处理时间，其结果如右表。

实验数据表明，本文改进后的多模式匹配算法AC＿I-BMH平均匹配效率得到一定程度提高。

5. 小结

为适应宽带网络入侵检测系统对模式匹配算法高速性的要求，本文提出了一种改进的多模式匹配算法AC＿I-BMH，既提高了多模式匹配效率，又允许模式间存在不相关性。实验结果表明，改进后的算法平均匹配效率得到一定程度的提高。

摘要：为适应宽带网络入侵检测系统对模式匹配算法高速性的要求, 本文在分析主流的模式匹配算法的基础上, 从概率论及模式相关性角度提出了一种改进的多模式匹配算法ACI-BMH。实验结果表明, 改进后的算法平均效率得到一定程度的提高。

关键词：网络入侵检测,模式匹配,BM,AC,ACI-BMH

参考文献

[1]CHEN Xun-xun, FANG Bin-xing.Optimizing of large-num-ber-patterns string matching algorithms based on definite-state au-tomata[J].Journal of Harbin Institute of Technology, 2007, 14 (2) :236-239.

[2].Boyer RS, Moore JS.A fast string searching algorithm[J].Com-munication of the ACM.1997, 20 (10) :762-772

[3].R.Nigel Horspool.Practical fast searching in strings.SoftwarePractice and Experience.1980, 10 (6) :501-506

[4].A Aho, M Corasick.Efficient string matching an aid to biblio-graphic search.Communication of the ACM, 1975, 18 (6) :333~340

[5].C Jason coit, Stuart Staniford.Toward faster string matching forintrusion detection or exceeding the speed of snort[J].IEEE, CSPress, 2001:367-373

[6].Mike fisk, George Varghese, Fast content-based packet handlingfor intrusion detection[R].UCSD Technical Report CS2001-0670.2001-05

入侵检测系统的融合模式匹配算法 篇9

应用于入侵检测系统的经典的模式匹配算法包括单模式匹配算法[1]中的KMP算法、BMG算法[2]、BMHF算法[3]、RK算法[4]和多模式匹配算法中的AC算法、AC—BM算法[5]。目前随着对各种算法的研究不断深入,提出了不同的改进方法,同时也曝露了一些缺陷。本文提出了入侵检测系统的融合模式匹配算法,经过实验验证取得了较好效果。

1 处理公共前缀字符串

1.1 构造公共前缀字符串

转换待匹配的字符串集合为一个树状有限状态自动机(类似于Aho-Corasick算法),使其基于字符串的前缀得以构建。

1.2 公共前缀字符串匹配算法

定义一个函数Q(X)[7,8],当字符X∈P,并且仅出现过1次时,Q(X)返回值为1,否则返回值为0,即

(1)自右向左进行匹配,若成功,应用Q(P[m])检查模式串中出现P[m]的次数,如出现次数为1,则将此次匹配过程中第1个Q(T[i])=1的指针i的值用一个变量p来记录,并继续比较。

(2)若某处匹配失败且p≠0,可以知道只出现过1次的字符存在于已匹配字符串中,则应修改文本串T的指针为i+p,用K1为其赋值;若p=0,可知p中多次出现过匹配失败之后的字符,则应修改T的指针为i+Pdist[T[i]](假设匹配失败发生在i处),用K1为其赋值。也就类似于在下一次匹配进行时,模式串开始于P[m],文本串开始于T[Pdist[T[i]]]。

(3)e+1+Pdist[e+1]是由模式串末端对应文本串字符T[i]下一位字符T[e]得到的右移位置,可将其赋值给K2。

(4)对K1、K2的大小进行判断,若K1大于K2,则应对齐模式串末端P[m]与T[K1]处,并使新一轮匹配得以进行,同时P值置0;若K1小于K2,则应对齐模式串末端P[m]与T[K2]处。

(5)新一轮匹配仍使用上面的规则。

函数Pdist的描述(见图1),函数Q(X)的描述(见图2)。

在文本串和公共前缀字符串按上述算法的匹配过程如表1所示。

2 匹配结束处理

(1)如果匹配的字符串集合只有一个字符串则整个匹配过程结束,否则执行第二步。(2)匹配成功后,以匹配成功处为起点再执行第一步,反复执行第一步直到文本末尾。(3)文本被匹配成功的公共前缀字符串分为n段,从文本的第一个公共前缀字符串开始到下一个公共前缀字符串之前作为字符串L1,从文本的第二个公共前缀字符串开始到下一个公共前缀字符串之前作为字符串L2,以此类推分别得到L1,L2,…,Ln-1,

3 在L1,L2,…,Ln-1中利用以下算法分别与模式串匹配

算法描述:输入:字符串树root,正文T[1..n],minlenl,maxlenl;输出:字符串位置。算法:i=n-–minlenl;while(i>=0){j=i;ctNode=root;while(ctNode->child[T[j]]!=NULL){ctNode=ctNode->child[T[j]]);if((ctNode->label)>=0){output(ctNode)j++;if(j>n)break;}}i=i-skip(T[i]);}其中skip的计算公式为:if存在k,j使Pk[j]=char,0<j≤minlenl skip(char)=min{j|Pk[j]=char,0<j≤minlenl,1≤k≤q,q为字符串树中字符串的个数;else skip(char)=minlen

实验1试验环境:将Pentium IV 1.5 GHZ作为主机处理器,采用MinGWDeveloper Studio作为编译器,用纯文本数据作为测试数据,用不同的文本及模式对不同算法进行匹配次数测试,表2即为测试结果。

由表2结果可知,相比较BM算法和BMHF算法,后者在的匹配次数在测试文本1中减少了14.5%,在文本2中减少了12.8%,在文本3中减少了10.3%,平均起来减少了12.5%。融合算法的匹配次数相对BMH、BMHS算法,明显减少。

实验2试验环境:CPU Intel P4,2.0G,内存512M,操作系统为Windows2000 Server,在Windows2000下使用VC6.0编译过的snort2.0作为测试本算法的入侵检测系统,使用规则为snort2.0默认值。用1999年美国国防部高级研究计划局(DARPA)做IDS评估时使用的数据集作为测试数据,大量的正常网络流量和各种攻击都囊括其中,极具代表性。表3为一个星期的数据。

由表3结果可知,融合算法优于AC-BM算法。

4 结论

该融合算法兼容了单模式匹配算法和多模式匹配算法的优点,即能完成单模式匹配又能完成多模式匹配,实验证明该算法减少了匹配次数,提高了效率,识别了正文的大小写。

摘要：运用入侵检测系统的融合模式匹配算法取得待匹配的字符串集合的公共前缀与文本匹配,若为单模式匹配则匹配结束,若为多模式匹配则将文本被分割成的字符串集中的字符串分别与模式串匹配,该融合算法对单模式匹配和多模式匹配均提高了效率,识别了正文的大小写。

关键词：融合算法,公共前缀,单模式匹配,多模式匹配,效率

参考文献

[1]牟永敏,李美贵,梁琦.入侵检测系统中模式匹配算法的研究[J].电子学报,2006,34(B12):98-100.

[2]张娜,张剑.一个快速的字符串模式匹配改进算法[J].微电子学与计算机,2007,24(4):102-105.

[3]姜庆民,吴宁,刘伟华.面向入侵检测系统的模式匹配算法研究[J].西安交通大学学报,2009,43(2):58-62.

[4]蔡晓研,戴冠中,杨黎斌.一种快速的单模式匹配算法[J].计算机应用研究,2008,25(1):45-49.

浅谈字符串模式匹配的常用算法 篇10

随着计算机技术的日新月异, 计算机的应用早已不限于数值计算, 而是更多的用于非数值计算的处理, 而非数值计算处理的对象很多都是字符串数据。字符串作为一种数据类型出现在更多的程序设计语言中, 同时也产生了一系列字符串相关的操作。字符串简称为串。在一些常见的应用程序中, 如学生的姓名和性别以及学生的民族、籍贯等一般都是作为字符串处理的, 合理的设计和应用字符串的各种操作变得尤为重要。子串定位操作是字符串串处理中最重要的运算之一, 而且字符串的模式匹配算法在计算机领域一直都是一个研究热点。

1 基本概念

字符串的定位操作亦被称为串的模式匹配。什么是模式匹配呢?模式匹配就是判断某个串, 亦称为模式串是否是其它给定串的子串。若是给定串的子串, 则返回该子串的起始位置, 即该串的第一个字符在给定字符串的数组的下标的位置。若不是, 则给出匹配不成功或不是子串的信息 (0或假) 。模式匹配的现实应用非常广, 例如在信息检索程序、文字编辑及翻译系统、实时对答系统、搜索引擎、特征码匹配以及DNA匹配等应用中, 都要用到串匹配操作。

2 模式匹配的基本算法

首先介绍一种最基本最简单的模式匹配算法, 它是一种回溯的匹配算法。也称为BF算法 (Brute-Force, 最基本的字符串匹配算法) , BF算法基本思路很简单:设置计数指针i和j分别指示主串S和子串即模式串T中目前正待比较的字符的位置。从主串S的首个字符开始和子串的第一个字符进行对比, 如果相等, 则继续逐一比较后面的每一个字符;若不相等则回溯, 从主串的当前与比较字符的下一个字符起重新和子串的第一个字符进行对比, 以此类推, 直到子串T中的每个字符都与主串S中的一个连续的字符串序列相等, 此时匹配成功, 函数返回值为与模式串T中的首个字符相等的字符在主串S中的数组下标的位置, 否则返回匹配不成功的信息。例如模式串T=”abcac”, 主串S=”ababcabcacb”, 函数返回值应该为6。

3 模式匹配的改进算法之KMP算法

这种由Knuth和Pratt以及Morris同时研究发现的改进的模式匹配算法, 简称KMP算法。算法的核心思想是利用已经得到的部分匹配信息来进行后面的匹配过程。它是一种在一个字符串中定位另一个串的高效算法, 简单匹配算法的时间复杂度为O (m*n) ;而KMP匹配算法, 可以证明它的时间复杂度为O (m+n) , 即算法可以基于时间复杂度O (m+n) 完成字符串的模式匹配操作。其改进之处主要表现在:当某一趟匹配过程中出现字符比较不匹配的时候, 不需要位置指针i进行回溯, 而是利用已经得到的“部分匹配”的信息将模式向右移动尽可能长的一段距离后, 继续进行下一次比较。

KMP算法的基本思路是:主串设为S, 模式串设为T, 通常的的做法即我们的期望的是某一趟匹配过程中, S[i]和T[j]匹配失败, 指针i不回溯, 模式串T向右移动至某个特定的位置上, 使得T[k]对应于S[i]继续向右进行匹配。很明显, 现在我们要解决的关键问题是串T移动到哪个位置上?假设此位置为k, 即S[i]和T[j]匹配失败后, 指针i不动, 模式串T向右移动, 使T[k]和S[i]对应上并继续向右进行比较, 这里把主串表示为S=s1s2s3…sn, 模式串表示为T=t1t2…tm。要满足这一假设, 就要有如下表达式成立:

式子左边是tk前的k-1个字符, 右边是si前的k-1个字符。而本趟匹配失败是在si和tj之处, 从此次匹配可得到的部分匹配结果是:

由于k

式3左边是tj前的k-1个字符, 右边是si前的k-1个字符, 通过 (式1) 和 (式3) 得到关系:

可得出结论:某一趟匹配在si和tj匹配失败后, 如果模式串中有满足关系4的子串存在, 就是说模式串中的前k-1个字符与模式串中tj字符前面的k-1个字符相等时, 模式串T就可以向右移动从而令tk和si对应上, 从而继续向右进行比较即可。求得模式的next函数之后, 匹配操作可继续进行:假设以指针i和j分别指示主串和模式串中的比较字符, 令i的初值为pos, j的初值为1。若在匹配过程中si≠tj, 则i和j分别增1, 若si≠tj匹配失败后, 则i不变, j退到next[j]位置再比较, 若相等, 则指针各自增1, 否则j再退到下一个next值的位置, 依此类推。直至下列两种情况:一种是j退到某个next值时字符比较相等, 则i和j分别增1继续进行匹配;另一种是j退到值为零 (即模式串的第一个字符) , 则此时i和j也要分别增1, 表明从主串的下一个字符起和模式串重新开始匹配。

模式匹配的KMP算法是一种改进的模式匹配算法, 之所以要改进, 是因为它较以前模式匹配的朴素算法有更高的效率和完整性, 更适合实际程序开发的需要。在实际应用中, 根据具体应用要求的不同, 可以自己设计更合理的结构, 基于结构设计出更适合自己应用需要的模式匹配算法, 不要过分拘泥于固有的形式和算法。

参考文献

[1]郝春梅.数据结构 (C语言版) [M].北京:清华大学出版社, 2010

[2]严蔚敏, 吴伟民.数据结构 (C语言版) [M].北京:清华大学出版, 2008

模式匹配算法 篇11

瞄准策略实Robocode机器人最基本的策略之一, 好的瞄准策略可以使我们赢得整个战斗, 要想打中敌人, 就要提高子弹的命中率, 也既要设计良好的瞄准系统, 在Robocode中有定点瞄准、直线预测瞄准、圆周预测瞄准等瞄准策略, 本文探讨了一种新的瞄准策略, 即模式匹配瞄准策略, 通过记录对手的历史记录, 进一步匹配历史记录, 预测对手的运动位置, 实现了更为精确的瞄准, 也是机器人的一种自我学习过程。

1. Robocode简介

Robocode是一个机器人战斗仿真器, 可以在所有支持Java2的平台上运行。创建一个机器人, 把它放到战场上, 然后让它同其他开发者们创建的机器人对手拼死战斗到底。Robocode里有一些预先做好的机器人对手让你入门, 但一旦您不再需要它们, 就可以把您自己创建的机器人加入到正在世界范围内形成的某个联盟里去和世界最强手对阵。

每个Robocode参加者都要利用Java语言元素创建自己的机器人, 这样就使从初学者到高级黑客的广大开发者都可以参与这一娱乐活动。初级的Java的开发者们可以学习一些基础知识:调用API代码、阅读Javadoc、继承、内部类、事件处理等等。高级开发者们可以在构建"最优品种"的软件机器人全球竞赛中提高他们的编程技巧。

Robocode里的每个机器人都由一个或多个Java类构成。这些类可以被压缩成一个JAR包。为此, Robocode的最新版本提供了一个可以在战场GUI窗口中激活的"Robot Packager"。

Robocode机器人是一个图形化的坦克, 机器人有一门可以旋转的炮, 炮上面的雷达也是可以旋转的。机器人坦克车 (Vehicle) 、炮 (Gun) 以及雷达 (Radar) 都可以单独旋转, 也就是说, 在任何时刻, 机器人坦克车、炮以及雷达都可以转向不同的方向。缺省情况下, 这些方向是一致的, 都指向坦克车运动的方向。

2. 现有的瞄准算法

目前常见的瞄准算法说明如下:

Headon:正对瞄准

Linear:直线瞄准

circular:圆周瞄准

nearest robot:接近机器人瞄准

Angular:找到最佳角度瞄准

Wave:波形瞄准, 子弹以波的方式进行探测

以上一些瞄准算法都是针对固定模式的瞄准算法, 比如直线提前量算法, 如果对手不是走直线, 就打不准;而圆周运动算法是针对做圆周运动的机器人的, 如果对手走S型路线, 要设计一套S行路线的瞄准算法;遇到走三角形路线的, 又要设计一套新的算法。如果对手的运动模式不断变化, 一会儿做圆周, 一会儿做S型, 该怎么办, 使用圆周算法瞄准还是S型算法瞄准?显然, 原来的思路出现了局限性。这里将要介绍一种技术, 能让机器人自己识别对手的运动模式, 然后从对手的模式推导出瞄准点, 不管对手怎样变, 只要有规律, 都能打得很准。这可以说是一种具有学习能力的算法了。

3. 算法分析

模式识别 (Pattern Recognition) 是指对表征事物或现象的各种形式的 (数值的、文字的和逻辑关系的) 信息进行处理和分析, 以对事物或现象进行描述、辨认、分类和解释的过程, 是信息科学和人工智能的重要组成部分。

有相似性的样本在模式空间中互相接近, 并形成"集团", 即"物以类聚"。其分析方法是根据模式所测得的特征向量Xi= (xi1, xi2, …, xid) T (i=1, 2, …, N) , 将一个给定的模式归入C个类ω1, ω2, …, ωc中, 然后根据模式之间的距离函数来判别分类。其中, T表示转置;N为样本点数;d为样本特征数。

在Robocode中, 如果对手机器人使用任何重复的模式, 就可以采用这种瞄准算法。基本概念是记录并寻找相似样本, 样本一般情况就是指对手的运动状态, 也就是说寻找相似的运动状态。比如对手做直线运动10个单位距离后又做20个圆周运动, 然后又开始做直线运动, 在做完9个单位距离之后你会预测它紧接着会怎样运动?按照常规的经验来分析, 会推测它会继续作1个单位的直线运动接着做圆周运动20周, 然后又做直线运动。为什么会做出这样的推断?首先, 因为首先记录了它原来的运动, 它原来是运动10次直线, 然后20个圆周, 其次做了比较, 找出了最匹配的地方, 把这9个单位距离直线直线运动, 看做它原来做10个单位距离的开始9个, 所以推断它还会按照原来的规律继续下去, 如果对手真是有这样的规律, 那么将击中它。模式匹配算法也正是采用了这两个步骤实现了推断能力。实际上通常的机器人运动都是有规律的, 只是有的很明显, 变化少, 有的不很明显, 变化多, 很显然对于前者, 模式匹配算法会打的很好, 对于后者, 可能效果略差。

通过上述分析, 我们的机器人有了一定的学习能力, 但是这只是很简单的学习, 应该加入一些其他样本信息会更好些, 可以采用运动方向、速度和转动速度作为比较样本。

4. 算法设计与实现

根据刚才的分析, 模式匹配算法主要是两个步骤, 记录对手运动状态的样本和执行匹配算法寻找最佳匹配点。实际上算法大体可以说就是三步, 如下图所示:

射击策略主要思路是用一个800长度的数组纪录一个直线提前量射击策略的Prediction Angle每个记录点都记录从自己子弹到敌人这段时间里Prediction Angle的累加

需要射击时, 寻找一个历史中 (所有以前的记录节点中) 完成了累加的, 而且与目前的Prediction Angle最相似的记录节点 (也就是以Prediction Angle最相似

就视为运动方式最相似) , 那么, 敌人以后的运动因该和历史中的那段运动情况很相似 (也就是历史重现) 。

找到了历史要重现的地方了, 那么用那段历史中的平均Prediction Angle作为射击Angle射击, 根据以上分析, 这里给出一个示例方案的相关代码:

5. 实验结果

创建一个新的机器人, 命名为PMRobot, 采用上面的相关代码, 建立成功后, 新建战斗选择此机器人, 再选择一个做圆周运动的机器人 (Spin Bot) 作为它的对手, 可以看到在对手饶几圈之后, 就能打得很准了, 说明机器坦克学习懂了对手的规律。换个绕墙走的对手 (Walls) , 基本上对手绕墙一圈后, 就能打得很准了, 再换其他规律的对手, 看看效果, 可以看出, 很多有规律的机器人, 不管它的规律是什么样的, 它几乎都能通过学习一段时间打的越来越好。

6. 改进与扩展

虽然该机器人已经拥有了学习能力, 但是这只是很简单的学习, 因为在做样本比较的时候, 只是比较了对于迭代推断敌人未来位置有用的敌人方向和敌人速度, 如果再加入一些其他样本信息, 可能会更好, 注意比较的样本信息必须是跟敌人运动有关系的才有用, 否则只会取得相反的效果。比如, 如果加入敌人的转动速度作为比较样本, 则比较有用, 但是加入敌人的能量作为比较信息, 则大部分情况都不会有用。还有, 只是比较了一个单位时间的样本 (当前样本和历史中的每一个样本比较) , 对于刚开始分析的时候举的例子, 敌人圆周运动几圈是需要若干个单位时间的, 因此, 如果增加比较的样本数量 (从当前到n个单位时间以前的一系列样本, 和历史中相同长度的一系列样本的比较) , 则更会取得更好的效果。方方面面的改进还有很多。具体实现这里就不多述。但比较的越多, 程序用的时间越长, Robcode中每个机器人每个单位时间所能用的计算时间是有限的, 因此在做改进的时候, 不能一味的增加复杂度, 以至于机器人运算超时而被系统强行终止。找出最有效的样本, 最合适的样本比较长度, 最合适的记忆长度, 才能写出最强的模式匹配机器人。

7. 结束语

模式匹配的优点是能够观察出敌人运动轨迹的规律, 并预测敌人未来出现的位置, 因此一些很有运动规律的机器人将很难逃过模式匹配的法眼, 但是正如它的优点的前提所说, 它只对有运动规律的机器人很有效, 而对于运动模式非常随机的机器人, 可能就不是那么有效了。绕如果机器人加入了反向的随机因素, 这增加其实战中对于模式匹配机器人的扰乱效果。模式匹配是个很复杂的领域, 它在人工智能中的作用也是非常大, 这里只是它的一个很小的应用。

摘要：通过分析现有Robocode的几种瞄准策略, 提出了模式匹配瞄准算法。模式匹配瞄准算法是记录并寻找相似的对手的运动状态, 并推测对手的运动方向、速度从而精确的击中对手, 本文给出了模式匹配算法的实现步骤和具体的实现方法。实验证明, 模式匹配算法是一种有效的瞄准算法。

关键词：模式匹配算法,Robocode机器人,瞄准策略

参考文献

[1].Mat Buckland《Programming Game AI by Example》Wordware Publish-ing, Inc.2005

[2].刑文训, 谢金星《现代优化计算方法 (第2版) 》清华大学出版社2005

[3].Steve Rabin著, 庄越挺等译《人工智能游戏编程真言》清华大学出版社2005

[4].朱福喜编著:《JAVA语言程序设计》, 清华大学出版社2005版

[5].唐钟、李磊民编著:《坦克机器人合作策略中的瞄准算法》, 西南工学院学报2001版

[6].张颖, 刘艳秋编著:《软计算方法》科学出版社2002

[7].刘正林, 周纯杰, 周凯波编著:《Java技术基础》, 华中科技大学出版社2004版