模式匹配Pattern Matching

r囧r小猫 2022-05-19 08:39 193阅读 0赞

**目录**

1.模式匹配(pattern matching)的概念

2. 制造模式匹配的测试串

3. 模式匹配蛮力算法（Brute-Force，也成Naive朴素算法）

3.1 Version 1

3.2 Version 2:（与Version 1的不同在于i，j）

3.3 算法分析

（1）最差情况

（2）最佳情况 —— 找到

（3）最佳情况 —— 没找到

4. 模式匹配KMP算法

5. 模式匹配BC(Begin With The End)算法

--------------------

# 1.模式匹配(pattern matching)的概念 #

——一个目标对象 T（字符串）  
——（pattern）P（字符串）  
在目标 T 中寻找一个给定的模式P的过程

![20181114135933755.png][]

**应用**  
1. 文本编辑时的特定词、句的查找  
•UNIX/Linux: sed, awk, grep  
2. DNA 信息的提取

# 2. 制造模式匹配的测试串 #

![70][]

制造模式匹配测试串的两种策略

**策略一：**随机生成Test串，随机生成Pattern串,然后进行匹配。该策略下，P在T中出现的概率小。

**策略二：**随机生成Test串，在从中随机截取Pattern串。

# 3. 模式匹配蛮力算法（Brute-Force，也成Naive朴素算法） #

![70 1][]

## 3.1 Version 1 ##

![70 2][]

**匹配过程详解：**

T = pepeople

P = people

\---------------------------------------

i = 0 j = 0

T = pepeople

P = people

T\[0\] = P\[0\] = p

i + 1 = 1

j + 1 = 1

\-----------------------------------------

i = 1 j = 1

T = pepeople

P = people

T\[1\] = P\[1\] = e

i + 1 = 2

j + 1 = 2

\----------------------------------------------

i = 2 j = 2

T = pepeople

P = people

T\[2\] = p

P\[2\] = 0

T\[2\] != P\[2\]

i = 2 - (2 - 1) = 1 **(T****回退****)**

j = 0 **(P****复位****)**

**------------------------------------------------**

i = 1 j = 0

T = pepeople

P = people

(......)

## **3.2 Ver**sion 2:（与Ve**rsion 1的不同在于i，j）** ##

![70 3][]

**匹配过程详解：**

T = pepeople

P = people

\---------------------------------------

i = 0 j = 0

T = pepeople

P = people

T\[0+0\]

T\[0\] = P\[0\] = p

j + 1 = 1

\-----------------------------------------

i = 0 j = 1

T = pepeople

P = people

T\[0+1\]

T\[1\] = P\[1\] = e

j + 1 = 2

\----------------------------------------------

i = 0 j = 2

T = pepeople

P = people

T\[0+2\]

T\[2\] = p

P\[2\] = 0

T\[2\] != P\[2\]

i = i+1 = 1

j = 0

**------------------------------------------------**

i = 1 j = 0

T = pepeople

P = people

T\[1+0\]

T\[1\] = e

P\[0\] = p

(......)

## 3.3 算法分析 ##

### 3.3.1 最差情况 ###

### ![20181114143312312.png][] ###

### 3.3.2 最佳情况 —— 找到 ###

### ![20181114143332228.png][] ###

### 3.3.3 最佳情况 —— 没找到 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70][]

# 4. 模式匹配KMP算法 #

