算法学习:字典树、KMP与AC自动机

发布于 / 算法学习 / 0 条评论

字典树

学习自博客:https://blog.csdn.net/qq_42815188/article/details/88677836

字典树(又称为单词查找树,Tire 树)是一种树形结构。它与字典相似,当要查找的一个单词是否在字典树中,首先看单词的第一个字母是否在字典树的第一层。如果不在,说明字典树中没有该单词;如果在,就在该单词的子节点中找是否有单词的第二个字母,如果没有,则说明没有此单词,有的话就继续查找,以此类推。

字典树

字典树有以下的基本性质:

  • 字典树使用边表示字符;(也可以理解为每个节点上保存字符,因为这个边的信息是使用j节点来标识的)
  • 有相同的前缀的单词共用前缀节点;
  • 根结点不包含有字符;
  • 每个单词结束的时候都用一个特殊字符表示,如图中使用的是一个 $ 符号;(或者使用数字表示存在该字符串的个数)
  • 从根结点道到一个 $ 所经过的所有边的字母就是一个字符串。

字典树常用于统计、排序和保存大量的字符串(不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。

优点:利用字符串的公众前缀来节约存储空间,最大限度地减少无用字符串的比较。

构建字典树

编号方案

引入数组tire[][]tire[i][j] = k表示:tire树中编号为i的节点的边上为字母(char)( 'a' + j )的儿子为编号为j的节点(这里不用于一般的树的储存方式)。而这个节点应存储的信息(如这个单词出现了多少次)则单独开一个以编号为下标的数组来记录。

数组编号信息

以此种方式标记好的字典树将如下图所示:(图中的数字指的是这条边结尾处的节点的编号,其中根结点编号为 0)。

建树

插入操作

当有新的需要插入的词语(字符串)出现时,我们就依次对比每一个字母在对应层中是否已经出现来判断新进入的词语是否与已经存在的词相同或语有相同的前缀。当出现差异时,我们就标记激活这个节点(标记这个节点为单词词尾节点并将其值(指另一个存储该节点信息的值)加一)。相同词语则直接使词尾节点的值(指另一个存储该节点信息的值)递增。具体操作如下代码:

// 实例为字符串中只有'a'~'b'26个字母的字典树
#define SIGMA_SIZE 26
// MAXN_NODE根据题意进行赋值
int tire[MAXN_NODE][SIGMA_SIZE] = {0}; 
int tag[MAXN_NODE] = {0};                      // 标记编号为i的节点是否为单词节点
int cnt[MAXN_NODE] = {0};                      // 记录编号为i的单词节点所对应的单词出现次数
int node = 0;                                  // Trie树的节点个数

void Insert(string str){
    int now = 0;                               // 用以记录目前遍历到的节点编号
    int len = str.length();
    for(int i = 0; i < len; i++){
        if(!tire[now][str[i] - 'a']){          // 如果这个节点未曾有子节点(前缀出现偏差)
            tire[now][str[i] - 'a'] = ++node;
        }
        now = ch[now][str[i] - 'a'];
    }
    tag[now] = true;
    cnt[now] ++;
}

查询操作

只要建树搞得好,这就莫的问题。

// 如果找到则返回词的个数,如果没有找到或无该词则返回-1
int find(string str){
    int len = str.length();
    int now = 0;
    for(int i = 0; i < len; i++){
        int c = str[i] - 'a';
        if(tire[now][c] == 0){ // 没有子节点了,也就是这个单词不存在实锤
            return -1;
        }
        now = trir[now][x];
    }
    if(tag[now])
        return cnt[now];
    else return -1;
}

KMP 算法

学习自博客:https://blog.csdn.net/v_july_v/article/details/7041827

Knuth-Morris-Pratt 字符串查找算法,简称 KMP 算法,常用在于一个文本串S内查找一个模式串P的出现位置,这个算法由Donald KnuthVaughan PrattJames H. Morris三人联合发表,故取这三个人的姓氏命名此算法。

传统的模式串匹配使用的是纯暴力匹配算法。

纯暴力匹配

  • 如果当前字符匹配成功(S[i] == P[j]),则i++j++,继续匹配下一个字符;
  • 如果没有匹配成果(S[i] != P[j]),则令i = i - (j - i)(回溯到开始匹配的字符的下一个字符)、j = 0,重新匹配模式串。

如以下的图解(假设文本串S = "BBC ABCDAB ABCDABCDABDE",模式串P = "ABCDABD"):

  • 首先从第0位开始匹配:

    KMP匹配第0位

    发现匹配不成功,则匹配串右移。

  • 匹配文本串的第1位:

    匹配第1位

    发现依旧不匹配,继续将匹配串右移。

  • 直到出现了一次匹配(匹配串移动到了第4位):

    第1位匹配成功
    发现匹配成功,则i++j++。对下一位进行匹配。

  • 将文本串的第5位与匹配串的第1位匹配:

    第2位匹配成功

    发现匹配成功,继续i++j++。对下一位匹配,直到出现不能匹配的项。

  • 再次出现不能匹配的项:

    出现失配

    发现匹配不成功,则匹配串右移,重新从匹配串的第一位开始进行匹配。

  • じゃ、もう一度!

    重新匹配

从示例可以看出,这种匹配模式下,每次出现错误的匹配都需要回溯到词头再进行匹配,十分的低效,算法复杂度也到了O(m\cdot n)。如果我们在进行匹配的时候,能基本做到不进行回溯而只移动模式串的话,算法复杂度将极大地提升。

KMP算法匹配字符串

让我们回到起点重新进行模式串匹配:

  • 首先匹配文本串的第0位:

    KMP匹配第0位

    发现匹配不成功,则匹配串右移。

  • 匹配文本串的第1位:

    KMP匹配第1位

    发现依旧不匹配,继续将匹配串右移。

  • 直到出现了一次匹配(匹配串移动到了第4位):

    KMP第1位匹配成功

    发现匹配成功,则i++j++。对下一位进行匹配。

  • 将文本串的第5位与匹配串的第1位匹配:

    KMP第2位匹配成功

    发现匹配成功,继续i++j++。对下一位匹配,直到出现不能匹配的项。

  • 再次出现不能匹配的项:

    KMP失配

    发现匹配不成功,则匹配串右移,重新从匹配串的第一位开始进行匹配。

这时我们考虑,真的要回溯到文本串的第5位然后重新开始与模式串的第一位进行比较么?我们可以发现我们已经匹配了的部分中有一段字符串"AB",而模式串的前缀中也有"AB"。也就是说,其实我们可以认为已经将模式串的前两位匹配成功了,我们只需要继续匹配模式串的第2位(从0开始编号)就可以了。

  • 不进行回溯而将模式串右移一定的位:

    KMP回溯

    发现匹配错误,将模式串继续移位。

  • 移位将字符串的第10位与模式串第0位进行匹配:

    KMP回溯

  • 发现匹配错误,移位对字符串的下一位进行匹配。

  • 移位将字符串第11位与模式串第0位进行匹配:

    KMP再次回配

    发现匹配成功。则i++j++,进行下一位匹配。以此类推,直到再次发生不能匹配。

  • 直到再一次发生匹配失败:

    KMP失配

    情况与上一次相似,都是出现在了'D'位,所以模式串向右移动。

  • 模式串向右移动四位:

    KMP回溯&再再回配

    发现匹配成功,则不断的i++j++

  • 匹配完成:

    KMP最终匹配成功

这种匹配方式下,字符串完全不需要进行回溯,只需要将模式串进行一定量的右移就可以得到最终结果。这是一种高效的模式串匹配方法。算法的时间复杂度仅为 O(m + n)

那么这个算法的重点就是在于:模式串应该如何的右移,也就是当发生匹配失败时,我应该去匹配模式串的哪一位?所以我们引进了next[]数组。

从我们过程的分析中可以发现,我们判断需要将模式串向右移动几位是依据我们的模式串的开头部分与结尾部分中是否有重复出现的一部分,如果存在,我们就可以移动模式串使着相同的部分重合,从而节省了前面一段部分的匹配。所以我们要找出这一位以前(包括这一位)前缀与后缀的数量的这个子串中出现的最长的具有相同元素的前缀与后缀。我们可以得到如下表格:

模式串的各个子串 前缀 后缀 最大公共元素长度
A 0
AB A B 0
ABC A, AB C, BC 0
ABCD A, AB, ABC D, CD, BCD 0
ABCDA A, AB, ABC, ABCD A, DA, CDA, BCDA 1
ABCDAB A, AB, ABC, ABCD, ABCDA B, AB, DAB, CDAB, BCDAB 2
ABCDABD A, AB, ABC, ABCD, ABCDA, ABCDAB D, BD, ABD, DABD, CDABD, BCDABD 0
字符 A B C D A1 B2 D
最大前缀后缀公共元素长度 0 0 0 0 1 2 0

nect[]数组的作用是,重复到拥有相同前缀的位置。所以我这一位要回到哪里要看的是这一位之前的字符串中最长长度的拥有的相同的前后缀的长度为多少。而对于第一位,他之前没有字符串,所以我需要做的是将字符串右移一位然后进行重新匹配,所以next[0]的值应为 -1 。所以next[]数组的值即为将最大前缀后缀公共元素长度表的内容全体后移一位然后将第0位赋值成 -1 即可!示例的next[]数组如下:

字符 A B C D A_1 B_1 D
next[]对应位的值 -1 0 0 0 0 1 2

而在求模式串的next[]数组的过程中,我需要找到模式串子串的前后缀,即比对模式串子串与模式串是否有相同部分的内容,同样可以使用KMP算法,所以我们在求后面几位的next[]时完全可以用到前面几位的next[]的值。

求得next[]数组的代码如下:

void GetNext(string p,int next[])
{
    int p_len = p.length();
    next[0] = -1;
    int k = -1;
    int j = 0; // 标记目前在计算第几位的next值
    while (j < p_len - 1){
        //p[k]表示前缀,p[j]表示后缀
        if (k == -1 || p[j] == p[k]) { // 初始状态或者需要右移或者匹配成功
            ++k;
            ++j;
            next[j] = k;
        } else {
            k = next[k]; // 匹配失败
        }
    }
}

在使用KMP算法匹配字符串的算法如下:

int KMPSearch(string str, string p){
    int i = 0, j = 0;
    int str_len = str.length();
    int p_len = p.length();
    while (i < str_len && j < p_len){
        if (j == -1 || s[i] == p[j]){ // 如果需要后移或者匹配成功
            i++;
            j++;
        }else{ // 如果匹配失败
            j = next[j];
        }
    }
    if(j == p_len) // 匹配成功
        return i - j;
    else return -1; // 匹配失败
}

AC 自动机

学习自博客:https://blog.csdn.net/bestsort/article/details/82947639

AC自动机是以字典树作为搜索数据结构,利用KMP原理减少回溯的操作,以实现多模式串匹配。算法复杂度优化到了 O(n)

AC自动机就是在字典树的基础上,增加上一个fail指针,如果当前点处匹配失败的话,就将指针转移到fail指针所指的位置,来减少没有必要的回溯。(类似KMP中的next[]的作用)

如我现在有待匹配的串,为"shershisher"。我现在有模式串"hers""hrs""she",形成如图所示的字典树:

形成字典树

fail指针的作用就是在我出现匹配失败的时候,我能立刻转移到相近的能继续匹配下去的串而不需要重新再来。所以我们需要找出在不同模式串中前缀匹配的部分。fail指针的构建都是用BFS来实现的,基本的操作就是指向节点的父节点fail指针所指向的节点的子节点中与其相同的节点,如果没有,则指向它父亲节点的fail指针指向的节点。以如图所示的字典树,我对他进行fail指针构建:

  • 第一层遍历,每个串的首字母肯定是指向根节点:

    第一层遍历

  • 第二层遍历,我们瞄准最左面的子树的第一个节点(被e指向的绿色节点):

    应指向他的父节点(h指向的橙色节点)的fail指针指向的节点(蓝色的根结点)的子节点中指向边为e的节点,不存在,所以指向他父节点的fail指针指向的节点(根结点)

    第二层第一节点

  • 第二层的第二个节点,相同。接下来看第三个节点(被h指向的绿色节点):

    应指向他的父节点(s指向的橙色节点)的fail指针指向的节点(蓝色的根结点)的子节点中指向边为h的节点(h指向的橙色节点)。所以得到如下图:

    第二层二三节点

  • 依次如此作图,最终得到如下图(有点乱):

    AC自动机

在我进行字符串"shershisher"匹配时,首先匹配"she"成功,ans++e之后没有字符继续匹配,所以指向fail指针指向的另一个e即开始匹配"hers",匹配成功,ans++。后s指向最右侧树的s,开始匹配"she",匹配到h后失配,所以指向fail开始匹配"hers",到s匹配失败。所以最终结果为 2

转载原创文章请注明,转载自: KONGJUNE » 算法学习:字典树、KMP与AC自动机
Not Comment Found