文档章节

利用有限自动机(finite automata)进行模式匹配

famince
 famince
发布于 2013/12/06 21:40
字数 2321
阅读 2227
收藏 27

一、一、有限自动机定义及基本术语:

一个有限自动机 M 是一个5元组(Q, q0,A, Σ, δ),其中:

  • Q 是所有状态的有限集合;

  • q0 ∈ Q (属于)是初始状态;

  • A ⊆ Q (子集)是接受状态的集合;(对应于多模式?)

  • Σ 是有限输入字母表;

  • δ 是从Q * Σ的转移函数,称为有限自动机M的转移函数;


记号与术语:
Σ*  表示用字母表Σ中所有字符形成的所有有限长度的字符串集合.
n   输入字符串(input string)的长度.
m  模式字符串(pattern string)的长度;也称作终态m,当状态为m时表示,m长度的模式串匹配成功.

|x| : 字符串x的长度, 如示符号记法.

 : 字符串w 是字符串x 的前缀,如示符号记法.

 : 字符串w 是字符串x 的后缀,如示符号记法.(注意前缀/后缀均遵循传递规则)

ε:表示空字符串,是所有字符串的后缀,前缀. (ε读作 epsilon )

a : 下文中的字符a泛指所有字符(a∈Σ),不特指字符'a'.


二、引入的函数定义:

  • 转移函数δ(transition function) ( δ 读作"delta",对应大写为 Δ )

        有限自动机开始于初始状态q0,每次读入输入字符串的一个字符,如果有限自动机在状态q是读入字符'a', 
        则M状态从q变成 δ(q, a);


  • 终态函数 Φ(finite state function) ( Φ 读作"fai", 对应小写为 φ )

        是从 Σ* 到 Q 的函数,Φ(w)是永动机M 扫描字符串 w 终止后的状态;M 接受字符串w 当且仅当Φ(w)∈A, 函数Φ有下列递归关系定义:
                φ(ε) = q0;(空字符串 ε 的终态为q0)

                φ(wa) = δ(φ(w),a) (其中w∈Σ*,a∈Σ)


  • 辅助函数,后缀函数σ 对应于模式字串P  ( σ 读作 "sigma", 对应大写为 Σ )

        是从Σ* 到{0,1, ..., m}上的映射,σ(x)是字符串x的后缀同时是P的前缀的最大长度;
                σ(x) = max{k: Pk ⊐ x }
                有P0 = ε是所有所有字符串的后缀; 

* 后缀函数的主要意义的是求出当前匹配失败时,求出已经匹配过的部分字串x是否是待匹配模式字串P的前缀,即匹配可以跳过x中部分长度( σ(x) ),可以用于实现转移过程;同时也表明在接受输入字符串x后的状态(终态),即也用于实现终态函数。


三、字符串匹配自动机(string-matching automation)

下图是依据模式串 P="ababaca" 构建的自动机图表:

 

上图(a)是一个自动机的状态转换图表,接受所有以字符串"ababaca"结尾的字符串。其中状态0是初始状态,状态7是唯一接受状态(单模式匹配).

1) 从状态i到状态j的带箭头的有向边表示转移过程: δ(i, a) = j(a∈Σ).

2) 右向边组成了自动机的主要"骨架",图中粗线部分,对应于输入字符同模式字串匹配成功的转移过程。左向边对应于匹配失败的转移过程(跳转,主要是计算已经匹配的部分字串 的后缀子串同时是模式串P的前缀的最大长度).部分匹配失败的过程没有标示出来。

3) 图中部分状态i在接受某字符a(a∈Σ)时,没有标示出对应有向边的情况表明其转移过程为: δ(i, a) = 0(a∈Σ),根据下面字符串模式匹配自动机定义,知当前已经匹配子串没有后缀字串是模式串P的前缀。如在状态3时,输入字符为'c',即在已经匹配了"aba"这时接受字符'c',知当前已匹配字串为"abac",对应模式字串P="ababaca",可知这时匹配失败,进行失败跳转求"abac"后缀子串同时是模式串P前缀的最大长度,可知为0.

