«

典型字符串匹配算法实现

0.序

相信大家对快捷键ctrl+F是做什么用的都应该很熟悉了,无论是文本编辑、网页浏览等程序上它都意味着字符串搜索,我们提供一个关键字,它将找到当前页面上的所有该关键字所在的位置。关键字称为模式串,在文本T中寻找模式串P出现的所有出现的位置,解决这种问题的算法叫做字符串匹配算法。字符串匹配算法可以说是计算机科学中最古老、研究最广泛的问题之一,并且字符串匹配的应用也随处可见,特别是信息检索领域和计算生物学领域。

字符串匹配算法有很多很多,多到可以出一本书了《柔性字符串匹配》...感兴趣的同学可以查阅一下这本书。

其中最著名可算是Knuth-Morris-Pratt(KMP)算法和Boyer-Moore(BM)算法,因为这两个经典算法都将匹配算法的时间复杂度的理论值从O(m*n)降到了线性的O(m+n),由此促使我好好研究了一下。除了经典算法,简洁但不失效率的较新的Horspool算法和Sunday算法也是我不可错过的。接下来先从最最最简单的朴素匹配算法开始讲起吧:

:文中的算法程序,输入文本T、模式串P,打印出P在T中的所有位置起点。)

1、朴素匹配算法

尽管很多资料上将最简单的匹配算法成为暴力匹配,但我仍然喜欢算法导论上的叫法,朴素的匹配算法。

文本T长度为m,模式串P长度为n。算法从文本第1位从左向右开始与模式串P进行匹配,无论是否匹配成功,模式串都后移1位开始继续进行重新匹配,总共进行m-n+1次匹配。算法极其简单,因此效率极其有限,时间复杂度为O(m * n),故不常被用。

图例:

第一步:

第二步:(模式串后移1位)

第三步、第四步...

代码实现:

// 1.朴素的字符串匹配算法  
void NaiveMatcher(const char *T, const char *P)  
{  
    int m = strlen(T);  
    int n = strlen(P);  

    for (int i=0; i<=m-n; i++)  
    {  
        int j;  
        for (j=0; j<n; j++)  
            if (T[i+j] != P[j]) break;  

        if (j==n) cout<<i<<" ";  
    }  
    cout<<endl;  
}  

2、KMP算法

要提高匹配算法的速度,关键点就在于每次匹配结束后,模式串需要向后偏移的位数。朴素匹配算法中不管三七二十一,每次就移一位,效率低下。所以人们开始思考是否能够通过之前的匹配结果产生某些知识,使得每次向后偏移的位数尽量得大来获得高效性。

后来人们成功了,最有名的的便是Knuth、Morris、Pratt三个人设计的线性时间字符串匹配算法,俗称KMP算法,在学校的算法课中必备,在算法导论中也是字符串匹配章节里压轴的。这个算法被人骂很难理解,个人但弄明白之后其实还是挺好懂得。算法通过匹配成功的模式串P的前缀来得到每次向后偏移的位数。

  1. 首先,算法需要对模式串P进行预处理,得到一个部分匹配表kt:

    表中kt[i]等于字符串P[0-i]的前缀和后缀的最长的共有元素的长度。(例如p[0-3] = "abab",它的前缀有”a“,”ab“,”aba“,后缀有”b“,”ab“,”bab“,共有元素为”ab“,其长度为2,所以kt[3]等于2)。

  2. 然后每次开始从左向右匹配,因此此类算法隶属于基于前缀搜索的方法:

    2.1 若前k位匹配成功,则 后移位数s = 已匹配的字符数k - 部分匹配表对应值kt[k]:

    2.2 若第1位就匹配不成功,则 后移1位。

代码实现:

// 2.KMP算法  
int* PartialMatchTable(const char *P)  
{  
    int m = strlen(P);  
    int *kt = new int[m];  
    kt[0] = 0;  

    for (int i = 1, k = 0; i < m; ++i)  
    {  
        while (k>0 && P[k]!=P[i])  
            k = kt[k];  
        if (P[k] == P[i])  
            k = k+1;  
        kt[i] = k;  
    }  
    return kt;  
}  

void KmpMatcher(const char *T, const char *P)  
{  
    int m = strlen(T);  
    int n = strlen(P);  
    int *kt = PartialMatchTable(P);  

    int i=0, k=0;  
    while (i<=m-n)  
    {  
        while (k<n && T[i+k] == P[k])  
            k++;  

        if (k==0) {  
            k = 0;  
            i = i+1;  
        }else  
        {  
            if (k==n) cout<<i<<" ";  
            i = i+k-kt[k-1];  
            k = kt[k-1];  
        }  
    }  
    cout<<endl;  
    delete []kt;  
}  

