The week's pick
Random Articles
Reseach Article
New and Efficient Recursive-based String Matching Algorithm (RSMA-FLFC)
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 86 - Number 15 |
| Year of Publication: 2014 |
| Authors: Jehad Q. Odeh |
10.5120/15058-3190
|
Jehad Q. Odeh . New and Efficient Recursive-based String Matching Algorithm (RSMA-FLFC). International Journal of Computer Applications. 86, 15 ( January 2014), 1-6. DOI=10.5120/15058-3190
Abstract
The need for simple and efficient string matching algorithms is essential for many applications, and especially for database query. In this paper, two major algorithms are proposed, namely first least frequency character algorithm (FLFC) and recursive-based string matching algorithm (RSMA). FLFC is considered as an enhanced version of scan for lowest frequency character SLFC proposed by Horspool [12]. FLFC algorithm extracts first least frequency character in the pattern and identifies the occurrences of such character in the whole text in a preprocessing phase, while the recursive algorithm (RSMA) recursively partitioning the pattern and the targeted substring in the text and compares them at mid-point (q) each time. The FLFC search accelerates the searching process, while RSMA enhances the speed of performance of the matching phase. The extensive testing and comparisons with Naïve (Brute force), Boyer-Moore (BM), and the FLFC without deploying recursive matching show that the proposed algorithms enhance the speed of performance dramatically.
References
- Crochemore, M. , A. Czumaj, L. Gasieniec, S. Jarominek, T. Lecroq, W. Plandowski and Rytter W. 1994. Speeding Up Two String Matching Algorithms. Algorithmica, 12(4-5): 247-267.
- Lecroq, T. 2007. Fast exact string matching algorithms. Journal of Information Processing Letter, 102: 229-235.
- Wu, Y. -C. , J. -C. Yang and Y. -S Lee. 2007. A Weighted String Pattern Matching-Based Passage Ranking Algorithm for Video Question Answering. Journal of Expert Systems with Applications, 34: 2588-2600.
- Ukkonen, E. 1985. Algorithms for approximate string matching. Information and Control, 64(1-3) 100–118
- Ukkonen, E. 1985. Finding approximate patterns in strings. Journal of Algorithms 6(1), 132–137
- Salmela , L and Tarhio , J. 2010. Approximate string matching with reduced alphabet. In T Elomaa , H Mannila & P Orponen (eds) , Algorithms and applications, Lecture Notes in Computer Science 6060 , Heidelberg, Berlin, Springer Verlag.
- Alqadi, Z. , M. Aqel and I. El Emary, 2007. Multiple-Skip Multiple-Pattern Matching Algorithm (MSMPMA). IAENG International Journal of Computer Science, 34(2): 14-20.
- Charras, C. ; Lecroq, T. 2004. Handbook of Exact String-Matching Algorithms, King's College Publications. Available from: http://www-igm. univ-mlv. fr/~lecroq/string/string. ps.
- Boyer, R. ; Moore, J. 1977. A fast string searching algorithm. Communications of the ACM, 20(10), 62-72.
- Danvy, O. and H. Rohde, 2006. On Obtaining the Boyer–Moore String-Matching Algorithm by Partial Evaluation. Journal of Information Processing Letter, 99: 158-162.
- Franek, F. , C. Jennings and W. F. Smyth, 2006. A simple fast hybrid pattern-matching algorithm. Journal of Discrete Algorithms, 5: 682-695.
- R. Nigel Horspool, 1980. Practical Fast Searching in Strings. Journal of Software Practice and Experience, vol. 10, pp: 501-506.
- Oxford Dictionary. Oxford University Press, What is the frequency of the letters of the alphabet in English?". http://www. oxforddictionaries. com/words/what-is-the-frequency-of-the-letters-of-the-alphabet-in-english, Last visited: 5th of December, 2013.
- Watson, B. and R. Watson. 2003. A Boyer–Moore-Style Algorithm for Regular Expression Pattern Matching. Journal of Science of Computer Programming, 48: 99-117.
Index Terms
Keywords