摘要
维吾尔文多模式匹配算法是影响维吾尔文关键词过滤和检测性能的关键步骤之一。为此,考虑维吾尔文语法特点、书写方式、字母变换形式、特殊字母等因素,提出一种基于维吾尔文音节划分的多模式匹配算法。通过Bohumsani函数的维吾尔语音节分解方法计算字符串音节数,利用Bohumxekli函数得到字符串音节结构,按语法特点从右至左方式进行模式比较,实现维吾尔文多模式匹配。实验结果表明,与现有模式匹配算法相比,该算法具有更高的匹配效率。
Uyghur multiple pattern matching algorithm is the one of the key steps of affecting the keywords filtering and detecting system performance.This paper proposes a multiple pattern string matching algorithm for Uyghur,based on Uyghur syllable partition with considering the Uyghur syntactic characteristics,alphabet writing form,the form of alphabets change and especial alphabets.It uses Bohum-sani function to calculate character syllable count,Bohum xekli function to get string syllable combination form.It implemerts patlern matching from right to left according to the language features.Experimental result shows that this algorithm has higher matching efficiency,and the new multiple pattern string matching algorithm for Uyghur language performance is better than improved pattern matching efficiency comprised with existing pattern matching algorithms.
引文
[1]哈密提·铁木尔.现代维吾尔语语法[M].北京:民族出版社,1987.
[2]AhoA,CorasickM.EfficientStringMatching:AnAid to Bibliographic Search[J].Communicationsofthe ACM,1975,18(6):333-343.
[3]早克热·卡德尔,艾山·吾买尔,吐尔根·依布拉音,等.维吾尔语名词构形词缀有限状态自动机的构造[J].中文信息学报,2009,23(6):116-121.
[4]阿依克孜·卡德尔,开沙尔·卡德尔,吐尔根·依布拉音.维吾尔语动词体范畴的有限状态自动机的构建[J].中文信息学报,2012,26(4):61-65.
[5]BoyerRS,MooreJS.A FastStringSearchingAlgori-thm[J].Communicationsofthe ACM,1977,20(10):762-772.
[6]FanJang-Jong,SuKeh-Yih.AnEfficientAlgorithm for MatchingMultiplePatterns[J].IEEE Transactionson KnowledgeandDataEngineering,1933,5(2):339-351.
[7]关超,蒋建中,郭军利.一种基于反向有限自动机的多模式匹配算法[J].计算机工程,2010,36(1):208-210.
[8]WuS,ManberU.A FastAlgorithm forMulti-pattern Searching[D].Tucson,USA:UniversityofArizona,1994.
[9]古丽拉·阿东别克,米吉提·阿布力米提.维吾尔语词切分方法初探[J].中文信息学报,2004,18(6):61-65.
[10]米吉提·阿不力米提.在多文种环境下的维吾尔语文字校对系统的开发研究[J].系统工程理论与实践,2003,23(5):117-124.
[11]马欢,吾守尔·斯拉木.维吾尔语文语转换系统文本分析模块初探[J].计算机工程,2006,32(16):267-268.
[12]阿比达·吾买尔,吐尔根·依步拉音.维吾尔文音节切分方法的研究与实现[C]//第十一届全国民族语言文字信息学术研讨会论文集.西双版纳:中国中文信息学会民族语言文字信息专业委员会,2007.