CFP last date
22 April 2024
Reseach Article

New and Efficient Recursive-based String Matching Algorithm (RSMA-FLFC)

by Jehad Q. Odeh
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

@article{ 10.5120/15058-3190,
author = { Jehad Q. Odeh },
title = { New and Efficient Recursive-based String Matching Algorithm (RSMA-FLFC) },
journal = { International Journal of Computer Applications },
issue_date = { January 2014 },
volume = { 86 },
number = { 15 },
month = { January },
year = { 2014 },
issn = { 0975-8887 },
pages = { 1-6 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume86/number15/15058-3190/ },
doi = { 10.5120/15058-3190 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:04:16.160098+05:30
%A Jehad Q. Odeh
%T New and Efficient Recursive-based String Matching Algorithm (RSMA-FLFC)
%J International Journal of Computer Applications
%@ 0975-8887
%V 86
%N 15
%P 1-6
%D 2014
%I Foundation of Computer Science (FCS), NY, USA
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
  1. 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.
  2. Lecroq, T. 2007. Fast exact string matching algorithms. Journal of Information Processing Letter, 102: 229-235.
  3. 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.
  4. Ukkonen, E. 1985. Algorithms for approximate string matching. Information and Control, 64(1-3) 100–118
  5. Ukkonen, E. 1985. Finding approximate patterns in strings. Journal of Algorithms 6(1), 132–137
  6. 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.
  7. 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.
  8. 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.
  9. Boyer, R. ; Moore, J. 1977. A fast string searching algorithm. Communications of the ACM, 20(10), 62-72.
  10. 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.
  11. Franek, F. , C. Jennings and W. F. Smyth, 2006. A simple fast hybrid pattern-matching algorithm. Journal of Discrete Algorithms, 5: 682-695.
  12. R. Nigel Horspool, 1980. Practical Fast Searching in Strings. Journal of Software Practice and Experience, vol. 10, pp: 501-506.
  13. 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.
  14. 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

Computer Science
Information Sciences

Keywords

Recursive string matching brute force Boyer-Moore least frequency characters