基于统计特征的模式匹配算法
基于统计特征的模式匹配算法
摘要
针对传统模式匹配算法的按模式中字符排列顺序匹配的过程，该算法模拟人脑思维利用模式中字符出现频率、位置等特征信息建立了一个新的匹配序列，打乱了原来的顺序匹配过程，从而在匹配过程中，利用特征信息尽可能的跳过更多的字符，从而达到比较高的匹配效率。该算法的另一大特点就是不需要遍历完所有文本中的字符就可以找出与模式匹配的字符串。与传统的BF、KMP、BM 等算法相比，该算法的平均时间复杂度已经达到了他们的最好情况。
关键词：模式匹配；算法；统计特征
Abstract
The difference to the traditional Algorithm of String-Matching is this algorithm uses the statistic characteristic of the position and frequency of the char to build a new matching list. During the process of the matching, this algorithm will try its best to use this characteristic to skip much more chars to improve the efficiency of the matching. Another characteristic of this Algorithm is it can successfully finish without comparing all chars in the Text. Comparing with the Algorithm before, like BF ,KMP, BM, this Algorithm’s average complication of time reaches then best condition of these.
Keywords: string-matching; algorithm; statistic characteristic
目录
引言 (1)
1绪论 (2)
1.1 基于统计特征的模式匹配算法提出原因 (2)
1.2 基本数据规定 (2)
2传统的模式匹配算法 (2)
2.1 BF算法 (2)
2.2 KMP算法 (3)
2.3 BM算法 (5)
3基于统计特征的模式匹配算法 (5)
3.1算法思想 (5)
3.2算法分析 (7)
结束语 (9)
参考文献 (10)
字符串匹配是字符串的基本运算之一。串的模式匹配即子串定位，是一种重
要的串运算。模式匹配就是在主串S= s
1s
2
s
3
s
4
……中查找模式串T= t
1
t
2
t
3
t
4
……
的所有出现，该技术在很多领域都发挥重要的作用，比如在情报检索、网络搜索、文本检索、拼写检查、语言翻译、数据压缩、网络入侵检测、计算机病毒特征码匹配以及DNA序列匹配等各个方面都有着很重要的应用。通过模式匹配，我们可以得到很多我们想要知道的信息，而这些是靠人工难以完成的。尤其是在以后的段落搜索，自然语言查询中，对模式匹配的速度、效率等要求会越来越高，而传统的BF、KMP和BM等算法并不能很高效的给出结果，因此我们有必要对模式匹配的算法进行进一步发展。本文主要在介绍了BF算法、KMP算法的基础上提出一种更好的算法—基于统计特征的模式匹配算法。
我们在日常生活中经常以局部特征判定事物，而这种方式是普遍认可的，也是最佳的。一项将此技术应用于计算机科学领域的就是基于统计特征的模式匹配算法。
1.1 基于统计特征的模式匹配算法提出原因
对于KMP、BM等算法有一个共同的特征：顺序扫描—或者从左至右，或者从右至左。这样的好处是匹配时有顺序的规律可循，比较容易理解，操作起来比较方便，缺点就是没有最大限度利用模式自身的一些统计特征—而只是利用了顺序的特征。如何利用统计特征呢？举个例子来证明。在街上我们遇到了一个似曾相识的人，我们判断那个人是不是我们认识的人的时候，我们是把遇到的那个人与我们记忆中的那个人的特征相比较，比如说秃顶，眼角有颗痔，身高，性别，胖瘦，脸型，肤色等等。我们比较是鲜明的特征，而不是从头到脚的扫描比较。也就是说我们在比较两个事物的时候是优先比较他们比较特殊的地方。对于模式匹配，这个优先级似的比较方式依然成立。
1.2 基本数据规定
传统的算法分析在有了模式匹配的需要后，出现了很多模式匹配的算法，在这里为后续内容分析而规定：主串S的长度为n，模式串T的长度为m，子串的定位操作Index(S,T,pos)，其中pos为某个字符在主串中的位置。
2传统的模式匹配算法
本章介绍三种典型的传统的模式匹配算法，并分别给出部分算法实现。2.1 BF算法
BF（Brute-Force）算法即简单模式匹配算法，也称朴素串匹配算法算法，其算法思想：对主串S和模式串T进行从左至右顺序匹配比较，若主串S的第一个字符和模式串T的第一个字符进行比较，若相等则同时向后移动一位，继续逐个比较后续字符，否则如果在完全匹配结束前发生不匹配，那么模式串T回溯到模式首字符，而主串S则回溯到起始位置的下一个字符进行比较。依次类推，直至模式串T和主串S中的一个子串相等，此时称为匹配成功，否则，称为匹配失败。图2-1展示了pos=1时，模式串T=’abcac’和主串S=’ababcabcacbab’的匹配过程。其中i和j指示主串S和模式串T中当前正待比较的字符位置。
串的简单模式匹配算法描述如算法2-1所示。
【算法描述】
int Index(SString S, SString T, int pos)
{
int i, j;
i=pos; j=1;
While (i<=S[0]&&j<=T[0])
{
if (S[i]== T[j]) { ++i; ++j; }
else { i=i-j+2; j=1; }
}
if (j>=T[0]) return (i- T[0]);
else return 0;
}
算法2-1 串的简单模式匹配
图2-1 串的简单模式匹配过程示意
这种算法看起来比较简单，但是效率比较低，最好的情况下为O(m+n)，在最坏情况下，每趟比较都在最后出现不等，最多要比较n-m-1趟，总比较次数为O((n-m+1)m)，算法的时间复杂度为O(m*n)。
2.2 KMP算法
2.2.1简述
KMP （无回溯的模式匹配）算法正是由D.E.Knuth 、V.R.Pratt 和J.H.Morris 同时发现的，因此称KMP 算法。它是针对上述算法频繁回溯的不足做了实质性的改进。其基本思想是：某趟匹配中，主串字符s i 和模式串t j 匹配失败后，指针i 不回溯，而是让模式串T 向右“滑动”至某个位置，假设这个位置是k ，使得t j 对准s i 继续向右进行比较。因此，KMP 算法的关键就在于找到模式串向右“滑动的距离”。
若用数组元素next[j]来表示字符t j 不匹配时的滑动距离，则next[j]的取值满足以下next 函数的定义：
2.2.2 KMP 算法实现
KMP 算法是在求得模式串的next 函数值的基础上执行的，next 函数值仅依赖于模式T 本身，而和主串S 无关。由2.2.1中next 函数的定义实现可得到模式串’abcaabbabcab ’的next 函数值，如表2-1所示。
KMP 算法如算法2-2所示，在形式上和算法2-1极为类似。假设模式串 T[1…m]中前 q 个字符已经匹配了主串 S[s…s+q -1]，那我们就可以避免一些重复匹配。找出最大的 k 使得 T [1…k]=T[(q-k+1)…q]，从而计算出 s ’使得 T [1…k]=S[s ’…s ’+k-1].其中 s ，+k-1=s+q-1。
【算法描述】
int Index_KMP(SString S, SString T, int pos) { int i, j; i=pos; j=1;
while (i<=S[0]&&j<=T[0]) {
if (j==0||S[i]== T[j]) { ++i; ++j; } else j = next[j];
}
if j>T[0]) return(i- T[0]);
else return 0;
}
算法2-2 KMP模式匹配
KMP算法最大限度的利用先前已经匹配成功的部分模式串，减少比较的次数，过滤掉那些多余的比较，进行最大限度的向前跳跃，再继续进行比较，从而提高模式匹配的效率。当模式中很少自我匹配的子串时，运行速度比较快，是O(m+n)。其在最坏情况下的运行时间仍然是Ο((n-m+1)m)。
2.3 BM算法
BM(Boyer Moore)算法可比KMP算法快上3至5倍。其与朴素匹配算法及KMP算法的不同点是在作S[k+1..k+m]与T[1..m]的匹配测试时是从后面往前面扫描，而不是从左到右。与KMP算法的相同点是在得到部分匹配时充分地利用部分匹配所隐含的、可帮助跳过不必要的测试、提高算法效率的信息。采用“坏字符”和“好尾缀”的启发式技术来修改s的值。
坏字符思想：当匹配发生在t
j !=s
i
时，且如果s
i
不出现在模式串T中，则将
模式串右移至t
i 右端再开始重新匹配。如果t
i
在模式串T中有若干出现，则
将模式中的t
j
右移至模式串T中最后出现的位置。具体的算法2-3如下：
【算法描述】
Bad_string(SString T, int m, int occ[]) ()
{
char a;
int j;
for (a=0; a<=m; a++)
occ[a]=-1;
for (j=0; j<=m; j++)
a= T[j];
occ[a]=j;
}
算法2-3坏字符匹配
好尾缀思想：当模式串T的后面k位和主串S中一致的部分有部分在T中其他部分出现，则可以将T向右移动直至这一部分与要求一致的部分尽可能长。其基本算法和KMP中的next比较相似，不作说明。
BM算法在最好的情况下时间复杂度可以达到O(n/m)。
3基于统计特征的模式匹配算法
3.1算法思想
在每个模式串中，各个字符出现的频率是不一样的，同一个字符出现的位置也是无法预测的。我们可以很好的利用这些无法预测性，因为越是特殊，那就
越不容易被匹配成功，这样，我们在模式匹配过程中就可以尽早的发现错误，尽早的调整匹配方案，从而达到最优的匹配结果。
整个算法的思想是：利用对模式的统计分析，将各个字符按照出现的频率、位置排序，出现次数最少的优先级越高，如果有频率相同的字符，则按照第一次出现的位置由大向小排。这样，就建立了一个新的序列，我们给它起个名字叫匹配序列。
3.1.1模式中相同字符的处理
针对模式中的相同字符，需要记录下同一字符出现位置之间的距离序列。只有当某个字符的所有出现都匹配成功才转向下一个字符。当匹配不成功时，如果是第一个就不成功，将文本向后移一位重新匹配；如果是某个字符的第k次出现匹配不成功，则可以通过类似于KMP中的next方法来获取该跳过的位置，只是这个时候传给next方法的是某字符的距离序列。也就是说用匹配序列代替模式原来的匹配顺序与文本的进行匹配。下面以一个例子来具体的说明。假使在一随机模式串为’dfdacaijaitopaqay’则建立的匹配序列为’yqpotjcfiiddaaaaaa’如果在主串中，y匹配成功，如下表3-1。
表3-1
原模式中q的位置应该在y的前面第二位，而文本中对应的是f,所以此时匹配不成功，因此文本应该向左移动后重新开始比较，因为字符y在模式中仅仅出现一次，而且位置在第17位，所以移动后必须要保证文本对应着模式中字符y 的位置的前面17个字符都没有y，也就是说，可以将文本直接向左移动17位。下面考虑更加一般的情况：
原模式中出现字符a的次数为6，出现的位置依次为：4，6，9，14，16，18 。可以得出字符a的距离序列为：2，3，5，2，2，利用前面KMP算法中的next方法，把字符a的距离序列当成是模式，可以算出：next[0]=0，next[1]=0，next[2]=0，next[3]=1，next[4]=1；这里的next数组值的意义和KMP中是next 数组值的意义相同。如果就单单从这个序列来看，当第三个a不匹配时，我们就可以简单的将文本向左移动两位然后重新进行匹配；当第六个a不匹配时，将文本向左移动10位然后重新进行匹配。如果所有a都匹配时，如果另一个不同的字符(例如d)不匹配时，那么至少可以象右移动第一个a和第五个a之间的距离12。但是，这些仅仅是从字符的序列上来看，还要考虑一个比较重要的因素：第一个a在模式中的位置。以上例为主：当第三个a不匹配时，原本按照next的含义，可以移动第一个a到第二个a的位置。如下表3-2：
模式1为原先模式的位置，模式2，模式3为移动后模式的位置。
在这里可以发现，如果这样移动，那么文本中与模式2的第一个a前面第二位对应的是a，这是不合理的，文本中与模式第一个a匹配的位置的前三个字符应该都不是a才对。所以，可以跳过更多的字符，事实上，模式可以向右移动6个字符(如模式3所示)。也就是说，当按照求得的next值去移动的同时，用考虑所移动到的位置与前一个相同字符之间的距离是否大于等于第一个字符的位置k。那么有必要对next进行修正，即在求next[k]时，要加上一个条件:第next[k]位距离前面一个相同字符的距离要大于等于k。具体的算法如算法3-1。
【算法描述】
V oid Next(SString T, int m, int k, int next[])
{
int t=0;
m=strlen(T);
next[1]=0;
for (int q=2; q<=m; q++)
{
while (t!=0)
{
while (t>0&&T[t+1]!=T[q])
{
t=next[t];
if (T[t+1]==T[q]&&p[t]>k)
t=t+1;break;
else t=next[t];
}
next[q]=t;
}
return (next);
}
}
算法3-1 基于统计特征的模式匹配
同理，对每个出现的字符都做一次这样的运算。可以得出当字符的某次出现没有匹配时，应该移动的最大数。
3.1.2模式中不同的字符的处理
对于模式中不同的字符，此时应该注意一点，如果该字符不是优先级最高的字符，那么移动的位置还应该考虑到优先级比它高的字符最多能移动的距离，然后取最大值。以上例为主，假使字符y, q的匹配成功，p匹配不成功，对于q 说，至少向右移动15位，而对于y来说至少向右移动17位，那么最终移动的位置要取最大值17位。通过上面的例子会发现两个现象：
(1)y匹配成功后，只要模式没有完全匹配成功，模式至少可以向右移17位，这种效率在其他算法中是没有的。
(2)在y右移的17位中，有一些的字符根本就没有被比较过，也就是说，这个算法不一定要遍历所有主串S的字符。这并不是一个特例，在实际运用上面，尤其是在模式比较长的时候，这种优势特别明显。
3.2算法分析
3.2.1算法应用举例
在分析算法之前，先看一个简单的例子：串’aabaaacaaddacac’，在KMP中，
每次不匹配可以右移的距离如下：
在本文介绍的算法中，由于是按照新的排序模式进行匹配，所以，匹配顺序与KMP中的顺序不同，每次不匹配时可以右移的距离如下：
相比之下可见，按照新的排序模式进行匹配的效率极高。此例并非特例，是各种算法的复杂度进行比较所得。
3.2.2算法比较
下面就KMP、BM两种算法和此算法做个简单的比较。
（1）KMP算法分析：KMP算法效率最高的时候应该对于模式串t
1t
2
…t
m
中的任意t
1t
2
…t
k
，都不存在一个j（1 1 t 2 …t j =t k-j+1 …t k ；此时如 果在第k位匹配不成功时，相当于可以跳过k-1位，也就是说，每比较一位就可以向后移一位，比较次数最多为m。 （2）BM算法分析：BM算法如果在最后一位字符就匹配不成功，并且主串S中的那个字符不在模式中出现，那么也可以向后移n位，但是此时仍然用主串S中的那个字符与模式串T比较了n次，因此BM算法的最好情况也是比较m 次。 （3）基于统计特征的模式匹配算法分析：对于匹配序列中的第一个字符（即优先级最高的字符），在模式中出现的位置是随机的，假使在每个位置上出现的概率都是相同的。对于长度为n的模式，匹配序列中第一个字符出现在第i位的概率为1/n，所以该字符出现位置的平均值为：pos=（1+2+3…+n）/n=(n+1)/2。所以当匹配序列中任一字符匹配不成功时跳过的位置d应该是：d>=(n+1)/2；在模式匹配过程中，假设在任一位匹配不成功的概率相等，则在第i位匹配不成功的概率为p=1/n，移动的位数为d>=(n+1)/2。所以每比较一位移动的位数为pos’=d/i>=[(n+1)/2]/[(1/n*n+2/n*n+……+n/n*n)/n]>=1 也就是说，每比较一位就相当于移动了一位，所以，KMP，BM算法最少都要比较m次，而基于统计特征的模式匹配算法最多只要匹配m次。所以通过比较发现该算法明显优于KMP，BM等传统的模式匹配算法的。 通过上面的阐述，可以清出的看出一个问题的提出经常半随着一个新算法的出现，且一个比一个优越、高效，使之更好的应用于实际生活当中。如随着互联网的日渐庞大，信息也是越来越多，如何在海量的信息中快速查找自己所要的信息是网络搜索研究的热点所在，在这其中，字符串匹配算法起着非常重要的作用，这是字符串匹配算法的应用领域之一，前面也提到了其他的应用领域。所以，一个高效的字符串匹配算法，可以极大的提高搜索的效率和质量。本文通过先介绍BF、KMP和BM字符串匹配算法，介绍了各个算法的特点，即原始的朴素字符串匹配算法平均性能很好，而且不需要预处理时间，KMP实现较为简单，BM 虽然实现相对于KMP复杂些，但二者均比前者优秀，然而最坏情况下三者均没有多大改进。所以，经过适当的比较和分析，提出了一种新型、人性化的、更为有效的匹配算法—基于统计特征的模式匹配算法，并着重加以介绍，从比较和举例中反应出新算法的优越性和高效性。 [1] 陈增武：电子计算机算法设计与分析[M]，浙江大学出版社，1986 [2] 娄定俊：算法与算法分析[M]，中山大学出版社，2005 [3] 李雪莹、刘宝旭、许榕生：字符串匹配技术研究[J]，计算机工程[M]，2004，30(20):24-26. [4] 严蔚敏、吴伟民：数据结构[M]，清华大学出版社，2001 [5] 傅清祥、王晓东：算法与数据结构[M]，电子工业出版社，1998 [6] D.Wood，DataStructures，AlgorithmsAndPerfomance，Reading，MA:AddisonWesley，1993 [7] 阮宏一、唐宏亮、杨鹤：数据结构（C/C++描述）[M]，中国水利水电出版社，2007 图像特征描述子之FREAK ?在前【给力追-女生资-源】面的博文中，介绍的BRIEF、ORB、BRISK 算法都是基于特征点周围邻域像素点对之间的比较，形成二进制编码串作为特征【ＱＱ】描述子，这种描述方法计算速度快，且占用内存小，满足一些实时【⒈】应用场景的需求。对于这类特征描述子，关键是确定邻域哪些像【０】素点对进行比较，以及如何匹配。BRIEF算法中特征点邻域的像素【１】点对是随机采样生成的，ORB算法是通过贪婪穷举的方法，在所有【６】可能的像素点对中选取相关性较小的若干点对，BRISK则是采用平【9】均采样的方法生成若干采样点。特征匹配方法通常都是采样Ham【⒌】ming距离来进行度量，由于是二进制编码方式，可通过异或操作快速计【２】算。 特征点检【б】测 ?FAST算法可实现快速检测图像特征点，而且对应有一个加速版本AGAST，因此在诸多特征描述子中，都是首先通过FAST算法搜索定位特征点，再加以描述。FREAK同BRISK算法类似，也是建立多尺度空间，在不同尺度的图像上使用FAST算法检测特征点。 采样模式 ?FREAK算法中采样模式接近于人眼视网膜接收图像信息的采样模型，如下图所示，人眼视网膜中，Fovea区域主要对高精度的图像信息进行处理，而Para区域则主要对低精度的图像信息进行处理。 在FREAK的采样模式中，图中每一个黑点代表一个采样点，每个圆圈代表一个感受野，每个采样点需进行高斯模糊处理，以降低噪声影响，感受野的半径表示高斯模糊的标准差。这种采样模式与BRISK的不同之处在于，感受野之间存在重叠的区域；与BRIEF和ORB算法的不同之处在于，FREAK的采样点根据与特征点的距离远近，采用了不同大小的高斯核函数进行平滑处理。不同大小的感受野在人眼视网膜中也存在类似的结构，通过重叠的感受野，可以获得更多的信息，使最终的描述符更具独特性和可区分性。最终FREAK算法的采样结构为6、6、6、6、6、6、6、1，6代表每层中有6个采样点并且这6个采样点在一个同心圆上，一共有7个同心圆，最后的1表示特征点。 特征描述 ?FREAK算法同样采用二进制编码描述特征点，用FF表示编码特征 F=Σ0≤aN2aT(Pa) F=Sigma_{0 leq a < N} 2^a T(P_a) T(Pa)={1,I(Pr1a)I(Pr2a) 0,otherwise T(P_a) = begin{cases} 1,I(P_a^{r_1}) > I(P_a^{r_2}) 0,otherwise end{cases} 式中，I(Pr1a)I(P_a^{r_1})表示采样点经过高斯模糊后的灰度值。 ?FREAK的采样模式中一共有43个采样点，可以产生N=43(43?1)-2=903N = 43(43 - 1)-2 = 903个采样点对，有些采样点对的编码值对特征描述并没有实际作用，反而会造成特征冗余，因此需要对特征的描述向量进行筛选，也就是降维。原论文中采用与ORB中类似的贪婪 模式匹配的KMP算法详解 模式匹配的KMP算法详解 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP算法。大概学过信息学的都知道，是个比较难理解的算法，今天特把它搞个彻彻底底明明白白。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？回溯，没错，注意到(1)句，为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 为什么会发生这样的情况？这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为abcdef这样的，大没有回溯的必要。 诚信声明 本人声明： 我所呈交的本科毕业设计论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。本人完全意识到本声明的法律结果由本人承担。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：日期：2010 年05 月20日 毕业设计（论文）任务书 设计（论文）题目： 学院：专业：班级： 学生指导教师（含职称）：专业负责人： 1．设计（论文）的主要任务及目标 (1) 了解图象匹配技术的发展和应用情况，尤其是基于特征的图象匹配技术的发展和应用。 (2) 学习并掌握图像匹配方法，按要求完成算法 2．设计（论文）的基本要求和内容 （1）查阅相关中、英文文献，完成5000汉字的与设计内容有关的英文资料的翻译。（2）查阅15篇以上参考文献，其中至少5篇为外文文献，对目前国内外图象匹配技术的发展和应用进行全面综述。 （3）学习图象匹配算法，尤其是基于特征的图象匹配算法。 （4）实现并分析至少两种基于特征的图象匹配算法，并分析算法性能。 3．主要参考文献 [1]谭磊, 张桦, 薛彦斌．一种基于特征点的图像匹配算法[J]．天津理工大学报，2006， 22(6)，66-69． [2]甘进，王晓丹，权文．基于特征点的快速匹配算法[J]．电光与控制，2009，16(2)， 65-66． [3]王军，张明柱．图像匹配算法的研究进展[J]．大气与环境光学学报，2007，2(1)， 12-15． 五、详细设计 #include int KMPFindImprove(String &P); //改进的KMP匹配算法 void Output2(); //输出子串在主串中出现的位置 }; int String::KMPFindImprove(String &P) { int sum=0; int j=KMPFindImprove(0,P); while(j!=-1) { count[sum++]=j; if(j<=n-P.n) j=KMPFindImprove(j+P.n,P); } return sum; } void String::Output2() //输出子串在主串中的位置 { int i=0; while(count[i]!=count[i+1] && i 角点提取与匹配算法实验报告 1 说明 本文实验的目标是对于两幅相似的图像，通过角点检测算法，进而找出这两幅图像的共同点，从而可以把这两幅图像合并成一幅图像。 下面描述该实验的基本步骤: 1.本文所采用的角点检测算法是Harris 角点检测算法，该算法的基本原理是取以目标像素点为中心的一个小窗口，计算窗口沿任何方向移动后的灰度变化，并用解析形式表达。设以像素点(x,y)为中心的小窗口在X 方向上移动u ，y 方向上移动v ，Harris 给出了灰度变化度量的解析表达式： 2 ,,|,|,,()(x y x y x u y v x y x y I I E w I I w u v o X Y ??= -=++??∑∑ (1) 其中，,x y E 为窗口内的灰度变化度量；,x y w 为窗口函数，一般定义为2 2 2 ()/,x y x y w e σ +=； I 为图像灰度函数，略去无穷小项有： 222222 ,,[()()2]2x y x y x y x y E w u I v I uvI I Au Cuv Bv = ++=++∑ （2） 将,x y E 化为二次型有： ,[]x y u E u v M v ?? =???? (3) M 为实对称矩阵： 2 ,2 x y x x y x y y I I I M w I I I ???= ???????∑ (4) 通过对角化处理得到： 11 ,200x y E R R λλ-??= ??? (5) 其中，R 为旋转因子，对角化处理后并不改变以u,v 为坐标参数的空间曲面的形状，其特征值反应了两个主轴方向的图像表面曲率。当两个特征值均较小时，表明目标点附近区域为“平坦区域”；特征值一大一小时，表明特征点位于“边缘”上；只有当两个特征值均比较大时，沿任何方向的移动均将导致灰度的剧烈变化。Harris 的角点响应函数(CRF)表达式由此而得到： 2 (,)det()(())C RF x y M k trace M =- (6) 在前面的图文中，我们讲了“串”这种数据结构，其中有求“子串在主串中的位置”（字符串的模式匹配）这样的算法。解决这类问题，通常我们的方法是枚举从A串（主串）的什么位置起开始与B串（子串）匹配，然后验证是否匹配。假设A串长度为n，B串长度为m，那么这种方法的复杂度是O(m*n)的。虽然很多时候复杂度达不到m*n（验证时只看头一两个字母就发现不匹配了），但是我们有许多“最坏情况”，比如： A=“aaaaaaaaaaaaaaaaaaaaaaaaab”，B=“aaaaaaaab”。 大家可以忍受朴素模式匹配算法（前缀暴力匹配算法）的低效吗？也许可以，也许无所谓。 有三位前辈D.E.Knuth、J.H.Morris、V.R.Pratt发表一个模式匹配算法，最坏情况下是O(m+n)，可以大大避免重复遍历的情况，我们把它称之为克努特-莫里斯-普拉特算法，简称KMP算法。 假如，A=“abababaababacb”，B=“ababacb”，我们来看看KMP是怎样工作的。我们用两个指针i和j分别表示，。也就是说，i是不断增加的，随着i 的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前j个字符（j当然越大越好），现在需要检验A[i+1]和B[j+1]的关系。 例子： S=“abcdefgab” T=“abcdex” 对于要匹配的子串T来说，“abcdex”首字符“a”与后面的串“bcdex”中任意一个字符都不相等。也就是说，既然“a”不与自己后面的子串中任何一字符相等，那么对于主串S来说，前5位字符分别相等，意味着子串T的首字符“a”不可能与S串的第2到第5位的字符相等。朴素算法步骤2,3,4,5的判断都是多余，下次的起始位置就是第6个字符。 例子： S=“abcabcabc” T=“abcabx” 模式匹配算法 源程序如下： #include printf("匹配的结果:%d\n",n); } //KMP模式匹配算法 int index_KMP(char *s,char *t,int pos) { int i=pos,j=1; while (i<=(int)strlen(s)&&j<=(int)strlen(t)) { if (j==0||s[i]==t[j-1]) { i++; j++; } else j=next[j]; } if(j>(int)strlen(t)) return i-strlen(t)+1; else return 0; } void get_next(char *t,int *next) { int i=1,j=0; next[0]=next[1]=0; while (i<(int)strlen(t)) { if (j==0||t[i]==t[j]) { i++; j++; next[i]=j; } else j=next[j]; } } 运行效果如下： 实验四：KMP算法实验报告 一、问题描述 模式匹配两个串。 二、设计思想 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KM P算法。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为a bcdef这样的，大没有回溯的必要。 改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。 如果不用回溯，那T串下一个位置从哪里开始呢？ 还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样： 一、问题描述 模式匹配两个串。 二、设计思想 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KM P算法。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为a bcdef这样的，大没有回溯的必要。 改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。 如果不用回溯，那T串下一个位置从哪里开始呢？ 还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样： ...ababd... ababc ->ababc 这样i不用回溯，j跳到前2个位置，继续匹配的过程，这就是KMP算法所在。这个当T[j]失配后，j应该往前跳的值就是j的next值，它是由T串本身固有决定的，与S串无关。 《数据结构》上给了next值的定义： 0 如果j=1 next[j]={Max{k|1 SIFT 特征点匹配算法 基于SIFT 方法的图像特征匹配可分为特征提取和特征匹配两个部分，可细化分为五个部分： ① 尺度空间极值检测（Scale-space extrema detection ）； ② 精确关键点定位（Keypoint localization ） ③ 关键点主方向分配（Orientation assignment ） ④ 关键点描述子生成（Keypoint descriptor generation ） ⑤ 比较描述子间欧氏距离进行匹配（Comparing the Euclidean distance of the descriptors for matching ） 1.1 尺度空间极值检测 特征关键点的性质之一就是对于尺度的变化保持不变性。因此我们所要寻找的特征点必须具备的性质之一，就是在不同尺度下都能被检测出来。要达到这个目的，我们可以在尺度空间内寻找某种稳定不变的特性。 Koenderink 和Lindeberg 已经证明，变换到尺度空间唯一的核函数是高斯函数。因此一个图像的尺度空间定义为：(,,)L x y σ，是由可变尺度的高斯函数(,,)G x y σ与输入图像(,)I x y 卷积得到，即： ),(),,(),,(y x I y x G y x L *=σσ （1.1） 其中：2222/)(221 ),,(σπσσy x e y x G +-= 在实际应用中，为了能相对高效地计算出关键点的位置，建议使用的是差分高斯函数（difference of Gaussian ）(,,)D x y σ。其定义如下： ) ,,(),,() ,()),,(),,((),,(σσσσσy x L k y x L y x I y x G k y x G y x D -=*-= （1.2） 如上式，D 即是两个相邻的尺度的差（两个相邻的尺度在尺度上相差一个相乘系数k ）。 二 特征点提取算法 1、基于SIFT （Scale Invariant Feature Transform ）方法的图像特征匹配 参看David G. Lowe 的“Distinctive Image Features from Scale-Invariant Keypoints ” 基于SIFT 方法的图像特征匹配可分为特征提取和特征匹配两个部分，可细化分为五个部分： ① 尺度空间极值检测（Scale-space extrema detection ）； ② 精确关键点定位（Keypoint localization ） ③ 关键点主方向分配（Orientation assignment ） ④ 关键点描述子生成（Keypoint descriptor generation ） ⑤ 比较描述子间欧氏距离进行匹配（Comparing the Euclidean distance of the descriptors for matching ） 1.1 尺度空间极值检测 特征关键点的性质之一就是对于尺度的变化保持不变性。因此我们所要寻找的特征点必须具备的性质之一，就是在不同尺度下都能被检测出来。要达到这个目的，我们可以在尺度空间内寻找某种稳定不变的特性。 Koenderink 和Lindeberg 已经证明，变换到尺度空间唯一的核函数是高斯函数。因此一个图像的尺度空间定义为：(,,)L x y σ，是由可变尺度的高斯函数(,,)G x y σ与输入图像(,)I x y 卷积得到，即： ),(),,(),,(y x I y x G y x L *=σσ （1.1） 其中：2222/)(221 ),,(σπσσy x e y x G +-= 在实际应用中，为了能计算的相对高效，所真正使用的是差分高斯尺度空间（difference of Gaussian ）(,,)D x y σ。其定义如下： ) ,,(),,() ,()),,(),,((),,(σσσσσy x L k y x L y x I y x G k y x G y x D -=*-= （1.2） 如上式，D 即是由两个相邻的尺度的差（两个相邻的尺度在尺度上相差一个相乘系数k ）。 关于快速高效的模式匹配算法的剖析与改进 摘要：模式匹配算法是现代化网络入侵检测中的关键环节，本文主要介绍了几种常用的模式匹配算法，并在此基础上，提出一种更快捷、更高效的改进方法，以提高模式匹配的效率与质量，确保网络安全。 关键词：模式匹配入侵检测改进 随着我国计算机与网络技术的飞速发展，网络应用已涉及到人们生产、生活的各个领域，其重要性日益凸显。随之而来的网络攻击问题也备受关注，给网络安全性带来挑战。传统的网络防御模式，主要采取身份认证、防火墙、数据加密等技术，但是与当前网络发展不适应。在此背景下，入侵检测技术营运而生，并建立在模式匹配基础上，确保检测的快捷性、准确性，应用越来越广泛。 1、模式匹配原理概述 模式匹配是入侵检测领域的重要概念，源自入侵信号的层次性。结合网络入侵检测的底层审计事件，从中提取更高层次的内容。通过高层事件形成的入侵信号，遵循一定的结构关系，将入侵信号的抽象层次进行具体划分。入侵领域大师kumar将这种入侵信号划分为四大层次，并将每一个层次与匹配模式相对应。以下将分别对四大层次进行分析： (1)存在。只要存在审计事项，就可以证明入侵行为的发生，并深层次挖掘入侵企图。存在主要对应的匹配模式就是“存在模式”。可以说，存在模式就是在固定的时间内，检查系统中的特定状态， 同时判断系统状态。 (2)序列。一些入侵的发生，是遵循一定的顺序，而组成的各种行为。具体表现在一组事件的秩序上。序列对应的是“序列模式”，在应用序列模式检测入侵时，主要关注间隔的时间与持续的时间。 (3)规则。规则表示的是一种可以扩展的表达方式，主要通过and 逻辑表达来连接一系列的描述事件规则。一般适用于这种模式的攻击信号由相关活动组成，这些活动之间往往不存在事件的顺序关系。 (4)其他。其他模式是不包含前面几种方法的攻击，在具体应用过程中，难以与其他入侵信号进行模式匹配，大多为部分实现方式。 2、几种常用的模式匹配算法 2.1 ac算法 ac算法（aho-corasick）是一种可以同时搜索若干个模式的匹配算法，最早时期在图书馆书目查询系统中应用，效果良好。通过使用ac算法，实现了利用有限状态自动机结构对所有字符串的接收过程。自动机具有结构性特征，且每一个前缀都利用唯一状态显示，甚至可同时应用于多个模式的前缀中。如果文本中的某一个字符不属于模式中预期的下一个字符范围内，或者可能出现错误链接的指向状态等，那么最长模式的前缀同时也可作为当前状态相对应的后缀。ac算法的复杂性在于o（n），预处理阶段的复杂性则在于o（m）。在采取ac算法的有限状态自动机中，应该在每一个字符的模式串中分别建立节点，提高该算法的使用效率与质量。目前，应用有限 /** *时间：2010年8月26日7:09:57 *功能：模式匹配算法代码 */ #include"stdio.h" #include"malloc.h" void kmp(int *ikmp,char *t,int t_length) { int k=0; int q=0; ikmp[0]=k; for(q=1;q while(t[t_length]!='\0') { t_length++; } /*测试*/ printf("t_length is %d\n",t_length); /*求t的kmp值*/ ikmp=malloc(t_length*sizeof(int)); kmp(ikmp,t,t_length); /*匹配过程*/ for(q=0;q 三个描述符的比较：SURF，FREAK和BRISK =================分割线================= 我认为从事对象识别，图像注册和使用关键点提取的其他领域的开发人员和研究人员可以发现这个帖子很有用。最近（从2.4.2），一个新的特征描述符算法被添加到OpenCV库中。据称FREAK描述符优于ORB和SURF描述符，但速度非常快（与ORB相当）。也有人在我的博客上的评论提到BRISK描述符，这是比SURF更新，更高效。那么，最后我找到一个时间来比较他们，并发表我的研究成果。 这篇文章与我过去的OpenCV比较报告非常相似。虽然这些报告是多年前发表的，但它们还是有些实际的。对于这个测试，我决定从头开始重写整个测试框架。源代码即将可用。但现在，让我解释我做了什么来找到最好的三种算法。将图像转换为描述符的主要目标是什么？从像素域移动到更紧凑的表示形式相同的数据。此外，我们希望我们的表示是旋转和比例不变的（例如，当源图像旋转或缩放时，表示保持不变或略微变化）。SURF，FREAK和BRISK描述符宣称它们是旋转和尺度不变的。 ========================分割线============================== 就像在OpenCV比较报告中一样，测试应用程序与测试模式图像一起工作。我们有四个基本的转换：旋转，缩放，模糊和亮度调整。这里是如何旋转转换类看起来像： class ImageRotationTransformation : public ImageTransformation ImageRotationTransformation(float startAngleInDeg, float endAngleInDeg, float step, cv::Point2f rotationCenterInUnitSpace) : ImageTransformation("Rotation") , m_startAngleInDeg(startAngleInDeg) , m_endAngleInDeg(endAngleInDeg) , m_step(step) , m_rotationCenterInUnitSpace(rotationCenterInUnitSpace) -- Fill the arguments for (float arg = startAngleInDeg; arg = endAngleInDeg; arg += step) m_args.push_back(arg); virtual std::vector getX() const return m_args; virtual void transform(float t, const cv::Mat source, cv::Mat result) const cv::Point2f center(source.cols * m_rotationCenterInUnitSpace.x, source.cols * m_rotationCenterInUnitSpace.y); //算法功能：串的朴素模式匹配是最简单的一种模式匹配算法，又称为 Brute Force 算法，简称为BF算法 #include int main() { SString S, T; int m; char strs1[MAXL]; //建立主串S char strs2[MAXL]; //建立模式串T printf("请输入主串和子串:\n"); printf("主串S: "); scanf("%s", strs1); printf("子串T: "); scanf("%s", strs2); StrAssign(S, strs1); StrAssign(T, strs2); m = Index(S, T, 1); if(m) printf("主串 S = {%s}\n子串 T = {%s}\n在第 %d 个位置开始匹配！\n", strs1, strs2, m); else printf("主串 S = {%s}\n子串 T = {%s}\n匹配不成功！\n", strs1, strs2); return 0; } 简单的模式匹配算法_Brute-Force算法 在串的操作中，子串的定位操作Index_string(s，t)，通常称之为模式匹配(其中：子串t称之为模式串)。其功能是：主串s＝“c0c1...c n-1”中，去查找子串t＝“t0t1...t m-1”，若找到则返回子串t在主串s中的位置,否则查找不成功，返回-1。 为了便于理解，我们举例进行说明。 1．例子 例如：主串s=”ababcabcacbab”,t=”abcac”。其匹配过程如图6－12所示。 第一趟匹配: i=2 a b a b c a b c a c b a b a b c j=2 第二趟匹配: i=1 a b a b c a b c a c b a b a j=0 第三趟匹配： i=6 a b a b c a b c a c b a b a b c a c j=4 第四趟匹配： i=3 a b a b c a b c a c b a b a j=0 第五趟匹配： i=4 a b a b c a b c a c b a b a j=0 第六趟匹配： i=10 a b a b c a b c a c b a b a b c a c j=5 图6－12 Brute-Force算法中串的匹配过程 2．算法思想 算法的基本思想是：分别设置计数指针i和j指示主串s和模式串t中当前正待比较的字符位置。从主串的第一个字符和模式的第一个字符比较，若相等，则继续逐个比较后续字符；否则从主串的下一个字符起再重新和模式串的字符比较。依次类推，直到模式串中的每个字符依次和主串中的一个连续的字符序列相等，则称匹配成功，函数值为和模式串中第一个字符相等的字符在主串中的序号，否则称匹配不成功。 这个算法简单，易于理解，但效率不高，主要原因是：主串指针i在若干个字符序列比较相等后只要有一个字符比较不等便需回溯。 图像局部特征（一）--概述 本文根据下面这篇文章，做下简单修改。 研究图像特征检测已经有一段时间了，图像特征检测的方法很多，又加上各种算法的变形，所以难以在短时间内全面的了解，只是对主流的特征检测算法的原理进行了学习。总体来说，图像特征可以包括颜色特征、纹理特等、形状特征以及局部特征点等。其中局部特点具有很好的稳定性，不容易受外界环境的干扰，本篇文章也是对这方面知识的一个总结。 1. 局部特征点 图像特征提取是图像分析与图像识别的前提，它是将高维的图像数据进行简化表达最有效的方式，从一幅图像的M×N×3?M×N×3的数据矩阵中，我们看不出任何信息，所以我们必须根据这些数据提取出图像中的关键信息，一些基本元件以及它们的关系。 局部特征点是图像特征的局部表达，它只能反正图像上具有的局部特殊性，所以它只适合于对图像进行匹配，检索等应用。对于图像理解则不太适合。而后者更关心一些全局特征，如颜色分布，纹理特征，主要物体的形状等。全局特征容易受到环境的干扰，光照，旋转，噪声等不利因素都会影响全局特征。相比而言，局部特征点，往往对应着图像中的一些线条交叉，明暗变化的结构中，受到的干扰也少。 而斑点与角点是两类局部特征点。斑点通常是指与周围有着颜色和灰度差别的区域，如草原上的一棵树或一栋房子。它是一个区域， 所以它比角点的噪能力要强，稳定性要好。而角点则是图像中一边物体的拐角或者线条之间的交叉部分。 2. 斑点检测原理与举例 2.1 LoG与DoH 斑点检测的方法主要包括利用高斯拉普拉斯算子检测的方法（LOG）,以及利用像素点Hessian矩阵（二阶微分）及其行列式值的方法（DOH）。 LoG的方法已经在斑点检测这入篇文章里作了详细的描述。因为二维高斯函数的拉普拉斯核很像一个斑点，所以可以利用卷积来求出图像中的斑点状的结构。 DoH方法就是利用图像点二阶微分Hessian矩阵： H(L)=[L?xx?L?xy?L?xy?L?yy?]?H(L)=[LxxLxyLxyLyy] 以及它的行列式的值DoH(Determinant of Hessian): det=σ?4?(L?xx?(x,y,σ)L?yy?(x,y,σ)?L?2?xy?(x,y,σ))?de t=σ4(Lxx(x,y,σ)Lyy(x,y,σ)?Lxy2(x,y,σ)) Hessian矩阵行列式的值，同样也反映了图像局部的结构信息。与LoG相比，DoH对图像中的细长结构的斑点有较好的抑制作用。 无论是LoG还是DoH，它们对图像中的斑点进行检测，其步骤都可以分为以下两步： 1）使用不同的σ?σ生成(?2?g?x?2?+?2?g?y?2?)?(?2g?x2+?2g?y2) 或?2?g?x?2?,?2?g?y?2?,?2?g?x?y?2g?x2,?2g?y2,?2g?x?y模板，并 Boyer-Moore 经典单模式匹配算法 BM模式匹配算法-原理（图解） 由于毕业设计（入侵检测）的需要，这两天仔细研究了BM模式匹配算法，稍有心得，特此记下。 首先，先简单说明一下有关BM算法的一些基本概念。 BM算法是一种精确字符串匹配算法（区别于模糊匹配）。 BM算法采用从右向左比较的方法，同时应用到了两种启发式规则，即坏字符规则和好后缀规则，来决定向右跳跃的距离。 BM算法的基本流程: 设文本串T，模式串为P。首先将T与P进行左对齐，然后进行从右向左比较，如下图所示: 若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则和好后缀规则，来计算模式串向右移动的距离，直到整个匹配过程的结束。 下面，来详细介绍一下坏字符规则和好后缀规则。 首先，诠释一下坏字符和好后缀的概念。 请看下图： 图中，第一个不匹配的字符（红色部分）为坏字符，已匹配部分（绿色）为好后缀。 1）坏字符规则（Bad Character）： 在BM算法从右向左扫描的过程中，若发现某个字符x不匹配，则按如下两种情况讨论： i. 如果字符x在模式P中没有出现，那么从字符x开始的m个文本显然不可能与P匹配成功，直接全部跳过该区域即可。 ii. 如果x在模式P中出现且出现次数>=1，则以该字符所在最右边位置进行对齐。 用数学公式表示，设Skip(x)为P右移的距离，m为模式串P的长度，max(x)为字符x在P中最右位置。 可以总结为字符x出现与否，将max(x)=0作为初值即可。 例1： 下图红色部分，发生了一次不匹配。 计算移动距离Skip(c) = m-max(c)=5 - 3 = 2，则P向右移动2位。 移动后如下图： 2）好后缀规则（Good Suffix）： 若发现某个字符不匹配的同时，已有部分字符匹配成功，则按如下两种情况讨论： i. 如果在P中位置t处已匹配部分P'在P中的某位置t'也出现，且位置t'的前一个字符与位置t的前一个字符不相同，则将P右移使t'对应t方才的所在的位置。 ii. 如果在P中任何位置已匹配部分P'都没有再出现，则找到与P'的后缀P''相同的P的最长前缀x，向右移动P，使x对应方才P''后缀所在的位置。 宜宾学院学报 Journal of Yibin University 优先数字出版 —————————————————————— 收稿日期：2014-07-03 2014-09-05 基金项目：安徽电子信息职业技术学院教科研项目“基于数据挖掘技术的高职院校招生决策系统研究与应用” （ADZX1306） 作者简介：余飞（1983-），男，硕士，讲师，研究方向为计算机网络安全、数据挖掘、分布式操作系统 网络出版时间： 网络出版地址： 基于特征值的模式匹配算法 余 飞，刘思宏 （安徽电子信息职业技术学院 软件学院，安徽蚌埠233060） 摘 要：模式匹配算法广泛应用于防火墙、入侵检测等网络安全领域，其算法效能直接影响到系统的工作效率．本文首次提出了一种基于特征值的模式匹配算法——FLC （First-Last-Characters ）算法．该算法打破了经典算法有序偏移的思想，突破了BMHS （Boyer-Moore-Horspool-Sunday ）算法最大偏移量（m+1）的上限，从而增大了偏移距离，减 则匹配成功；若有一个字符不同，则匹配不成功，模式串向右移动一个字符的位置，继续比较，直到将文本串的所有位都比较过来．BF 算法实现简单，但模式串每次仅偏移一个字符，这导致模式串几乎要与文本串中的每一个字符进行比较，运行效率极其低下． KMP 算法[2]是BF 的一种改进算法，该算法由Knuth 等人提出．KMP 算法根据给定的模式串，定义一个next 函数．模式串与文本串按顺序进行从左到右匹配， 2014-09-12 13:00 https://www.wendangku.net/doc/da18198803.html,/kcms/detail/51.1630.Z.20141211.1054.008.htmlF R E A K 特 征 点 匹 配 算 法 介 绍 ( 2 0 2 0 )
模式匹配的KMP算法详解
基于特征的图像匹配算法毕业设计论文(含源代码)
模式匹配算法的设计与实现
图像中角点(特征点)提取与匹配算法
字符串的模式匹配算法
数据结构-模式匹配算法
模式匹配KMP算法实验报告
模式匹配KMP算法实验步骤
SIFT特征点提取与匹配算法
SIFT特征点提取与匹配算法
关于快速高效的模式匹配算法的剖析与改进
模式匹配算法
F R E A K 特 征 点 匹 配 算 法 介 绍 ( 2 0 2 0 )
串的朴素模式匹配算法(BF算法)
简单的模式匹配算法
F R E A K 特 征 点 匹 配 算 法 介 绍
BM模式匹配算法图解
基于特征值的模式匹配算法