KMP算法分为两个步骤,先通过P计算出部分匹配表,时间复杂度为O(n);再通过此表进行匹配位移,时间复杂度为O(m),故理论上的总时间复杂度为O(m+n),达到线性效率。理论效率高,但实际上却未特别突出。

参考文章:

  1. 《字符串匹配的KMP算法》

  2. 《算法导论》第32章"字符串匹配"

3、Boyer-Moore算法

Boter-Moore又是一个经典算法,传说中比KMP还快,由Bob Boyer与J Strother Moore在1977年提出。

与KMP有两个不同点:①每次匹配时,匹配方向不同,BM算法每次从右向左匹配,此类算法隶属于基于后缀搜索的方法。②匹配后向后偏移的位数由两种计算方式得到:坏字符偏移和好后缀偏移。下面详细介绍一下这两种方式:

上图中,文本中匹配成功的“AGAG”称为“好后缀”,文本中匹配失败的“C”称为“坏字符”。

一、坏字符偏移

当出现一个坏字符时,从模式串中找到最靠右的这个字符,将其位移到与坏字符相对,然后继续匹配。此时会有两种情况:

二、好后缀偏移

在模式串中找到除“好后缀”外,最靠右的与“好后缀”相同的子串,且子串前一位字符不等于“好后缀”前一位字符,则将此子串位移到与“好后缀”对应,然后继续匹配。此时会有三种情况:

**BM算法依然分为两步:

  1. 根据模式串P先计算出坏字符表bc和好后缀表gs,至于如何高效计算出两个表,其中gs表需要先求后缀表suff,详细请参考下面的参考文章,几位大牛已经讲得很详细了。图例:

  2. 根据坏字符表bc和好后缀表gs,依次匹配位移。

**BM总位移量计算:

IF 匹配完全成功
  根据好后缀偏移。
ELSE
  计算坏字符偏移量和好后缀偏移量,选择较大的偏移量进行偏移。

代码实现:

// 3.Boyer-Moore算法  
int* BadCharacter(const char *P)  
{  
    int m = strlen(P);  
    int *bc = new int[256];  
    for (int i=0; i<256; i++)  
        bc[i] = m;  
    for (int i=0; i<m; i++)  
        bc[(int)P[i]] = m - i - 1;  
    return bc;  
}  

int* suffixes(const char *P)  
{  
    int m = strlen(P);  
    int f = 0, g = m-1;  
    int *suff = new int[m];  
    for (int i=0; i<m; i++)  
        suff[i] = 0;  
    suff[m-1] = m;  

    for (int i=m-2; i>=0; --i)  
    {  
        if (i>g && suff[i+m-1-f]<i-g)  
            suff[i] = suff[i+m-1-f];  
        else  
        {  
            if (i<g)  
                g = i;  
            f = i;  
            while (g>=0 && P[g] == P[g+m-1-f])  
                g--;  
            suff[i] = f - g;  
        }  
    }  
    return suff;  
}  

int* GoodSuffix(const char *P)  
{  
    int m = strlen(P);  
    int *suff = suffixes(P);  
    int *gs = new int[m];  

    for (int i=0; i<m; i++)  
        gs[i] = m;  

    for (int i=m-1, j=0; i>=0; i--)  
    {  
        if (suff[i] == i+1)  
        {  
            for (j=0; j<m-1-i; j++)  
                if (gs[j] == m)  
                    gs[j] = m-1-i;  
        }  
    }  

    for (int i=0; i<=m-2; i++)  
        gs[m-1-suff[i]] = m-1-i;  

    delete []suff;  
    return gs;  
}  

void BoyerMooreMatcher(const char *T, const char *P)  
{  
    int m = strlen(T);  
    int n = strlen(P);  
    int *bc = BadCharacter(P);  
    int *gs = GoodSuffix(P);  

    int i=0, k=n-1;   
    while (i<=m-n)  
    {  
        for (k = n-1; k>=0 && T[i+k] == P[k]; k--);  

        if (k==-1)  
        {  
            cout<<i<<" ";  
            i = i + gs[0];  
        } else {  
            int offset = bc[(int)T[i+k]] - m + 1 + k;  
            if (offset < gs[k]) offset=gs[k];  
            i = i + offset;  
        }  
    }  
    cout<<endl;  

    delete []bc;  
    delete []gs;  
} 

BM算法计算坏字符表bc和好后缀表gs需要的时间复杂度最快都为O(n),第二步匹配位移时间复杂度为O(m),所以总的时间复杂度依旧为O(m+n),但理论上要比KMP快、快、快。。。

**参考文章:

