原贴发表时间:2012年4月9日,作者:Stoimen

前言

我们前面已经看到,强力字符串搜索算法和Rabin-Karp字符串搜索算法均非有效算法。不过,为了改进某种算法,首先需要详细理解其基本原理。我们已经知道,强力字符串匹配的速度缓慢,并已尝试使用Rabin-Karp中的一个散列函数对其进行改进。问题是,Rabin-Karp的复杂度与强力字符串匹配相同,均为O(mn)。

我们显然需要采用一种不同方法,但为了提出这种不同方法,先来看看强力字符串搜索有什么不妥之处。事实上,再深入地研究一下它的基本原理,就能找到问题的答案了。

在强力匹配算法中,查看文本中的每个字符是否与模式串的第一个字符匹配。如果匹配,则顺次比较模式串的第二个字符是否与文本的下一字符匹配。问题在于,当出现失配时,我们必须要在文本中回退若干位置。嗯,这种方法事实上是无法优化的。

在强力字符串匹配算法中,若出现失配,必须回退,并对比已经对比过的字符!

在强力字符串匹配算法中,若出现失配,必须回退,并对比已经对比过的字符!

从上图可以看出问题所在:一旦出现失配,必须回滚,从正文中一个已经考察过的位置开始比较。在这里给出的示例中,我们已经查对了第一、二、三、四字母,此时模式串与文本之间出现失配,于是……于是我们就得返回去,从文本的第二个字母重新开始比较。

这一过程显然没有任何作用,因为我们已经知道模式串的起始字母为“a”,而且在位置1与位置3之间没有这一字母。那我们如何消除这种不必要的重复呢?

概述

James H. Morris和Vaughan Pratt在1977年回答了这一问题,他们当时对自己的算法进行了介绍,这种算法会跳过大量无用对比,所以其效率高于强力字符串匹配。我们来详细地研究一下。唯一值得注意的地方就是:它利用了在对模式串与可能匹配进行对比期间收集的信息,如下图所示。

Morris-Pratt向前移动到下一可能匹配位置,略过一些对比!

Morris-Pratt向前移动到下一可能匹配位置,略过一些对比!

为利用该信息,必须首先对模式串进行预处理,以获取后续匹配的可能位置。之后开始查找可能的匹配结果,在发生失配时,我们可以准确地知道应当跳转到何处,以跳过没有任何用处的对比。

生成后续对比位置表格

这是Morris-Pratt算法中最富有技巧性的地方,这种算法就是通过这一步骤来克服强力字符串搜索算法的缺陷的。让我们来看几张图片。

显然,如果模式串中仅包含不同字符,在发生失配时,应当开始将文本中的下一字符与模式串的第一字符进行对比!

显然,如果模式串中仅包含不同字符,在发生失配时,应当开始将文本中的下一字符与模式串的第一字符进行对比!

不过,当模式串中存在重复字符时,如果在该字符之后出现失配,则必须从这一重复字符开始查找可能匹配,如下图所示。

如果模式串中包含重复字符,则“下一位置”表格会稍有不同!

如果模式串中包含重复字符,则“下一位置”表格会稍有不同!

最后,如果文本中的重复字符不止1个,“下一个”表格将给出其位置。

“下一个”表格中包含重复字符的位置!

“下一个”表格中包含重复字符的位置!

有了这个包含“后续”可能位置的表格之后,就可以开始在文本中查找模式串了。

enter image description here

实现

Morris-Pratt算法的实现并不困难。首先,必须对模式串进行预处理,然后执行搜索。以下PHP代码展示了具体过程。

/**
* Pattern
* 
* @var string
*/
$pattern = 'mollis';

/**
* Text to search
* 
* @var string
*/
$text = 'Lorem ipsum dolor sit amet, consectetur adipiscing elit. Quisque eleifend nisi viverra ipsum elementum porttitor quis at justo. Aliquam ligula felis, dignissim sit amet lobortis eget, lacinia ac augue. Quisque nec est elit, nec ultricies magna. Ut mi libero, dictum sit amet mollis non, aliquam et augue';

/**
* Preprocess the pattern and return the "next" table
* 
* @param string $pattern
*/
function preprocessMorrisPratt($pattern, &$nextTable)
{
    $i = 0;
    $j = $nextTable[0] = -1;
    $len = strlen($pattern);

    while ($i < $len) {
        while ($j > -1 && $pattern[$i] != $pattern[$j]) {
            $j = $nextTable[$j];
        }

        $nextTable[++$i] = ++$j;
    }
}

/**
* Performs a string search with the Morris-Pratt algorithm
* 
* @param string $text
* @param string $pattern
*/
function MorrisPratt($text, $pattern)
{
     // get the text and pattern lengths
    $n = strlen($text);
    $m = strlen($pattern);
    $nextTable = array();

    // calculate the next table
    preprocessMorrisPratt($pattern, $nextTable);

    $i = $j = 0;
    while ($j < $n) {
         while ($i > -1 && $pattern[$i] != $text[$j]) {
            $i = $nextTable[$i];
        }
        $i++;
        $j++;
        if ($i >= $m) {
            return $j - $i;
        }
    }
    return -1;
  }

 // 275
 echo MorrisPratt($text, $pattern);

复杂度

这一算法需要一定的时间和空间进行预处理。模式串的预处理可以在O(m)内完成,其中m为模式串的长度,而搜索本身需要O(m+n)。好消息是预处理过程只需要完成一次,然后就可以根据需要执行任意次搜索了!

下面的图表给出了5字母模式串的O(n+m)复杂度,并将其与O(nm)进行对比。

enter image description here

应用

优点

  1. 其搜索复杂度为O(m+n),快于强力算法和Rabin-Karp算法
  2. 其实现相当容易

缺点

  1. 需要额外的空间与时间-O(m)进行预处理
  2. 可以稍加优化(Knuth-Morris-Pratt)

结语

显然,这一算法非常有用,因为它以一种非常雅致的方式对强力匹配算法进行了改进。另一方面,我们必须知道还有诸如Boyer-Moore算法等更快速的字符串查找算法。不过,Morris-Pratt算法在许多情况下都非常有用,所以理解其基本原理后可能会非常便利。

相关贴子:

  1. 计算机算法:Boyer-Moore字符串查找法
  2. 计算机算法:Rabin-Karp字符串查找法
  3. 计算机算法:强力字符串查找法

原文标题:Computer Algorithms: Morris-Pratt String Searching 原文链接:http://www.stoimen.com/blog/2012/04/09/computer-algorithms-morris-pratt-string-searching/