一种基于汉字编码特征的中文多模式匹配算法

黄　宇,　侯整风,　余　虎,　刘春晖

(合肥工业大学 计算机与信息学院,安徽 合肥　230009)



一种基于汉字编码特征的中文多模式匹配算法

黄宇,侯整风,余虎,刘春晖

(合肥工业大学 计算机与信息学院,安徽 合肥230009)

对于大规模中文模式串匹配,由于汉字的散度较高,导致AC算法有限状态自动机中的零状态过长,算法的效率急剧下降。文章提出了一种基于汉字编码特征的改进算法,考虑到汉字的首字节范围比尾字节的小,先查找首字节,再查找尾字节,若失败则直接跳转,降低了查找时间。该算法通过给零状态中字符设置标记,有效避免重复匹配和部分匹配,提高了匹配效率。

AC算法;多模式匹配;汉字编码特征;标记

模式匹配算法是信息领域的重要内容,广泛应用于搜索引擎[1]、网络入侵检查系统[2-3]、DNA序列匹配[4]等领域。单模式匹配中,BM (Brute-Force)算法[5]运用坏字符规则和好后缀规则来计算模式串右移距离,实现了模式串的跳跃式匹配。BMH (Brute-Force-Horspol)算法[6]是对BM算法的改进,该算法仅考虑坏字符规则,简化预处理,提高了匹配效率;AC (Aho-Corasick) 算法[7]是一种经典的多模式匹配算法,该算法基于有限状态自动机,通过状态转移,扫描一遍文本串可匹配多个模式串。AC_BM算法[8]是AC算法的改进,其结合BM算法的模式串的跳跃式移动的思想,可跳跃式匹配,但跳转距离过于保守,平均跳转距离较小。文献[9]利用Tuned BM算法的思想计算平均跳转距离,提出AC_Tuned BM算法;文献[10]提出的IACBM算法利用BMH和QS算法的思想计算平均跳转距离。 上述方法在一定程度上增加了平均跳转距离,但没有考虑到有限状态自动机的存储结构对跳跃式匹配过程的影响。

由于汉字字符的散度较高,随着模式串的增加,基于AC算法的中文多模式匹配算法需要巨大的空间开销,从而导致goto状态转移函数计算量大,算法的时间复杂度急剧增加,不适合大规模中文模式匹配。采用Hash表[11]和压缩稀疏矩阵[12]存储有限状态机,虽然在一定程度上有所改善,但当模式串的数量巨大时,Hash表存储方式由于内存消耗过大,算法效率下降;稀疏矩阵的存储方式压缩率也不是很高,所需存储空间仍然较大,Cache命中率下降,频繁进行缺页中断操作。文献[13]采用状态编码以消除不必要转移,试图减小存储空间开销,但对中文模式匹配,这种“不必要转移”较少,存储空间开销依然巨大,导致算法的效率依然不是很高;文献[14]尝试用位图压缩来存储,对中文模式串压缩率约为25%,没有从根本上解决内存消耗过大、Cache命中率下降问题；文献[15]提出的邻接链表存储方式,虽然考虑到存储结构对模式匹配的影响,但是由于零状态过长,查找效果依然不是很理想。

本文提出一种基于汉字编码特征的改进算法,建立首字节桶和匹配桶,首先查找首字节,查找成功则查找尾字节;并设置标记,减少了查找跳转距离次数,有效避免了重复匹配和部分匹配。与传统的AC算法及其改进算法相比,本文算法降低了算法的时间复杂度。

1　AC算法

1.1预处理

(1) 构造有限状态自动机。设模式串集合P={p1,p2,…，pi，…，pn}。对P中的每个模式串pi,初始状态设为0。每次添加都是从状态0开始,逐个取出pi中的每一个字符;如果从当前状态出发发现已存在标注该字符的矢线,则将矢线所指的状态作为当前状态;否则,添加1个新状态作为当前状态,新状态为已有的最大状态加1。当处理完P中的所有字符串,最后添加一条始于状态0止于状态0的自反线,并标注始于状态0的字符集。例如P={what,how,where,when},有限状态自动机如图1所示。