1.《Boyer-Moore算法学习》

2.《Boyer-Moore算法详解》

4、Horspool算法

看完了两种理论上很经典的算法,是不是觉得有点头疼那,那么...现在忘了它们吧,为啥?因为,它们太复杂了,在字符串匹配研究领域中的一人所共知的事实便是“算法的思想越简单,实际应用效果越好”。KMP算法看起来很牛逼吧,但它在实际应用中比朴素算法还要慢一倍,BM算法牛逼吧,但其高度简化的后版本在实际中比它本身要快上很多。所以,让我们把该死的KMP算法和BM算法给忘了吧,来认识两种既简单又高效的字符串匹配算法。

首先介绍的是Horspool算法,它便是首个对BM算法进行简化的算法。它认为原BM算法中坏字符算法总能产生更大的偏移位移,于是它对坏字符算法进行了小修改,使其易于计算并能产生更大的偏移位移。

在BM算法中“坏字符”的定义是,已经匹配串前一位的文本字符,而在Horspool算法中,我们考虑的是自右向左匹配后匹配成功串的最后一个字符,然后在模式串P中找到非尾最靠右的这个字符,将其位移到对应位置。此时也会出现两种情况:

  1. 模式串P中能找到这个字符,则位移到对应位置

    此例中匹配串为“cd”,最后一位为“d”,找到P中最靠右且非尾的字符“d”,将其位移到对应位置后继续匹配)

  2. 模式串中不能找到这个字符,则位移n位

    因此,本算法同样分两步:第一步先通过P计算出“坏字符”表的变异版本,然后通过此表依次匹配位移。简单吧,比什么KMP和BM算法简单和好记多了,代码也简单。

实现代码:

// 4.Horspool算法  
int* HorspoolTable(const char *P)  
{  
    int n = strlen(P);  
    int *ht = new int[256];  
    for (int i=0; i<256; i++)  
        ht[i] = n;  
    for (int i=0; i<n-1; i++)  
        ht[(int)P[i]] = n - i - 1;  
    return ht;  
}  

void Horspool(const char *T, const char *P)  
{  
    int m = strlen(T);  
    int n = strlen(P);  
    int *ht = HorspoolTable(P);  

    int i=0, k=n-1;  
    while (i<=m-n)  
    {  
        for (k=n-1; k>=0 && T[i+k]==P[k]; k--) ;  

        if (k==-1)  
            cout<<i<<" ";  
        i = i + ht[(int)T[i+n-1]];  
    }  
    cout<<endl;  
    delete []ht;  
}  

5、Sunday算法

再来说一个好算法,Sunday算法,它与上面说的Horspool很类似,唯一不同点在于,Horspool利用的是匹配串的最后一位字符,而Sunday用得事匹配窗口后面的一位字符,这样可以带来更大的平均移动距离。尽管它的移动距离要长一些,但是“展开”的Horspool具有更少的内存引用次数,因而一般来说比Horspool算法要更慢一些。

下面依旧用图示说明两种情况:

  1. 无论匹配是否成功,模式串P中能找到匹配窗口后一位的文本字符,则位移到对应位置

  2. 模式串P中不能找到匹配窗口后一位的文本字符,则位移到此字符之后

实现代码:

// 5.Sunday算法  
int* SundayTable(const char *P)  
{  
    int n = strlen(P);  
    int *st = new int[256];  
    for (int i=0; i<256; i++)  
        st[i] = n;  
    for (int i=0; i<n; i++)  
        st[(int)P[i]] = n - i - 1;  
    return st;  
}  

void Sunday(const char *T, const char *P)  
{  
    int m = strlen(T);  
    int n = strlen(P);  
    int *st = SundayTable(P);  

    int i=0, k=0;  
    while (i<=m-n)  
    {  
        for (k=0; k<n && T[i+k]==P[k]; k++) ;  

        if (k==n)  
        {  
            cout<<i<<" ";  
            if ((i+n) > m)  
                break;  
        }  

        i = i + st[(int)T[i+n]] + 1;  
    }  
    cout<<endl;  

    delete []st;  
}  

6、总结

以上介绍的其实都是单字符串匹配算法,除了介绍的几种之外此类算法还有Shift-And/Shift-Or算法、BNDM算法、BOM算法等;除了这类,还有像Multiple Shift-And算法、Aho-Corasick算法、Set Horspool算法等等多字符串匹配的算法。这个领域水很深那,对于我来说还没那个必要去研究那么多,因为暂时用不上,现阶段知道几个简单高效的性价比高的单字符串匹配算法就ok了,比如Horspool和Sunday算法,因为在实际应用中编码效率和程序执行效率才是王道。

分享