Horspool扩展算法在方块苗文模式匹配中的应用

doi:10.13438/j.cnki.jdzk.2018.04.007

吉首大学学报（自然科学版）

Horspool扩展算法在方块苗文模式匹配中的应用

曾磊，莫礼平，刘笔余，唐澳斌，莫春望，尹娟

（吉首大学信息科学与工程学院，湖南吉首 416000）

出版日期:2018-07-25 发布日期:2018-07-31
通讯作者: 莫礼平（1972—），女，湖南安化人，吉首大学信息科学与工程学院高级实验师，主要从事中文信息处理、Petri网理论及其应用研究.
基金资助:
国家自然科学基金资助项目(61462029，61741205)；湖南省校企合作创新创业教育基地创新性项目(JDCX1702)

Extended Horspool Algorithm and Its Application in Square Hmong String Pattern Matching

ZENG Lei,MO Liping,LIU Biyu,TANG Aobin,MO Chunwang,YIN Juan

(College of Information Science & Engineering,Jishou University,Jishou 416000,Hunan China)

Online:2018-07-25 Published:2018-07-31

摘要/Abstract

摘要：

分析了Horspool算法的原理及特点，提出了一种适用于方块苗文环境的字符串模式匹配算法.该算法结合方块苗文的编码方式及字符串查找的特点，通过对Horspool算法中的字符处理单位进行扩展来适应方块苗文的字符串匹配.实验结果表明，在单字词、双字词和多字词的方块苗文字符串匹配过程中，该算法均呈现出较好的性能，能够用于解决方块苗文的快速检索问题.

关键词： 模式匹配, 字符串, Horspool算法, 方块苗文

Abstract:

A string matching algorithm is proposed for the matching of the square Hmong characters in Hmong environment based on the the principle and characteristics of the Horspool algorithm.The proposed algorithm extends the character processing units in the Horspool algorithm according to the encoding method of the square Hmong characters and the characteristics of Hmong string searching.The experimental results show that the algorithm shows a good performance in the Hmong pattern matching of single words,double words and multiple words,and can be used to solve the problem of fast retrieval of the square Hmong information.

Key words: pattern matching, string, Horspool algorithm, square Hmong characters

曾磊，莫礼平，刘笔余，唐澳斌，莫春望，尹娟. Horspool扩展算法在方块苗文模式匹配中的应用[J]. 吉首大学学报（自然科学版）, DOI: 10.13438/j.cnki.jdzk.2018.04.007.

ZENG Lei,MO Liping,LIU Biyu,TANG Aobin,MO Chunwang,YIN Juan. Extended Horspool Algorithm and Its Application in Square Hmong String Pattern Matching[J]. Journal of Jishou University（Natural Sciences Edition), DOI: 10.13438/j.cnki.jdzk.2018.04.007.

参考文献

[1] 刘萍,刘燕兵,郭莉,等.串匹配算法中模式串与文本之间关系的研究[J].软件学报,2010,21(7):1 503-1 514.
[2] 赵晓,何立风,王鑫,等.一种高效的模式串匹配算法[J].陕西科技大学学报(自然科学版),2017,35(1):183-187.
[3] KNUTH D E,MORRIS J H,PRATT V R.Fast Pattern Matching in Strings[J].SIAM Journal of Computing,1977,6(2):323-350.
[4] 韩光辉,曾诚.KMP算法的理论研究[J].微电子学与计算机,2013,30(4):30-33.
[5] BOYEＲ R S,MOORE J S.A Fast String Searching Algorithm[J].Communications of the ACM,1977,20(10):762-772.
[6] NAVARRO U,RALLINOT M.Flexible Pattern Matching in Strings[J].Cambridge:Cambridge University Press,2002:19-22.
[7] GUIBAS L J,ODLYZKO A M.A New Proof of the Linearity of the Boyer-Moore String Searching Algorithm[J].SIAM Journal of Computing,1980,9(4):672-682.
[8] SCHABACK R.On the Expected Sub-Linearity of the Boyer-Moore Algorithm[J].SIAM Journal on Computing,1988,17(4):648-658.
[9] COLE R,HARIHARAN R.Tighter Upper Bounds on the Exact Complexity of String Matching[J].SIAM Journal of Computing,1997,26(3):803-856.
[10] SUNDAY D M.A Very Fast Substring Search Algorithm[J].Communications of the ACM,1990,33(8):132-142.
[11] 王文霞.BM模式匹配算法的研究与改进[J].山西师范大学学报(自然科学版),2017,32(1):37-39.
[12] 韩光辉,曾诚.Boyer-Moore串匹配算法的改进[J].计算机应用,2014,34(3):865-868.
[13] HORSPOOL R N.Practical Fast Searching in Strings[J].Software Practice and Experience,1980,10(6):501-506.
[14] 赵丽明,刘自齐.湘西方块苗文[J].民族语文,1990(1):44-49.
[15] 莫礼平,曾水玲,周恺卿.音形结合的方块苗文输入编码方案研究[J].计算机科学与探索,2014,8(8):1 017-1 024.
[16] 莫礼平,周恺卿,蒋效会.基于OpenType技术的方块苗文字库研究[J].中文信息学报,2015,29(2):150-156.

Horspool扩展算法在方块苗文模式匹配中的应用

Extended Horspool Algorithm and Its Application in Square Hmong String Pattern Matching

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

编辑推荐

Metrics

本文评价

[1]	孙宇扬, 欧云, 奉松绿, 周恺卿. 基于改进GST算法的字符串相似度检测[J]. 吉首大学学报（自然科学版）, 2021, 42(5): 34-37.
[2]	沈黎，肖勇，刘莺. 一种基于中文关键字符串核函数的分类算法[J]. 吉首大学学报（自然科学版）, 2019, 40(1): 18-20.
[3]	伍文源，曾水玲，蒋天保. 湘西方块苗文图像的预处理方法[J]. 吉首大学学报（自然科学版）, 2016, 37(3): 24-27.
[4]	莫礼平，杨再彪. 与本身读音无关的方块苗文输入音形编码新方法[J]. 吉首大学学报（自然科学版）, 2016, 37(3): 19-23.
[5]	莫礼平, 周胜, 尹楠佳. 基于构件汉语拼音的湘西方块苗文输入法[J]. 吉首大学学报（自然科学版）, 2014, 35(2): 30-34.