The week's pick
Reseach Article
String Searching with DFA-based Algorithm
| International Journal of Applied Information Systems |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 9 - Number 8 |
| Year of Publication: 2015 |
| Authors: Preye Ejendibia, Barileé B. Baridam |
10.5120/ijais2015451415
|
Preye Ejendibia, Barileé B. Baridam . String Searching with DFA-based Algorithm. International Journal of Applied Information Systems. 9, 8 ( October 2015), 1-6. DOI=10.5120/ijais2015451415
Abstract
Searching for information in large depositories or the Internet employs the concept of string searching. With the world-wide web expanding with databases from diverse fields it has become a growing concern for database curators to find an efficient searching algorithms for the task. In comparative terms, the power of an algorithm over another is in its time-complexity and efficiency of operation. A lot of algorithms have been designed for the task of string searching. Also, some of the fast string searching algorithms were developed based on the Deterministic Finite Automata (DFA), which prompts the need to thoroughly research and investigate how this principle is applied. This paper analyses and compares the searching power of DFA and brute-force searching algorithms. The DFA approach is used to overcome the problem of backtracking, which is faced with the brute-force approach thereby improving the time complexity, the speed and efficiency of search based on results obtained.
References
- Ben Wellner (471 13 0453 7) and Michael Dant (390 80 0003 1) The Unix “GREP” utility, “CS520 – Introduction to Formal Models” http://pages.cs.wisc.edu/~mdant/cs520_4.html
- J. Kaur, B. Chauhan and J. K. Korepal “Implementation of Query Processor Using Automata and Natural Language Processing” International Journal of Scientific and Research Publications, ISSN: 2250-3153 Volume 3, Issue 5, pp. 1- 5, May 2013.
- E. Gribkoff “Applications of Deterministic Finite Automata” ECS 120 UC Davis, Spring 2013.
- N. Singla, D. Garg “String Matching Algorithms and their Applicability in various Applications” International Journal of Soft Computing and Engineering (IJSCE) ISSN: 2231-2307, Volume 1, Issue 6, pp. 218 – 222, January 2012.
- G. A. Stephen, “String Searching Algorithms” Singapore: World Scientific, Chapter 2, pp. 5-37, 2001.
- S. Mitra, T. Acharya “Data Mining: Multmedia, Soft Computting and Bioinformatics” New Jersey: Wiley-Interscience, Chapter 4, pp. 143-169, 2003.
- J. D. Ullman, Video Lecture “Informal Introduction to finite automata” Stanford University, May 2012, www.coursera.com
- J. E. Hopcroft, R. Motwani and J. D. Ullman “Finite Autmata and Regular Expression” Introduction to automata theory, languages and computation, New York: Addison Wesley, pp. 13-45, 2006.
- D. Knuth, J. Morris and V. Pratt “Fast pattern matching in strings” SIAM journal of Computting, Volume 6, pp. 323-350, 1977.
- A.V. Aho, M.J. Corasick “Efficient string matching: an aid to bibliographic search” Communications of the ACM, Volume 18, No. 6, pp. 333-340, June 1975.
- R. S. Boyer, J. S. Moore “A fast string searching algorithm” Communications of the ACM, Volume 20, No. 10 pp.762-772, October 1977.
- R. N. Hoorspool “Practical fast searching in strings” Software – Practice and Experience, Volume 10 No. 6, pp. 501-506, 1980.
- R. M. Karp and M. O. Rabin “Efficient randomized pattern matching algorithms” IBM Journal of Research and Development, Volume 31, No 6, pp. 249-260, 1987.
- D. M. Sunday “A very fast substring searchalgorithm” Communications of the ACM, Volume 33, No. 8, pp. 132-142, August 1990.
- A. V. Aho and J. D. Ullman “Patterns, Automata and Regular expressions” Foundations of Computer Science, New York: W. H. Freeman & Company, pp. 530-571.
- M. V. Lawson “Introduction to finite automata; Non-deterministic automata; Kleene’s Theorem” Finite Automata, 1 ed. New York: Chapman and Hall/CRC, pp.1-14, pp. 53-60, 2003.
Index Terms
Keywords