字符串匹配:Horspool算法

2016年01月06日 原创
关键词: C++ 数据结构 算法
摘要 字符串匹配算法是最常用的算法之一,Horspool算法是一种较好的字符串匹配算法。

比起蛮力算法每次总是只移动一个位置,从右到左的字符比较使模式移动的更远。然而,如果这个算法在每次尝试的时候都必须检查模式中的每个字符,它的优势也会丧失殆尽。我们可以预先算出每次移动的距离并把它们存在表中。这个表是以文本中所有可能遇到的字符为索引的,对于一个自然语言的文本来说,这些字符包括空格、标点符号和其他一些特殊符号。(请注意,对于最终要查找的文本,我们并不需要它的其他信息。)我们将移动的距离填入表中的单元格。具体来说,对于每一个字符c,我们可以用以下公式算出移动距离:

例如,对于模式BARBER,除了E,B,R,A的单元格分别为1,2,3,4,之外,表中所有的单元格都等于6。

这里有一个简单的算法用来计算移动表中每个单元格的值。初始时把所有的单元格都置为模式的长度m,然后从左到右扫描模式,将下列步骤重复m-1遍:对于模式中的第j个字符(0≤j≤m-2),将它在表中的单元格改写为m-1-j,这是该字符到模式右端的距离。注意,因为该算法从左到右扫描模式,一个字符的最后一次改写是在该字符最右边一次出现的时候,这正是我们所希望的。

算法  ShiftTable(P[0...m-1])

   //填充移动表

   //输入:模式P[0..m-1]以及一个可能出现字符的字母表Table[0..size-1]

   //输出:以字母表中字符为索引的数组Table[0..size-1]

   //表中填充的移动距离是通过上述公式(图片)算出来的

  把Table中所有的元素初始化为m

  for j←0 to m-2 do Table[P[j]]←m-1-j

  return Table

现在,我们可以对该算法做如下总结。

Horspool算法

第一步:对于给定的长度为m的模式和在模式及文本中用到的字母表,按照上面的描述构造移动表。

第二步:将模式与文本的开始处对齐。

第三步:重复下面的过程,直到发现了一个匹配子串或者模式的到达了文本的最后一个字符以外。从模式的最后一个字符开始,比较模式和文本中的相应字符,直到:要么所有m个字符都匹配(然后停止),要么遇到了一对不匹配的祖父。在后一种情况下,如果c是当前文本中和模式的最后一个字符相对齐的字符,从移动表的第c列中取出单元格t(c)的值,然后将模式沿着文本向右移动t(c)个字符的距离。

以下是Horspool的一段伪代码。

算法   HorspoolMatching(P[0..m-1],T[0..n-1])

   //实现Horspool字符串匹配算法

   //输入:模式P[0..m-1]和文本T[0..n-1]

   //输出:第一个匹配子串最左端字符的下标,但如果没有匹配子串,则返回-1

   ShiftTable(P[0..m-1])

   i←m-1

   while i≤n-1 do

     k←0

     while k≤m-1 and P[m-1-k]=T[i-k] do

       k←k+1

      if k=m

       return i-m+1

     else i←i+Table[T[i]]

   return -1

对于随机文本来说,Horspool算法的效率是Θ(n)的。

下面是Horspool算法的c++代码:

#include<iostream>
#include<cstring>
using namespace std;
int* ShiftTable(char* arr, int n) {
    int* table = new int[256];
    for (int i = 0; i < 255; i++) {
        table[i] = n;
    }
    for (int i = 0; i < n-1; i++) {
        table[arr[i]] = n - i-1;
    }

    return table;
}
int HorspollMatching(char* pattern, char* text) {
    int m = strlen(pattern);
    int n = strlen(text);
    int* table = ShiftTable(pattern,m);
    int i = m - 1;
    while (i < n) {
        int k = 0;
        while (k < m&&pattern[m-k-1]==text[i-k]) {
            k++;
        }
        if (k == m) {
            return i - m + 1;
        }
        else {
            i = i + table[text[i]];
        }
    }
    return -1;

}
int main() {
    char* text = "JIM_SAW_ME_IN_A_BARBBERSHOPBARBAECARBER";
    char* pattern = "CARBER";
    int pos = HorspollMatching(pattern, text);
    cout << pos << endl;
    return 0;
}

运行结果: