logo
当前位置:首 页 > 编程技术 > 查看文章

Aho-Corasick 算法介绍

编程技术 你是第419个围观者 0条评论 供稿者:

背景

Aho–Corasick 算法(也称 AC 算法,AC 自动机)是由 Alfred V. Aho 和 Margaret J.Corasick 发明的字符串搜索算法,该算法在 1975 年产生于贝尔实验室,是著名的多模匹配算法之一。

一个典型应用就是:给出 k 个单词,再给出一段文章(长度是 n),让你找出有多少个单词在文章里出现过。

与其它模式串匹配不同,KMP 算法是单模式串的匹配算法,AC 算法是多模式串的匹配算法,匹配所需的时间复杂度是 O(n)。

AC 算法建立在字典树基础上,如果您还不了解字典树,可以参考字典树入门。

算法过程分析

以上述所说的典型应用为例,现给定 3 个单词 {“china”, “hit”, “use”},再给定一段文本 “chitchat”,求有多少个单词出现在文本中。

根据单词 {“china”, “hit”, “use”} 建立字典树。

根据所给文本 “chitchat” 依次匹配,图中所示 “chi” 为匹配成功的字符串。

当匹配到第四个字符时,“t”和 “n” 匹配失败。

我们此时是知道已匹配成功的字符串的,即 “chi”。

AC 算法的核心就是在所有给定的单词中,找到这样的一个单词,使其与已匹配成功字符串的相同前后缀最长,利用这个最长的相同前后缀实现搜索跳转。

如上图,单词 “hit” 与已匹配成功字符串 “chi” 的最长相同前后缀为 “hi”,因此下一步从单词“hit” 的“t”开始搜索。

此时 “t” 是匹配的,在文本 “chitchat” 中找到一个单词“hit”。

其实到这里,AC 算法的思想已经基本呈现在大家面前了。剩下的问题就是如何解决第(3)步所述的 “核心”。

AC 算法核心

在每个结点里设置一个指针(我们称之为 fail 指针),指向跳转的位置。

对于跳转位置的选择,基于以下两点:

对于根结点的所有儿子结点,它们的 fail 指针指向根结点;

而对于其它结点,不妨设该结点上的字符为ch,沿着它的父亲结点的 fail 指针走,直到走到一个结点,它的儿子中也有字符为ch的结点,然后把该结点的 fail 指针指向那个字符为ch的结点。如果一直走到了根结点都没找到,那就把 fail 指针指向根结点。

对于第 2 点,初学者可能有点不理解,我这里稍微解释下。请仔细阅读上面的第(3)步过程,利用父亲结点的最长相同前后缀来找到儿子的最长相同前后缀。

完整代码

/**

*

* author : 刘毅(Limer)

* date   : 2017-08-10

* mode   : C++

*/

#include <iostream>

#include <queue>

#define TREE_WIDTH 26

using namespace std;

struct Node

{

int end;

Node * fail;

Node * next[TREE_WIDTH];

Node()

{

this->end = 0;

this->fail = nullptr;

for (int i = 0; i < TREE_WIDTH; i++)

this->next[i] = nullptr;

}

};

class AC

{

private:

Node * root;

public:

AC();

~AC();

void destroy(Node * t);

void add(char * s);

void build_fail_pointer();

int ac_automaton(char * t);

};

AC::AC()

{

root = new Node;

}

AC::~AC()

{

destroy(root);

}

void AC::destroy(Node * t)

{

for (int i = 0; i < TREE_WIDTH; i++)

if (t->next[i])

destroy(t->next[i]);

delete t;

}

void AC::add(char * s)

{

Node * t = root;

while (*s)

{

if (t->next[*s – ‘a’] == nullptr)

t->next[*s – ‘a’] = new Node;

t = t->next[*s – ‘a’];

s++;

}

t->end++;  // 假设单词可重复

}

void AC::build_fail_pointer()

{

queue<Node*> Q;

for (int i = 0; i < TREE_WIDTH; i++)

{

if (root->next[i])

{

Q.push(root->next[i]);

root->next[i]->fail = root;

}

}

Node * parent = nullptr;

Node * son = nullptr;

Node * p = nullptr;

while (!Q.empty())

{

parent = Q.front();

Q.pop();

for (int i = 0; i < TREE_WIDTH; i++)

{

if (parent->next[i])

{

Q.push(parent->next[i]);

son = parent->next[i];

p = parent->fail;

while (p)

{

if (p->next[i])

{

son->fail = p->next[i];

break;

}

p = p->fail;

}

if (!p)  son->fail = root;

}

}

}

}

int AC::ac_automaton(char * t)

{

int ans = 0;

int pos;

Node * pre = root;

Node * cur = nullptr;

while (*t)

{

pos = *t – ‘a’;

if (pre->next[pos])

{

cur = pre->next[pos];

while (cur != root)

{

if (cur->end >= 0)

{

ans += cur->end;

cur->end = -1;  // 避免重复查找

}

else

break;  // 等于 -1 说明以前这条路径已找过,现在无需再找

cur = cur->fail;

}

pre = pre->next[pos];

t++;

}

else

{

if (pre == root)

t++;

else

pre = pre->fail;

}

}

return ans;

}

int main()

{

int n;

char s[1000];

while (1)

{

cout << “请输入单词个数:”;

cin >> n;

AC tree;

cout << “请输入” << n << “个单词:\n”;

while (n–)

{

cin >> s;

tree.add(s);

}

 

cout << “请输入搜索文本:”;

cin >> s;

 

tree.build_fail_pointer();

cout << “共有” << tree.ac_automaton(s) << “个单词匹配” << endl << endl;

}

return 0;

}

执行截图:

一个有大大梦想但是没有支撑这梦想的技术的攻城狮,大家就当这个博客是你的技术工具箱吧,我会吧我工作中遇到的问题贴在这,大家需要的记得把我放到收藏夹哦! 百度输入“子傲代码”就可以了

—— 陈子傲

admin
众说纷纭Comments
大眼 可爱 大笑 坏笑 害羞 发怒 折磨 快哭了 大哭 白眼 晕 流汗 困 腼腆 惊讶 憨笑 色 得意 骷髅 囧 睡觉 眨眼 亲亲 疑问 闭嘴 难过 淡定 抗议 鄙视 猪头
小提示:直接粘贴图片到输入框试试
努力发送中...
  • 评论最多
  • 最新评论
  • 随机文章
footer logo
未经许可请勿自行使用、转载、修改、复制、发行、出售、发表或以其它方式利用本网站之内容
Copyright ©ziao design Studio All Rights Reserved.沪ICP备14052271号-3