(2) goto函数。goto函数用于计算当前状态的下一状态。若能从当前状态出发可以找到标注字符 “c” 的矢线,则goto函数返回矢线所指的状态,否则返回跳转失败状态fail。由图1可知,goto(0,w)=1,goto(2,e)=8,goto(1,a)=fail。

(3) failure函数。failure函数是在字符匹配失败时跳转的依据。状态s的深度depth(s)定义为从状态0到状态s的最短路径长度。由图1可知,状态1和状态5的深度为1。设状态r的父状态为s,标注的字符为“c”。若depth(s)=0,则failure(r)=0;否则 failure(r)=goto(failure(s),c)。由图1可知,failure(5)=0,failure(2)=goto(0,h)=5。

图1　有限状态自动机

(4) output函数。output函数用来输出成功匹配的模式串。在构造有限状态自动机的过程中,当处理完一个模式串pi后,将该模式串pi加入到当前状态的输出函数中。

在计算失效函数过程中,若failure(r)=r′,则output(r)=output(r)∪output(r′)。由图1可知,output(7)={how},output(4)={what}。

1.2匹配过程

(1) 将当前状态r置为0,文本串指针指向文本串的首字符。

(2) 若文本串的当前指针不为空,则取出指向的字符“c”;否则匹配过程结束。

(3) 计算r′=goto(r,a)。若r′≠fail,则r=r′,文本串指针向右移动1位,计算output函数,若output(r)=NULL,转步骤(2);否则,输出output(r)的值,表示有模式串匹配成功,转步骤(2)。

(4) 若r′=fail,调用failure函数,即当前状态r=failure(r′),转步骤(3)。

2　存储结构

2.1常用存储结构

(1) 状态矩阵存储方式。状态矩阵为每个状态s建立一个数组As,As中的值表示匹配成功时所跳转的状态。所有的As组成一个二维矩阵N[0…i][0…j],其中,0…i表示状态;0…j表示所有模式串中不重复的字符。由于汉字的散度较高,随着模式串的增大,这种存储结构所需存储空间迅速增加。

(2) 完全哈希表存储方式。对于单字节的英文字符,其完全哈希表所占用的空间为Num(state)×256,其中Num(state)为状态数目,对于中文字符串,占用的空间为Num(state)×256×256。随着模式串数目的增大,状态数随之增大,导致内存消耗过大。

(3) 邻接链表存储方式。对于邻接链表存储方式,虽然占用的存储空间比状态矩阵和完全哈希表存储方式有所降低,但是零状态过长,增加了查找时间,导致算法的时间效率依然不是很高。

2.2带标记的混合存储结构

本文采用混合存储结构，算法的匹配效率不仅由跳转距离决定,有限状态机的存储方式对匹配亦有影响,并考虑到重复匹配和部分匹配以及重复查找跳转距离带来的时间开销,增加跳转标记和匹配标记,使算法效率得到提高。

2.2.1混合存储结构

汉字的散度较高,使用邻接链表存储时,导致零状态过长,基于这一特征,本文采用首字节桶和匹配桶存储零状态字符。每个汉字存储占用2个字节,如GBK编码,首字节的范围是81—FE,126个,尾字节的范围是40—FE,190个。

首先建立一个首字节桶,其大小为126字节,依次编号81,82,…,FE,每字节存储的内容与其编号相同,存储所有零状态中字符的首字节,且不重复存放。例如模式串集P={好声音,热播,平凡人,奇迹,理念},各模式串首字符的首字节存储方式如图2所示。

图2　首字节桶

再建立190个匹配桶,编号40,41,…,FE。每个桶由2个域组成,首字节域保存某一字符尾字节对应的首字节,跳转状态域保存跳转到头结点表中的位置。例如模式串集P={好声音,热播,平凡人,奇迹,理念},各模式串首字符的匹配桶如图3所示。图3中,“首域”指首字节域,“跳域”指跳转状态域。当匹配桶中含有不止1个字符的首字节时,每增加1个字符就在桶中增加1组首字节域、跳转状态域。

图3　匹配桶

模式串集P={好声音,热播,平凡人,奇迹,理念}的混合存储结构如图4所示。其中,首字节桶如图2所示,匹配桶如图3所示。

