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

doi:10.13438/j.cnki.jdzk.2018.04.007

Abstract

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

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.

References

[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.