推荐JULY的博文：[https://blog.csdn.net/v\_JULY\_v/article/details/7041827][https_blog.csdn.net_v_JULY_v_article_details_7041827]

推荐阮一峰的博文[http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt\_algorithm.html][http_www.ruanyifeng.com_blog_2013_05_Knuth_E2_80_93Morris_E2_80_93Pratt_algorithm.html]

**字符串：****BBC ABCDAB ABCDABCDABDE**

**搜索词：****ABCDABD**

**1.**

![bg2013050103.png][]

B与A不匹配，搜索词后移一位。

**2.**

## ![bg2013050104.png][] ##

B与A不匹配，搜索词再往后移。

**3.**

![bg2013050105.png][]

直到字符串有一个字符，与搜索词的第一个字符相同为止。

**4.**

![bg2013050106.png][]

接着比较字符串和搜索词的下一个字符，还是相同。

**5.**

![bg2013050107.png][]

直到字符串有一个字符，与搜索词对应的字符不相同为止。

**6.**

![bg2013050108.png][]

这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。

**7.**

![bg2013050107.png][]

一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。

**8.**

怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。

![bg2013050109.png][]

**9.**

![bg2013050107.png][]

![70 4][]

已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，最后一个匹配字符B对应的"部分匹配值"为2，因此按照下面的公式算出向后移动的位数：

> 　　移动位数 = 已匹配的字符数 - 对应的部分匹配值（搜索词"前缀"和"后缀"的最长的共有元素的长度）

因为 6 - 2 等于4，所以将搜索词向后移动4位。

**10.**

![bg2013050110.png][]

![70 5][]

因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（"AB"），对应的"部分匹配值"为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。

**11.**

![bg2013050111.png][]

因为空格与A不匹配，继续后移一位。

**12.**

![bg2013050112.png][]

逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。

**13.**

![bg2013050113.png][]

逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位，这里就不再重复了。

**14.**

![bg2013050114.png][]

下面介绍《部分匹配表》是如何产生的。

首先，要了解两个概念："前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。

**15.**

![bg2013050109.png][]

"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，

> 前缀 后缀 　 公有元素的长度
> 
> 　 "A" 空集 空集 **0**
> 
> 　 "AB" \[A\] \[B\] **0**
> 
> 　　"ABC" \[A, AB\] \[BC, C\] **0**
> 
> 　　"ABCD" \[A, AB, ABC\] \[BCD, CD, D\] **0**
> 
> 　　"ABCDA" \[**A**, AB, ABC, ABCD\] \[BCDA, CDA, DA, **A**\] **1**
> 
> 　　"ABCDAB" \[A, **AB**, ABC, ABCD, ABCDA\] \[BCDAB, CDAB, DAB, **AB**, B\] **2**
> 
> 　　"ABCDABD" \[A, AB, ABC, ABCD, ABCDA, ABCDAB\] \[BCDABD, CDABD, DABD, ABD, BD, D\] **0**

**16.**

![bg2013050112.png][]

"部分匹配"的实质是，有时候，字符串头部和尾部会有重复。比如，"ABCDAB"之中有两个"AB"，那么它的"部分匹配值"就是2（"AB"的长度）。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），就可以来到第二个"AB"的位置。

**17. next数组**

**next 数组相当于“最大长度值” 整体向右移动一位，然后初始值赋为-1**。

![70 6][]

> 移动位数 = 失配字符所在位置（下标从0开始） - 失配字符对应的next 值

**18 next数组优化版**

![20181205105824983.png][]

相等，则让next\[j\] = next\[k\]

j=3，k=0，next\[0\]=-1

j=5，k=1，next\[1\]=0

j=7，k=1，next\[1\]=0

j=8，k=2，next\[2\]=0

# 5. 模式匹配BC(Begin With The End)算法 #

推荐阮一峰的博文：[http://www.ruanyifeng.com/blog/2013/05/boyer-moore\_string\_search\_algorithm.html][http_www.ruanyifeng.com_blog_2013_05_boyer-moore_string_search_algorithm.html]

[20181114135933755.png]: /images/20220519/9cb07620348f440aaa4ea4bc7aeef536.png
[70]: /images/20220519/f5e1cea6072849388503685ee6ea79a2.png
[70 1]: /images/20220519/896f3bc432fe43ee84ec6c5257a537ff.png
[70 2]: /images/20220519/22eba1ca1d104b2c9bfd5c281465d532.png
[70 3]: /images/20220519/0613e21283ff430286a2f9ddaec6a1b5.png
[20181114143312312.png]: /images/20220519/3e44e36204a04bcb8b828a6ec8f6f685.png
[20181114143332228.png]: /images/20220519/7a969a3451c642258cadd7bab6163376.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3d5ZHlkMTEw_size_16_color_FFFFFF_t_70]: /images/20220519/537d8a8723a64c53a4cbd8e89d3e78a7.png
[https_blog.csdn.net_v_JULY_v_article_details_7041827]: https://blog.csdn.net/v_JULY_v/article/details/7041827
[http_www.ruanyifeng.com_blog_2013_05_Knuth_E2_80_93Morris_E2_80_93Pratt_algorithm.html]: http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
[bg2013050103.png]: http://www.ruanyifeng.com/blogimg/asset/201305/bg2013050103.png
[bg2013050104.png]: http://www.ruanyifeng.com/blogimg/asset/201305/bg2013050104.png
[bg2013050105.png]: http://www.ruanyifeng.com/blogimg/asset/201305/bg2013050105.png
[bg2013050106.png]: http://www.ruanyifeng.com/blogimg/asset/201305/bg2013050106.png
[bg2013050107.png]: http://www.ruanyifeng.com/blogimg/asset/201305/bg2013050107.png
[bg2013050108.png]: http://www.ruanyifeng.com/blogimg/asset/201305/bg2013050108.png
[bg2013050109.png]: http://www.ruanyifeng.com/blogimg/asset/201305/bg2013050109.png
[70 4]: /images/20220519/5505fd548f8d439d8f0946b1eb85aae5.png
[bg2013050110.png]: http://www.ruanyifeng.com/blogimg/asset/201305/bg2013050110.png
[70 5]: /images/20220519/c3b6268f01204e6ca8b6372a548b6e27.png
[bg2013050111.png]: http://www.ruanyifeng.com/blogimg/asset/201305/bg2013050111.png
[bg2013050112.png]: http://www.ruanyifeng.com/blogimg/asset/201305/bg2013050112.png
[bg2013050113.png]: http://www.ruanyifeng.com/blogimg/asset/201305/bg2013050113.png
[bg2013050114.png]: http://www.ruanyifeng.com/blogimg/asset/201305/bg2013050114.png
[70 6]: /images/20220519/8f277886a2a242019679f6e2373df34e.png
[20181205105824983.png]: /images/20220519/9ac693fa5c6f421eabf78d20c025b3ef.png
[http_www.ruanyifeng.com_blog_2013_05_boyer-moore_string_search_algorithm.html]: http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html