4) 匹配成功的转移过程(对应状态,以及对应输入字符)均标示为灰色,

5) 表(c)是自动机在处理(接受)输入文本T="abababacaba"的最终状态表。当输入字符T[i]时,此时字串T[0...i]对应的的最终状态φ(T[0...i]) 同表(c)最后一列一一对应。有T["abababaca"] = P.length = 7(唯一接受状态),即这时候在T串中匹配成功模式串P,结束位置为9,起始位置为(9-P.length+1)=3。


1、字符串匹配有限自动机定义:

给定模式(pattern)字符串 P[1...m],其对应的字符串匹配有限自动机定义如下:

1、状态集Q = {0,1,...m},开始状态q0 是状态0,state m 是唯一的接受状态;

2、转移函数δ 可以用后缀函数来表示 (这个很重要, 因为状态转移函数是个抽象概念,而后缀函数可以用code表示) :

δ(q,a) = σ(Pq,a)   <等式一>


假设当前已经读入的字符串为T,为了让T的字串(以T[i]为结尾) 能匹配模式字串Pj,必须满足Pj是Ti的后缀;同时假设q = φ(Ti),说明读取字串Ti后自动机M 状态变成q;同时根据转移函数<等式一>可知q是模式字串P最大长度的前缀,同时是Ti的后缀;因此在状态q,有Pq ⊐ Ti 和 q = σ(Ti) (当q 等于m 时,说明模式字串P整个是Ti的后缀,也意味着匹配查找成功了),因此有σ(Ti)= q,得出永动机也支持下面的等式(终态函数也是抽象的,转化为后缀函数表达式后,可以用code表示):

φ(Ti) = σ(Ti)(i = 0,1,...n)        <等式二>



2、同时有两个引理(具体证明可以参考算法导论):

  • 引理1、后缀函数不等式:

            σ(xa) ≤ σ(x) + 1 (对于任何字符串x,以及字母a)

  • 引理2、后缀函数递归引理:

        对于任何字符串x,以及字母a,如果q = σ(x),有:
            σ(xa) = σ(Pqa)


<等式二> 可以用数学归纳法证明,具体如下:
1、当i = 0,因为T0 = ε,因此有φ(Ti) = 0 = σ(Ti)
2、假设φ(Ti) = σ(Ti),证明φ(Ti+1) = σ(Ti+1),用q 表示φ(Ti),用字母a表示T[i+1],有:
φ(Ti+1) = φ(Tia) (Ti+1 == Tia)
             = δ(φ(Ti),a) (根据终态函数的定义)
            = δ(q,a) (根据q的定义)
            = σ(Pqa) (根据等式一)
            = σ(Tia) (根据引理二)
            = σ(Ti+1) (Ti+1 == Tia)


从上面可以知道当读入T i 的终态(亦即读入T[i]后转移函数状态)等于模式长度,就匹配成功了,下面是有限自动机机匹配算法伪代码:


下面就是根据<等式一>来实现转移函数的伪代码:


下面是我自己实现的code:

#include <iostream>
#include <string.h>
using namespace std;

#define MIN(X,Y) 	((X)<=(Y) ? (X) : (Y))

#define MAX_NEEDLE_LEN		0xFF
#define MAX_ALPHABET_NUM	0XFF

/*
check if needle[0~k-1] is suffix of needle[0~q-1 'ch']
 */
int is_suffix(const char * needle, int k, int q, unsigned char ch)
{
	int i = 0;
	int suffix_len = k;

	if(NULL == needle || suffix_len < 0 || suffix_len > 7)
	{
		return -1;
	}

	if(needle[suffix_len - 1] != ch)
	{
		return -1;
	}

	if(1 == suffix_len)
	{
		return 0;
	}

	for(i=0; (suffix_len > 1)&&(i < suffix_len) && (i < q); i++)
	{
		if(needle[suffix_len - 2 - i] != needle[q - 1 - i])
		{
			break;
		}
	}

	if(i >= q)
	{
		return 0;
	}

	return -1;
}

