字符串精确匹配算法改进探讨.doc

字符串精确匹配算法改进探讨 　　摘要：如何改进字符串匹配算法，提高查询速度，是目前研究的重要领域之一，本文在对BF算法、KMP算法、BM算法、BMH算法、RK算法和SUNDAY算法等几种常见算法分析的基础上，提出改进的意见。 　　关键词：精确匹配；KMP算法；模糊匹配 　　 　　一、引言 　　 　　字符串精确匹配在计算机领域有着广泛的应用, 它可用于数据处理、数据压缩、文本编辑、信息检索等多方面。如何改进字符串匹配算法，提高查询速度，是目前研究的重要领域之一。 　　所谓精确字符串匹配问题，是在文本 S中找到所有与查询 P 精确匹配的子串。字符串精确匹配要求匹配严格准确，其实现算法主要有BF算法、KMP算法、BM算法、BMH算法、RK算法和SUNDAY算法等。本文在对这几种常见算法分析的基础上，提出改进的意见。 　　 　　二、常见算法分析 　　 　　1．BF算法 　　BF(Brute Force)算法是效率最低的算法。其核心思想是：T是文本串，P是模式串。首先S[1]和P[1]比较，若相等，则再比较S[2]和P[2]，一直到P[M]为止；若S[1]和P[1]不等，则P 向右移动一个字符的位置，再依次进行比较。如果存在t，1≤t≤N，且S[t+1..t+M]= P[1..M],则匹配成功；否则失败。该算法最坏情况下要进行M*(N-M+1)次比较，时间复杂度为O(M*N)。 　　2．KMP 算法 　　KMP(Knuth-Morris-Pratt)算法是D.E.Knuth、J.H.Morris和V.R.Pratt 3 人于1977 年提出来的。其核心思想是：在匹配失败时，正文不需要回溯，而是利用已经得到的“部分匹配”结果将模式串右移尽可能远的距离，继续进行比较。这里要强调的是，模式串不一定向右移动一个字符的位置，右移也不一定必须从模式串起点处重新试匹配，即模式串一次可以右移多个字符的位置，右移后可以从模式串起点后的某处开始试匹配。KMP算法的时间复杂度是O(m+n)，最坏情况下时间复杂度为O（m*n）。空间复杂度是O(m)，对BF算法进行了很大的改进。虽然，KMP 算法有着它自身的局限性，但是，在现代科学的众多领域中的应用仍然普遍。 　　3．BM算法 　　1977 年，Boyer 和Moore 提出了一个全新的模式匹配算法――BM 算法。该算法在匹配过程中，模式串从左向右移动，但字符比较按照P[M]、P[M-1]、...、P[1]的次序从右向左进行。BM 算法的一个最主要的特点是：在匹配过程中，可以跳过很多无用的字符。通过这种跳跃式的匹配，获得了极高的匹配效率。该算法的核心思想是：对于模式串P，定义一个函数d：Σ → {1, 2, ...,M } ，函数d 给出了正文中可能出现的字符在模式中的位置。该算法最坏情况下的时间复杂度为O(N*M)。但由于在实际应用中这种情况极少出现，因此BM算法仍得到广泛的应用。 　　4．BMH算法 　　1980 年, Horspool 提出了对BM 算法的一种改进算法――BMH算法。它首先比较文本指针所指字符和模式的最后一个字符,如相等再比较其余m - 1个字符。无论文本中哪个字符造成了匹配失败,都将由文本中和模式最后一个位置对应的字符来启发模式向右的滑动。即文本自位置I起与模式的从右至左的匹配检查中, 一旦发现不匹配,就将I重新赋值为End + d[T[End]]。(End是一个中间变量,记录了文本中每次从右至左匹配的起始位置) 　　5．RK算法 　　RK算法是Turing奖获得者R.M.Karp和M.O.Rabin在1981年提出来的，该算法采用了与KMP算法和BM算法完全不同的方法。该算法利用Hash方法和素数理论，首先定义一个Hash函数，然后将模式串P和文本串T中长度为m的子串利用Hash函数转换成数值。显然只需比较那些与模式串具有相同Hash函数值的子串，从而提高了效率。当然因为Hash冲突的存在，还要进一步进行字符串比较，但只要选择适当的素数Hash冲突的概率就会很小。RK算法的时间复杂度是O(n+m)。 　　6．Sunday 算法 　　Sunday 算法是Daniel M.Sunday 于1990年提出的一种比BM算法搜索速度更快的算法。该算法的核心思想是：在匹配过程中，模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较,它在发现不匹配时, 算法能跳过尽可能多的字符以进行下一步的匹配，从而提高了匹配效率。按照这种字串移动算法，然后按照字符从右向左的次序匹配。如果完全匹配了，则匹配成功；否则，再进行下一轮的移动，直到正文T 的最右端结束。该算法最坏 　　情况下的时间复杂度为O(N*M)。对于短模式串的匹配问题，该算法执行速度较快。