图4　混合存储结构

在查找时首先在首字节桶中查找,如果成功则查找匹配桶,失败则跳转。查找成功时则根据跳转状态域信息在头结点表中找到某状态，然后继续匹配，此举降低了goto函数的计算时间,提高了算法效率。

2.2.2跳转标记及匹配标记

(1) 跳转标记。考虑到汉字散度较高,本文在构造跳转距离表时借鉴了BMH算法,构建链表时添加1列跳转距离标记,能同步完成状态查询和跳转距离查询,提高了时间效率。

设当前模式串的长度为l,最短模式串长度为m,字符“c”在有限状态自动机中的状态为s,在模式串中的位置为p。字符“c”的跳转距离d(c)=l-p(c),初始时跳转距离表为空,查询跳转距离表,依次取出模式串中的每个字符；若字符“c”未出现在跳转距离表中,则将跳转距离和状态s写入到跳转距离表中;否则,将查询到的跳转距离d′(c)与d(c)的较小者和状态s写入到跳转距离表中。模式串的尾字符跳转距离设为l,未在模式串中出现的字符(统一用*表示)跳转距离取为m。模式串集P={好声音,热播,平凡人,奇迹,理念}的跳转距离见表1所列。

表1　跳转距离表

在链表中设置跳转标记,可以同步完成状态查询和跳转距离查询,避免了重复多次查找带来的时间开销,提高了算法的时间效率。

(2) 匹配标记。由于模式串中的字符在文本串中往往不止1次出现,会造成模式串重复匹配的情况,也会出现模式串的首字符或前几个字符匹配,但后面字符匹配失败的情况,即半匹配。设置匹配标记,能有效避免重复匹配和部分匹配导致的时间开销,随着匹配的进行,标记的作用越来越明显。

在匹配桶中为每个字符后增加1项匹配标记,用于记录字符在模式串中出现的次数。匹配标记是动态的,每成功匹配1个模式串,对应的标记位减1,当某零状态的标记为0时则直接跳过,不再匹配该模式串。模式串集P={好声音,热播,平凡人,奇迹,理念},各模式串首字符带标记的匹配桶如图5所示,其中“首域”指首字节域,“跳域”指跳转状态域,“匹域”指匹配标记域。

图5　带匹配标记的匹配桶

模式串集P={好声音,热播,平凡人,奇迹,理念}的混合存储结构如图6所示,其中,首字节桶如图2所示,匹配桶如图5所示。

图6　带标记的混合存储结构

3　本文的多模式匹配算法

本文基于汉字编码特征,提出一种优化查找方法,首先查找首字节桶，仅当查找成功时才查找匹配桶，减少了匹配桶查找次数。此外,设置标记,减少重复匹配和部分匹配以及重复查找跳转距离带来的时间开销。

3.1预处理

预处理需构造有限状态自动机及计算转移函数goto、失效函数failure和输出函数output,根据有限状态自动机建立带标记的链表,并建立首字节桶和匹配桶。

设模式串集合P={p1,p2,…,pi,…,pn},模式串pi的长度为li,字符 “c”在有限状态自动机对应的状态为s,在pi中的位置为local (c)。

(1) 有限状态自动机的构造过程与AC算法一样。

(2) 构建初始链表。建立头节点表v,用于记录单链表头地址。对于模式串集中的每个模式串pi,初始状态为状态0。逐个取出模式串pi中的每个字符,搜索首个头节点表v后面的单链表的字符域;若找到字符域为该字符的节点,则将该节点的状态域的值i作为当前状态,并跳转到v[i];否则,添加1个新头节点,新节点的状态域为已有的最大状态加1,字符域为当前读入的模式串的字符,继续对pi中的下一个字符进行处理。

(3) 构建带标记的链表。首先,构造跳转距离表。在头节点表状态列后增加1列,根据跳转距离表，将跳转标记加上去。然后,设置初始匹配标记。在构建链表时,新的表节点中的匹配标记域设为1,当零状态中再次出现已存在的字符,其匹配标记域加1,匹配标记记录模式串中字符在零状态中出现的次数。

