A fast string matching algorithm based on lowlight characters in the pattern
作者： Zhengjun Cao , Zhenzhen Yan , Lihua Liu
DOI: 10.1109/ICACI.2015.7184773
关键词:
摘要: String matching is of great importance in pattern recognition. We put forth a new string algorithm which matches the from neither left nor right end, instead special position. Comparing with Knuth-Morris-Pratt and Boyer-Moore algorithm, more flexible to pick position for starting comparisons. The option really brings it saving cost. method requires statistical probability table alphabets can be set up using evolution strategies dynamic conditions. If chosen lowlight character given has λ, length text n m. then we conjecture that complexity Θ(n/λm).
arxiv.org
sci-hub.se 参考文章(30)
DIMACS (Group), Improved Dynamic Dictionary Matching Information & Computation. ,vol. 119, pp. 258- 282 ,(1995) , 10.1006/INCO.1995.1090
Amihood Amir, Gruia Călinescu, Alphabet-Independent and Scaled Dictionary Matching Journal of Algorithms. ,vol. 36, pp. 34- 62 ,(2000) , 10.1006/JAGM.2000.1081
Zvi Galil, Optimal parallel algorithms for string matching Information and Control. ,vol. 67, pp. 144- 157 ,(1985) , 10.1016/S0019-9958(85)80031-0
Amihood Amir, Eran Chencinski, Costas Iliopoulos, Tsvi Kopelowitz, Hui Zhang, Property matching and weighted matching Theoretical Computer Science. ,vol. 395, pp. 298- 310 ,(2008) , 10.1016/J.TCS.2008.01.006
Amihood Amir, Ayelet Butman, Moshe Lewenstein, Real scaled matching Information Processing Letters. ,vol. 70, pp. 185- 190 ,(1999) , 10.1016/S0020-0190(99)00060-5
Amihood Amir, Ayelet Butman, Moshe Lewenstein, Ely Porat, Real Two Dimensional Scaled Matching Algorithmica. ,vol. 53, pp. 314- 336 ,(2009) , 10.1007/S00453-007-9021-X
Dany Breslauer, Zvi Galil, An optimal O (log n )time parallel string matching algorithm SIAM Journal on Computing. ,vol. 19, pp. 1051- 1058 ,(1990) , 10.1137/0219072
Amihood Amir, Yonatan Aumann, Oren Kapah, Avivit Levy, Ely Porat, Approximate string matching with address bit errors Theoretical Computer Science. ,vol. 410, pp. 5334- 5346 ,(2009) , 10.1016/J.TCS.2009.09.010
Daniel Luchaup, Randy Smith, Cristian Estan, Somesh Jha, Speculative Parallel Pattern Matching IEEE Transactions on Information Forensics and Security. ,vol. 6, pp. 438- 451 ,(2011) , 10.1109/TIFS.2011.2112647
HyunJin Kim, Sungho Kang, A Pattern Group Partitioning for Parallel String Matching using a Pattern Grouping Metric IEEE Communications Letters. ,vol. 14, pp. 878- 880 ,(2010) , 10.1109/LCOMM.2010.080210.092347