基于跳跃式匹配的藏文多模式匹配算法  

作　　者：周磊超 彭展 ZHOU Leichao;PENG Zhan

机构地区：[1]西藏民族大学信息工程学院,陕西咸阳712000

出　　处：《信息技术与信息化》2025年第1期15-18,共4页Information Technology and Informatization

摘　　要：在计算机科学的研究领域中,字符串匹配算法是基础性问题的关键一环,依据查找过程中所涉及模式串的数量差异,可细分为单模式匹配算法与多模式匹配算法这两大类别。其中,AC算法作为多模式匹配算法范畴内极具代表性且应用极为广泛的经典算法。文章通过分析AC算法及其相关改进算法,并结合藏文结构的特点,提出了一种基于跳跃式匹配的藏文多模式匹配算法—AC_BM2T算法。该算法基于当前匹配窗口末尾的2个字符,设计了一种新的模式树移动规则,使得模式树可以实现跳跃式匹配并且跳跃距离相对较大,以此提高算法执行效率。实验结果表明,在处理藏文时,AC_BM2T算法的执行时间是其他改进算法的50%~60%;在模式串数量较少时,AC_BM2T算法的执行时间是AC算法的25%~90%。

关 键 词：多模式匹配算法 AC算法 藏文结构 模式树 跳跃 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]