(4) 计算failure函数及output函数。计算过程同AC 算法。

(5) 构建首字节桶和匹配桶。

3.2匹配过程

(1) 将当前状态s初始化为0,文本串指针指向文本串的首字符。

(2) 若文本串指针不为空,则取出所指的字符“c”,否则匹配过程结束。

(3) 利用状态转移函数,计算s′=goto(s,c)。若s=0,首先查找首字节桶,如果查找成功则继续查找匹配桶,根据匹配桶中的跳转状态域值跳转到链表中继续匹配,同时查看匹配标记，如果为0则跳转;如果查找失败则跳转。

(4) 若s′≠fail,则s=s′;否则,转步骤(5)。若output(s)=NULL,转步骤(2);如果output(s)≠NULL,输出output(s)的值,表示有模式串匹配成功,将模式串中字符对应的匹配标记减1，转步骤(2)。

(5) 调用failure函数,计算当前状态s=failure(s)。

(6) 若s≠0,根据当前状态s直接在带跳转标记的头节点链表中的“跳转距离域”得到跳转距离d,文本串指针向右移动d位,转步骤(2)。

例如,模式串集P={好声音,热播,平凡人,奇迹,理念},文本串为“中国好声音的热播再次将平凡人创造奇迹的选秀理念推向高潮”，匹配过程见表2所列。

表2　匹配过程表

4　时间复杂度分析

基于有限状态自动机的多模式匹配算法的时间开销主要分为计算goto状态转移函数和跳跃式匹配过程2个部分。

(1) goto状态转移函数时间复杂度。带标记位的链表存储方式计算goto状态转移函数，实质上是2次直接存取,首先在首字节桶中查找,再查找匹配桶,首字节桶的大小为126,匹配桶一共190个,根据汉字编码特征,匹配桶中最多只有126组数据,3次都是常量级的查找,所以时间复杂度为O(1)。

(2) 跳跃式匹配时间复杂度。跳跃式匹配的时间复杂度与各个字符出现的概率有关。文献[5]中提出了一种概率模式,即通过发现失配字符所花的代价和能够跳转的距离之比来计算跳跃式匹配的时间复杂度,计算公式为:

时间复杂度=

(1)

其中,m表示模式串在长度为m处失配;cost()为搜索所花的代价；prob()为发生失配的概率;k为失配时可跳转的距离;skip(m,k)为失配后可跳转的概率。

考虑到有限状态自动机对跳跃式匹配过程的影响,本文对这一模型进行拓展,计算公式为:

时间复杂度=

(2)

其中,seanum(k)表示为得到跳转距离k,在跳转距离表中搜索的次数;n为重复匹配和半匹配的次数。通常,不同的跳跃式匹配算法的cost(m)、prob(m)及skip(m,k)基本相同,本文算法可同时完成状态和跳转距离的查询,seanum(k)为1,而其他跳跃式匹配算法如AC_BM、IACBM等需搜索跳转距离表,seanum(k)远大于1。同时,在文本串中与模式串中首字符相同的字符常不止1处,因此n常大于1。而本文算法n=1,因此,本文算法跳跃式匹配过程的时间性能最优。

5　测试结果与分析

测试环境:CPU为Intel(R) Core(TM) i5-3210M,2.50 GHz,内存2 G,操作系统为Microsoft Windows 7 Professional Service Pack 1,VC++6.0语言实现。

为了验证算法的有效性,选取AC_BM、IACBM、AC_Tuned BM算法进行对比。4种算法的平均跳转距离如图7所示。

图7　4种不同算法的平均跳转距离

模式串集取自百度过滤关键词集,关键词集中二字词、三字词、四字词、多字词约占61.8%、12.7%、22.6%、2.9%。每次实验从中随机取出一定数量的中文模式串。测试文本为5个不同的中文文本(约为13 M),每个文本测试10次,最后取其平均值。从图7可知,随着模式串的增加,本文算法跳转距离约为AC_BM算法平均跳转距离的1.6倍,AC_Tuned BM算法的1.4倍,IACBM算法的1.3倍。跳跃式匹配算法的时间性能很大程度上取决于平均跳转距离，平均跳转距离越大，则时间性能越好，因此，本文算法的时间性能最优。

