An Enhanced Version of Pattern Matching Algorithm using Bitwise XOR Operation
作者： K. P.Ambika , U. Ramesh , K. Saravanan , J. Hencil Peter
DOI: 10.5120/11720-7392
关键词:
摘要: this study, a new algorithm for the traditional pattern matching problem has been proposed. This is modified version of KMP and using bitwise XOR operation to process two characters (or bytes) in parallel, speed up process. An additional loop avoid undesirable comparison(s) also introduced let initiate, continue only essential comparisons from required location. As uses principle Finite automata which used by Bitwise character match, it shows some reasonable performance improvement. Also easy implement as doesn't require any additional/complex data structure(s) suitable DNA sequence search. KeywordsAlgorithm, Pattern Matching. Exact
ijcaonline.org
harvard.edu
researchgate.net 参考文章(17)
Andrzej Ehrenfeucht, Anselm Blumer, David Haussler, Ross M. McConnell, J. Blumer, Linear size finite automata for the set of all subwords of a word - an outline of results. Bulletin of The European Association for Theoretical Computer Science. ,vol. 21, pp. 12- 20 ,(1983)
Hannu Peltola, Jorma Tarhio, Alternative Algorithms for Bit-Parallel String Matching string processing and information retrieval. pp. 80- 93 ,(2003) , 10.1007/978-3-540-39984-1_7
Simone Faro, Thierry Lecroq, An Efficient Matching Algorithm for Encoded DNA Sequences and Binary Strings combinatorial pattern matching. pp. 106- 115 ,(2009) , 10.1007/978-3-642-02441-2_10
Jin Wook Kim, Eunsang Kim, Kunsoo Park, Fast Matching Method for DNA Sequences Combinatorics, Algorithms, Probabilistic and Experimental Methodologies. pp. 271- 281 ,(2007) , 10.1007/978-3-540-74450-4_25
Beate Commentz-Walter, A String Matching Algorithm Fast on the Average international colloquium on automata, languages and programming. pp. 118- 132 ,(1979) , 10.1007/3-540-09510-1_10
Cyril Allauzen, Maxime Crochemore, Mathieu Raffinot, Factor Oracle: A New Structure for Pattern Matching conference on current trends in theory and practice of informatics. ,vol. 1725, pp. 295- 310 ,(1999) , 10.1007/3-540-47849-3_18
Gonzalo Navarro, Mathieu Raffinot, A Bit-Parallel Approach to Suffix Automata: Fast Extended String Matching combinatorial pattern matching. pp. 14- 33 ,(1998) , 10.1007/BFB0030778
Richard M. Karp, Michael O. Rabin, Efficient randomized pattern-matching algorithms Ibm Journal of Research and Development. ,vol. 31, pp. 249- 260 ,(1987) , 10.1147/RD.312.0249
A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M.T. Chen, J. Seiferas, THE SMALLEST AUTOMATON RECOGNIZING THE SUBWORDS OF A TEXT Theoretical Computer Science. ,vol. 40, pp. 31- 55 ,(1985) , 10.1016/0304-3975(85)90157-4
Daniel M. Sunday, A very fast substring search algorithm Communications of the ACM. ,vol. 33, pp. 132- 142 ,(1990) , 10.1145/79173.79184