-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathac.html
146 lines (124 loc) · 8.17 KB
/
ac.html
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
146
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" /><meta name="generator" content="Docutils 0.17.1: http://docutils.sourceforge.net/" />
<title>AC 自动机 — Feng's blog 1.0 documentation</title>
<link rel="stylesheet" type="text/css" href="_static/pygments.css" />
<link rel="stylesheet" type="text/css" href="_static/alabaster.css" />
<script data-url_root="./" id="documentation_options" src="_static/documentation_options.js"></script>
<script src="_static/jquery.js"></script>
<script src="_static/underscore.js"></script>
<script src="_static/doctools.js"></script>
<script src="_static/custom.js"></script>
<link rel="index" title="Index" href="genindex.html" />
<link rel="search" title="Search" href="search.html" />
<link rel="next" title="一次 tcpdump bpf filter “失效”的问题排查" href="tcpdump-bpf-filter-vlan-tagged-and-untagged-traffic.html" />
<link rel="prev" title="#1123 cloudflare 的四层代理架构" href="l4lb/1123.html" />
<link rel="stylesheet" href="_static/custom.css" type="text/css" />
<meta name="viewport" content="width=device-width, initial-scale=0.9, maximum-scale=0.9" />
</head><body>
<div class="document">
<div class="documentwrapper">
<div class="bodywrapper">
<div class="body" role="main">
<section id="ac-zi-dong-ji">
<h1>AC 自动机<a class="headerlink" href="#ac-zi-dong-ji" title="Permalink to this headline">¶</a></h1>
<ul class="simple">
<li><p>论文：<a class="reference external" href="https://dl.acm.org/doi/10.1145/360825.360855">https://dl.acm.org/doi/10.1145/360825.360855</a></p></li>
<li><p>实现：<a class="reference external" href="https://github.com/chanfung032/labs/blob/master/ac/ac.go">https://github.com/chanfung032/labs/blob/master/ac/ac.go</a></p></li>
</ul>
<section id="gai-shu">
<h2>概述<a class="headerlink" href="#gai-shu" title="Permalink to this headline">¶</a></h2>
<p>给定一堆关键字和一篇文档，AC 自动机可以在文档中快速查找出所有的关键字匹配。算法复杂度为 O(n)，n 为文档的长度。AC 自动机正式的名字叫 Aho-Corasick 算法，以算法发明人 Alfred V. Aho 和 Margaret J.Corasick 的名字命名。</p>
<p>AC 自动机的构建包含三个步骤： 构建前缀树、计算失配指针、计算后缀匹配项。</p>
<p>我们以 {say, she, shr, he, her} 为例，来看下 AC 自动机的构建和查找过程。</p>
</section>
<section id="gou-jian-qian-zhui-shu-trie">
<h2>构建前缀树 (Trie)<a class="headerlink" href="#gou-jian-qian-zhui-shu-trie" title="Permalink to this headline">¶</a></h2>
<p><a class="reference external" href="https://zh.wikipedia.org/wiki/Trie">https://zh.wikipedia.org/wiki/Trie</a></p>
<p>将关键词列表中的关键词逐个字符的加入前缀树。</p>
<img alt="_images/ac-trie.jpg" src="_images/ac-trie.jpg" />
<p>因为前缀树只能顺着某一个路径往下匹配，如果中途遇到不匹配的节点，只能回溯然后从根节点选择另外一个分支继续往下匹配。以处理字符串 sher 为例：首先，我们匹配了 she 子树，下一个字符 r 无法匹配，这时需要回溯到开始，然后从前缀树的根节点再选择 her 分支往下匹配。但是观察可以发现 her 的前缀 he 是 she 的一个后缀，she 匹配也就意味着 he 已经匹配，我们可以直接跳过 her 子树的 he 匹配，直接从 e 节点开始继续往下匹配，这个横向的跳转就是 <strong>失配指针</strong> 。</p>
<img alt="_images/ac-fail.jpg" src="_images/ac-fail.jpg" />
<p>AC 自动机构建的主要过程就是计算失配指针的过程。</p>
</section>
<section id="ji-suan-shi-pei-zhi-zhen">
<h2>计算失配指针<a class="headerlink" href="#ji-suan-shi-pei-zhi-zhen" title="Permalink to this headline">¶</a></h2>
<p>AC 自动机的前缀树的节点都存在失配指针，它表示从当前状态节点往下匹配失败后，我们应该跳转到哪个节点继续匹配。如上图中红色的箭头。</p>
<p>失配指针的计算过程如下：</p>
<ol class="arabic simple">
<li><p>第二层节点的失配指针为根节点。</p></li>
<li><p>从第三层开始对前缀树做宽度优先遍历。若当前处理到节点 x，从它的父节点开始沿着失配指针上溯直到根节点，如果中间遇到某个节点存在一个子节点，其字符和节点 x 的相同，那么就将节点 x 的失配指针指向这个子节点。否则失配指针为根节点。</p></li>
</ol>
<p>完全计算完成后失配指针如下图所示：</p>
<img alt="_images/ac-fail1.jpg" src="_images/ac-fail1.jpg" />
</section>
<section id="ji-suan-hou-zhui-pi-pei-xiang">
<h2>计算后缀匹配项<a class="headerlink" href="#ji-suan-hou-zhui-pi-pei-xiang" title="Permalink to this headline">¶</a></h2>
<p>我们看 she 字符串的匹配，当前缀树匹配到 e 这个节点的时候，代表匹配了 she 字符串，但其实 he 这个后缀也是匹配的。也就是说，对于前缀树上的每一个节点，我们除了判断节点本身是否是一个匹配项外，还需要判断其是否存在后缀匹配项。</p>
<p>后缀匹配项的计算方式如下：</p>
<p>宽度优先遍历所有节点，对于每一个节点 x，沿着其失配指针一直回溯直到根节点，中间遇到的节点如果是匹配节点（红色节点），那么这个节点代表的字符串就是节点 x 的一个后缀匹配项。实现中每个节点只需记录一个指向最长后缀匹配项节点的指针即可（下图中的蓝色箭头），查找的时候沿着这个指针上溯即可找到所有的后缀匹配项。</p>
<img alt="_images/ac-output.jpg" src="_images/ac-output.jpg" />
<hr class="docutils" />
<p>这个算法可以用来解答 <a class="reference external" href="https://leetcode-cn.com/problems/stream-of-characters/">Leet#1032 字符流</a> 问题。 <a class="reference external" href="https://github.com/chanfung032/labs/blob/master/Aho-Corasick/leet-1032.go">解答</a> 。</p>
</section>
</section>
</div>
</div>
</div>
<div class="sphinxsidebar" role="navigation" aria-label="main navigation">
<div class="sphinxsidebarwrapper">
<h3><a href="index.html">Table of Contents</a></h3>
<ul>
<li><a class="reference internal" href="#">AC 自动机</a><ul>
<li><a class="reference internal" href="#gai-shu">概述</a></li>
<li><a class="reference internal" href="#gou-jian-qian-zhui-shu-trie">构建前缀树 (Trie)</a></li>
<li><a class="reference internal" href="#ji-suan-shi-pei-zhi-zhen">计算失配指针</a></li>
<li><a class="reference internal" href="#ji-suan-hou-zhui-pi-pei-xiang">计算后缀匹配项</a></li>
</ul>
</li>
</ul>
<div role="note" aria-label="source link">
<h3>This Page</h3>
<ul class="this-page-menu">
<li><a href="_sources/ac.rst.txt"
rel="nofollow">Show Source</a></li>
</ul>
</div>
<div id="searchbox" style="display: none" role="search">
<h3 id="searchlabel">Quick search</h3>
<div class="searchformwrapper">
<form class="search" action="https://cn.bing.com/search" method="get">
<input type="text" name="q" aria-labelledby="searchlabel" autocomplete="off" autocorrect="off" autocapitalize="off" spellcheck="false"/>
<input type="submit" value="Go" />
</form>
</div>
</div>
<script>
$('#searchbox').show(0);
document.getElementsByClassName('search')[0].addEventListener('submit', function(event) {
event.preventDefault();
var form = event.target;
var input = form.querySelector('input[name="q"]');
var value = input.value;
var q = 'ensearch=1&q=site%3Achanfung032.github.io++' + value;
var url = form.action + '?' + q;
window.location.href = url;
});
</script>
</div>
</div>
<div class="clearer"></div>
</div>
<div class="footer">
©2017, chanfung032.
|
Powered by <a href="http://sphinx-doc.org/">Sphinx 4.1.2</a>
& <a href="https://github.com/bitprophet/alabaster">Alabaster 0.7.12</a>
|
<a href="_sources/ac.rst.txt"
rel="nofollow">Page source</a>
</div>
</body>
</html>