对数据库开发和文本处理软件而言,字符串匹配(String matching)可谓至关重要。幸运的是,在所有的现代程序设计语言和代码库中,字符串处理函数比比皆是,它们对我们的日常工作大有裨益。然而要是能理解它们的原理那就太棒了!

序言

对数据库开发和文本处理软件而言,字符串匹配(String matching)可谓至关重要。幸运的是,在所有的现代程序设计语言和代码库中,字符串处理函数比比皆是,它们对我们的日常工作大有裨益。然而要是能理解它们的原理那就太棒了!

字符串算法主要可分为几大类。字符串匹配就是其中之一。

当我们提起字符串匹配时,最基本的方法就是“暴力(brute force)”法,这意味着只需检查文本中的每个字符与模式串(通常比文本更短)的匹配情况。我们要做的就是回答此模式串是否在文本中出现过。

概述

暴力字符串匹配的原理十分简单。我们必须检查文本(text)的首字符与模式串(pattern)的首字符是否匹配,如下图所示。

First step of brute force string matching (若以上图片无法正常显示,请点击这里) 我们从文本和模式串的首字符开始比较!

要是它们不匹配,我们就后移至文本的第二个字符。然后拿文本的第二字符与模式串的首字符相比较。要是它们又不匹配,我们就继续后移,直到获得匹配,或是达到文本的末端为止。

Second step of brute force string matching (若以上图片无法正常显示,请点击这里) 由于文本首字符与模式串首字符不匹配,因此我们后移至文本的第二个字符。然后我们拿文本的第二字符与模式串的首字符相比较!

如果它们相匹配,我们就后移至模式串的第二字符,拿它与文本的“下一”字符相比较,

Third step of brute force string matching (若以上图片无法正常显示,请点击这里) 一旦文本中的字符与模式串首字符相匹配,我们就后移至模式串的第二个字符和文本的下一字符!(继续进行比较。)

我们不能仅因为找到文本中的某一字符与模式串的首字符相匹配,就说文本里有模式串。我们必须后移,以便确认文本中是否包含整个模式串。

Match in brute force string matching (若以上图片无法正常显示,请点击这里) 模式串匹配上啦!

实现

暴力字符串匹配的实现很容易,所以在这里我们来看个简短的PHP示例。不过坏消息是,这个算法天生就非常慢。

function sub_string($pattern, $subject)
{
    $n = strlen($subject);
    $m = strlen($pattern);

    for ($i = 0; i < $n-$m; $i++) {
        $j = 0;
        while ($j < $m && $subject[$i+$j] == $pattern[$j]) {
            $j++;
        }
        if ($j == $m) return $i;
    }
    return -1;
}

echo sub_string('o wo', 'hello world!');

译注:尽管以上示例实现了暴力字符串匹配,但是代码的可读性实在不敢苟同,因此俺用Javascript重写了此示例,以便读者(包括俺自己在内)理解,示例如下:

// 暴力字符串匹配实现之Javascript示例。
function IndexOf(pattern, text)
{
    var textLength = text.length;
    var patternLength = pattern.length;

    for (var textIndex = 0; textIndex < (textLength-patternLength); textIndex++)
    {
        var patternIndex = 0;
        // 判断是否【未到达模式串末尾】且【文本字符与模式字符相匹配】。
        while ((patternIndex < patternLength) && text.charAt(textIndex+patternIndex) == pattern.charAt(patternIndex))
        {
            patternIndex++;
        }
        // 当模式串完整匹配时,返回当前文本索引位置。
        if (patternIndex == patternLength)
            return textIndex;
    }

    // 无完整匹配时返回-1。
    return -1;
}

document.write(IndexOf('o wo', 'hello world!'));
// 将在页面上输出:4

复杂度

如我所说,这个算法很慢。其实所有名字里含有“暴力(brute force)”二字的算法都很慢,不过为了说明字符串匹配有多慢,我会说其复杂度是O(n.m)。其中n是文本长度,而m是模式串长度。

Brute force string matching complexity chart 1

对于m = 5的定长模式串,我们可以看到,即便是对于相对较短的文本,时间增长得也很快!

如果我们固定下文本长度,然后用变长模式串来进行测试,我们还是获得了快速增长的函数。

Brute force string matching complexity chart 2

应用

暴力字符串匹配可能收效甚微,不过在某些情况下也可能大显身手。正如顺序搜索(sequential search)一文所讲的一样。

它可能大显身手……

  1. 无需对文本进行预处理——如果我们仅搜索一次文本,确实没必要对其进行预处理。大多数字符串匹配算法为了达到快速搜索的目的,都需要构建文本索引。当你要对某段文本多次搜索时,这么做是很棒,不过如果你仅搜索一次的话,那么或许(对于短文本)暴力匹配就很不错了!
  2. 无需额外空间——因为暴力匹配无需预处理,所以它也无需更多空间,这是此算法一大的特色!
  3. 对短文本和短模式串效果显著!

它可能收效甚微……

  1. 如果我们对文本进行多次搜索——如上节所述,要是你会执行多次搜索,可能最好使用其他会构建索引的字符串匹配算法,而且那些算法会更快。
  2. 它很慢——通常暴力算法都很慢,因此暴力匹配也不例外。

最后的话

字符串匹配在软件开发中是非常特别的一类,而且其用途广泛,因此每位开发者须对此了然于心。

查看英文原文:Computer Algorithms: Brute Force String Matching

相关博文

  1. Computer Algorithms: Rabin-Karp String Searching
  2. Computer Algorithms: Morris-Pratt String Searching
  3. Powerful PHP: Less Known String Manipulation

图灵社区相关译文

  1. 图说Rabin-Karp字符串查找算法

iTran乐译

【iTran乐译】参加活动,读好文章!