- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章java编程之AC自动机工作原理与实现代码由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.
在阅读本文之前,大家可以先参考下《多模字符串匹配算法原理及java实现代码》 。
简介:
本文是博主自身对ac自动机的原理的一些理解和看法,主要以举例的方式讲解,同时又配以相应的图片。代码实现部分也予以明确的注释,希望给大家不一样的感受。ac自动机主要用于多模式字符串的匹配,本质上是kmp算法的树形扩展。这篇文章主要介绍ac自动机的工作原理,并在此基础上用java代码实现一个简易的ac自动机.
1.应用场景—多模字符串匹配 。
我们现在考虑这样一个问题,在一个文本串text中,我们想找出多个目标字符串target1,target2,……出现的次数和位置。例如:求出目标字符串集合{"nihao","hao","hs","hsr"}在给定文本"sdmfhsgnshejfgnihaofhsrnihao"中所有可能出现的位置。解决这个问题,我们一般的办法就是在文本串中对每个目标字符串单独查找,并记录下每次出现的位置。显然这样的方式能够解决问题,但是在文本串较大、目标字符串众多的时候效率比较低。为了提高效率,贝尔实验室于1975年发明著名的多模字符串匹配算法——ac自动机。ac自动机在实现上要依托于trie树(也称字典树)并借鉴了kmp模式匹配算法的核心思想。实际上你可以把kmp算法看成每个节点都仅有一个孩子节点的ac自动机.
ac自动机用于多模匹配,所谓多模匹配,就是给定一个带匹配的字符串string,给定一个字典dictionary,dictionary中有多个字符串{ str1,str2, str3 … } 多模匹配就是要得到string字符串中出现了dictionary的哪些字符,且这些字符出现在了string中的哪个位置.
2.ac自动机及其运行原理 。
2.1初识ac自动机 。
ac自动机的基础是trie树。和trie树不同的是,树中的每个结点除了有指向孩子的指针(或者说引用),还有一个fail指针,它表示输入的字符与当前结点的所有孩子结点都不匹配时(注意,不是和该结点本身不匹配),自动机的状态应转移到的状态(或者说应该转移到的结点)。fail指针的功能可以类比于kmp算法中next数组的功能.
我们现在来看一个用目标字符串集合{abd,abdk,abchijn,chnit,ijabdf,ijaij}构造出来的ac自动机 。
上图是一个构建好的ac自动机,其中根结点不存储任何字符,根结点的fail指针为null。虚线表示该结点的fail指针的指向,所有表示字符串的最后一个字符的结点外部都用红圈表示,我们称该结点为这个字符串的终结结点。每个结点实际上都有fail指针,但为了表示方便,本文约定一个原则,即所有指向根结点的fail虚线都未画出.
从上图中的ac自动机,我们可以看出一个重要的性质:每个结点的fail指针表示由根结点到该结点所组成的字符序列的所有后缀和整个目标字符串集合(也就是整个trie树)中的所有前缀两者中最长公共的部分.
比如图中,由根结点到目标字符串“ijabdf”中的‘d'组成的字符序列“ijabd”的所有后缀在整个目标字符串集{abd,abdk,abchijn,chnit,ijabdf,ijaij}的所有前缀中最长公共的部分就是abd,而图中d结点(字符串“ijabdf”中的这个d)的fail正是指向了字符序列abd的最后一个字符.
2.2ac自动机的运行过程:
1)表示当前结点的指针指向ac自动机的根结点,即curr=root 。
2)从文本串中读取(下)一个字符 。
3)从当前结点的所有孩子结点中寻找与该字符匹配的结点, 。
若成功:判断当前结点以及当前结点fail指向的结点是否表示一个字符串的结束,若是,则将文本串中索引起点记录在对应字符串保存结果集合中(索引起点=当前索引-字符串长度+1)。curr指向该孩子结点,继续执行第2步 。
若失败:执行第4步.
4)若fail==null(说明目标字符串中没有任何字符串是输入字符串的前缀,相当于重启状态机)curr=root,执行步骤2, 。
否则,将当前结点的指针指向fail结点,执行步骤3) 。
现在,我们来一个具体的例子加深理解,初始时当前结点为root结点,我们现在假设文本串text=“abchnijabdfk”.
图中的实曲线表示了整个搜索过程中的当前结点指针的转移过程,结点旁的文字表示了当前结点下读取的文本串字符。比如初始时,当前指针指向根结点时,输入字符‘a',则当前指针指向结点a,此时再输入字符‘b',自动机状态转移到结点b,……,以此类推。图中ac自动机的最后状态只是恰好回到根结点.
需要说明的是,当指针位于结点b(图中曲线经过了两次b,这里指第二次的b,即目标字符串“ijabdf”中的b),这时读取文本串字符下标为9的字符(即‘d')时,由于b的所有孩子结点(这里恰好只有一个孩子结点)中存在能够匹配输入字符d的结点,那么当前结点指针就指向了结点d,而此时该结点d的fail指针指向的结点又恰好表示了字符串“abc”的终结结点(用红圈表示),所以我们找到了目标字符串“abc”一次。这个过程我们在图中用虚线表示,但状态没有转移到“abd”中的d结点.
在输入完所有文本串字符后,我们在文本串中找到了目标字符串集合中的abd一次,位于文本串中下标为7的位置;目标字符串ijabdf一次,位于文本串中下标为5的位置.
3.构造ac自动机的方法与原理 。
3.1构造的基本方法 。
首先我们将所有的目标字符串插入到trie树中,然后通过广度优先遍历为每个结点的所有孩子节点的fail指针找到正确的指向.
确定fail指针指向的问题和kmp算法中构造next数组的方式如出一辙。具体方法如下 。
1)将根结点的所有孩子结点的fail指向根结点,然后将根结点的所有孩子结点依次入列.
2)若队列不为空:
2.1)出列,我们将出列的结点记为curr,failto表示curr的fail指向的结点,即failto=curr.fail 。
2.2)a.判断curr.child[i]==failto.child[i]是否成立, 。
成立:curr.child[i].fail=failto.child[i], 。
不成立:判断failto==null是否成立 。
成立:curr.child[i].fail==root 。
不成立:执行failto=failto.fail,继续执行2.2) 。
b.curr.child[i]入列,再次执行再次执行步骤2) 。
若队列为空:结束 。
3.2通过一个例子来理解构造ac自动机的原理 。
每个结点fail指向的解决顺序是按照广度优先遍历的顺序完成的,或者说层序遍历的顺序进行的,也就是说我们是在解决当前结点的孩子结点fail的指向时,当前结点的fail指针一定已指向了正确的位置.
为了说明问题,我们再次强调“每个结点的fail指针表示:由根结点到该结点所组成的字符序列的所有后缀和整个目标字符串集合(也就是整个trie树)中的所有前缀两者中最长公共的部分”.
以上图所示为例,我们要解决结点x1的某个孩子结点y的fail的指向问题。已知x1.fail指向x2,依据x1结点的fail指针的含义,我们可知红色实线椭圆框内的字符序列必然相等,且表示了最长公共部分。依据y.fail的含义,如果x2的某个孩子结点和结点y表示的字符相等,那么y.fail就该指向它.
如果x2的孩子结点中不存在结点y表示的字符,这个时候该怎么办?由于x2.fail指向x3,根据x2.fail的含义,我们可知绿色方框内的字符序列必然相等。显然,如果x3的某个孩子结点和结点y表示的字符相等,那么y.fail就该指向它.
如果x3的孩子结点中不存在结点y表示的字符,我们可以依次重复这个步骤,直到xi结点的fail指向null,这时说明我们已经到了最顶层的根结点,这时,我们只需要让y.fail=root即可.
构造的过程的核心本质就是,已知当前结点的最长公共前缀的前提下,去确定孩子结点的最长公共前缀。这完全可以类比于kmp算法的next数组的求解过程.
3.2.1确定图中h结点fail指向的过程 。
现在我们假设我们要确定图中结点c的孩子结点h的fail指向。图中每个结点都应该有表示fail的虚线,但为了表示方便,按照本文约定的原则,所有指向根结点的fail虚线均未画出.
左图表示h.fail确定之前, 右图表示h.fail确定之后 。
左图中,蓝色实线框住的结点的fail都已确定。现在我们应该怎样找到h.fail的正确指向?由于且结点c的fail已知(c结点为h结点的父结点),且指向了trie树中所有前缀与字符序列‘a'‘b'‘c'的所有后缀(“bc”和“c”)的最长公共部分。现在我们要解决的问题是目标字符串集合的所有前缀中与字符序列‘a'‘b'‘c'‘h'的所有后缀的最长公共部分。显然c.fail指向的结点的孩子结点中存在结点h,那么h.fail就应该指向c.fail的孩子结点h,所以右图表示了h.fail确定后的情况.
3.2.2确定图中i.fail指向的过程 。
左图表示i.fail确定之前, 右图表示i.fail确定之后 。
确定i.fail的指向时,显然h.fail(h指图中i的父结点的那个h)已指向了正确的位置。也就是说我们现在知道了目标字符串集合所有前缀中与字符序列‘a'‘b'‘c'‘h'的所有后缀在trie树中的最长前缀是‘c'‘h'。显然从图中可知h.fail的孩子结点是没有i结点(这里h.fail只有一个孩子结点n)。字符序列‘c'‘h'的所有后缀在trie树中的最长前缀可由h.fail的fail得到,而h.fail的fail指向root(依据本博客中画图的原则,这条fail虚线并未画出),root的孩子结点中存在表示字符i的结点,所以结果如右图所示.
在知道i.fail的情况下,大家可以尝试在纸上画出j.fail的指向,以加深ac自动机构造过程的理解.
4.ac自动机的java代码实现 。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
package
datastruct;
import
java.util.arraylist;
import
java.util.hashmap;
import
java.util.linkedlist;
import
java.util.list;
import
java.util.map.entry;
public
class
ahocorasickautomation {
/*本示例中的ac自动机只处理英文类型的字符串,所以数组的长度是128*/
private static final int ascii = 128;
/*ac自动机的根结点,根结点不存储任何字符信息*/
private node root;
/*待查找的目标字符串集合*/
private list<string> target;
/*表示在文本字符串中查找的结果,key表示目标字符串, value表示目标字符串在文本串出现的位置*/
private hashmap<string, list<integer>> result;
/*内部静态类,用于表示ac自动机的每个结点,在每个结点中我们并没有存储该结点对应的字符*/
private static class node{
/*如果该结点是一个终点,即,从根结点到此结点表示了一个目标字符串,则str != null, 且str就表示该字符串*/
string str;
/*ascii == 128, 所以这里相当于128叉树*/
node[] table = new node[ascii];
/*当前结点的孩子结点不能匹配文本串中的某个字符时,下一个应该查找的结点*/
node fail;
public boolean isword(){
return str != null;
}
}
/*target表示待查找的目标字符串集合*/
public ahocorasickautomation(list<string> target){
root = new node();
this.target = target;
buildtrietree();
build_ac_fromtrie();
}
/*由目标字符串构建trie树*/
private void buildtrietree(){
for (string targetstr : target){
node curr = root;
for (int i = 0; i < targetstr.length(); i++){
char ch = targetstr.charat(i);
if(curr.table[ch] == null){
curr.table[ch] = new node();
}
curr = curr.table[ch];
}
/*将每个目标字符串的最后一个字符对应的结点变成终点*/
curr.str = targetstr;
}
}
/*由trie树构建ac自动机,本质是一个自动机,相当于构建kmp算法的next数组*/
private void build_ac_fromtrie(){
/*广度优先遍历所使用的队列*/
linkedlist<node> queue = new linkedlist<node>();
/*单独处理根结点的所有孩子结点*/
for (node x : root.table){
if(x != null){
/*根结点的所有孩子结点的fail都指向根结点*/
x.fail = root;
queue.addlast(x);
/*所有根结点的孩子结点入列*/
}
}
while(!queue.isempty()){
/*确定出列结点的所有孩子结点的fail的指向*/
node p = queue.removefirst();
for (int i = 0; i < p.table.length; i++){
if(p.table[i] != null){
/*孩子结点入列*/
queue.addlast(p.table[i]);
/*从p.fail开始找起*/
node failto = p.fail;
while(true){
/*说明找到了根结点还没有找到*/
if(failto == null){
p.table[i].fail = root;
break;
}
/*说明有公共前缀*/
if(failto.table[i] != null){
p.table[i].fail = failto.table[i];
break;
} else{
/*继续向上寻找*/
failto = failto.fail;
}
}
}
}
}
}
/*在文本串中查找所有的目标字符串*/
public hashmap<string, list<integer>> find(string text){
/*创建一个表示存储结果的对象*/
result = new hashmap<string, list<integer>>();
for (string s : target){
result.put(s, new linkedlist<integer>());
}
node curr = root;
int i = 0;
while(i < text.length()){
/*文本串中的字符*/
char ch = text.charat(i);
/*文本串中的字符和ac自动机中的字符进行比较*/
if(curr.table[ch] != null){
/*若相等,自动机进入下一状态*/
curr = curr.table[ch];
if(curr.isword()){
result.get(curr.str).add(i - curr.str.length()+1);
}
/*这里很容易被忽视,因为一个目标串的中间某部分字符串可能正好包含另一个目标字符串,
* 即使当前结点不表示一个目标字符串的终点,但到当前结点为止可能恰好包含了一个字符串*/
if(curr.fail != null && curr.fail.isword()){
result.get(curr.fail.str).add(i - curr.fail.str.length()+1);
}
/*索引自增,指向下一个文本串中的字符*/
i++;
} else{
/*若不等,找到下一个应该比较的状态*/
curr = curr.fail;
/*到根结点还未找到,说明文本串中以ch作为结束的字符片段不是任何目标字符串的前缀,
* 状态机重置,比较下一个字符*/
if
(curr ==
null
){
curr = root;
i++;
}
}
}
return
result;
}
public
static
void
main(string[] args){
list<string> target =
new
arraylist<string>();
target.add(
"abcdef"
);
target.add(
"abhab"
);
target.add(
"bcd"
);
target.add(
"cde"
);
target.add(
"cdfkcdf"
);
string text =
"bcabcdebcedfabcdefababkabhabk"
;
ahocorasickautomation aca =
new
ahocorasickautomation(target);
hashmap<string, list<integer>> result = aca.find(text);
system.out.println(text);
for
(entry<string, list<integer>> entry : result.entryset()){
system.out.println(entry.getkey()+
" : "
+ entry.getvalue());
}
}
}
|
运行结果如下,从结果中我们可以看出文本串中bcd出现了二次,分别是文本串下标为3和下标为13的位置,…….
1
2
3
4
5
6
|
bcabcdebcedfabcdefababkabhabk
bcd : [
3
,
13
]
cdfkcdf : []
cde : [
4
,
14
]
abcdef : [
12
]
abhab : [
23
]
|
总结 。
以上就是本文关于java编程之ac自动机工作原理与实现代码的全部内容,希望对大家有所帮助。如有不足之处,欢迎留言指出.
原文链接:http://www.cnblogs.com/nullzx/p/7499397.html 。
最后此篇关于java编程之AC自动机工作原理与实现代码的文章就讲到这里了,如果你想了解更多关于java编程之AC自动机工作原理与实现代码的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我尝试理解[c代码 -> 汇编]代码 void node::Check( data & _data1, vector& _data2) { -> push ebp -> mov ebp,esp ->
我需要在当前表单(代码)的上下文中运行文本文件中的代码。其中一项要求是让代码创建新控件并将其添加到当前窗体。 例如,在Form1.cs中: using System.Windows.Forms; ..
我有此 C++ 代码并将其转换为 C# (.net Framework 4) 代码。有没有人给我一些关于 malloc、free 和 sprintf 方法的提示? int monate = ee; d
我的网络服务器代码有问题 #include #include #include #include #include #include #include int
给定以下 html 代码,将列表中的第三个元素(即“美丽”一词)以斜体显示的 CSS 代码是什么?当然,我可以给这个元素一个 id 或一个 class,但 html 代码必须保持不变。谢谢
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 我们不允许提问寻求书籍、工具、软件库等的推荐。您可以编辑问题,以便用事实和引用来回答。 关闭 7 年前。
我试图制作一个宏来避免重复代码和注释。 我试过这个: #define GrowOnPage(any Page, any Component) Component.Width := Page.Surfa
我正在尝试将我的旧 C++ 代码“翻译”成头条新闻所暗示的 C# 代码。问题是我是 C# 中的新手,并不是所有的东西都像 C++ 中那样。在 C++ 中这些解决方案运行良好,但在 C# 中只是不能。我
在 Windows 10 上工作,R 语言的格式化程序似乎没有在 Visual Studio Code 中完成它的工作。我试过R support for Visual Studio Code和 R-T
我正在处理一些报告(计数),我必须获取不同参数的计数。非常简单但乏味。 一个参数的示例查询: qCountsEmployee = ( "select count(*) from %s wher
最近几天我尝试从 d00m 调试网络错误。我开始用尽想法/线索,我希望其他 SO 用户拥有可能有用的宝贵经验。我希望能够提供所有相关信息,但我个人无法控制服务器环境。 整个事情始于用户注意到我们应用程
我有一个 app.js 文件,其中包含如下 dojo amd 模式代码: require(["dojo/dom", ..], function(dom){ dom.byId('someId').i
我对“-gencode”语句中的“code=sm_X”选项有点困惑。 一个例子:NVCC 编译器选项有什么作用 -gencode arch=compute_13,code=sm_13 嵌入库中? 只有
我为我的表格使用 X-editable 框架。 但是我有一些问题。 $(document).ready(function() { $('.access').editable({
我一直在通过本教程学习 flask/python http://blog.miguelgrinberg.com/post/the-flask-mega-tutorial-part-i-hello-wo
我想将 Vim 和 EMACS 用于 CNC、G 代码和 M 代码。 Vim 或 EMACS 是否有任何语法或模式来处理这种类型的代码? 最佳答案 一些快速搜索使我找到了 this vim 和 thi
关闭。这个问题不符合Stack Overflow guidelines .它目前不接受答案。 想改进这个问题?更新问题,使其成为 on-topic对于堆栈溢出。 7年前关闭。 Improve this
这个问题在这里已经有了答案: Enabling markdown highlighting in Vim (5 个回答) 6年前关闭。 当我在 Vim 中编辑包含 Markdown 代码的 READM
我正在 Swift3 iOS 中开发视频应用程序。基本上我必须将视频 Assets 和音频与淡入淡出效果合并为一个并将其保存到 iPhone 画廊。为此,我使用以下方法: private func d
pipeline { agent any stages { stage('Build') { steps { e
我是一名优秀的程序员,十分优秀!