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