一种基于Aho?Corasick算法改进的多模式匹配算法
陈永杰 吾守尔·斯拉木 于清
关键词： 字符串匹配; 多模式匹配; Trie树; 双数组; AC算法; 匹配速度
中图分类号： TN919?34; TP301.6 ? ? ? ? ? ? ? 文献标识码： A ? ? ? ? ? ? ? ? ? ?文章编号： 1004?373X（2019）04?0089?05
An improved multi?pattern matching algorithm based on Aho?Corasick algorithm
CHEN Yongjie， Wushour Silamu， YU Qing
（School of Information Science and Engineering， Xinjiang University， Urumqi 830046， China）
Abstract： There exists a large amount of text data on the Internet currently. In allusion to the problem that how to search out multiple different target character strings accurately and quickly in such large text， an improved fast multi?pattern matching algorithm is proposed on the basis of introducing the advantages and disadvantages of common pattern matching algorithms， and combining with the idea of converting the Trie tree into the double array form. A comparison experiment was carried out. The analysis results show that the improved AC algorithm can successfully match all the to?be queried pattern strings in the text， and its matching speed is about 5 times of that of the AC algorithm， which shows that the improved AC algorithm has good effects in aspects of matching speed， recall ratio and space utilization rate.
Keywords： character string matching; multi?pattern matching; Trie tree; double array; AC algorithm; matching speed0 ?引 ?言
当今信息社会，数据量空前的庞大，如何快速正确地从百万字符的文本中找到想要的字符是当前研究的一个热点，这就催生出字符串模式匹配[1]这个研究领域。模式匹配的概念：字符串模式匹配是从指定的文本当中，通过某种方式找到想要的字符或者字符串。把这个文本称为目标串，把要找到的字符或者字符串称为模式串。经过几十年的发展，字符串模式匹配广泛应用于计算机、敏感词检测、生物学、文本处理、统计等领域。当前也存在许多匹配算法，根据模式个数的多少可以分为两种算法：一种是单模式匹配算法;另一种是多模式匹配算法[2]，单模式匹配代表算法有BF算法、KMP算法、Sunday算法等，多模式匹配算法有AC自动机等[3]。
BF算法是一种最基本的匹配算法，该算法要求逐个比较目标串和模式串中的字符，若匹配正确，则继续匹配，否则取当前目标串字符随后的字符，继续与模式串的首字符进行匹配。当目标串和模式串的长度分别为a，b，则BF算法的时间复杂度最大为O（ab），而在一般的实际应用中近似为O（a+b），不过在有些情况下算法效果会大大降低。文献[4]改良了传统的BF算法，虽然效率有所提高，但是在某些情况下会出现匹配次数不减反增的异常情况。
KMP算法的核心思想是假如字符对比不成功，则根据已匹配成功的子串将模式串向右移动最大的距离后再进行匹配。例如：目标串为“abcabcde”，模式串为“abcabb”，当第6个字符时匹配失败，这时匹配成功的子串是“abcab”;发现子串的前缀和后缀都存在“ab”，长度为2，则模式串向右移动2个距离，即从子串的第三个字符“c”与目标串的下一个字符即第7个字符“d”进行比较。由于BF算法的每次移动距离为1，所以KMP算法有着较高的效率，但当目标串和模式串有多个一样的字符时会重复匹配，这会影响算法的效率。
Sunday算法：当目标串和模式串匹配失败的时候，Sunday算法会先得到目标串中下一个未匹配的字符，如果该字符在模式串当中，则移动的长度为模式串中最右端的该字符到结束的字符长度，否则移动的长度为模式串的字符个数加1。例如，目标串为“abcabcde”，模式串为“abcabb”，当第6个字符时匹配失败，而且目标串的下一个字符为“d”，字符“d”在模式串中未出现，则移动距离为6+1，即字符“e”，用该字符继续从模式串的首字符“a”依次进行匹配，对比KMP算法，Sunday移动的距离更大，所以效率更高。文献[5]改进了该算法，根据是否满足条件去掉了冗余的匹配，给出了一种执行效率更高的算法。
针对常见模式算法的特点，本文结合Trie树转化成双数组形式的思想，提出一种改进的快速多模式匹配算法。1 ?AC算法及双数组Trie树
1.1 ?AC算法
AC（Aho?Corasick）算法属于多模式匹配算法，能够从文本中匹配出多个字符串，也能够得到这些字符串的相关信息，比如位置和总数。假定目标串T的总长为n，模式串集合为P={p1，p2，…，pm}，则时间复杂度是O（n），也就是在该复杂度内，必定能在n内匹配到所有的模式串，不会受m大小的影响。
AC算法本质上由3张表组成，也就是goto表：字符匹配成功时从一个状态转移到另一个状态，根据全部的模式串创建的状态转移自动机;fail表：字符匹配失败时从一个状态转移到对应的失败状态;output表：是由匹配成功的模式串构成。
设模式串集合P={新疆，美丽的新疆，新中国，新疆大学}，目标串为T=“新疆大学位于新中国美丽的新疆自治区”，以此为例说明AC算法的构造过程：
步骤1：goto表的构建。用goto（i，c）表示状态i匹配字符c后的下一个状态，goto表本质上是根据模式串集合P构造的确定有限状态自动机，首先将“新疆”构建到goto表中，用公式表示为goto（1，‘疆）=2，依次将模式串集合中剩余的模式串加入goto表，最终得到如图1所示的有限状态自动机[3]。
步骤2：fail表的构建。fail（i）在状态匹配不成功时转移到下一个状态。和状态0相邻的全部状态的失败状态均为状态0。比如在图1中，状态1与状态0相邻，则fail（1）=0。对于其他与状态0不相邻的状态，设当前状态为S2，S2前一状态为S1，则状态S的失败跳转状态为fail（S）=goto（fail（S1），c）。最终得到的fail表如表1所示。
步骤3：output表的构建。根据图1的有限状态自动机可知，圆圈带阴影的4个状态是输出状态，当目标串沿着自动机达到这几个状态时，说明匹配成功了相应的模式串。使用output表存储这一可输出状态，在确定有限状态自动机中用背景为灰色的圆圈表示。得到output表如表2所示。下面进行匹配，匹配的方法：从初始状态0开始进行匹配，若字符相同，则根据完整自动机，当前状态跳转到对应的状态，当到达可输出状态（背景为阴影的状态）时表示模式匹配成功，则根据output表输出对应模式串;若字符不同，则当前状态变为对应的fail状态，然后进行下一步匹配。具体过程为：
1） 自动机从0状态出发，首先按照goto表（实线）进行字符匹配;
2） 接收目标串首字符“新”，字符匹配成功，转移到状态1;
3） 接收字符“疆”，字符匹配成功，转移到状态2，因为状态2是输出状态，根据output表输出模式串“新疆”;
4） 依次接收字符“大”“学”，转移到状态11，根据output表输出模式串“新疆大学”;
5） 接收字符“位”，字符匹配失败，跳转到状态11的失败状态0，同理接收字符“于”，跳转到状态0;
6） 依次接收字符“新”“中”“国”，跳转到状态9，输出模式串“新中国”;
7） 依次接收字符“美”“丽”“的”“新”“疆”，跳转到状态11，输出模式串“美丽的新疆”和“新疆”;
8） 最后匹配字符“自”“治”“区”，无模式串输出。
1.2 ?双数组Trie树
Trie树[6]是哈希树的另一种表示形式，空间复杂度为O（n），数据结构通常很繁琐，占用的空间比较大，为了解决这些问题，Aoe. J用2个数组构建Trie树，即双数组Trie树[7?8]。
双数组Trie[9]由两个正数数组表示，即base[]和check[]，在数组中，状态和数组下标是一一对应并且值相等，即状态s所对应的数组下标也是s。状态转移需要满足式（1）式（2），其中c是收到的字符，s是当前状态，t是下一状态。
[checkbases+c=s] ? ?（1）
[bases+c=t] ? ? ? ? （2）
状态转移图如图3所示。状态s所对应的base值为base[s]，接收字符c后转移到状态t，即t=base[s]+c，而状态t所对应的check数组值为s，即check[t]=s。以图1为例，结合以上条件构建双数组Trie的过程如下：
1） 字符编码。按照模式串P中字符的入树顺序对字符进行编码，得到编码结果为：新?1，美?2，中?3，疆?4，丽?5，国?6，大?7，的?8，学?9。其称之为字符序列码表[3] ;
2） 接收字符“新”，由于“新”的序列码为1，所以对应的数组位置为1，初始化为base[1]=1，check[0]=0;
3） 接收“中”，在数组当中的索引值為前一状态对应的base值和接收字符的编码值之和，即base[1]+3=4，因而base[4]=base[1]=1，check[4]=1。接收 “国”，同理，base[base[4]+6]=base[7]=1，check[7]=4。依次接收所有的字符，根据条件确定相应的值。
4） 如果index对应的是结束状态，使base[index]=（-1）* index，比如index=7对应的字符串“新中国”是结束状态，则base[7]=-7;如果index对应的是中间输出状态，则base[index]=（-1）*base[index]，比如index=5，“新疆”是输出状态但不是结束状态，则令base[5]=（-1）*
base[5]=-1，同理将其他所有结束状态设置为相应的值。
最终得到如表3所示的双数组表。
匹配过程：以匹配“新中国”为例，接收字符“新”，根据序列码表定位到数组的位置为index=1，base[1]=1为非输出状态;继续接收字符“中”，定位到index=base[1]+3=4，为非输出状态;继续接收字符“国”，定位到index=base[4]+1=7，得到base[7]=-7，是输出状态，从而得到匹配结果为“新中国”。
当进行字符个数为n的单模式字符串查询时，双数组Trie的时间复杂度为O（n），但是对于多模式查询，首先要进行前缀的匹配，之后通过多次获得文本后缀方可实现多模式查询，从而造成进行多次目标串匹配的问题，因而当进行多模式匹配时效率很差。
2 ?改进AC算法
由第1节可知，AC自动机在多模式匹配方面效率很高，但是占用空间过大;双数组Trie树虽然解决了Trie树占用空间大的问题，但是在多模式匹配方面性能不理想，所以在此介紹一种结合两者的改进方法，该方法在保证多模式匹配的前提下尽量提高匹配速度和减少占用的内存。
改进AC算法主要思想：将AC自动机的3张表（goto表、fail表和output表）以数组的形式表示，与双数组Trie树的base，check数组相结合，形成一种多数组关系。
base数组本质就是一种状态转移，即字符匹配成功跳向下一状态，匹配失败跳向根节点，所以base数组与goto表的作用是一样的，所以只需将剩下的fail表，output表转换成数组形式。改进AC算法图示如图4所示。
字符匹配流程图如图5所示。字符串匹配过程为：
步骤1：初始状态o收到字符c;
步骤2：若字符匹配成功，则跳到下一状态t=base[s]+c;若字符匹配失败，则跳到下一状态o=fail[s];
步骤3：若base[t]<0（或者base[o]<0），则状态t（或者o）是输出状态，输出模式串output[t]（或者output[o]），否则不输出;
步骤4：将状态t（或者o）设为当前状态，取下一个字符，转到步骤2继续匹配，直至目标串中的所有字符完成匹配。3 ?实验及结果分析
本实验的硬件环境是CPU 3.4 GHz（Intel Core i7 4770），内存为8 GB，64位Windows 10操作系统，软件使用的是Myecplise 2014。模式串的数据来自《现代汉语常用词汇表》，总计38 285个词汇，其中双字词23 573个、三字词5 289个、四字词9 423个;目标串数据来自文学作品《平凡的世界》的完整版，大小为2.28 MB，大约共79万字。总共进行两项实验，分别为多模式匹配查全率实验和匹配速度实验。
3.1 ?多模式匹配查全率实验
该实验目的是验证改进AC算法能否进行多模式匹配，以及能否返回目标串中所有的本文所要匹配的模式串。实验是以使用Microsoft Word的查找功能得到的结果为比较标准，假如通过Word查找功能得模式串的个数共有m个，通过改进AC算法得到的模式串的个数为n个，则查全率R为：
[R=nm] ? ? ? （3）
式中：R的值为1时，说明能够查找到全部的模式串;越接近于1，说明改进AC算法的查找效果越好。
随机抽取9个词语为样本，作为模式串集合，得到的实验数据及结果如表5所示。
根据表5中的数据和式（3）计算出改进AC算法的查全率R：
[24+19+1+5+121+36+124+16+124+19+1+5+121+36+124+16+1=1]
查全率R为1，说明改进AC算法不仅能够进行多模式匹配，而且可以匹配到目标串中全部的结果，查全率达到了要求的水平。
3.2 ?匹配速度实验
该实验在相同的条件下比较了AC算法和改进AC算法的匹配速度，根据模式串个数的不同共进行8组测试，分别为模式串个数为5 000，10 000，…，35 000和38 285。为了避免由于偶然性所导致的异常结果，每个模式串组分别进行10次匹配，对得到的匹配时间求平均值。最终得到对比结果如图6所示。
从图6中可以看出，改进AC算法的匹配时间明显低于AC算法的匹配时间，在模式串个数为30 000个时，改进AC算法匹配所有的2.28 MB目标串只需50 ms，匹配速度达到了45.6 MB/s，而AC算法的匹配速度为10.2 MB/s，改进AC算法的匹配速度是原AC算法的4～5倍，说明改进AC算法的匹配速度要远远高于AC算法的匹配速度。
4 ?结 ?语
本文介绍AC算法和双数组Trie树的原理，在此基础之上将双数组Trie树的思想应用于AC算法，也就是用数组表示AC自动机的多模式匹配算法。通过实验对比原有算法和改进AC算法的查全率和速度可知：改进AC算法不仅能够匹配出所有的模式串，而且匹配速度提高了4～5倍，改进AC算法取得了良好的效果。
参考文献
[1] 蒋莉莉.字符串模式匹配算法的改进研究[J].电脑知识与技术，2008（3）：526?528.
JIANG Lili. The research of improved matching algorithm of string pattern [J]. Computer knowledge and technology， 2008（3）： 526?528.
[2] 张利香.基于后缀数组的字符串模式查找的算法[D].兰州：西北师范大学，2010.
ZHANG Lixiang. The string pattern searching algorithms based on suffix arrays [D]. Lanzhou： Northwest Normal University， 2010.
[3] 杨波.基于有限状态自动机的中文多模式匹配算法研究[D].合肥：合肥工业大学，2013.
YANG Bo. Research on multi?pattern matching algorithm for Chinese based on finite state automata [D]. Hefei： Hefei University of Technology， 2013.
[4] 蔡恒，张帅.基于BF算法改进的字符串模式匹配算法[J].电脑编程技巧与维护，2014（22）：14?15.
CAI Heng， ZHANG Shuai. An improved string pattern matching algorithm based on BF algorithm [J]. Computer programming skills & maintenance， 2014（22）： 14?15.
[5] 李明月，张善卿，陆剑锋，等.一种改进的Sunday匹配算法[J].杭州电子科技大学学报（自然科学版），2015，35（1）：93?96.
LI Mingyue， ZHANG Shanqing， LU Jianfeng， et al. A modified Sunday matching algorithm [J]. Journal of Hangzhou Dianzi University （Natural Sciences）， 2015， 35（1）： 93?96.
[6] 刘丽霞，张志强.基于Trie树的相似字符串查找算法[J].计算机应用，2013，33（8）：2375?2378.
LIU Lixia， ZHANG Zhiqiang. Similar string search algorithm based on Trie tree [J]. Journal of computer applications， 2013， 33（8）： 2375?2378.
[7] YANG Wenchuan， FANG Zeyang， LI Pengfei. Study for the double?array Trie tree based algorithm in word segmentation [C]// Proceedings of 2015 International Conference on Computer Science and Environmental Engineering. Beijing： DEStech Publications Inc.， 2015： 7.
[8] 徐聪，张丰，杜震洪，等.基于哈希和双数组Trie树的多层次地址匹配算法[J].浙江大学学报（理学版），2014，41（2）：217?222.
XU Cong， ZHANG Feng， DU Zhenhong， et al. A multi?level address?matching algorithm based on Hash function and double?array Trie?tree [J]. Journal of Zhejiang University （Science edition）， 2014， 41（2）： 217?222.
[9] KAROONBOONYANAN T. An implementation of double?array Trie [EB/OL]. [2018?11?21]. https：//linux.thai.net/～thep/datrie/datrie.html.
关键词： 字符串匹配; 多模式匹配; Trie树; 双数组; AC算法; 匹配速度
中图分类号： TN919?34; TP301.6 ? ? ? ? ? ? ? 文献标识码： A ? ? ? ? ? ? ? ? ? ?文章编号： 1004?373X（2019）04?0089?05
An improved multi?pattern matching algorithm based on Aho?Corasick algorithm
CHEN Yongjie， Wushour Silamu， YU Qing
（School of Information Science and Engineering， Xinjiang University， Urumqi 830046， China）
Abstract： There exists a large amount of text data on the Internet currently. In allusion to the problem that how to search out multiple different target character strings accurately and quickly in such large text， an improved fast multi?pattern matching algorithm is proposed on the basis of introducing the advantages and disadvantages of common pattern matching algorithms， and combining with the idea of converting the Trie tree into the double array form. A comparison experiment was carried out. The analysis results show that the improved AC algorithm can successfully match all the to?be queried pattern strings in the text， and its matching speed is about 5 times of that of the AC algorithm， which shows that the improved AC algorithm has good effects in aspects of matching speed， recall ratio and space utilization rate.
Keywords： character string matching; multi?pattern matching; Trie tree; double array; AC algorithm; matching speed0 ?引 ?言
当今信息社会，数据量空前的庞大，如何快速正确地从百万字符的文本中找到想要的字符是当前研究的一个热点，这就催生出字符串模式匹配[1]这个研究领域。模式匹配的概念：字符串模式匹配是从指定的文本当中，通过某种方式找到想要的字符或者字符串。把这个文本称为目标串，把要找到的字符或者字符串称为模式串。经过几十年的发展，字符串模式匹配广泛应用于计算机、敏感词检测、生物学、文本处理、统计等领域。当前也存在许多匹配算法，根据模式个数的多少可以分为两种算法：一种是单模式匹配算法;另一种是多模式匹配算法[2]，单模式匹配代表算法有BF算法、KMP算法、Sunday算法等，多模式匹配算法有AC自动机等[3]。
BF算法是一种最基本的匹配算法，该算法要求逐个比较目标串和模式串中的字符，若匹配正确，则继续匹配，否则取当前目标串字符随后的字符，继续与模式串的首字符进行匹配。当目标串和模式串的长度分别为a，b，则BF算法的时间复杂度最大为O（ab），而在一般的实际应用中近似为O（a+b），不过在有些情况下算法效果会大大降低。文献[4]改良了传统的BF算法，虽然效率有所提高，但是在某些情况下会出现匹配次数不减反增的异常情况。
KMP算法的核心思想是假如字符对比不成功，则根据已匹配成功的子串将模式串向右移动最大的距离后再进行匹配。例如：目标串为“abcabcde”，模式串为“abcabb”，当第6个字符时匹配失败，这时匹配成功的子串是“abcab”;发现子串的前缀和后缀都存在“ab”，长度为2，则模式串向右移动2个距离，即从子串的第三个字符“c”与目标串的下一个字符即第7个字符“d”进行比较。由于BF算法的每次移动距离为1，所以KMP算法有着较高的效率，但当目标串和模式串有多个一样的字符时会重复匹配，这会影响算法的效率。
Sunday算法：当目标串和模式串匹配失败的时候，Sunday算法会先得到目标串中下一个未匹配的字符，如果该字符在模式串当中，则移动的长度为模式串中最右端的该字符到结束的字符长度，否则移动的长度为模式串的字符个数加1。例如，目标串为“abcabcde”，模式串为“abcabb”，当第6个字符时匹配失败，而且目标串的下一个字符为“d”，字符“d”在模式串中未出现，则移动距离为6+1，即字符“e”，用该字符继续从模式串的首字符“a”依次进行匹配，对比KMP算法，Sunday移动的距离更大，所以效率更高。文献[5]改进了该算法，根据是否满足条件去掉了冗余的匹配，给出了一种执行效率更高的算法。
针对常见模式算法的特点，本文结合Trie树转化成双数组形式的思想，提出一种改进的快速多模式匹配算法。1 ?AC算法及双数组Trie树
1.1 ?AC算法
AC（Aho?Corasick）算法属于多模式匹配算法，能够从文本中匹配出多个字符串，也能够得到这些字符串的相关信息，比如位置和总数。假定目标串T的总长为n，模式串集合为P={p1，p2，…，pm}，则时间复杂度是O（n），也就是在该复杂度内，必定能在n内匹配到所有的模式串，不会受m大小的影响。
AC算法本质上由3张表组成，也就是goto表：字符匹配成功时从一个状态转移到另一个状态，根据全部的模式串创建的状态转移自动机;fail表：字符匹配失败时从一个状态转移到对应的失败状态;output表：是由匹配成功的模式串构成。
设模式串集合P={新疆，美丽的新疆，新中国，新疆大学}，目标串为T=“新疆大学位于新中国美丽的新疆自治区”，以此为例说明AC算法的构造过程：
步骤1：goto表的构建。用goto（i，c）表示状态i匹配字符c后的下一个状态，goto表本质上是根据模式串集合P构造的确定有限状态自动机，首先将“新疆”构建到goto表中，用公式表示为goto（1，‘疆）=2，依次将模式串集合中剩余的模式串加入goto表，最终得到如图1所示的有限状态自动机[3]。
步骤2：fail表的构建。fail（i）在状态匹配不成功时转移到下一个状态。和状态0相邻的全部状态的失败状态均为状态0。比如在图1中，状态1与状态0相邻，则fail（1）=0。对于其他与状态0不相邻的状态，设当前状态为S2，S2前一状态为S1，则状态S的失败跳转状态为fail（S）=goto（fail（S1），c）。最终得到的fail表如表1所示。
步骤3：output表的构建。根据图1的有限状态自动机可知，圆圈带阴影的4个状态是输出状态，当目标串沿着自动机达到这几个状态时，说明匹配成功了相应的模式串。使用output表存储这一可输出状态，在确定有限状态自动机中用背景为灰色的圆圈表示。得到output表如表2所示。
下面进行匹配，匹配的方法：从初始状态0开始进行匹配，若字符相同，则根据完整自动机，当前状态跳转到对应的状态，当到达可输出状态（背景为阴影的状态）时表示模式匹配成功，则根据output表输出对应模式串;若字符不同，则当前状态变为对应的fail状态，然后进行下一步匹配。具体过程为：1） 自动机从0状态出发，首先按照goto表（实线）进行字符匹配;
2） 接收目标串首字符“新”，字符匹配成功，转移到状态1;
3） 接收字符“疆”，字符匹配成功，转移到状态2，因为状态2是输出状态，根据output表输出模式串“新疆”;
4） 依次接收字符“大”“学”，转移到状态11，根据output表输出模式串“新疆大学”;
5） 接收字符“位”，字符匹配失败，跳转到状态11的失败状态0，同理接收字符“于”，跳转到状态0;
6） 依次接收字符“新”“中”“国”，跳转到状态9，输出模式串“新中国”;
7） 依次接收字符“美”“丽”“的”“新”“疆”，跳转到状态11，输出模式串“美丽的新疆”和“新疆”;
8） 最后匹配字符“自”“治”“区”，无模式串输出。
1.2 ?双数组Trie树
Trie树[6]是哈希树的另一种表示形式，空间复杂度为O（n），数据结构通常很繁琐，占用的空间比较大，为了解决这些问题，Aoe. J用2个数组构建Trie树，即双数组Trie树[7?8]。
双数组Trie[9]由两个正数数组表示，即base[]和check[]，在数组中，状态和数组下标是一一对应并且值相等，即状态s所对应的数组下标也是s。状态转移需要满足式（1）式（2），其中c是收到的字符，s是当前状态，t是下一状态。
[checkbases+c=s] ? ?（1）
[bases+c=t] ? ? ? ? （2）
状态转移图如图3所示。状态s所对应的base值为base[s]，接收字符c后转移到状态t，即t=base[s]+c，而状态t所对应的check数组值为s，即check[t]=s。
以图1为例，结合以上条件构建双数组Trie的过程如下：1） 字符编码。按照模式串P中字符的入树顺序对字符进行编码，得到编码结果为：新?1，美?2，中?3，疆?4，丽?5，国?6，大?7，的?8，学?9。其称之为字符序列码表[3] ;
2） 接收字符“新”，由于“新”的序列码为1，所以对应的数组位置为1，初始化为base[1]=1，check[0]=0;
3） 接收“中”，在数组当中的索引值為前一状态对应的base值和接收字符的编码值之和，即base[1]+3=4，因而base[4]=base[1]=1，check[4]=1。接收 “国”，同理，base[base[4]+6]=base[7]=1，check[7]=4。依次接收所有的字符，根据条件确定相应的值。
4） 如果index对应的是结束状态，使base[index]=（-1）* index，比如index=7对应的字符串“新中国”是结束状态，则base[7]=-7;如果index对应的是中间输出状态，则base[index]=（-1）*base[index]，比如index=5，“新疆”是输出状态但不是结束状态，则令base[5]=（-1）*
base[5]=-1，同理将其他所有结束状态设置为相应的值。
最终得到如表3所示的双数组表。
匹配过程：以匹配“新中国”为例，接收字符“新”，根据序列码表定位到数组的位置为index=1，base[1]=1为非输出状态;继续接收字符“中”，定位到index=base[1]+3=4，为非输出状态;继续接收字符“国”，定位到index=base[4]+1=7，得到base[7]=-7，是输出状态，从而得到匹配结果为“新中国”。
当进行字符个数为n的单模式字符串查询时，双数组Trie的时间复杂度为O（n），但是对于多模式查询，首先要进行前缀的匹配，之后通过多次获得文本后缀方可实现多模式查询，从而造成进行多次目标串匹配的问题，因而当进行多模式匹配时效率很差。
2 ?改进AC算法
由第1节可知，AC自动机在多模式匹配方面效率很高，但是占用空间过大;双数组Trie树虽然解决了Trie树占用空间大的问题，但是在多模式匹配方面性能不理想，所以在此介紹一种结合两者的改进方法，该方法在保证多模式匹配的前提下尽量提高匹配速度和减少占用的内存。
改进AC算法主要思想：将AC自动机的3张表（goto表、fail表和output表）以数组的形式表示，与双数组Trie树的base，check数组相结合，形成一种多数组关系。
base数组本质就是一种状态转移，即字符匹配成功跳向下一状态，匹配失败跳向根节点，所以base数组与goto表的作用是一样的，所以只需将剩下的fail表，output表转换成数组形式。改进AC算法图示如图4所示。
字符匹配流程图如图5所示。字符串匹配过程为：步骤1：初始状态o收到字符c;
步骤2：若字符匹配成功，则跳到下一状态t=base[s]+c;若字符匹配失败，则跳到下一状态o=fail[s];
步骤3：若base[t]<0（或者base[o]<0），则状态t（或者o）是输出状态，输出模式串output[t]（或者output[o]），否则不输出;
步骤4：将状态t（或者o）设为当前状态，取下一个字符，转到步骤2继续匹配，直至目标串中的所有字符完成匹配。3 ?实验及结果分析
本实验的硬件环境是CPU 3.4 GHz（Intel Core i7 4770），内存为8 GB，64位Windows 10操作系统，软件使用的是Myecplise 2014。模式串的数据来自《现代汉语常用词汇表》，总计38 285个词汇，其中双字词23 573个、三字词5 289个、四字词9 423个;目标串数据来自文学作品《平凡的世界》的完整版，大小为2.28 MB，大约共79万字。总共进行两项实验，分别为多模式匹配查全率实验和匹配速度实验。
3.1 ?多模式匹配查全率实验
该实验目的是验证改进AC算法能否进行多模式匹配，以及能否返回目标串中所有的本文所要匹配的模式串。实验是以使用Microsoft Word的查找功能得到的结果为比较标准，假如通过Word查找功能得模式串的个数共有m个，通过改进AC算法得到的模式串的个数为n个，则查全率R为：
[R=nm] ? ? ? （3）
式中：R的值为1时，说明能够查找到全部的模式串;越接近于1，说明改进AC算法的查找效果越好。
随机抽取9个词语为样本，作为模式串集合，得到的实验数据及结果如表5所示。
根据表5中的数据和式（3）计算出改进AC算法的查全率R：
[24+19+1+5+121+36+124+16+124+19+1+5+121+36+124+16+1=1]
查全率R为1，说明改进AC算法不仅能够进行多模式匹配，而且可以匹配到目标串中全部的结果，查全率达到了要求的水平。
3.2 ?匹配速度实验
该实验在相同的条件下比较了AC算法和改进AC算法的匹配速度，根据模式串个数的不同共进行8组测试，分别为模式串个数为5 000，10 000，…，35 000和38 285。为了避免由于偶然性所导致的异常结果，每个模式串组分别进行10次匹配，对得到的匹配时间求平均值。最终得到对比结果如图6所示。
从图6中可以看出，改进AC算法的匹配时间明显低于AC算法的匹配时间，在模式串个数为30 000个时，改进AC算法匹配所有的2.28 MB目标串只需50 ms，匹配速度达到了45.6 MB/s，而AC算法的匹配速度为10.2 MB/s，改进AC算法的匹配速度是原AC算法的4～5倍，说明改进AC算法的匹配速度要远远高于AC算法的匹配速度。
4 ?结 ?语
本文介绍AC算法和双数组Trie树的原理，在此基础之上将双数组Trie树的思想应用于AC算法，也就是用数组表示AC自动机的多模式匹配算法。通过实验对比原有算法和改进AC算法的查全率和速度可知：改进AC算法不仅能够匹配出所有的模式串，而且匹配速度提高了4～5倍，改进AC算法取得了良好的效果。
参考文献
[1] 蒋莉莉.字符串模式匹配算法的改进研究[J].电脑知识与技术，2008（3）：526?528.
JIANG Lili. The research of improved matching algorithm of string pattern [J]. Computer knowledge and technology， 2008（3）： 526?528.
[2] 张利香.基于后缀数组的字符串模式查找的算法[D].兰州：西北师范大学，2010.
ZHANG Lixiang. The string pattern searching algorithms based on suffix arrays [D]. Lanzhou： Northwest Normal University， 2010.
[3] 杨波.基于有限状态自动机的中文多模式匹配算法研究[D].合肥：合肥工业大学，2013.
YANG Bo. Research on multi?pattern matching algorithm for Chinese based on finite state automata [D]. Hefei： Hefei University of Technology， 2013.
[4] 蔡恒，张帅.基于BF算法改进的字符串模式匹配算法[J].电脑编程技巧与维护，2014（22）：14?15.
CAI Heng， ZHANG Shuai. An improved string pattern matching algorithm based on BF algorithm [J]. Computer programming skills & maintenance， 2014（22）： 14?15.
[5] 李明月，张善卿，陆剑锋，等.一种改进的Sunday匹配算法[J].杭州电子科技大学学报（自然科学版），2015，35（1）：93?96.
LI Mingyue， ZHANG Shanqing， LU Jianfeng， et al. A modified Sunday matching algorithm [J]. Journal of Hangzhou Dianzi University （Natural Sciences）， 2015， 35（1）： 93?96.
[6] 刘丽霞，张志强.基于Trie树的相似字符串查找算法[J].计算机应用，2013，33（8）：2375?2378.
LIU Lixia， ZHANG Zhiqiang. Similar string search algorithm based on Trie tree [J]. Journal of computer applications， 2013， 33（8）： 2375?2378.
[7] YANG Wenchuan， FANG Zeyang， LI Pengfei. Study for the double?array Trie tree based algorithm in word segmentation [C]// Proceedings of 2015 International Conference on Computer Science and Environmental Engineering. Beijing： DEStech Publications Inc.， 2015： 7.
[8] 徐聪，张丰，杜震洪，等.基于哈希和双数组Trie树的多层次地址匹配算法[J].浙江大学学报（理学版），2014，41（2）：217?222.
XU Cong， ZHANG Feng， DU Zhenhong， et al. A multi?level address?matching algorithm based on Hash function and double?array Trie?tree [J]. Journal of Zhejiang University （Science edition）， 2014， 41（2）： 217?222.
[9] KAROONBOONYANAN T. An implementation of double?array Trie [EB/OL]. [2018?11?21]. https：//linux.thai.net/～thep/datrie/datrie.html.
