序言: 1
多模匹配算法之AC算法详解 3
算法概述 3
转向函数goto原理 4
输出函数output原理 4
失效函数failure原理 4
算法使用的存储结构 5
转向函数goto的实现 6
输出函数Output的实现 7
失效函数failure的实现 7
匹配函数的实现 9
总结 9
单模匹配之BM算法详解 10
算法概述 10
坏字符规则原理 10
好后缀规则原理 11
坏字符规则实现 12
好后缀规则实现 12
匹配函数的实现 14
总结 14
多模匹配算法之AC算法详解
算法概述
●Aho-Corasick算法
-这是一种字典匹配算法，它用于在输入文本中查找字典中的字符串。时间复杂度是线性的。该算法应用有限自动机巧妙地将字符比较转化为了状态转移。
●该算法的基本思想
−在预处理阶段，AC自动机算法建立了三个函数，转向函数goto，失效函数failure和输出函数output，由此构造了一个树型有限自动机。
−在搜索查找阶段，则通过这三个函数的交叉使用扫描文本，定位出关键字在文本中的所有出现位置。
●字典树的构造
-要匹配的一些字符串添加到树结构中去，树边就是单词中的字符，单词中最后一个字符的连接节点添加标志，以表示改节点路径包含1个字典中的字符串，搜索到此节点就表示找到了字典中的某个单词，可以直接输出。
例：模式串集合 P=｛he,she,his,hers｝，下面的分析都根据这个集合展开
图1
转向函数goto原理
我们规定g(state1,ch) = state2.：状态state1 经过 字符ch 可以到达状态state2 。(1)模式串he：g(0,h)=1 g(1,e)=2 模式串he的转向函数构造完毕；
(2)模式串she：g(0,s)=3 g(3,h)=4 g(4,e)=5 模式串she构造完毕；
(3)模式串his：g(0,h)=1 g(1,i)=6 g(6,s)=7 模式串hers构造完毕；
(4)模式串hers：g(0,h)=1 g(1,e)=2 g(2,r)=8 g(8,s)=9 模式串hers构造完毕；
注：(3)中g(0,h)为何不跳到6状态，原因(这个跳转也已存在，所以无需在添加新的状态)，(4)中的g(0,h)=1 g(1,e)=2一样的原因。
整个模式串集合构造完毕。可以根据转向函数画出上面的图1。
输出函数output原理
在转向函数构造的基础上实现输出函数output()。模式串he最后的状态为状态2。当模式匹配的时候遇到状态2。说明待匹配的字符串,已经匹配到了模式串he。在构造模式串的转向函数的结尾，来完成output函数的构建。
失效函数failure原理
在转向函数的基础上实现失效函数f()。规定：深度为1的状态失效跳转到状态0,即f(1)=0,f(3)=0;(因为第一个字符匹配都失败了，所以只能从新开始匹配)
当前字符无匹配，表示当前状态的任何一条路径都无法达到下一跳，此时不能沿现有路径前进，只能回溯，回溯到存在的最长的后缀字符串处，如果没有任何后缀字符串匹配则回溯到树根处。然后从当前回溯节点判断是否可以到达目标字符串字符。
失效函数理解有些难。算法的实现却很巧妙。
失效函数算法：
规定：f(1) = 0 f(3) = 0 ; （第一个字符匹配都失败了，所以只能从新开始匹配)
g(1,e) = 2; f(2) = g(f(1),e) = g(0,e) = 0;
g(1,i) = 6; f(6) = g(f(1),i) = g(0,i) = 0;
g(3,h) = 4; f(4) = g(f(3),h) = g(0,h) = 1;
g(2,r) = 8; f(8) = g(f(2),r) = g(0,2) = 0;
g(6,s) = 7; f(7) = g(f(6),s) = g(0,s) = 3;
g(4,e) = 5; f(5) = g(f(4),e) = g(1,e) = 2;
g(8,s) = 9; f(9) = g(f(8),s) = g(0,s) = 3;
注：此图所构造的失效函数跳转没有遇到失败的情况，有可能会出现失效的情况，具体培训的时候会讲到。(f(N) = g(f(M),s) | g(f(f(M)),s)......如果前面任意的一个跳转不为-1，就赋值给f(N)).
所有的失效跳转构造完毕 ，可以得到:
| state | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| f | 0 | 0 | 0 | 1 | 2 | 0 | 3 | 0 | 3 |
通过队列的方式来实现：首先深度为1的状态入队列1和3入队列，然后1出队列的同时它的下一跳2和6入队列。然后3出队列的同时它的下一跳4入队列，下一步2出队列它的下一跳8入队列；下一步6出队列它的下一跳7入队列；直到9出队列，队列为空，失效函数构建完毕。
算法使用的存储结构
1．AC字典树的存储结构
typedef struct
{
int acsmMaxStates; /*总的模式串的长度*/
int acsmNumStates; /*状态，实现跳转函数g*/
ACSM_PATTERN * acsmPatterns; /*模式串链表头*/
ACSM_STATETABLE * acsmStateTable; /*状态链表，g*/
}ACSM_STRUCT;
/*ACSM_STRUCT * acsm*/
/*acsm->acsmStateTable[M].NextState[i] = N; 意思就是g(M,i) = N;*/
2. 模式串存储结构
typedef struct _acsm_pattern
{
struct _acsm_pattern *next;
unsigned char *patrn; /*经过转化以后的模式串*/
unsigned char *casepatrn; /*源模式串*/
int n; /*源模式串长度*/
int nocase; /*模式串是否进行大小写转化*/
void *id; /*保留字段，未用*/
int nmatch; /*该模式串所匹配的次数*/
} ACSM_PATTERN;
3.状态表
typedef struct
{
int NextState[ ALPHABET_SIZE ]; /*下一跳*/
int FailState; /*失效函数f的跳转*/
ACSM_PATTERN *MatchList; /*输出函数的存储链表头*/
}ACSM_STATETABLE;
转向函数goto的实现
转向函数g(状态，字符) = 下一个状态的构建。
例:模式串集合(he,she,his,hers)
第一个模式串he，g(0,h)=1, g(1,e)=2;
第二个模式串she,g(0,s)=3, g(3,h)=4,g(4,e)=5;
第三个模式串his, g(0,h) =1,g(1,i)=6,g(6,s)=7;
第四个模式串hers, g(0,h) =1, g(1,e)=2,g(2,r)=8,g(8,s)=9.
*如果字符匹配到了状态2,5,7,9就说明了已经匹配上了关键字。构建输出函数output。
static void AddPatternStates (ACSM_STRUCT * acsm, ACSM_PATTERN * p)
{
unsigned char *pattern;
int state=0, next, n;
n = p->n;
pattern = p->patrn;
/*这个for循环就是检查是否前面的模式串已经存在当前的跳转，如果存在
则无需创建新的状态，如果不存在，则break跳转到下面的for循环来赋予新的跳转*/
for (; n > 0; pattern++, n--)
{
next = acsm->acsmStateTable[state].NextState[*pattern];
if (next == ACSM_FAIL_STATE)
break;
state = next;
}
/*模式串跳转状态赋值操作*/
for (; n > 0; pattern++, n--)
{
acsm->acsmNumStates++;
acsm->acsmStateTable[state].NextState[*pattern] = acsm->acsmNumStates;
state = acsm->acsmNumStates;
}
/*增加每个模式串最后的状态,output函数的构建*/
AddMatchListEntry (acsm, state, p);
}
输出函数Output的实现
将状态state（2,5,7,9）对应的模式串px加入到链表里，链表头MatchList.
static void AddMatchListEntry (ACSM_STRUCT * acsm, int state, ACSM_PATTERN * px)
{
ACSM_PATTERN * p;
p = (ACSM_PATTERN *) AC_MALLOC (sizeof (ACSM_PATTERN));
MEMASSERT (p, "AddMatchListEntry");
memcpy (p, px, sizeof (ACSM_PATTERN));
p->next = acsm->acsmStateTable[state].MatchList;
acsm->acsmStateTable[state].MatchList = p;
}
失效函数failure的实现
/*****************************************************************************
重点理解: (状态M 经过字符c 到达状态N。如果在状态N的时候字符串匹配失效，则判断状态M的失效状态是否有经过字符c到达的状态X，如果有，则状态N的失效跳转必然跳转到状态 X。如果没有则判断状态M的失效跳转的失效跳转。。直到有一个状态经过字符c到达的状态Q不为-1，状态N的失效就跳转到Q)。
状态节点深度为1的节点先入队列深度为1的失效跳转规定为0。
通俗的理解: (f(N) = g(f(M),s) | g(f(f(M)),s)......如果前面任意的一个跳转不为-1，就赋值给f(N)).
*****************************************************************************/
static void Build_DFA (ACSM_STRUCT * acsm)
{
int r, s;
int i;
QUEUE q, *queue = &q;
ACSM_PATTERN * mlist=0;
ACSM_PATTERN * px=0;
/* Init a Queue */
queue_init (queue);
/*深度为1 的字符匹配失效，必然会回到深度为0的状态)，将下一个状态入队列*/
for (i = 0; i < ALPHABET_SIZE; i++)
{
s = acsm->acsmStateTable[0].NextState[i];
if (s)
{
queue_add (queue, s);
acsm->acsmStateTable[s].FailState = 0;
}
}
while (queue_count (queue) > 0)
{
r = queue_remove (queue);
for (i = 0; i < ALPHABET_SIZE; i++)
{
int fs, next;
if ((s = acsm->acsmStateTable[r].NextState[i]) != ACSM_FAIL_STATE) /* 如果存在g(r,i) = s */
{
queue_add(queue,s); /*状态s 入队列*/
fs=acsm->acsmStateTable[r].FailState; /*得到r失效的状态跳转fs*/
while ((next=acsm->acsmStateTable[fs].NextState[i]) ==
ACSM_FAIL_STATE) /*判断fs 状态经过字符i 是否有下一跳next，直到 状态next 为0 为止*/
{
fs = acsm->acsmStateTable[fs].FailState; /*如果没有，继续失效到fs的失效跳转*/
}
acsm->acsmStateTable[s].FailState = next; /*如果有,赋值状态s的失效跳转为状态next*/
}
else{
acsm->acsmStateTable[r].NextState[i] =acsm->acsmStateTable[acsm->acsmStateTable[r].FailState].NextState[i];
/*状态r 经过字符i 到达不可达的状态，则g(r,i) = g(f(r),i)*/
}}}
queue_free (queue);
}
匹配函数的实现
int acsmSearch (ACSM_STRUCT * acsm, unsigned char *Tx, int n,void (*PrintMatch) (ACSM_PATTERN * pattern,ACSM_PATTERN * mlist, int nline,int index))
{
int state;
ACSM_PATTERN * mlist;
unsigned char *Tend;
ACSM_STATETABLE * StateTable = acsm->acsmStateTable;
int nfound = 0;
unsigned char *T;
int index;
ConvertCaseEx (Tc, Tx, n);
T = Tc;
Tend = T + n;
for (state = 0; T < Tend; T++)
{
state = StateTable[state].NextState[*T];
if( StateTable[state].MatchList != NULL )
{
for(mlist=StateTable[state].MatchList;mlist!=NULL;mlist=mlist->next )
{
index = T - mlist->n + 1 - Tc;/*模式串在匹配串中的位置*/
nfound++;
PrintMatch (acsm->acsmPatterns,mlist, nline,index);
}
}
}
return nfound;
}
总结
※预处理阶段：
转向函数把一个由状态和输入字符组成的二元组映射成另一个状态或者一条失败消息。
失效函数把一个状态映射成另一个状态。当转向函数报告失效时，失效函数就会被询问。
输出状态，它们表示已经有一组关键字被发现。输出函数通过把一组关键字集（可能是空集）和每个状态相联系的方法，使得这种输出状态的概念形式化。
※搜索查找阶段：
文本扫描开始时，初始状态置为状态机的当前状态，而输入文本y的首字符作为当前输入字符。然后，树型有限自动机通过对每个文本串的字符都做一次操作循环的方式来处理文本。
此算法有两个特点，一个是扫描文本时完全不需要回溯，另一个是时间复杂度为O(n)，时间复杂度与关键字的数目和长度无关。
单模匹配之BM算法详解
算法概述
BM算法的基本流程: 设文本串T，模式串为P。首先将T与P进行左对齐，然后进行从右向左比较 ，如下图所示:
若是某趟比较不匹配时，BM算法就采用两条启发式规则，即坏字符规则 和好后缀规则 ，来计算模式串向右移动的距离，直到整个匹配过程的结束。
坏字符规则 和好后缀规则 ：
图中，第一个不匹配的字符（红色部分）为坏字符，已匹配部分（绿色）为好后缀。
坏字符规则原理
BM算法从右向左扫描的过程中，若发现某个字符x不匹配，则按如下两种情况讨论：
i.如果字符x在模式P中没有出现，那么从字符x开始的m个文本显然不可能与P
匹配成功，直接全部跳过该区域即可。
ii. 如果x在模式P中出现，则以该字符进行对齐。
下图红色部分，发生了一次不匹配。
移动后如下图：
| 字符 | a | b | c | a | b |
| 坏字符 | 2 | 1 | 3 | 2 | 1 |
| 好后缀 | 8 | 7 | 6 | 5 | 1 |
假设1第一个字符b匹配成功，T的倒数第二个字符是c。与模式串P的a不匹配。查找模式串存在c字符，将c与p中的c对齐，实际移动的距离是1.；
假设2 前面所有的都匹配成功，只有最后一个字符不匹配，此时T的第一个字符为c，查找模式串存在c字符，将c与p中的c对齐，实际移动的距离是-2
通过假设1 和假设2可以看出，只通过坏字符移动，有时候可能会出现匹配串后移的情况。那这些实际的移动距离（2 , 1，-2）与上面表格里面给出的坏字符表中c对应的跳转3有何关系呢？与实际匹配成功的次数有关，移动距离（2 , 1 ，-2）与匹配成功次数 ( 0,1,4)有关，（可以理解为匹配串后移了匹配成功的次数，然后在前移坏字符跳转），所以坏字符跳转是与字符在模式串出现的位置有关，坏字符规则就是这样得到的。
好后缀规则原理
若发现某个字符不匹配的同时，已有部分字符匹配成功，则按如下两种情况讨论：
i 最长后缀匹配。
ii 如果已匹配部分没有在模式串中再出现，则跳过所有匹配的字符。
下图中，已匹配部分cab（绿色）在P中再没出现。
再看下图，其后缀T'（蓝色）与P中前缀P'（红色）匹配，则将P'移动到T'的位置。
移动后如下图:
| 字符 | a | b | c | a | b |
| 坏字符 | 2 | 1 | 3 | 2 | 1 |
| 好后缀 | 8 | 7 | 6 | 5 | 1 |
坏字符规则实现
/*首先初始化所有的ascii坏字符 跳转的长度为plen + 1，接着按照模式串中出现的字符按照从左向右依次赋值*/
int *make_skip(char *ptrn, int plen)
{
int *skip = (int *)malloc(256 * sizeof(int));
int *sptr = skip + 256;
if (skip == NULL)
fprintf(stderr, "malloc failed!");
while (sptr -- != skip)
*sptr = plen + 1;
while (plen != 0)
skip[(unsigned char)*ptrn++] = plen--;
return skip;
}
好后缀规则实现
/*主要理解：指针p1, 指针p2,指针p3, 指针pptr，指针ptrn的作用*/
/*p1指针查找模式串中和带匹配的倒数第一个字符相同的字符*/
/*p2指针指向带匹配的倒数第二个字符*/
/*p3指针指向p1前面的那个字符*/
/*ptrn指针，控制指针，每次移动后的匹配串的第一个字符*/
/*pptr指针，控制指针*/
/*p2和p3内容做比较，ptrn和pptr控制做多少次比较，比如模式串abcd…nab…dqmab，已经成功匹配了dqmab。下一个字符匹配失败，查找模式串中是否存在dqmab最大后缀的匹配, 不移动nab的ab到dqmab对齐，因为字符n和字符m不同，通过指针pptr控制。
abcd中的ab可以移动到dqmab的ab对齐，通过ptrn指针控制。*/
int *make_shift(char *ptrn, int plen)
{
int *shift = (int *)malloc(plen * sizeof(int));
int *sptr = shift + plen - 1;//shift最后
char *pptr = ptrn + plen - 1;//模串最后
char c;
if (shift == NULL)
fprintf(stderr, "malloc failed!");
c = ptrn[plen - 1];//模串最后一个字符
*sptr = 1;
while (sptr -- != shift)
{
char *p1 = ptrn + plen - 2, *p2, *p3;
do
{
while (p1 >= ptrn && *p1-- != c);
p2 = ptrn + plen - 2;
p3 = p1;
while (p3 >= ptrn && *p3-- == *p2-- && p2 >=pptr);
}while (p3 >= ptrn && p2 >= pptr);
*sptr = shift + plen - sptr + p2 - p3;
pptr--;
}
return shift;
}
匹配函数的实现
/*在匹配过程中，匹配失败了，取坏字符跳转和好后缀跳转中的大者*/
int mSearch(char *buf, int blen, char *ptrn, int plen, int *skip, int *shift)
{
int b_idx = plen;
int test_cmp_num = 0;
if (plen == 0)
return 1;
while (b_idx <= blen)
{
int p_idx = plen, skip_stride, shift_stride;
while (test_cmp_num ++,buf[--b_idx] == ptrn[--p_idx])
{
if (b_idx < 0)
return 0;
if (p_idx == 0)
{
printf("compare number = %d \\n",test_cmp_num);
return b_idx;
}
}
skip_stride = skip[(unsigned char)buf[b_idx]];
shift_stride = shift[p_idx];
b_idx += (skip_stride > shift_stride) ? skip_stride : shift_stride;
}
printf("compare number = %d \\n",test_cmp_num);
return 0;
}
总结
BM算法是Boyer-Moore算法的缩写，贝叶-莫尔算法，是一种基于后缀比较的模式串匹配算法。目前所知的最快的单键字符匹配算法。
Copyright © 2019-2026 51dongshi.net 版权所有
违法及侵权请联系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市万商天勤律师事务所王兴未律师提供法律服务