unsigned int delta[MAX_NEEDLE_LEN][MAX_ALPHABET_NUM] = {0};
void compute_transition_func(const char *haystack, const char *needle)
{
	int q = 0, k = 0, j = 0;
	int n = strlen(haystack);
	int m = strlen(needle);

	for(q = 0; q < m; q++)
	{
		for(j = 0; j < n; j++)
		{
			k = MIN(m+1,q+2);

			do
			{
				k--;
				if(0 == is_suffix(needle, k, q, haystack[j]))
				{
					break;
				}
			}while(k > 0);

			delta[q][haystack[j]] = k;
		}
	}
}

void finite_automaton_matcher(const char *haystack, const char *needle)
{
	unsigned int n = strlen(haystack);
	unsigned int m = strlen(needle);
	int q = 0, i =0, j = 0;
	int reCheck_Pos_array[0xff] = {0};
	unsigned int reCheck_Index = 0;

	unsigned need_reCheck = 0;
	unsigned reOccurence = 0;

	if(needle[0] == needle[1])
	{
		need_reCheck = 1;
	}

	for(i = 0; i< n; i++)
	{
		//printf("q=[%d], haystack[%d]=[%c] delta[%d][%c]=[%d]\n", q, i, haystack[i], q, haystack[i], delta[q][haystack[i]]);
		q = delta[q][haystack[i]];

		if(q == m)
		{
			printf("\nSuccess find at haystack[%d] !\n", i-m+1);
		}

		if(needle[0] == haystack[i])
		{
			reOccurence++;
			if(reOccurence >=2)
				reCheck_Pos_array[reCheck_Index++] = i-1;
		}
		else
		{
			reOccurence = 0;
		}
	}

	if(0 == need_reCheck)
		return;

	printf("Need recheck ,and reCheck times [%d]\n", reCheck_Index);

	for(i = 0; i< reCheck_Index; i++)
	{
		q = 0;
		for(j = 0; j< m; j++)
		{
			//printf("q=[%d], haystack[%d]=[%c] delta[%d][%c]=[%d]\n", q, reCheck_Pos_array[i] + j, haystack[reCheck_Pos_array[i] + j], q, haystack[reCheck_Pos_array[i] + j], delta[q][haystack[reCheck_Pos_array[i] + j]]);
			q = delta[q][ haystack[ reCheck_Pos_array[i] + j ] ];

			if(q == m)
			{
				printf("Recheck RSuccess find at haystack[%d] !\n", reCheck_Pos_array[i]);
			}
		}
	}
}

void main()
{
	char needle[] = "aabab";
	char haystack[] = "aaababaabaababaab";

	//compute delta
	compute_transition_func((const char *)haystack, (const char *)needle);

	finite_automaton_matcher((const char *)haystack, (const char *)needle);
}

后面在测试的时候,发现在“aaababaabaababaab”里面查找“aabab”会有遗漏,大家可以debug看下,我针对这种情况作了处理,部分要回过头重复检查, 会影响效率,没想到好方法,欢迎大家指点~~


ps : 2014-08-06日,自己回顾下有限自动机,发现部分错漏,自己重新看了遍算法导论,修正了一遍,以此记录。通过回顾,自己归纳下字符串匹配自动机主要是在某个字符匹配失败时,利用已知匹配失败的部分,看是否有部分是模式串P的前缀,以便跳过部分以节省时间。关键是后缀函数的理解, 当然后面几篇模式匹配算法也有用到其他方法,也有几种方法结合的,具体要看业务需要。


参考:

1、《Introduction to algorithms》

© 著作权归作者所有

共有 人打赏支持
famince
粉丝 9
博文 19
码字总数 34161
作品 0
深圳
高级程序员
加载中

评论(9)

