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

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Time Efficient String Matching Solution for Single and Multiple Pattern using Bit Parallelism

by Vidya Saikrishna, Akhtar Rasool, Nilay Khare
journal cover thumbnail

International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 46 - Number 6
Year of Publication: 2012
Authors: Vidya Saikrishna, Akhtar Rasool, Nilay Khare
10.5120/6911-9274

Vidya Saikrishna, Akhtar Rasool, Nilay Khare . Time Efficient String Matching Solution for Single and Multiple Pattern using Bit Parallelism. International Journal of Computer Applications. 46, 6 ( May 2012), 15-20. DOI=10.5120/6911-9274

@article{ 10.5120/6911-9274,
author = { Vidya Saikrishna, Akhtar Rasool, Nilay Khare },
title = { Time Efficient String Matching Solution for Single and Multiple Pattern using Bit Parallelism },
journal = { International Journal of Computer Applications },
issue_date = { May 2012 },
volume = { 46 },
number = { 6 },
month = { May },
year = { 2012 },
issn = { 0975-8887 },
pages = { 15-20 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume46/number6/6911-9274/ },
doi = { 10.5120/6911-9274 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:39:03.090437+05:30
%A Vidya Saikrishna
%A Akhtar Rasool
%A Nilay Khare
%T Time Efficient String Matching Solution for Single and Multiple Pattern using Bit Parallelism
%J International Journal of Computer Applications
%@ 0975-8887
%V 46
%N 6
%P 15-20
%D 2012
%I Foundation of Computer Science (FCS), NY, USA
Abstract

Bit Parallelism exploits bit level parallelism in hardware to perform operations. Bit Parallelism is a technique that is used to solve string matching problem, when the pattern to be searched for is less than or equal word size of a system. It is a technique that takes the advantage of intrinsic parallelism of the bit operations inside a system word. By using cleverly this fact, the number of operations that an algorithm performs can be cut down by a factor of at most w, the number of bits in system word. Since in current architecture word size is 32 bits or 64 bits, the speedup is very significant in practice. It is a form of parallel computing and is used to have a solution to exact string matching problem. The approach is further extended for multiple patterns string matching problem.

References
  1. 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.
  2. G. Navarro,M. Raffinot, Fast and flexible string matching by combining bit-parallelism and suffix automata,ACM J. Experimental Algorithmics (JEA) 5 (4) (2000).
  3. 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
  4. R. Baeza-Yates, G. Gonnet, A new approach to text searching, Comm. ACM 35 (10) (1992) 74–82.
  5. Hannu Peltola and Jorma Tarhio , Alternative Algorithms for Bit-Parallel String Matching, String Processing and Information Retrieval, 2003 - Springer
  6. http://en. wikipedia. org/wiki/bit-level_parallelism
  7. http://en. wikipedia. org/wiki/string_searching_algorith m
  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. G. Myers , " A fast bit-vector algorithm for approximate string matching based on dynamic programming ", J. ACM, 46 (3) (1999), pp. 395–415
  10. G. Novarro, " A guided tour to approximate string matching", ACM Comput. Surv. , 33(1)(2001),pp 31-88
  11. Heikki Hyyro, Kimmo Fredrikson, Gonzalo Novarro, "Increased Bit Parallelism for Approximate and Multiple String Matching", Journal of Experimental Algorithmics, Vol 10 , 2005
Index Terms

Computer Science
Information Sciences

Keywords

String Matching Bit Parallelism Suffix Automata.

Powered by PhDFocusTM