-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmin-gan-ci-xiang-mu-zhong-rou-xing-zi-fu-chuan-pi-pei-wen-ti.html
377 lines (334 loc) · 43.4 KB
/
min-gan-ci-xiang-mu-zhong-rou-xing-zi-fu-chuan-pi-pei-wen-ti.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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta http-equiv="Content-Type" content="text/html" charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
<title>敏感词项目中柔性字符串匹配问题</title>
<meta name="HandheldFriendly" content="True" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="referrer" content="origin" />
<meta name="generator" content="Pelican" />
<link href="/" rel="canonical" />
<!-- Feed -->
<link href="/theme/css/style.css" type="text/css" rel="stylesheet" />
<!-- Code highlight color scheme -->
<link href="/theme/css/code_blocks/github.css" rel="stylesheet">
<!-- Custom fonts -->
<link href='https://fonts.googleapis.com/css?family=Montserrat:400,300' rel='stylesheet' type='text/css' />
<link href="https://fonts.googleapis.com/css?family=Lato" rel="stylesheet" type="text/css" />
<!-- HTML5 Shim and Respond.js IE8 support of HTML5 elements and media queries -->
<!-- WARNING: Respond.js doesn't work if you view the page via file:// -->
<!--[if lt IE 9]>
<script src="https://oss.maxcdn.com/libs/html5shiv/3.7.0/html5shiv.js"></script>
<script src="https://oss.maxcdn.com/libs/respond.js/1.4.2/respond.min.js"></script>
<![endif]-->
<link href="/min-gan-ci-xiang-mu-zhong-rou-xing-zi-fu-chuan-pi-pei-wen-ti.html" rel="canonical" />
<meta name="description" content="背景问题 在给定文本中排查一个固定字符串并不是一件很难的事情，但是倘若给定的字符串库十分庞大，以及涉及到多种字词组合的时候，性能和效率都成了不得不考虑的问题。对此，算法团队做了一些系统的工作，并将其用于对果壳网现有敏感词项目的改进。...">
<meta name="author" content="小熊猫">
<!-- Open Graph -->
<meta property="og:site_name" content="果壳网平台组博客"/>
<meta property="og:title" content="敏感词项目中柔性字符串匹配问题"/>
<meta property="og:description" content="背景问题 在给定文本中排查一个固定字符串并不是一件很难的事情，但是倘若给定的字符串库十分庞大，以及涉及到多种字词组合的时候，性能和效率都成了不得不考虑的问题。对此，算法团队做了一些系统的工作，并将其用于对果壳网现有敏感词项目的改进。..."/>
<meta property="og:locale" content="en_US"/>
<meta property="og:url" content="/min-gan-ci-xiang-mu-zhong-rou-xing-zi-fu-chuan-pi-pei-wen-ti.html"/>
<meta property="og:type" content="article"/>
<meta property="article:published_time" content="2015-10-09 10:20:00+08:00"/>
<meta property="article:modified_time" content=""/>
<meta property="article:author" content="/author/xiao-xiong-mao.html">
<meta property="article:section" content="算法"/>
<meta property="og:image" content="/https://3-im.guokr.com/AmjuedrC2_wytXS5i0Le-rywoYVFGOCxcMJ0BkMAVC3oAwAAKwEAAEpQ.jpg">
<!-- Twitter Card -->
<script type="application/ld+json">
{
"@context": "http://schema.org",
"@type": "Article",
"name": "敏感词项目中柔性字符串匹配问题",
"headline": "敏感词项目中柔性字符串匹配问题",
"datePublished": "2015-10-09 10:20:00+08:00",
"dateModified": "",
"author": {
"@type": "Person",
"name": "小熊猫",
"url": "/author/xiao-xiong-mao.html"
},
"image": "/https://3-im.guokr.com/AmjuedrC2_wytXS5i0Le-rywoYVFGOCxcMJ0BkMAVC3oAwAAKwEAAEpQ.jpg",
"url": "/min-gan-ci-xiang-mu-zhong-rou-xing-zi-fu-chuan-pi-pei-wen-ti.html",
"description": "背景问题 在给定文本中排查一个固定字符串并不是一件很难的事情，但是倘若给定的字符串库十分庞大，以及涉及到多种字词组合的时候，性能和效率都成了不得不考虑的问题。对此，算法团队做了一些系统的工作，并将其用于对果壳网现有敏感词项目的改进。..."
}
</script>
</head>
<!-- TODO : Body class -->
<body class="home-template">
<nav id="menu">
<a class="close-button">Close</a>
<div class="nav-wrapper">
<p class="nav-label">Menu</p>
<ul>
<li role="presentation"><a href="/pages/guan-yu-wo-men.html">关于我们</a></li>
</ul>
</div>
</nav>
<!-- Progressbar -->
<div class="progress-container">
<span class="progress-bar"></span>
</div>
<!-- Page Header -->
<!-- Set your background image for this header on the line below. -->
<header id="post-header" class="has-cover">
<div class="inner">
<nav id="navigation">
<span id="home-button" class="nav-button">
<a class="home-button" href="/" title="Home"><i class="ic ic-arrow-left"></i> Home</a>
</span>
<span id="menu-button" class="nav-button">
<a class="menu-button"><i class="ic ic-menu"></i> Menu</a>
</span>
</nav>
<h1 class="post-title">敏感词项目中柔性字符串匹配问题</h1>
<!-- TODO : Proper class for headline -->
<span class="post-meta">
<a href="/author/xiao-xiong-mao.html">小熊猫</a>
| <time datetime="Fri 09 October 2015">Fri 09 October 2015</time>
</span>
<!-- TODO : Modified check -->
<div class="post-cover cover" style="background-image: url('https://3-im.guokr.com/AmjuedrC2_wytXS5i0Le-rywoYVFGOCxcMJ0BkMAVC3oAwAAKwEAAEpQ.jpg')">
</div>
</header>
<section id="wrapper">
<a class="hidden-close"></a>
<!-- Post content -->
<main class="content" role="main">
<article class="post">
<div class="inner">
<section class="post-content">
<h2>背景问题</h2>
<p>在给定文本中排查一个固定字符串并不是一件很难的事情，但是倘若给定的字符串库十分庞大，以及涉及到多种字词组合的时候，性能和效率都成了不得不考虑的问题。对此，算法团队做了一些系统的工作，并将其用于对果壳网现有敏感词项目的改进。</p>
<p>敏感词的排查是所有社交网络都会面临的一个任务，对于固定的字符串，直观的想法可以是从列表中挨个取出所有的敏感词，再将它们与全文做一一比对，这样的思路虽然可行，但是在面对不断扩大的敏感词列表，既丑陋又笨拙。除此之外，线上还有一些动名词组合的情况需要考虑，即动词和名词分别可以出现，但是当它们以一种可以被识别的形式出现，并传达确定意义的时候，那就理应得到屏蔽。</p>
<p>对于固定的字符串，如何最快速地将它们全部抓出来；对于动名词组合，如何在做到不放过一条漏网之鱼的情况下尽量避免误伤，都是亟待解决的问题。</p>
<p>对于固定的敏感词匹配，可以粗略地为字符串匹配问题，不过在正式解决之前，我们先来对这个问题再次做个定义。</p>
<h2>对问题的重定义</h2>
<p>一个字符串是一个定义在有限字母集合 <span class="math">\(\sum\)</span> 上的字符序列。例如 <span class="math">\(ABCDABC\)</span> 就是字母表 <span class="math">\(\sum = \{A,B,C,D\}\)</span> 上的一个字符串。那么字符串匹配问题实际上就是在一个大的字符串 <span class="math">\(T\)</span> 中搜索某个特定的字符串 <span class="math">\(p\)</span> 出现的位置。为方便表述，在这里我们不妨把 <span class="math">\(T\)</span> 称作文本，<span class="math">\(p\)</span> 称作模式串，长度为 <span class="math">\(m\)</span>，以及 <span class="math">\(T\)</span> 和 <span class="math">\(p\)</span> 都定义在同一个字母表 <span class="math">\(\sum\)</span> 上。
对于单个的字符串问题，根据搜索模式串的方式的不同，一般来说可以归结为三种思路： </p>
<p><strong>基于前缀</strong>：从文本中挨个读字符，每读一个字符就更新相应的变量，检查是否存在一个可能的匹配。这种思路中最为典型的就是大名鼎鼎算法 KMP 以及后来居上的 Shift-Or。</p>
<p><strong>基于后缀</strong>：先设定一个滑动的窗口 <span class="math">\(W\)</span>，滑动窗口沿着文本 <span class="math">\(T\)</span> 移动，对于任意位置上的窗口，在窗口中从后向前搜索窗口中的文本和模式串 <span class="math">\(p\)</span> 的公共后缀。BM 算法 就是使用了这种思想，但是一般情况下，BM 的一个简化版本 Horspool 性能更好，同时也有着非常广泛的应用，通常我们的浏览器、编辑器中的搜索功能都是它的实现。</p>
<p><strong>基于子串</strong>：和第二种方法类似，这里也使用了滑动窗口的概念，也是从后向前搜索。有区别的地方是，搜索目标变成了是窗口中文本的最长后缀，显然它同时也是模式串 <span class="math">\(p\)</span> 的一个子串。最早使用这个思想的算法是 BDM，如果模式串 <span class="math">\(p\)</span> 稍短，可以将它改进为 BNDM。</p>
<p>鉴于基于前缀的搜索比较慢，以及基于子串的搜索方法只适合非常长的字符串，而这与我们的敏感词匹配要求并不复合，因此我们选择基于后缀的搜索方法。</p>
<p>前面提到这种基于后缀的搜索算法的基本思路是要设定一个滑动的窗口，然后让它沿着文本移动进行匹配，事实上这种方法最大的难点也就在于如何安全地移动窗口，以避免错过正确的匹配。</p>
<h2>Boyer-Moore 算法</h2>
<p>我们先设定三个移动窗口函数 <span class="math">\(d_1,d_2,d_3\)</span> 来用来分别对应后面提到的移动窗口时候面对的三种不同的情况。这里我们不妨假设已经读入了一个既是窗口中文本的后缀，也是模式串 <span class="math">\(p\)</span> 的子串的字符串 <span class="math">\(p_0\)</span>，以及恰好下面即将读入的文本中的字符串 <span class="math">\(\alpha\)</span> 与 <span class="math">\(p\)</span> 中的下一个字符 <span class="math">\(\beta\)</span> 不一样。</p>
<p>我们先来看第一种情况，后缀 <span class="math">\(p_0\)</span> 在模式串 <span class="math">\(p\)</span> 的多个位置有出现，假设最右出现的位置为 <span class="math">\(j\)</span>，这里不包括在模式串末尾的情况。此时我们已经匹配好的后缀 <span class="math">\(p_0 = p_{j-|p_0|+1}…p_j\)</span>，以及安全的移动方法是，将窗口往右移动 <span class="math">\(m-j\)</span> 个字符，才能使得文本中的 <span class="math">\(p_0\)</span> 与 <span class="math">\(p\)</span> 下一个 <span class="math">\(p_0\)</span> 的出现的位置对齐。对于 <span class="math">\(p\)</span> 的每一个后缀，都需要计算它到它下一次出现位置之间的距离，这个距离我们就用前面定义的窗口移动函数 <span class="math">\(d_1\)</span> 来表示。显然的一个特例是，如果 <span class="math">\(p_0\)</span> 在 <span class="math">\(p\)</span> 中只出现一次，那么此时 <span class="math">\(d_1(p_0) = m\)</span>。</p>
<p><img src="https://ws2.sinaimg.cn/large/006tKfTcgy1fjmbjjq2osj30ns07kt94.jpg"></p>
<p>再说第二种情况，此时后缀 <span class="math">\(p_0\)</span> 不出现 <span class="math">\(p\)</span> 中的其他位置。此时考虑情况如下图，即 <span class="math">\(p_0\)</span> 的一个后缀 <span class="math">\(p_0’\)</span> 同时也是 <span class="math">\(p\)</span> 的一个前缀。显然，在这种情况下，如果直接移动整个窗口的大小是很危险的动作，可能会错过正确的匹配。于是我们需要对模式串的所有后缀计算第二个函数 <span class="math">\(d_2\)</span>，即对于 <span class="math">\(p\)</span> 的每一个后缀 <span class="math">\(p_0, p_1,…p_i,…,p_n\)</span> 来说，<span class="math">\(p_i\)</span> 会存在一个 <span class="math">\(p_i’\)</span>，它是 <span class="math">\(p\)</span> 的前缀和 <span class="math">\(p_i\)</span> 的后缀的重合体中长度最长的那个。</p>
<p><img src="https://ws2.sinaimg.cn/large/006tKfTcgy1fjmbljlu7jj30nt07qwex.jpg"></p>
<p>最后再来说存在的第三种情况，当我们的搜索窗口从后向前移动时，在文本字符 <span class="math">\(\alpha\)</span> 处不能成功匹配。此时如果用第一种情况下的 <span class="math">\(d_1\)</span> 进行窗口移动，并且 <span class="math">\(p\)</span> 中对应的字符并不是 <span class="math">\(\alpha\)</span>，而是 <span class="math">\(\beta\)</span>，那么将会对新的搜索窗口多一次验证，这显然是冗余的。我们的第三种移动函数 <span class="math">\(d_3\)</span> 也就应运而生了。<span class="math">\(d_3\)</span> 可以用来保证下一次验证时文本字符 <span class="math">\(\alpha\)</span> 与 <span class="math">\(p\)</span> 中的 <span class="math">\(\alpha\)</span> 对齐。我们不妨将 <span class="math">\(d_3(\alpha\)</span>) 记作 <span class="math">\(\alpha\)</span> 在 <span class="math">\(p\)</span> 中最右的位置到末尾的距离。当然，倘若 <span class="math">\(\alpha\)</span> 在 <span class="math">\(p\)</span> 中并没有出现，那么 <span class="math">\(d_3(\alpha) = m\)</span>。 </p>
<p><img src="https://ws3.sinaimg.cn/large/006tKfTcgy1fjmbm1e2vij30ns085t97.jpg"> </p>
<p>有了这三种情况的拆分，BM 算法整体就相对好理解了。回到开始，即将读入的文本中的字符串 <span class="math">\(\alpha\)</span> 与 <span class="math">\(p\)</span> 中的下一个字符 <span class="math">\(\beta\)</span> 不一样，窗口移动的距离就由这三个函数来决定：</p>
<ul>
<li>比较 <span class="math">\(d_1(p_0\)</span>) 与 <span class="math">\(d_2(p_0’\)</span>)，将它们中较大的那一个用作窗口移动的距离，因为我们期望的是 <span class="math">\(p_0\)</span> 和它在 <span class="math">\(p\)</span> 中下一次出现的位置对齐；</li>
<li>取上面的结果，并与 <span class="math">\(m-d_2(p_0\)</span>) 来作比较，将它们中较小的用作窗口移动的距离，这是很显然的，因为 <span class="math">\(m-d_2(p_0\)</span>) 已经是最大可以接受的安全距离。</li>
</ul>
<p>BM 的搜索时间复杂是 <span class="math">\(O(mn\)</span>)，总的来说还算不错，但是比较麻烦的地方在于需要计算 <span class="math">\(d_1, d_2, d_3\)</span>，下面介绍它的一个简化版本，也是它应用最多的一个版本，Horspool。</p>
<h2>Horspool 算法</h2>
<p>Horspool 相对于 BM 最大的简化的地方是使用了一个统计上的经验，即，在面对字母表的 <span class="math">\(\sum\)</span> 较大的时候，<span class="math">\(d_3\)</span> 总是有很大概率产生最大的移动距离。基于此，我们不妨就让 <span class="math">\(d_3\)</span> 能够产生更大的移动距离。 不妨用下图来说明，对于每个移动的搜索窗口，Horspool 将窗口中文本字符串 <span class="math">\(T\)</span> 的最后一个字符（图中的 <span class="math">\(\theta\)</span>）和模式串 <span class="math">\(p\)</span> 的最后一个字符 <span class="math">\(p[-1]\)</span> 进行比较。如果它们相等，则需要进行验证。过程是首先在搜索窗口中从后向前对 <span class="math">\(T\)</span> 和 <span class="math">\(p\)</span> 进行比较，直到出现完全相等（匹配成功），或者第一个不匹配（图中 <span class="math">\(\alpha\)</span> 和 <span class="math">\(\beta\)</span>），然后，无论是否成功，窗口的下一个移动距离是依据 <span class="math">\(p\)</span> 中 <span class="math">\(\theta\)</span> 的位置： <img src="https://ws4.sinaimg.cn/large/006tKfTcgy1fjmbn8ft1xj30np0aggmb.jpg"> 下面对算法整体的流程简述：</p>
<ul>
<li>输入：模式串 <span class="math">\(p = p_1p_2…p_m\)</span>；目标文本 <span class="math">\(T = t_1t_2…t_n\)</span>；</li>
<li>输出：窗口指针位置 <span class="math">\(pos\)</span>；</li>
<li>步骤：<ol>
<li>数据预处理阶段，主要是做一些存储。对所有 <span class="math">\(c \in \sum\)</span>，有 <span class="math">\(d[c] \leftarrow m\)</span>；对所有 <span class="math">\(j \in 1,2,…,m-1\)</span>，有 <span class="math">\(d[p_j] \leftarrow m-j\)</span>；</li>
<li>搜索阶段。首先将当前位置 <span class="math">\(pos\)</span> 置为0，检查 <span class="math">\(pos \leqslant n-m\)</span>，倘若是，那么 <span class="math">\(j \leftarrow m\)</span>；然后去 3，如果否，跳转到 5；</li>
<li>检查 <span class="math">\(j>0\)</span> 且 <span class="math">\( t_{pos} == p_j\)</span>，倘若是，有 <span class="math">\(j \leftarrow j-1\)</span>，然后去 4；如果否，跳转到 5；</li>
<li>检查如果 <span class="math">\(j == 0\)</span>，然后记录下匹配位置 <span class="math">\(pos+1\)</span>，跳转到 5；</li>
<li>窗口位置移动，即当前位置的指针执行移动：<span class="math">\(pos \leftarrow pos+d[t_{pos+m}]\)</span>，后跳转 2；</li>
</ol>
</li>
</ul>
<h2>多字符串匹配</h2>
<p>回到开头，我们的问题其实是在一个给定的敏感词列表中进行排查，即表中的所有字符串都不能在文本中出现，即字符串集匹配，或者多字符串匹配问题。</p>
<p>其实单字符出匹配问题可以很自然地扩展到这样的多字符串匹配问题，<span class="math">\(P = \{p_1,p_2,…,p_r\}\)</span> 就是一组我们要搜索的字符串。在系统分析这个问题之前，我们先不妨做一些定义： <span class="math">\(p_i\)</span> 是定义在一个有限字母表 <span class="math">\(\sum\)</span> 上的字符串，<span class="math">\(p_i=p_{i1}p_{i2}...p_{im_i}\)</span>。记 <span class="math">\(|P|\)</span> 为 <span class="math">\(P\)</span> 中所有字符串长度之和，即 <span class="math">\(|P| = \sum_{i=1}^{r}|p^i|=\sum_{i=1}^{r}m_i\)</span>，同时 <span class="math">\(l_{min}\)</span> 和 <span class="math">\(l_{max}\)</span> 分别是 <span class="math">\(P\)</span> 中最短和最长模式串的长度，目标文本 <span class="math">\(T = t_1t_2…t_n\)</span>。</p>
<p>注意 <span class="math">\(P\)</span> 中的少数字符串可能是集合中其他字符串的前后缀，例如涉枪涉爆类别中既有「枪弩」也有「气枪弩」，也就是说如果「枪弩」被匹配成功，显然「气枪弩」也是会被匹配出来。因此，模式串总的出现次数最大可能为 <span class="math">\(rn\)</span>。那么我们真正的目标实际上是所有满足 <span class="math">\(p_i=t_{j-|p_i|+1}…t_j\)</span> 的整数对 <span class="math">\((i,j)\)</span>。</p>
<p>其实对于多字符串匹配的一个最简单的思路就是使用前面的单字符串匹配方法，遍历整个集合即可。但是这样会直接搜索的时间复杂度为 <span class="math">\(O(rn\)</span>)，以及还有数据预处理阶段的大量时间。显然这么做是笨拙的，也是低效的，我们下面对前面使用的单字符串匹配算法进行一定的扩展，以达到性能上的优化。</p>
<p>虽然单字符串匹配问题中的三种思路都是可以扩展，但是对于我们的问题后缀搜索效率最高，故将我们的主要工作重心放在基于后缀的字符串匹配问题的扩展上。
<img src="https://ws3.sinaimg.cn/large/006tKfTcgy1fjmbohn3pij30nt08zwez.jpg">
<h3 id="trie-tree">Trie Tree</h3></p>
<p>我们先介绍一种称之为前缀树的数据结构，或者叫字典树，trie tree，之所以要先介绍它首先是因为它能够帮助理解后面的推导与演算，还有一个重要的原因是前缀树在非常多的字符串问题中扮演了极其重要的角色。</p>
<p>那我们就这个项目举例来看，假设集合 <span class="math">\(P = \{p_1,p_2,…,p_r\}\)</span> 对应的前缀树结构其实是一棵有向的有根树，每个从根节点开始到叶子节点结束的路径上的所有标号构成的字符串，都对应着集合 <span class="math">\(P\)</span> 中的某一个元素 <span class="math">\(p_i\)</span>，反过来，集合 <span class="math">\(P\)</span> 中的每一个元素也都对应着前缀树中的一条从 root 到叶子节点的路径。对于前缀树来说，倘若一个结点 <span class="math">\(q\)</span> 对应这一个 <span class="math">\(P\)</span> 中的某个元素，那我们我们就将它称之为可以接受的状态，函数 <span class="math">\(F(q\)</span>) 包含了 <span class="math">\(q\)</span> 所对应的集合 <span class="math">\(P\)</span> 中的所有字符串。
下图就是一个简单例子，是 <span class="math">\(P = \{tee, tea, teacher\}\)</span> 所对应的 trie 结构。</p>
<p><img src="https://ws1.sinaimg.cn/large/006tKfTcgy1fjmbozxb0kj30l4063q37.jpg"></p>
<h3>自动机</h3>
<p>在计算机科学中，自动机这个词其实意义很多。我们下面单就字符串匹配领域来说说自动机，照例，我们先给出一些定义。</p>
<p>一个有限状态自动机 <span class="math">\(\mathcal{A}\)</span>，或者简称做自动机，一般是由五个元素组成：</p>
<ol>
<li>一个有限的状态集合 <span class="math">\(\mathcal{Q}\)</span></li>
<li>一个初始状态 <span class="math">\(\mathcal{s} \in \mathcal{Q}\)</span></li>
<li>一个输入字母表 <span class="math">\(\sum\)</span>（非空有限的状态集合）</li>
<li>一个可以被接受的状态的集合 <span class="math">\(\mathcal{F} \subseteq \mathcal{Q}\)</span></li>
<li>一个状态转移函数 <span class="math">\(\delta: \mathcal{Q} \times \sum \rightarrow \mathcal{Q}\)</span>（例如：<span class="math">\( \delta (q,\sigma) = p,(p,q \in \mathcal{Q}, \sigma\in\sum\)</span>）</li>
</ol>
<p>这样，自动机 <span class="math">\(\mathcal{A} = (\mathcal{Q}, \sum, \mathcal{s}, \mathcal{F}, \delta\)</span>) 就用这样的五元组来表示。</p>
<p>在实际应用中，根据状态转移函数的形式大抵可以分为两类：一类称之为非确定的有限自动机，它的状态转移函数 <span class="math">\(\delta\)</span> 将某一个状态 <span class="math">\(q\)</span> 通过一个给定字符 <span class="math">\(\sigma\)</span> 关联到多于1个的状态，即 </p>
<div class="math">$$\delta(q,\sigma) = \{q_1,q_2,…,q_k\}, k>1$$</div>
<p>
或者某些状态装一能被标记为 <span class="math">\(\varepsilon\)</span>。此时，我们的状态转移函数 <span class="math">\(\sigma\)</span> 就可以用三元组：
</p>
<div class="math">$$\Delta = \{(q,\sigma,q’)\}, q\in\mathcal{Q}, \sigma\in\sum,q’ \in \delta(q,\sigma)\}$$</div>
<p>
的集合来表示。另外一类则称之为确定的有限自动机，区别在于它的状态转移函数 <span class="math">\(\delta\)</span> 可以用一个部分函数 <span class="math">\(\delta：\mathcal{Q}\times\sum \rightarrow \mathcal{Q}\)</span> 来表示，如果 <span class="math">\(\delta(q,\sigma) = \{q’\}\)</span>，那么 <span class="math">\(\delta(q,\sigma) = q’\)</span>，下图给出了两个例子： </p>
<p><img src="https://ws3.sinaimg.cn/large/006tKfTcgy1fjmbsqsbapj30r60afjsj.jpg"></p>
<p>上图中给出了两种自动机的模型。其中 <span class="math">\(0\)</span> 是初始状态，灰色表示可以被接受的终止状态。左边的是非确定性的自动机，因为从状态 <span class="math">\(0\)</span> 通过 <span class="math">\(d\)</span> 或者 <span class="math">\(d\rightarrow a\rightarrow b\)</span> 到达状态 <span class="math">\(6\)</span>，即便是只通过 <span class="math">\(d\)</span> 的话，也可以达到 <span class="math">\(6\)</span> 或者 <span class="math">\(2\)</span>。而右图则是确定性的自动机，因为对于任何一个字符，每个状态都只能转移到一个状态。</p>
<p>那么在这个自动机 <span class="math">\(\mathcal{A} = (\mathcal{Q}, \sum, \mathcal{s}, \mathcal{F}, \delta\)</span>) 中，如果将从状态 <span class="math">\(s\)</span> 到一个可以被接受的状态路径上的标记连起来可以得到的字符串则可以被自动机 <span class="math">\(\mathcal{A}\)</span> 识别。</p>
<p>注意，在非确定的有限状态机中，是允许状态转移上被标记为空串的，我们将这样的状态转移称之为 <span class="math">\(\varepsilon\)</span>-转移。这就意味着不必要读入一个字符也可完成一次状态转移。那么如果到达了一个 <span class="math">\(\varepsilon\)</span>转移的原状态，那么不用读取就可以立即完成跳转，这样也是可以看做是读入了一个空串。事实上，<span class="math">\(\varepsilon\)</span> 转移通常用来简化这种非确定的有限状态自己懂的构造，但是总是存在一个与之等价的不含 <span class="math">\(\varepsilon\)</span> 转移的自动机。</p>
<p>但是总而言之，不管是在确定性还是非确定性的有限状态自动机中，如果将从 <span class="math">\(s\)</span> 到某一个状态的 <span class="math">\(s_0\)</span> 的路径上标记穿起来可以得到字符串 <span class="math">\(x\)</span>，那么就说，读入 <span class="math">\(x\)</span> 后的状态 <span class="math">\(s_0\)</span> 是一个活动状态。在任何时候，确定性的有限状态自动机中，最多只有一个活动状态，而非确定性的则可能存在多个。</p>
<p>上图表示两个自动机中的状态转移不会构成环，这样的自动机不论确定性与否，都被称之为无环的下图两个的自动机则是有环的，一个有环的自动机可以接受的状态集合可能是无限的。</p>
<p><img src="https://ws1.sinaimg.cn/large/006tKfTcgy1fjmbt2tl77j30r50a70u2.jpg"></p>
<p>例如上图中的有环自动机，左图可以识别 <span class="math">\(P=\{dab\}\)</span>, 也可以识别 <span class="math">\(P=\{dab, dabaab, dabaabaab,…\}\)</span>。</p>
<h2>基于后缀的多字符串匹配</h2>
<p>穿插着了解了前缀树和自动机之后，我们回到上文继续讨论基于后缀的多字符串匹配问题，我们这里主要的思想是对使用后缀匹配思想单字符串的匹配算法的扩展。这样的第一个算法对 BM 的扩展， Commentz-Walter，当然也有对 Hospool 的扩展，下面我们逐一讨论。</p>
<h3>Commentz-Walter</h3>
<p>Commentz-Walter（以下简称 CW 算法） 算法是对 BM 算法的扩展，它的应用非常广泛，例如 UNIX 下的非常著名的搜索程序 Grep 的第二个版本就是它的一个实现。</p>
<p>CW 算法中用前缀树来表示 <span class="math">\(P=\{p_1,p_2,…,p_r\}\)</span> 的反转 <span class="math">\(P_{rv}=\{p_{1,rv},p_{2,rv},…,p_{r,rv}\}\)</span>，并用它来识别文本字符。由于这个算法性能差强人意，我们简单说说思想。在窗口移动过程中，指针 <span class="math">\(pos\)</span> 指向 <span class="math">\(l_{min}\)</span>，对于 <span class="math">\(pos\)</span> 的每个新位置，从 <span class="math">\(pos\)</span> 开始，从后向前识别文本 <span class="math">\(t_1t_2…t_{pos}\)</span> 的最长后缀 <span class="math">\(u\)</span>，使得 <span class="math">\(u\)</span> 也是某一个模式串的后缀，然后根据在多模式串集合上扩展的 BM 算法的三个函数 <span class="math">\(d_1,d_2\)</span> 和 <span class="math">\(d_3\)</span>，将 <span class="math">\(pos\)</span> 右移。以及对于前缀树的每个状态，都需要计算 <span class="math">\(d_1\)</span> 和 <span class="math">\(d_2\)</span>，当最长后缀 <span class="math">\(u\)</span> 在可以接受的状态集合中被识别出来并抵达状态 <span class="math">\(q\)</span> 时，再根据 <span class="math">\(d_1\)</span> 和 <span class="math">\(d_2\)</span> 进行移动。</p>
<ul>
<li><span class="math">\(d_1(q)\)</span> 是使得 <span class="math">\(u = \mathcal{L}(q)\)</span> 与某一个模式串的子串对齐的最小移动距离 <span class="math">\(p_j \in \mathcal{P}\)</span></li>
<li><span class="math">\(d_2(q)\)</span> 是使得 <span class="math">\(u = \mathcal{L}(q)\)</span> 的一个后缀与某一个模式串的前缀相匹配的最小移动距离 <span class="math">\(p_j \in \mathcal{P}\)</span></li>
</ul>
<p>那么对于 <span class="math">\(\sum\)</span> 中每个字符 <span class="math">\(\alpha\)</span> 和每一个位置 <span class="math">\(0\leqslant k< l_{max}\)</span>，<span class="math">\(d_3[\alpha,k]\)</span> 是使得位置 <span class="math">\(pos-k\)</span> 处的字符串与模式串 <span class="math">\(p\)</span> 中某个字符相匹配的最小移动距离 <span class="math">\(p_j \in \mathcal{P}\)</span>。</p>
<p>下面简述如何用这三个函数来计算我们所需的移动距离，我们不妨假设从文本位置 <span class="math">\(pos\)</span> 从后向前读入了 <span class="math">\(k\)</span> 个字符，并且在自动机中抵达了状态 <span class="math">\(q\)</span>，那么移动距离 <span class="math">\(s[q,pos,k]\)</span> 可以由下面的公式推导而来：
</p>
<div class="math">$$s[q,pos,k] = min\left\{\begin{matrix} max(d_1[q],d_3[t_{pos-k},k]) \\ d_2[q] \end{matrix}\right.$$</div>
<p>
上式是 BM 算法窗口移动的直接扩展，显然有 <span class="math">\(d_2\leqslant l_{min}\)</span>，所以最长的跳跃距离必然不会超过 <span class="math">\(l_{min}\)</span>。</p>
<p>CW 算法的时间复杂度为 <span class="math">\(O(n \times l_{max}\)</span>)，<span class="math">\(d_1,d_2,d_3\)</span>可以在 <span class="math">\(O(|P|\)</span>) 的时间内计算完成。</p>
<h3>Set Horspool</h3>
<p>Set Horspool （下称 SH）是对单字符串的 Horspool 算法扩展，它也可以看作是 CW 算法的简化。</p>
<p>SH 算法的基本流程如图，假设当前文本位置 <span class="math">\(pos\)</span> 初始化为 <span class="math">\(l_{min}\)</span>，从 <span class="math">\(pos\)</span> 开始，从后向前读入文本字符。这里使用所有模式串反转 <span class="math">\(p_{rv}\)</span> 构建的前缀树来完成识别过程，如果到达状态 <span class="math">\(s_0\)</span> 恰好属于可以接受的结束状态，就标记下一个匹配，假设当无法继续识别读入的文本字符，就根据第一个读入的文本字符 <span class="math">\(\beta\)</span> 来决定 <span class="math">\(pos\)</span> 的移动。<span class="math">\(pos\)</span> 移动到使得 <span class="math">\(\beta\)</span> 与它在前缀树中下一次出现位置对齐的地方。一个显然的特例是，如果 <span class="math">\(\beta\)</span> 不再重复出现，那么就直接移动 <span class="math">\(l_{min}\)</span> 即可。</p>
<p><img src="https://ws1.sinaimg.cn/large/006tKfTcgy1fjmbughca9j30o30bxq3x.jpg"></p>
<p>下面简述 SH 算法的流程：</p>
<ul>
<li>输入：模式串集 <span class="math">\(P = \{p_1,p_2,…,p_r\}\)</span>，目标文本 <span class="math">\(T=t_1t_2…t_n\)</span>； </li>
<li>输出：窗口指针位置 <span class="math">\(pos\)</span>；</li>
<li>步骤：<ol>
<li>预处理阶段。<span class="math">\(HO \leftarrow Trie(P_{rv}=\{p_{1,rv},p_{2,rv},…,p_{r,rv}\})\)</span>，其中这里的<span class="math">\(\delta_{HO}\)</span>是状态转移函数；对于<span class="math">\(c\in\sum\)</span>，有<span class="math">\(d[c]\leftarrow l_{min}\)</span>；对于所有<span class="math">\(j\in 1,2,…,r\)</span>，有<span class="math">\(d[p_{jk}]\leftarrow min(d[p_{jk}], m_j-k), k\in 1,2,…,m_j-1\)</span></li>
<li>初始化当前指针位置，<span class="math">\(pos \leftarrow l_{min}\)</span>，检查 <span class="math">\(pos \leqslant n\)</span>，如果是，<span class="math">\(j \leftarrow 0\)</span>，也即从 <span class="math">\(HO\)</span> 中拿到它的初始状态，然后跳转到 3，如果不是，跳转到 6；</li>
<li>检查如果 <span class="math">\(pos - j >0\)</span> 且 <span class="math">\(\delta_{HO}(t_{pos-j}, Current)\neq\theta\)</span>，跳转到 4，如果不是，跳转到 6；</li>
<li>检查 <span class="math">\(Current\)</span> 是否是可以被接受的终止状态，如果是则记录下 <span class="math">\(\mathcal{F}(Current, pos\)</span>)，如果不是，跳转到 5；</li>
<li>执行状态转移 <span class="math">\(Current \leftarrow \delta_{HO}(t_{pos-j}, Current)\)</span>，同时 <span class="math">\(j \leftarrow j+1\)</span>；</li>
<li>位置指针转移 <span class="math">\(pos \leftarrow pos + d[t_{pos}]\)</span>；</li>
</ol>
</li>
</ul>
<p>SH 算法的复杂度是 <span class="math">\(O(n\times l_{max}\)</span>)，一般来说，它只适合模式串集合很小，但是字母表 <span class="math">\(\sum\)</span> 却很大的场合。</p>
<h3>Wu-Manber</h3>
<p>SH 在多模式串的情况下其实性能很差，主要归咎于字母表 <span class="math">\(\sum\)</span> 中每个字符通常都以较高概率出现在某个模式串中，从而导致移动距离下降。</p>
<p>Wu-Manber（下称 WM）解决的思路是读入一块字符，从而降低字符块在某个模式串中出现的概率。这里我们不妨假设块的长度为 <span class="math">\(B\)</span>。问题的难点在于，如果 <span class="math">\(B\)</span> 比较大，那么总共就可能会有 <span class="math">\(|\sum|^B\)</span> 个不同的块，对存储空间是一个不小的挑战。</p>
<p>WM 首先使用一个散列函数 <span class="math">\(h_1\)</span> 将所有可能的块散列到一个有限的表 <span class="math">\(SHIFT\)</span>上，两个不同的块有可能被散列映射到 <span class="math">\(SHIFT\)</span> 的同一个位置。对于每个新的位置，如果读入一块字符 <span class="math">\(Bl\)</span> 而不是像 Horspool 那样只读入最后一个字符，则必须确保 <span class="math">\(Bl\)</span> 的移动距离 <span class="math">\(SHIFT(h_1(Bl)\)</span>) 是安全的。为了确保这一点，算法在 <span class="math">\(SHIFT(j\)</span>) 中存入满足 <span class="math">\(j=h_1(Bl\)</span>) 的所有块的移动距离的最小值。具体地说，构建 <span class="math">\(SHIFT\)</span> 表的步骤如下：</p>
<ol>
<li>如果块 <span class="math">\(Bl\)</span> 不出现在 <span class="math">\(P\)</span> 中的任何一个模式串中，则可以安全地向右移动 <span class="math">\(l_{min}-B+1\)</span> 个字符。因此，将表的每一项都初始化为 <span class="math">\(l_{min}-B+1\)</span>。</li>
<li>反之，如果块 <span class="math">\(Bl\)</span> 出现在 <span class="math">\(P\)</span> 中的某一个模式串中，我们不妨把它记作 <span class="math">\(p_i\)</span>，则需要找出 <span class="math">\(Bl\)</span> 在 <span class="math">\(p_i\)</span> 中最右出现的末尾位置 <span class="math">\(j\)</span>，然后将 <span class="math">\(SHIFT(h_1(Bl)\)</span>) 置为 <span class="math">\(m_i -j\)</span>。</li>
</ol>
<p>为了计算 <span class="math">\(SHIFT\)</span> 表的所有值，对于每个模式串 <span class="math">\(p_i=p_{i1}p_{i2}…p_{im_i}\)</span> 的每个块 <span class="math">\(B=p_{i,j-B+1}…p_{i,j}\)</span>，都需要在 <span class="math">\(SHIFT\)</span> 中寻找出对应的表项 <span class="math">\(h_1(B\)</span>)，并将 <span class="math">\(SHIFT(h_1(Bl)\)</span>) 置为 <span class="math">\(m_i -j\)</span> 和它当前值中的较小的那个。</p>
<p>其实块长 <span class="math">\(B\)</span> 取决于三个因素：最短的关键词长度 <span class="math">\(l_{min}\)</span>；模式串集合的大小以及字母表 <span class="math">\(\sum\)</span> 的大小。研究表明，取 <span class="math">\(B = log_{|\sum|}(2\times l_{min} \times r\)</span>) 能够产生最好的实验结果。<span class="math">\(SHIFT\)</span> 的大小也是随着可用空间的大小而变化。</p>
<p>只要移动距离 <span class="math">\(l>0\)</span>，就可以安全地将当前位置向右移动，当移动距离 <span class="math">\(l = 0\)</span> 时，当前位置的左边可能就是一个被成功匹配的模式串，那么对于这种情况，WM 巧妙地使用另一个散列表 <span class="math">\(HASH\)</span> 和散列函数 <span class="math">\(h_2\)</span>，它的每个表项 <span class="math">\(HASH(j\)</span>) 本质是一个链表结构，记录了最后一个块在 <span class="math">\(h_2\)</span> 的散列映射中到 <span class="math">\(j\)</span> 的所有模式串集合。于是这样就可以顺藤摸瓜找出那些最后一块的散列值与当前读入的文本块 <span class="math">\(Bl\)</span> 散列值相同的所有模式串。</p>
<p>搜索阶段和 SH 算法是类似的，首先将当前位置 <span class="math">\(pos\)</span> 初始化置为 <span class="math">\(l_{min}\)</span>，那么对于每个当前位置 <span class="math">\(pos\)</span>，从后向前读入 <span class="math">\(B\)</span> 个字符的块 <span class="math">\(Bl\)</span>。这时倘若 <span class="math">\(j = SHIFT(h_1(Bl)) > 0\)</span>，那么将窗口移动到位置 <span class="math">\(pos+j\)</span>，并继续搜索；反之，如果 <span class="math">\(SHIFT(h_1(Bl)) = 0\)</span>，那我们就用 <span class="math">\(HASH\)</span> 算出文本块对应的一组模式串 <span class="math">\(HASH(h_2(Bl)\)</span>)，并逐个与文本进行比较，算法流程如下：</p>
<ul>
<li>输入：模式串集 <span class="math">\(P = \{p_1,p_2,…,p_r\}\)</span>，目标文本 <span class="math">\(T=t_1t_2…t_n\)</span>；</li>
<li>输出：窗口指针位置 <span class="math">\(pos\)</span>；</li>
<li>步骤：<ol>
<li>预处理阶段，计算 <span class="math">\(B\)</span>，然后继续构建两个哈希表 <span class="math">\(SHIFT\)</span> 和 <span class="math">\(HASH\)</span>；</li>
<li>初始化当前指针位置，<span class="math">\(pos \leftarrow l_{min}\)</span>，检查 <span class="math">\(pos \leqslant n\)</span>，如果是，<span class="math">\(i \leftarrow h_1(t_{pos-B+1}…t_{pos}\)</span>，然后跳转到 3，否则算法结束；</li>
<li>检查 <span class="math">\(SHIFT[i] == 0\)</span>，如果是，<span class="math">\(list \leftarrow HASH[h_2(t_{pos-B+1}…t_{pos})]\)</span>，这里的 <span class="math">\(list\)</span> 装载了匹配好的模型，挨个对应着目标文本<span class="math">\(T\)</span>，随后照例 <span class="math">\(pos \leftarrow pos + 1\)</span>，如果不是，跳转到 4；</li>
<li>窗口指针位置转移 <span class="math">\(pos \leftarrow pos + SHIFT[i]\)</span>；</li>
</ol>
</li>
</ul>
<p>以上就是对于固定的敏感词列表的排查算法的研究，其中也包含了大量的实践操作，虽然它们各有优劣，但是就目前敏感词列表大小，词组长度以及字母表的长度而言，Wu-Manber 是不二的选择。</p>
<h2>总结</h2>
<p>虽然排查敏感词从功能上来说并不是一个十分艰巨的任务，但是我们还是对这个问题做了一个较为系统和深入的研究工作，以期从算法角度得到高效且优雅的解决方案。</p>
<script type="text/javascript">if (!document.getElementById('mathjaxscript_pelican_#%@#$@#')) {
var align = "center",
indent = "0em",
linebreak = "false";
if (false) {
align = (screen.width < 768) ? "left" : align;
indent = (screen.width < 768) ? "0em" : indent;
linebreak = (screen.width < 768) ? 'true' : linebreak;
}
var mathjaxscript = document.createElement('script');
mathjaxscript.id = 'mathjaxscript_pelican_#%@#$@#';
mathjaxscript.type = 'text/javascript';
mathjaxscript.src = 'https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.3/latest.js?config=TeX-AMS-MML_HTMLorMML';
mathjaxscript[(window.opera ? "innerHTML" : "text")] =
"MathJax.Hub.Config({" +
" config: ['MMLorHTML.js']," +
" TeX: { extensions: ['AMSmath.js','AMSsymbols.js','noErrors.js','noUndefined.js'], equationNumbers: { autoNumber: 'AMS' } }," +
" jax: ['input/TeX','input/MathML','output/HTML-CSS']," +
" extensions: ['tex2jax.js','mml2jax.js','MathMenu.js','MathZoom.js']," +
" displayAlign: '"+ align +"'," +
" displayIndent: '"+ indent +"'," +
" showMathMenu: true," +
" messageStyle: 'normal'," +
" tex2jax: { " +
" inlineMath: [ ['\\\\(','\\\\)'] ], " +
" displayMath: [ ['$$','$$'] ]," +
" processEscapes: true," +
" preview: 'TeX'," +
" }, " +
" 'HTML-CSS': { " +
" styles: { '.MathJax_Display, .MathJax .mo, .MathJax .mi, .MathJax .mn': {color: 'inherit ! important'} }," +
" linebreaks: { automatic: "+ linebreak +", width: '90% container' }," +
" }, " +
"}); " +
"if ('default' !== 'default') {" +
"MathJax.Hub.Register.StartupHook('HTML-CSS Jax Ready',function () {" +
"var VARIANT = MathJax.OutputJax['HTML-CSS'].FONTDATA.VARIANT;" +
"VARIANT['normal'].fonts.unshift('MathJax_default');" +
"VARIANT['bold'].fonts.unshift('MathJax_default-bold');" +
"VARIANT['italic'].fonts.unshift('MathJax_default-italic');" +
"VARIANT['-tex-mathit'].fonts.unshift('MathJax_default-italic');" +
"});" +
"MathJax.Hub.Register.StartupHook('SVG Jax Ready',function () {" +
"var VARIANT = MathJax.OutputJax.SVG.FONTDATA.VARIANT;" +
"VARIANT['normal'].fonts.unshift('MathJax_default');" +
"VARIANT['bold'].fonts.unshift('MathJax_default-bold');" +
"VARIANT['italic'].fonts.unshift('MathJax_default-italic');" +
"VARIANT['-tex-mathit'].fonts.unshift('MathJax_default-italic');" +
"});" +
"}";
(document.body || document.getElementsByTagName('head')[0]).appendChild(mathjaxscript);
}
</script>
</section>
<section class="post-info">
<div class="post-share">
<a class="twitter" href="https://twitter.com/share?text=敏感词项目中柔性字符串匹配问题&url=/min-gan-ci-xiang-mu-zhong-rou-xing-zi-fu-chuan-pi-pei-wen-ti.html" onclick="window.open(this.href, 'twitter-share', 'width=550,height=235');return false;">
<i class="ic ic-twitter"></i><span class="hidden">Twitter</span>
</a>
<a class="facebook" href="https://www.facebook.com/sharer/sharer.php?u=/min-gan-ci-xiang-mu-zhong-rou-xing-zi-fu-chuan-pi-pei-wen-ti.html" onclick="window.open(this.href, 'facebook-share','width=580,height=296');return false;">
<i class="ic ic-facebook"></i><span class="hidden">Facebook</span>
</a>
<a class="googleplus" href="https://plus.google.com/share?url=/min-gan-ci-xiang-mu-zhong-rou-xing-zi-fu-chuan-pi-pei-wen-ti.html" onclick="window.open(this.href, 'google-plus-share', 'width=490,height=530');return false;">
<i class="ic ic-googleplus"></i><span class="hidden">Google+</span>
</a>
<div class="clear"></div>
</div>
<div class="clear"></div>
</section>
<aside class="post-nav">
<div class="clear"></div>
</aside>
</div>
</article>
</main>
<!-- TODO : Body class -->
<div id="body-class" style="display: none;" class=""></div>
<footer id="footer">
<div class="inner">
<section class="credits">
<span class="credits-theme">Theme <a href="https://github.com/arulrajnet/attila" rel="nofollow">Attila</a></span>
<span class="credits-software">Published with <a href="https://github.com/getpelican/pelican" rel="nofollow">Pelican</a></span>
</section>
</div>
</footer>
</section>
<script type="text/javascript" src="/theme/js/script.js"></script>
</body>
</html>