基于藏文音节结构的单模式匹配算法  

A Single Pattern Matching Algorithm Based on Tibetan Syllable Structure

作　　者：张学通 彭展 ZHANG Xue-tong;PENG Zhan(College of Information Engineering,Xizang Minzu University,Xianyang Shaanxi 712082,China)

机构地区：[1]西藏民族大学,陕西咸阳712082

出　　处：《计算机仿真》2024年第8期374-378,共5页Computer Simulation

基　　金：西藏自治区自然科学基金项目(XZ202101ZR0089G)。

摘　　要：字符比较次数和失配后的跳转长度是影响模式(字符串)匹配算法效率的两个关键因素。BM算法是最经典的单模式字符串匹配算法之一。在长度为m的模式串中,其失配后的最大跳转长度为m,但是在应用于藏文环境时无意义字符比较次数较多、最大跳转长度还可增加。针对以上两点不足并结合藏文的文字特征,提出一种基于藏文音节点的单模式匹配算法:BM-Tibetan算法。算法采用“先对齐,再匹配”的思想以减少匹配次数,失配后的最大跳转距离为m+k(2≤k≤8)。实验结果表明,BM-Tibetan算法的字符比较次数和模式串的移动次数均少于BM算法,算法性能有一定优势。The number of character comparisons and the jump length after mismatch are two key factors affecting the efficiency of string matching algorithms.BM algorithm is one of the most classical single pattern string matching algorithms.In a pattern string with a length of m,the maximum jump length after mismatch is m.However,when applied to Tibetan environments,there are more comparisons of meaningless characters,and the maximum jump length can be increased.This paper proposes a single patterm matching algorithm based on Tibetan syllable points:BM-Tibetan algorithm.The algorithm uses the idea of"alignment first,then matching"to reduce the number of matching,and the maximum jump distance after mismatch is m+k(2≤k≤8).Experimental results show that the number of character comparison and pattern string movement of BM-Tibetan algorithm are less than BM algorithm,and the performance of the algorithm has certain advantages.

关 键 词：字符串匹配 单模式匹配算法 藏文 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]