一种基于AC自动机的藏文多模式匹配算法_王蒙.pdf

计算机与图像技术Computer&Multimedia Technology电子技术与软件工程Electronic Technology&Software Engineering143模式（字符串）匹配（string matching）也叫做字串定位操作1，要求在给定文本串中寻找某个特定模式串出现的位置，是计算机科学领域的经典问题之一。如何在数以万计的文本中快速查找指定字符串在人工智能、机器学习、深度学习等领域变得越来越重要2。根据模式串的数量的多少，模式串匹配可分为单模式匹配和多模式匹配两类，经典的单模式匹配算法有简单直观的 BF 算法、可有效避免回溯问题的 KMP 算法3、利用后缀匹配的 BM 算法4、以及 BM 算法的改进算法Horspool 算法5和 Sunday 算法6等，经典的多模式匹配算法有基于自动机的 AC 算法、基于特征串的 WM 算法7、基于多级哈希思想和动态切割策略的MDH算法8、基于 Oracle 数据结构的 BOM 算法9以及将 BM 算法和AC 算法结合起来的 AC-BM 算法10等。AC算法是KMP算法在多模式情形下的推广，目前，各种 AC 算法的变体在实际当中被广泛采用11。AC 算法通过为模式集构造一个确定性有限状态自动机(DFA)，然后将文本串中的字符依次输入到自动机中进行状态转移，来实现多模式匹配。然而，经典的 AC 算法是针对ASCII 字符集12设计的，若将该算法直接应用于藏文，则匹配效率较低。为此，本文改进了经典的 AC 算法提出了适用于藏文的多模式匹配算法TAC 算法，该算法充分利用藏文特点，克服了现有算法应用于藏文匹配速度慢的问题，具有匹配次数少、运行速度快的优点。1 藏文结构分析藏文目前还是藏族群众主要的交流书写工具，其发展有千年的历史，规定藏文文法传统上所指的是藏文 30字母，即为吐弥.采布扎撰写的藏文文法三十颂及字性组织法指定的字符13，这 30 个字符内涵意义与西方音素文字并不完全一样，30 字符不包括元音字符14。每一个独立成字的藏文辅音字符蕴含了元音要素，所以其具有独立使用的性质，即音节的特性。音节点是书面藏语中音节字与音节字、音节字与标点符号之间的分隔符称为音节点或称为分音点15。音节点的形式是“”（国标编码是：0F0C)，属于藏文自创符号，可用于所有的藏文文本，也可以理解为每个藏语词都由音节点结尾、分隔。常用的藏文由三十个辅音字母，四个元音符号，五个反写字母和五个并体字母组成16。一般来说，辅音字母每四个为一组，总共七组半，以发音部位分组为序。藏文字的拼写顺序是前加字、上加字、基字、下加字、元音字符、后加字、再后加字（如图 1）。因为藏文字型特殊，在计算机操作藏文字时会把藏文拆成构建各个构件进行处理17，即藏文字型的拼写元素，如将“”拆解为“、”四个组成部分。那么传统字符串匹配算法在进行藏文字匹配时效率就会非常低，出现很多没必要的匹配。本文针对藏文这一特点，对 AC 多模式匹配算法做了改进，大大提高了匹配效率。2 AC算法介绍2.1 基本思想AC(Aho-Corasick)算法由 Alfred V.Aho 和 Margaret J.Corasick 在 1975 年提出18，设长度为 n 的文本串 S=c1 一种基于 AC 自动机的藏文多模式匹配算法王蒙彭展*（西藏民族大学 陕西省咸阳市 712000）摘要：本文基于 AC（Aho-Corasick）算法提出了一种适用于藏文字符集的多模式匹配算法TAC（Tibetan Aho-Corasick）算法。该算法有效利用藏文以音节点为结尾这一特点，检测到失配字符后不再将文本串读入自动机而是进行下一个词读入，从而提高了效率。实验结果表明，在处理藏文多模式匹配方面，TAC 算法相较于 AC 算法效率大幅度提高。可很好地应用于藏文字取证、拼写检查器以及抄袭检测等领域。关键词：藏文处理；AC 算法；多模式匹配；文本匹配；算法改进基金项目：西藏自治区自然科学基金项目藏文模式匹配与文本索引关键技术研究（XZ202101ZR0089G）。计算机与图像技术Computer&Multimedia Technology电子技术与软件工程Electronic Technology&Software Engineering144c2 c3cn，由 m 个模式串组成的模式串集合 P=p1,p2,p3,pm，该算法能够以 O(n)的时间复杂度查找到文本串 S 中所有属于 P 的元素，其效率和 m 无关。AC 算法的核心思想是先将模式串集合 P 建立为一个确定性有限状态自动机（DFA）19，再将文本串 S 逐字符输入到自动机中进行状态转移，一旦达到终止状态则输出匹配成功的模式串。AC 算法由状态转移函数（goto 表）、失效转移函数（fail 表）和输出函数（output 表）组成，其具体功能是：goto 表：由模式串集合中的所有元素构成的状态转移自动机。当输入文本串字符时可依据 goto 表找到将要转移的状态。fail 表：在 goto 表中匹配失败后状态跳转的依据。当 goto 表下一个状态无效时，可以根据 fail 表找到应该退回的状态。output 表：到达终止状态时输出成功匹配的模式串。2.2 实例设藏文模式串集合为 P=、，根据 P 建立自动机（如图 2），设置 0 为初始状态，4、9、13 为结束状态：依 次 输 入 文 本 串 S=，根据 goto 表和 fail 表（如表 1）进行状态的转换，再根据output 表（如表 2）输出匹配到的模式串。具体过程分析如下：（1）首先输入字符串的所有构件，根据fail表都是从状态0转移至状态0，进行了18步字符比较。（2）再输入字符，按照 goto 表转移至状态 4，进行 4 步字符比较，根据 output 表输出。（3）接着再次输入字符，按照 goto 表转移至状态9，进行 6 步字符比较，根据 output 表输出。（4）依次输入字符串的所有构件，根据 fail 表都是从状态 0 转移至状态 0，进行了 4 步字符比较。（5）输入字符，按照 goto 表转移至状态 13，进行 4 步字符比较，根据 output 表输出。（6）接着输入字符串的所有构件，根据 fail 表都是从状态 0 转移至状态 0，进行了 5 步字符比较，结束算法。根据以上步骤可知，AC 算法对文本串 S 进行了 41步字符比较才成功找到模式串集合 P。可以得出其效率和模式串数量无关，只与文本串长度有关，随着文本串长度的增大，运行时间也会相应增加。3 TAC算法及应用3.1 TAC算法TAC（Tibetan Aho-Corasick）算法是基于 AC 自动机的藏文多模式匹配算法，本文针对算法运行时间和文本串 S 的大小呈正相关这一特点，改进读取文本串的方式，当 fail 表指向失败状态时，文本串不再读取下一个字符进入自动机，而是直接找到失配字符右边第一个遇到的藏文音节点“”的下一位，这样可以有效避免失配字符的比较，大大提高了算法的效率。TAC 算法核心伪代码如下：表 1：fail 表状态 012345678910 11 12 13Next 0010000001102000 表 2：output 表状态output 值4913图 1：藏文字型结构图 2：根据 P 建立的自动机（goto 表）计算机与图像技术Computer&Multimedia Technology电子技术与软件工程Electronic Technology&Software Engineering145Input：S=c1 c2 、P=p1,p2,p3,pmOutput：i /匹配成功，返回 P 在 S 中的起始位置 iprocedure TAC（n，m：integer）；var i，j：integer；input P=p1,p2,p3,pm:/输入模式串集合 P，建立自动机（goto 表）newstate 0；state 0；j 1for i 1 until m do enter(pi)/依次输入模式串集合 P 中的每个模式串for all p such that g(0,p)=fail do g(0,p)0 /若是失败状态就回到初始状态 0while g(state,pj)fail do /已经存在的状态不用再次创建，只需建立新的状态state g(state,pj)；j j+1for k j until m do /状态转移g(state,pk)newstate+1state newstate+1output(state)p1,p2,p3,pmqueue empty /采用队列的方式建立 fail表for each p such that g(0,p)=s 0 do queue queue s；f(s)0while queue empty do /队列不空则一直执行循环let r be the next state in queue /将队首达到的有效状态加入队列queue queue-rfor each p such that g(r,p)=s fail do /将队列中每一个状态的 fail 值都求出queue queue s；state f(r)while g(state,p)=fail do state f(state)f(s)g(state,p)output(s)output(s)output(f(s)/更新 output 数组输出值endfor endwhileinput S=c1 c2 /输入文本串 S 进行匹配state 0for i 1 until n dowhile g(state,ci)=fail do state f(state)/调用 fail 函数，并更新状态for i i+1 until ci=“”do i i+1 /找到音节点下一位输入自动机state g(state,ci)if output(state)empty thenprint i，output(state)/输出返回 P 在S 中的起始位置 i 与成功匹配的模式串end TAC 3.2 实例还是用上文举例的文本串和模式串集合，将改进的TAC 算法应用于实例方便与 AC 算法进行比较，具体步骤如下：（1）分别输入、，下一个字符均不在自动机中，根据 fail 表从状态 0 转移至状态 0，则文本串不再输入到自动机中，直接跳到失配字符右边第一个遇到的藏文音节点“”的下一位，一共进行了 4 步字符比较。（2）输入字符，按照 goto 表转移至状态 4，进行了 4 步字符比较，根据 output 表输出。（3）接着再次输入字符，按照 goto 表转移至状态9，进行了 6 步字符比较，根据 output 表输出。（4）输入字符，根据fail表从状态0转移至状态0，进行了 1 步字符比较，则文本串直接跳到字符。（5）输入字符，按照 goto 表转移至状态 13，进行了 4 步字符比较，根据 output 表输出。（6）输入字符，根据 fail 表从状态 0 转移至状态 0，进行 1 步字符比较，无法跳跃至音节点下一位，结束算法。根据以上步骤，得出 TAC 算法对文本串 S 进行了20 步字符串的比较成功找到模式串集合 P，相对于 AC算法需要 41 步，减少了一半以上。由此得出 TAC 算法在藏文多模式匹配上可以有效提高匹配效率，运行时间计算机与图像技术Computer&Multimedia Technology电子技术与软件工程Electronic Technology&Software Engineering146明显减少。4 实验及结果分析下面通过实验从不同方面对 AC 算法和 TAC 算法进行测试比较，本实验测试环境为 12th Gen Intel(R)Core(TM)i5-12500H 2.50 GHz，内存为 16.0GB。算法使用 python 语言实现，编译环境为 PyCharm 2020。测表 3：实验一：运行时间对比 模式串数量：1