dede 网站地图,看网红直播做爰的网站,上饶市住房和城乡建设网站,上海建工网站目录
前置知识
概述
核心概念#xff1a;fail指针
作用
构建
图示
Code
成员变量
创建销毁
添加词库
文本扫描
复杂度
Code 前置知识
在此前#xff0c;你应该首先了解trie树#xff08;字典树#xff09;的概念#xff1a;
「字符串」详解Trie#xff0…目录
前置知识
概述
核心概念fail指针
作用
构建
图示
Code
成员变量
创建销毁
添加词库
文本扫描
复杂度
Code 前置知识
在此前你应该首先了解trie树字典树的概念
「字符串」详解Trie字典树|前缀树并实现对应的功能 / 手撕数据结构C
我们建议你先阅读这篇文章以了解我们实现字典树所用的一些结构比如trie_node以及词尾节点存储了整个字符串这些概念。 概述
AC自动机是能以线性时间复杂度对整个文本进行黑名单词汇统计的数据结构。
我们先将黑名单语句词库逐条插入这棵字典树。当我们扫描文本时就能以一次遍历实现对文本中所有出现的黑名单库中的语句进行统计。
你应该这样认识AC自动机它首先是一颗字典树其次是它还有一个成员fail指针数组。
就如同他的名字一样这个自动机结构会根据输入的内容自动地调整内部的行为这就是它能以单次扫描就匹配全部文本的奥妙之处。 核心概念fail指针
作为一颗独特的字典树AC自动机还有fail指针数组。
作用
它的定义是trie_node* fail[i]
fail指针顾名思议它会在匹配失败时指向另一个可行的节点。
这个数组是干什么的你可以认为如果我们的匹配失败那么fail指针就会启动并跳转到一个具有和当前节点相同字符的节点上例如fail[5]存储了与5号节点具有相同字符的节点地址。
这样讲似乎很让人不能理解我们来看这张图 预先插入了以上敏感词字符串。如果我们要匹配的是“sher”如果进行朴素匹配那么我们只能得到“she”但我们知道有三个字符串“she”“he”“her”都在其中我们怎么才能只扫描一次就得到这些字符串呢fail指针做了这件事。
当我们匹配到字符r时发现无法继续此时fail指针发力了由于位于5号节点而fail[5]-8号节点的地址所以我们可以跳转到8号节点继续匹配。 这样一来“she”“he”“her”就全部匹配上了。
下面我们来说说fail指针是怎么构建的。
构建
有三条原则
1.root节点的fail指针指向自己此后按层遍历进行各个层次的fail指针的构建。
2.如果某节点A的fail指针指向另一非root节点B那么A的字符与B的字符是相同的。如fail[5]-8号节点。
3.如果当前节点child1的父节点father1的fail指针指向另一节点father2而father2名下恰好有与child1同字符的child2那么fail[child1]-child2如果没有同字符的child2那么fail[child1]-root。
我们重点解释第三条这是为了保证我们的匹配是有效的
如果fail[father1]-father2那么father1与father2是相同字符节点那么可以保证从child1通过fail指针跳转到child2时他们前面匹配过得一部分字符串即father1和father2是相同的这样一来可以保证在我们进行文本匹配时不会出现3号节点跳转到6号节点看上图的现象。
*注意*也有child1跳转到child2时不存在前面匹配过的一部分字符串即child1的字符可能是某个敏感词的首字符这时候跳转到root进行匹配即第三条规则的最后一句话。
图示
我们希望你结合以上三条规则在图上画出全部fail指针在此我们给出答案 Code
node-idx代表节点编号它同时担任了fail指针数组下标的功能。
std::vector trie_node* fail;
void bulid_fail() {fail.resize(val_size,root);std::queuetrie_node*que;que.push(root);while (!que.empty()) {int len que.size();while (len--) {trie_node* node que.front(); que.pop();for (int i 0; i branches; i) {trie_node* father node;trie_node* child node-next[i];if (child ! nullptr) {que.push(child);if (fail[father-idx]-next[i] ! nullptrfail[father-idx]-next[i]!child)fail[child-idx] fail[father-idx]-next[i];}}}}//int i 0;//for (const trie_node* node : fail)std::cout i - node-idx std::endl;
}
接下来我们封装AC_automaton类实现AC自动机的基本功能。Code和测试案例附后 成员变量
ac自动机以私有方式继承trie树并封装std::vector trie_node* fail指针。
class AC_automaton:private trie{
private:std::vector trie_node* fail;...
public:...}
}; 创建销毁
提供三种构造一种析构函数。
这些内容均于「字符串」详解Trie字典树|前缀树并实现对应的功能 / 手撕数据结构C中提及。
我们删除了复制构造和复制赋值等于号以防止两份AC自动机的fail指针指向同一组地址。
AC_automaton(int branch 128) :trie(branch), fail(1, root) {};
AC_automaton(const trie data) :trie(data), fail(1,root) {bulid_fail();
};
AC_automaton(const AC_automaton another) delete;
AC_automaton(const std::initializer_liststd::string ini_list) :trie(ini_list), fail(1, root) {bulid_fail();
}
~AC_automaton() {};
AC_automaton operator(const AC_automaton another) delete; 添加词库
提供insert_blackedlist与它的重载支持单条语句和多语句插入。
随后调用build_fail重建fail指针。
void insert_blacklist(const std::string str) {trie::insert(str);bulid_fail();
}
void insert_blacklist(const std::vectorstd::string strs) {trie::insert(strs);bulid_fail();
} 文本扫描
文本扫描是AC自动机的另一个核心部分它是fail指针的具体应用。
初始化指针p指向根节点。text为待扫描文本。
对于这个流程我们总结为以下几点
1.当p指向根节点并且黑名单字符串库不存在当前text[i]开头的字符那么跳过当前字符。
2.当p指针指向的节点储存了str黑名单字符串将其加入统计结果。
3.当p指针无法继续向下匹配启动fail指针前往fail[p-idx]p-idx表示当前节点的序号fail[p-idx]存储当前节点的跳转位置
*注意*因为跳转后的节点字符与跳转前的节点字符相同此时请不要向后移动text文本字符即不要进行i操作这会导致匹配错位。
4.脱离循环后将p位置可能存在的字符串加入统计结果以及p位置的fail指针指向的节点也可能有字符串他们都需要加入统计结果。这是由于p抵达最后一个字符时循环已经结束并且fail指针有着p的相同前缀以及相同字符他们都有可能成为统计结果。
std::vectorstd::string query(std::string text) {std::vectorstd::string ans;trie_node* p root;const int len text.size();for (int i 0; i len;) {if (p root p-next[text[i]] nullptr)i;if (p-str.empty()false)ans.push_back(p-str);if (p-next[text[i]] ! nullptr)p p-next[text[i]];else p fail[p-idx];}if (p-str.empty() false)ans.push_back(p-str);if(fail[p-idx]-str.empty()false); ans.push_back(fail[p-idx]-str);return ans;
} 复杂度 时间复杂度插入O(n*m) 扫描O(m) 空间复杂度插入O(n*m) 扫描O(1) n插入字符串数目 m插入/待扫描字符串长度 Code
#include queue
#include trie.h
#ifndef AC_AUTOMATON
#define AC_AUTOMATON
class AC_automaton:private trie{
private:std::vector trie_node* fail;void bulid_fail() {fail.resize(val_size,root);std::queuetrie_node*que;que.push(root);while (!que.empty()) {int len que.size();while (len--) {trie_node* node que.front(); que.pop();for (int i 0; i branches; i) {trie_node* father node;trie_node* child node-next[i];if (child ! nullptr) {que.push(child);if (fail[father-idx]-next[i] ! nullptrfail[father-idx]-next[i]!child)fail[child-idx] fail[father-idx]-next[i];}}}}//int i 0;//for (const trie_node* node : fail)std::cout i - node-idx std::endl;}
public:AC_automaton(int branch 128) :trie(branch), fail(1, root) {};AC_automaton(const trie data) :trie(data), fail(1,root) {bulid_fail();};AC_automaton(const AC_automaton another) delete;AC_automaton(const std::initializer_liststd::string ini_list) :trie(ini_list), fail(1, root) {bulid_fail();}~AC_automaton() {};AC_automaton operator(const AC_automaton another) delete;void insert_blacklist(const std::string str) {trie::insert(str);bulid_fail();}void insert_blacklist(const std::vectorstd::string strs) {trie::insert(strs);bulid_fail();}std::vectorstd::string query(std::string text) {std::vectorstd::string ans;trie_node* p root;const int len text.size();for (int i 0; i len;) {if (p root p-next[text[i]] nullptr)i;if (p-str.empty()false)ans.push_back(p-str);if (p-next[text[i]] ! nullptr)p p-next[text[i]];else p fail[p-idx];}if (p-str.empty() false)ans.push_back(p-str);if(fail[p-idx]-str.empty()false); ans.push_back(fail[p-idx]-str);return ans;}
};
#endif
测试
#include iostream
#include AC_automaton.h
using namespace std;
int AC_automaton_test() {AC_automaton ACA { say,she,shy,he,her,hee,ee};vectorstring ans ACA.query(sherhee);cout -----------------test----------------- endl;for (const string str : ans)cout str endl;;return 0;
}
