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

Submit your paper
Know more
Reseach Article

Approximate Multiple Pattern String Matching using Bit Parallelism: A Review

by Syed Danish Ali, Zuber Farooqui
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 74 - Number 19
Year of Publication: 2013
Authors: Syed Danish Ali, Zuber Farooqui
10.5120/13006-0312

Syed Danish Ali, Zuber Farooqui . Approximate Multiple Pattern String Matching using Bit Parallelism: A Review. International Journal of Computer Applications. 74, 19 ( July 2013), 47-51. DOI=10.5120/13006-0312

@article{ 10.5120/13006-0312,
author = { Syed Danish Ali, Zuber Farooqui },
title = { Approximate Multiple Pattern String Matching using Bit Parallelism: A Review },
journal = { International Journal of Computer Applications },
issue_date = { July 2013 },
volume = { 74 },
number = { 19 },
month = { July },
year = { 2013 },
issn = { 0975-8887 },
pages = { 47-51 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume74/number19/13006-0312/ },
doi = { 10.5120/13006-0312 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T21:42:46.818488+05:30
%A Syed Danish Ali
%A Zuber Farooqui
%T Approximate Multiple Pattern String Matching using Bit Parallelism: A Review
%J International Journal of Computer Applications
%@ 0975-8887
%V 74
%N 19
%P 47-51
%D 2013
%I Foundation of Computer Science (FCS), NY, USA
Abstract

String matching is to find all the occurrences of a given pattern in a large text both being sequence of characters drawn from finite alphabet set. Approximate String Matching involves the detection of correct patterns along with the detection of some wrong patterns inside the text. Bit Parallelism is a feature that can be used to detect patterns inside the text and is reported to result in more efficient approximate string matching. Bit parallelism enhances the processing speed of the approximate string matching algorithm as it takes the benefit of the internal bit operations taking place in parallel inside the system. The bit parallel method has also been compared with the traditional Aho Corasick Algorithms which consumes more time and memory. In general bit parallel are both memory and time efficient.

References
  1. Rajesh Prasad, Suneeta Agarwal, Ishadutta Yadav, Bharat Singh "Efficient Bit-Parallel Multi-Patterns String Matching Algorithms for Limited Expression", Compute 2010 ACM
  2. Heikki Hyyr¨o, Kimmo Fredriksson Gonzalo Navarro "Increased Bit-Parallelism for Approximate and Multiple String Matching", ACM Journal of Experimental Algorithmics Vol 10 2006.
  3. Gonzalo Navarro and Mathieu Raffinot. A Bit Parallel approach to Suffix Automata : Fast Extended String Matching. In M. Farach (editor), Proc. CPM'98, LNCS 1448. Pages 14-33, 1998.
  4. G. Navarro,M. Raffinot, Fast and flexible string matching by combining bit-parallelism and suffix automata,ACM J. Experimental Algorithmics (JEA) 5 (4) (2000).
  5. M. Crochemore et al. , A bit-parallel suffix automaton approach for (?, ? )-matching in music retrieval, in: Proc. 10th Internat. Symp. on String Processing and Information Retrieval (SPIRE'03), in: Lecture Notes in Computer. Sci. , vol. 2857, 2003, pp. 211–223
  6. R. Baeza-Yates, G. Gonnet, A new approach to text searching, Comm. ACM 35 (10) (1992) 74–82.
  7. Hannu Peltola and Jorma Tarhio , Alternative Algorithms for Bit-Parallel String Matching, String Processing and Information Retrieval, 2003 - Springer
  8. Leena Salmela, J. Tarhio and J. Kytojoki "MultiPattern String Matching with Very Large Pattern Sets", ACM Journal of Experimental Algorithmics, Volume 11, 2006.
  9. AHO, A. AND CORASICK, M. 1975. Efficient string matching: n aid to bibliographic search. Communications of the ACM 18, 6, 333–340.
  10. HYYR¨O, H. AND NAVARRO, G. 2002. Faster bit-parallel approximate string matching. In Proc. 13th Combinatorial Pattern Matching (CPM '02). LNCS 2373. Berlin, Germany, Springer, New York. 203–224.
  11. NAVARRO, G. AND RAFFINOT, M. 2000. Fast and flexible string matching by combining bitparallelism and suffix automata. ACM Journal of Experimental Algorithmics (JEA). 5, 4.
  12. Vidya Saikrishna, Akhtar Rasool and Nilay Khare. Article: Spam Filtering through Multiple Pattern Bit Parallel String Matching Combining Shift AND & OR. International Journal of Computer Applications 61(5):40-45, January 2013. Published by Foundation of Computer Science, New York, USA.
Index Terms

Computer Science
Information Sciences

Keywords

Approximate String matching Bit parallelism Shift OR String Matching