CFP last date
20 December 2024
Call for Paper
January Edition
IJCA solicits high quality original research papers for the upcoming January edition of the journal. The last date of research paper submission is 20 December 2024

Submit your paper
Know more
The week's pick
Responsive image
Improved Shuffled Frog Leaping Algorithm with Self-Adaptive Shuffling for Fuzzy Logic PD+G Controller Optimization in Robotic Manipulators

Duc Hoang Nguyen
Random Articles
Reseach Article

An Enhanced Version of Pattern Matching Algorithm using Bitwise XOR Operation

by K. P. Ambika, U. Ramesh, K. Saravanan, J. Hencil Peter
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 68 - Number 23
Year of Publication: 2013
Authors: K. P. Ambika, U. Ramesh, K. Saravanan, J. Hencil Peter
10.5120/11720-7392

K. P. Ambika, U. Ramesh, K. Saravanan, J. Hencil Peter . An Enhanced Version of Pattern Matching Algorithm using Bitwise XOR Operation. International Journal of Computer Applications. 68, 23 ( April 2013), 24-30. DOI=10.5120/11720-7392

@article{ 10.5120/11720-7392,
author = { K. P. Ambika, U. Ramesh, K. Saravanan, J. Hencil Peter },
title = { An Enhanced Version of Pattern Matching Algorithm using Bitwise XOR Operation },
journal = { International Journal of Computer Applications },
issue_date = { April 2013 },
volume = { 68 },
number = { 23 },
month = { April },
year = { 2013 },
issn = { 0975-8887 },
pages = { 24-30 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume68/number23/11720-7392/ },
doi = { 10.5120/11720-7392 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:28:42.115861+05:30
%A K. P. Ambika
%A U. Ramesh
%A K. Saravanan
%A J. Hencil Peter
%T An Enhanced Version of Pattern Matching Algorithm using Bitwise XOR Operation
%J International Journal of Computer Applications
%@ 0975-8887
%V 68
%N 23
%P 24-30
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
Abstract

In this study, a new algorithm for the traditional pattern matching problem has been proposed. This algorithm is a modified version of KMP algorithm and using bitwise XOR operation to process two characters (or bytes) in parallel, to speed up the pattern matching process. An additional loop to avoid the undesirable comparison(s) also been introduced and let the algorithm to initiate, and continue only the essential comparisons from the required location. As the new algorithm uses the principle of Finite automata which is used by KMP algorithm and Bitwise XOR operation to speed up the character match, it shows some reasonable performance improvement. Also this new algorithm is easy to implement as it doesn't require any additional/complex data structure(s) and suitable for DNA sequence search.

References
  1. Baeza-Yates, R. A. and Gonnet, G. H. 1992. A new approach to text searching. Communications of the ACM 35, 10, 74–82.
  2. Bálint Dömölki, An algorithm for syntactical analysis, Computational Linguistics 3, Hungarian Academy of Science pp. 29–46, 1964.
  3. Knuth, Donald; Morris, James H. , jr; Pratt, Vaughan (1977). "Fast pattern matching in strings". SIAM Journal on Computing 6 (2): 323–350.
  4. Boyer, Robert S. ; Moore, J Strother (October 1977). "A Fast String Searching Algorithm. ". Communications of the ACM (New York, NY, USA: Association for Computing Machinery) 20 (10): 762–772.
  5. Karp, R. M. , Rabin, M. O. , 1987, Efficient randomized pattern-matching algorithms, IBM Journal on Research Development 31(2):249-260.
  6. A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler, and R. McConnel: Linear size finite automata for the set of all subwords of a word: an outline of results. Bull. Eur. Assoc. Theor. Comput. Sci. , 21 1983, pp. 12–20.
  7. M. Crochemore: Optimal factor tranducers, in Combinatorial Algorithms on Words, A. Apostolico and Z. Galil, eds. , vol. 12 of NATO Advanced Science Institutes, Series F, Springer-Verlag, Berlin, 1985, pp. 31–44.
  8. A. Blumer, J. Blumer, A. Ehrenfeucht, D. Haussler, M. T. Chen, and J. Seiferas: The smallest automaton recognizing the subwords of a text. Theor. Comput. Sci. , 40(1) 1985, pp. 31–55.
  9. C. Allauzen, M. Crochemore, and M. Raffinot: Factor oracle: a new structure for pattern matching, in SOFSEM'99, J. Pavelka, G. Tel, and M. Bartosek, eds. , LNCS 1725, Milovy, Czech Republic, 1999, Springer-Verlag, Berlin, pp. 291–306.
  10. Galil, Z. , and Giancarlo, R. Improved string matching with k mismatches. SIGACT News 17 (1986), 52-54.
  11. Landau, G. M. , and Vishkin, U. Fast string matching with k differences. J. Comput. System Sci. 37 (1988), 63-78.
  12. Landau, G. M. , and Vishkin, U. Fast parallel and serial approximate string matching. Journal of Algorithms 10 (1989).
  13. J. Holub and B. Durian. Fast variants of bit parallel approach to suffix automata. Unpublished Lecture, University of Haifa, April 2005.
  14. G. Navarro and M. Raffinot. Fast and flexible string matching by combining bit-parallelism and suffix automata. ACM Journal of Experimental Algorithms, 5(4):1-36, 2000.
  15. H. Peltola and J. Tarhio. Alternative algorithms for bit-parallel string matching. In LNCS 2857, Proceedings of SPIRE'2003, pages 80-94, 2003.
  16. G. Navarro and M. Raffinot. A bit-parallel approach to suffix automata: Fast extended string matching. In CPM, volume 1448 of LNCS, pages 14–33. Springer-Verlag, 1998.
  17. B. Commentz-Walter. A string matching algorithm fast on the average. In ICALP, volume 71 of LNCS, pages 118–132, 1979.
  18. Simone Faro, Thierry Lecroq: An Efficient Matching Algorithm for Encoded DNA Sequences and Binary Strings. CPM 2009: 106-115.
  19. J. W. Kim, E. Kim, and K. Park. Fast matching method for DNA sequences. In Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, volume 4614 of LNCS, pages 271–281, 2007.
  20. D. M. Sunday. A very fast substring search algorithm. Commun. ACM, 33(8):132–142, 1990.
  21. Human DNA Sequences downloaded from, ftp://ftp. ncbi. nlm. nih. gov
Index Terms

Computer Science
Information Sciences

Keywords

KMP Algorithm Pattern Matching. Exact Pattern Matching

Powered by PhDFocusTM