C语言 字符串匹配算法.pdfVIP

字符串匹配算法（一）简介 收藏 注：本文大致翻译自EXACT STRING MATCHING ALGORITHMS ，去掉一些废话，增加一些解释。 文本信息可以说是迄今为止最主要的一种信息交换手段，而作为文本处理中的一个重要领域——字符串匹配，就是 我们今天要说的话题。（原文还特意提及文本数据数量每18 个月翻一番，以此论证算法必须要是高效的。不过我注 意到摩尔定律也是 18 个月翻番，这正说明数据的增长是紧紧跟随处理速度的，因此越是使用高效的算法，将来待 处理的数据就会越多。这也提示屏幕前的各位，代码不要写得太快了……） 字符串匹配指的是从文本中找出给定字符串（称为模式）的一个或所有出现的位置。本文的算法一律输出全部的匹 配位置。模式串在代码中用x[m]来表示，文本用y[n]来，而所有字符串都构造自一个有限集的字母表Σ，其大小为 σ。 根据先给出模式还是先给出文本，字符串匹配分为两类方法： • 第一类方法基于自动机或者字符串的组合特点，其实现上，通常是对模式进行预处理； • 第二类方法对文本建立索引，这也是现在有哪些信誉好的足球投注网站引擎采用的方法。 本文仅讨论第一类方法。 文中的匹配算法都是基于这样一种方式来进行的：设想一个长度为m 的窗口，首先窗口的左端和文本的左端对齐， 把窗口中的字符与模式字符进行比较，这称为一趟比较，当这一趟比较完全匹配或者出现失配时，将窗口向右移动。 重复这个过程，直到窗口的右端到达了文本的右端。这种方法我们通常叫sliding window 。 对于穷举法来说，找到所有匹配位置需要的时间为O(mn)，基于对穷举法改进的结果，我们按照每一趟比较时的比 较顺序，把这些算法分为以下四种： 1. 从左到右：最自然的方式，也是我们的阅读顺序 2. 从右到左：通常在实践中能产生最好的算法 3. 特殊顺序：可以达到理论上的极限 4. 任意顺序：这些算法跟比较顺序没关系（例如：穷举法） 一些主要算法的简单介绍如下： 从左到右 采用哈希，可以很容易在大部分情况下避免二次比较，通过合理的假设，这种算法是线性时间复杂度的。它最先由 Harrison 提出，而后由Karp 和Rabin 全面分析，称为KR 算法。 在假设模式长度不大于机器字长时，Shift-Or 算法是很高效的匹配算法，同时它可以很容易扩展到模糊匹配上。 MP 是第一个线性时间算法，随后被改进为KMP ，它的匹配方式很类似于自动机的识别过程，文本的每个字符与模 式的每个字符比较不会超过logΦ(m+1)，这里Φ是黄金分隔比1.618，而随后发现的类似算法——Simon 算法，使得 文本的每个字符比较不超过 1+log m ，这三种算法在最坏情况下都只要2n-1 次比较。（抱歉限于我的水平这一段既 2 没看懂也没能查证，大家就看个意思吧） 基于确定性有限自动机的算法对文本字符刚好只用n 次访问，但是它需要额外的O(mσ) 的空间。 一种叫Forward Dawg Matching 的算法同样也只用n 次访问，它使用了模式的后缀自动机。 Apostolico-Crochemore 算法是一种简单算法，最坏情况下也只需要3n/2 次比较。 还有一种不那么幼稚（Not So Naive ）的算法，最坏情况下是n 平方，但是预处理过程的时间和空间均为常数，而 且平均情况下的性能非常接近线性。 从右到左 BM 算法被认为是通常应用中最有效率的算法了，它或者它的简化版本常用于文本编辑器中的有哪些信誉好的足球投注网站和替换功能，对 于非周期性的模式而言，3n 是这种算法的比较次数上界了，不过对于周期性模式，它最坏情况下需要n 的二次方。 BM 算法的一些变种避免了原算法的二次方问题，比较高效的有：Apostolico and Giancarlo 算法、Turbo BM 算法和 Reverse Colussi 算法。 实验的结果表明，Quick Search 算法（BM 的一个变种）以及基于后缀自动机的Reverse Factor 和Turbo Reverse Factor 算法算是实践中最有效的算法了。 2 Zhu and Takaoka 算法和BR 算法也是BM 的变种，它们则需要O(σ) 的额外空间。 特殊顺序 最先达到空间线性最优的是Galil-Seiferas 和Two Way 算法，它们把模式分为两部分，先从左到右有哪些信誉好的足球投注网站右边的部分， 如果没有失配，再有哪些信誉好的足球投注网站左边的部分。 Colussi 和Galil-Giancarlo 算法将