DocumentCode :
3523636
Title :
A fast string matching algorithm based on lowlight characters in the pattern
Author :
Zhengjun Cao ; Zhenzhen Yan ; Lihua Liu
Author_Institution :
Dept. of Math., Shanghai Univ., Shanghai, China
fYear :
2015
fDate :
27-29 March 2015
Firstpage :
179
Lastpage :
182
Abstract :
String matching is of great importance in pattern recognition. We put forth a new string matching algorithm which matches the pattern from neither the left nor the right end, instead a special position. Comparing with the Knuth-Morris-Pratt algorithm and the Boyer-Moore algorithm, the new algorithm is more flexible to pick the position for starting comparisons. The option really brings it a saving in cost. The method requires a statistical probability table for alphabets which can be set up using evolution strategies for dynamic conditions. If the chosen lowlight character in a given pattern has the probability λ, the length of the text is n and the length of the pattern is m. then we conjecture that the complexity of the new algorithm is Θ(n/λm).
Keywords :
computational complexity; pattern recognition; probability; statistical analysis; string matching; text analysis; Θ(n/λm) complexity; alphabets; dynamic conditions; evolution strategies; fast-string matching algorithm; lowlight characters; pattern length; pattern matching; pattern recognition; statistical probability table; text length; Probability;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Advanced Computational Intelligence (ICACI), 2015 Seventh International Conference on
Conference_Location :
Wuyi
Print_ISBN :
978-1-4799-7257-9
Type :
conf
DOI :
10.1109/ICACI.2015.7184773
Filename :
7184773
Link To Document :
بازگشت