盖慧彤
盖慧彤
写的不错.
寒武纪
寒武纪
只记得上课有上过,但是不知道讲的是神马,感觉很厉害的样子13
xioxin
xioxin
我只是看了永动机才不明觉厉的
famince
famince

引用来自“鑫酱”的评论

不明觉厉!!

仔细看下,也不难
famince
famince

引用来自“自由建客”的评论

永动机44

弄错了,是自动机
famince
famince

引用来自“casinozyz”的评论

纠正一下,是有限状态自动机,五元组描述。

xioxin
xioxin
不明觉厉!!
casinozyz
casinozyz
纠正一下,是有限状态自动机,五元组描述。
自由建客
自由建客
永动机44
KMP算法的理解,伪代码,c代码实现

1、字符串问题形式化定义:假设文本是一个长度为n的T[1..n],而模式是一个长度为m的数组P[1..m],其中m<=n,如果有T[s+1..s+m]==P[1..m],那么就称模式P在T中出现。s为有效偏移,否则称为无效...

thoresa
2015/05/18
0
0
KMP 字符串匹配经典算法深度解析

摘要:KMP算法是字符串匹配的经典算法,由于其O(m+n)的时间复杂度,至今仍被广泛应用。大道至简,KMP算法非常简洁,然而,其内部却蕴含着玄妙的理论,以至许多人知其然而不知其所以然。本文旨...

红薯
2011/08/10
2.2K
0
确定性有限自动机(DFA)多模式匹配算法

在上篇 ac多模式匹配最后,有说到下面的冗余转移,这篇探讨下确定性有限自动机多模式匹配算法; 已知g(4,e) = 5; 假设M 当前状态为4, 且下一个字符不是'e',这时候M 会调用f(4)=1,其实这时候我...

famince
2014/02/24
0
3
AC自动机+trie树实现高效多模式匹配字典

前言 经常会遇到一类需求,在一段字符串中查找所有能匹配上的模式,比如查找一段文字匹配上字典中哪些短语。这时为了高效处理,就会考虑 AC 自动机,即 Aho-Corasick 自动机算法。它的核心思...

超人汪小建
07/09
0
0
基于DFA敏感词查询的算法简析

文章版权由作者李晓晖和博客园共有,若转载请于明显处标明出处:http://www.cnblogs.com/naaoveGIS/ 1.背景 项目中需要对敏感词做一个过滤,首先有几个方案可以选择: a.直接将敏感词组织成S...

李晓晖
2016/10/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

python3.6 取整除法

python3.6 中取整除法运算逻辑如下: d 非零,那么商 q 满足这样的关系: a = qd + r ,且0 ≤ r n1=7//3#7 = 3*2 +1n2=-6.1//3#-7 = 3*(-3)+2'{},{}'.format(n1,n2) 从运行结果可以...

colinux
19分钟前
0
0
阶段总结——用虚拟机搭建一个高可用负载均衡集群架构

[toc] linux基本知识已经介绍完,现有一个业务需要操作,通过对这个项目的操作,可以复习、总结、巩固之前的知识点; ** 用13台虚拟机搭建一个高可用负载均衡集群架构出来,并运行三个站点,...

feng-01
23分钟前
0
0
mysql 设置utf8字符集 (CentOS)

1.查看数据库及mysql应用目前使用的编码方式 (1)链接mysql 客户端 (2)执行:status 结果: 2.修改mysql 应用的字符编码(server characterset ) (1)打开配置文件:vim /etc/mysql/my...

qimh
23分钟前
0
0
windows无法格式化u盘解决方法

1。点开始-运行-输入cmd-format f: /fs: fat32 (这里f:是指U盘所在盘符) 这个格式化会很慢 请耐心等待

大灰狼wow
34分钟前
0
0
MySql 8.0连接失败

原来,MySql 8.0.11 换了新的身份验证插件(caching_sha2_password), 原来的身份验证插件为(mysql_native_password)。而客户端工具Navicat Premium12 中找不到新的身份验证插件(caching_s...

放飞E梦想O
51分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部