The week's pick
Random Articles
Reseach Article
Hardware based String Matching Algorithms: A Survey
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 88 - Number 11 |
| Year of Publication: 2014 |
| Authors: Gulfishan Firdose Ahmed, Nilay Khare |
10.5120/15396-3898
|
Gulfishan Firdose Ahmed, Nilay Khare . Hardware based String Matching Algorithms: A Survey. International Journal of Computer Applications. 88, 11 ( February 2014), 16-19. DOI=10.5120/15396-3898
Abstract
There are various string matching Algorithms which are software based but some are hardware based. The main factor of string matching algorithm is depending on searching efficiency. In this paper we have discussed about the hardware based string matching algorithms such as Brute Force, KMP, and Aho-Corasicks with their applications. There are different types of string matching algorithms which are software based solution and hardware based solution. Since software-based solutions are slower and less efficient, now a day, so the hardware-based solutions are highly preferred. Hardware based approaches are more efficient in terms of speed, memory size and power consumption than software based approaches. Hardware based solutions has great importance in the real life applications. This paper focus on the hardware based solutions and describes the hardware based implementation of string matching algorithms such as Brute Force, KMP and Aho- Corasicks.
References
- Christen Charras and Thierry Lecroq, "Hand Book of Exact String Matching Algorithms", pp. 251-288, Addison-Wesley Publishing Company, 2011.
- Seongyong Ahn, Hyejong Hong, Hyunjin Kim, Jin-Ho Ahn, "A Hardware-Efficient Multi-character String Matching Architecture Using Brute-force Algorithm", pp. 464-467,IEEE , ISOCC, 2009.
- D. E. Knuth, J. H. Morris and V. R. Pratt, "Fast pattern matching in strings," SIAM Journal of Computing, vol. 6, no. 2, pp. 323–350, June,1977.
- Indrawati Gauba, "A Reconfigurable Pattern Matching Hardware Implementation using on chip RAM Based FSM", thesis Boise State University, August, 2010.
- Chien-Chi Chen and Sheng-De Wang, "A Multi-character Transition String Matching Architecture Based On Aho-Corasick Algorithm", ICIC International Volume 8, pp. 8367-8386, 2012.
- Leena Salmela, J. Tarhio and J. Kytojoki, "Multi- Pattern String Matching with Very Large Pattern Sets", ACM Journal Algorithmic, Volume 11, 2006.
- M. Burrows and D. J. Wheeler, "A Block-sorting Lossless Data Compression Algorithm," SRC Research Report, May, 1994.
- Edward Fernandez, Walid Najjar and Stefano Lonardi, "String Matching in Hardware using the FM-Index", IEEE International Symposium on Field-Programmable Custom Computing Machines, 2011.
Index Terms
Keywords