一种基于AC自动机的藏文多模式匹配算法_王蒙.pdf
《一种基于AC自动机的藏文多模式匹配算法_王蒙.pdf》由会员分享,可在线阅读,更多相关《一种基于AC自动机的藏文多模式匹配算法_王蒙.pdf(6页珍藏版)》请在咨信网上搜索。
1、计算机与图像技术Computer&Multimedia Technology电子技术与软件工程Electronic Technology&Software Engineering143模式(字符串)匹配(string matching)也叫做字串定位操作1,要求在给定文本串中寻找某个特定模式串出现的位置,是计算机科学领域的经典问题之一。如何在数以万计的文本中快速查找指定字符串在人工智能、机器学习、深度学习等领域变得越来越重要2。根据模式串的数量的多少,模式串匹配可分为单模式匹配和多模式匹配两类,经典的单模式匹配算法有简单直观的 BF 算法、可有效避免回溯问题的 KMP 算法3、利用后缀匹配的
2、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 字符
3、集12设计的,若将该算法直接应用于藏文,则匹配效率较低。为此,本文改进了经典的 AC 算法提出了适用于藏文的多模式匹配算法TAC 算法,该算法充分利用藏文特点,克服了现有算法应用于藏文匹配速度慢的问题,具有匹配次数少、运行速度快的优点。1 藏文结构分析藏文目前还是藏族群众主要的交流书写工具,其发展有千年的历史,规定藏文文法传统上所指的是藏文 30字母,即为吐弥.采布扎撰写的藏文文法三十颂及字性组织法指定的字符13,这 30 个字符内涵意义与西方音素文字并不完全一样,30 字符不包括元音字符14。每一个独立成字的藏文辅音字符蕴含了元音要素,所以其具有独立使用的性质,即音节的特性。音节点是书面藏语
4、中音节字与音节字、音节字与标点符号之间的分隔符称为音节点或称为分音点15。音节点的形式是“”(国标编码是:0F0C),属于藏文自创符号,可用于所有的藏文文本,也可以理解为每个藏语词都由音节点结尾、分隔。常用的藏文由三十个辅音字母,四个元音符号,五个反写字母和五个并体字母组成16。一般来说,辅音字母每四个为一组,总共七组半,以发音部位分组为序。藏文字的拼写顺序是前加字、上加字、基字、下加字、元音字符、后加字、再后加字(如图 1)。因为藏文字型特殊,在计算机操作藏文字时会把藏文拆成构建各个构件进行处理17,即藏文字型的拼写元素,如将“”拆解为“、”四个组成部分。那么传统字符串匹配算法在进行藏文字匹
5、配时效率就会非常低,出现很多没必要的匹配。本文针对藏文这一特点,对 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)算法。该算法有效利用藏文以音节点为结尾这
6、一特点,检测到失配字符后不再将文本串读入自动机而是进行下一个词读入,从而提高了效率。实验结果表明,在处理藏文多模式匹配方面,TAC 算法相较于 AC 算法效率大幅度提高。可很好地应用于藏文字取证、拼写检查器以及抄袭检测等领域。关键词:藏文处理;AC 算法;多模式匹配;文本匹配;算法改进基金项目:西藏自治区自然科学基金项目藏文模式匹配与文本索引关键技术研究(XZ202101ZR0089G)。计算机与图像技术Computer&Multimedia Technology电子技术与软件工程Electronic Technology&Software Engineering144c2 c3cn,由 m
7、个模式串组成的模式串集合 P=p1,p2,p3,pm,该算法能够以 O(n)的时间复杂度查找到文本串 S 中所有属于 P 的元素,其效率和 m 无关。AC 算法的核心思想是先将模式串集合 P 建立为一个确定性有限状态自动机(DFA)19,再将文本串 S 逐字符输入到自动机中进行状态转移,一旦达到终止状态则输出匹配成功的模式串。AC 算法由状态转移函数(goto 表)、失效转移函数(fail 表)和输出函数(output 表)组成,其具体功能是:goto 表:由模式串集合中的所有元素构成的状态转移自动机。当输入文本串字符时可依据 goto 表找到将要转移的状态。fail 表:在 goto 表中匹
8、配失败后状态跳转的依据。当 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
9、步字符比较,根据 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。可以得出其效率和模式串数量无关,只与文本
10、串长度有关,随着文本串长度的增大,运行时间也会相应增加。3 TAC算法及应用3.1 TAC算法TAC(Tibetan Aho-Corasick)算法是基于 AC 自动机的藏文多模式匹配算法,本文针对算法运行时间和文本串 S 的大小呈正相关这一特点,改进读取文本串的方式,当 fail 表指向失败状态时,文本串不再读取下一个字符进入自动机,而是直接找到失配字符右边第一个遇到的藏文音节点“”的下一位,这样可以有效避免失配字符的比较,大大提高了算法的效率。TAC 算法核心伪代码如下:表 1:fail 表状态 012345678910 11 12 13Next 0010000001102000 表 2:
11、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 表)newsta
12、te 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 /采用队列的方式建
13、立 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)
14、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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一种 基于 AC 自动机 藏文 模式 匹配 算法 王蒙
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。