6　结　　论

考虑到汉字的散度较高,本文对零状态的查找做了优化处理,加快了查找速度;同时设置跳转标记和匹配标记,有效降低了查找跳转距离和重复匹配以及部分匹配带来的时间开销。最后对不同匹配算法的平均跳转距离进行了测试,测试结果及分析表明,本文算法的平均跳转距离和时间性能都优于AC_BM算法、AC_Tuned BM算法及IACBM算法。

[1]赵珂,逯鹏,李永强.基于 Lucene 的搜索引擎设计与实现[J].计算机工程,2011,37(16):39-41.

[2]董明明,巩青歌,张琦.入侵检测系统中模式匹配算法的改进 [J].计算机应用与软件,2011,28(5): 272-274.

[3]郑礼良,吴国凤,胡晓明,等.基于Snort的入侵检测系统的研究与改进[J].合肥工业大学学报(自然科学版),2011,34(4):529-532.

[4]WHEELER D L,CHAPPEY C,LASH A E,et al.Database resources of the National Center for Biotechnology Information[J].Nucleic Acids Research,2007,28(1):10-14.

[5]BOYER R S,MOORE J S.A fast string searching algorithm[J].Communications of the ACM,1977,20(10):762-772.

[6]HORSPOOL R N.Practical fast searching in strings[J].Software：Practice and Experience,1980,10(6):501-506.

[7]AHO A V,CORASICK M J.Efficient string matching: an aid to biographic search[J].Communications of the ACM,1975,18(6):333-340.

[8]COMMENTZ-WALTER B.A string matching algorithm fast on the average [C]//Proceedings of 6th ICALP,1979:118-132.

[9]殷丽华,方滨兴,张宏莉.快速的多模式匹配算法[J].哈尔滨工业大学学报,2007,39(12):1925-1929.

[10]陈牮华.网络入侵检测系统中的模式匹配算法优化研究[J].计算机仿真,2011,28(2):160-162.

[11]王永成,沈州,许一震.改进的多模式匹配算法[J].计算机研究与发展,2002,39(1):55-60.

[12]NORTON M.Optimizing pattern matching for intrusion detection [EB/OL].(2006-05-11)[2015-03-10].https://static.aminer.org/pdf/PDF/000/309/890/optimizing-pattern-matching.pdf.

[13]杜文超,陈庶樵.一种基于双重状态编码的多模式匹配算法[J].计算机应用研究,2012,29(5):1887-1890.

[14]张元竞,张伟哲.一种基于位图的多模式匹配算法[J].哈尔滨工业大学学报,2010,42(2):277-280.

[15]侯整风,杨波,朱晓玲.一种节约内存的中文多模式匹配算法[J].微型机与应用,2013,32(13):53-57.

(责任编辑张淑艳)

A Chinese multi-pattern matching algorithm based on the characteristic of Chinese character coding

HUANG Yu, HOU Zhengfeng, YU Hu, LIU Chunhui

(School of Computer and Information, Hefei University of Technology, Hefei 230009, China)

For large-scale patterns in Chinese string matching, the higher divergence of Chinese characters makes zero state in finite state automata of AC algorithm overlong, and this leads to sharp decline in the efficiency of algorithm. For this problem, a new algorithm based on the characteristic of Chinese character coding is proposed. Considering the range of the first byte in characters is smaller than that of the trail byte, this algorithm finds the first byte first, and then searches the trail byte, if fails, jump directly, reducing the search time. Through setting tags to characters of zero state, reduplicate and partial matching can be avoided effectively, which improves the matching efficiency.

AC algorithm; multi-pattern matching; characteristic of Chinese character coding; tag

2015-03-27；

2015-04-21

教育部广东省产学研资助项目(2009B090200049)

黄宇(1988-),男,安徽淮南人,合肥工业大学硕士生;

侯整风(1958-),男,安徽和县人,合肥工业大学教授,硕士生导师.

10.3969/j.issn.1003-5060.2016.08.011

TP393.08

A

1003-5060(2016)08-1060-06