CFP last date
15 January 2025
Call for Paper
February Edition
IJAIS solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 15 January 2025

Submit your paper
Know more
The week's pick
Responsive image
Ordered Frequent Itemsets Matrix Based On Fp-Tree Structure And Apriori Algorithm

Abdulkader M. Al-Badani Abdualmajed A. Al-Khulaidi
Random Articles
Reseach Article

String Searching with DFA-based Algorithm

by Preye Ejendibia, Barileé B. Baridam
journal cover thumbnail

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

@article{ 10.5120/ijais2015451415,
author = { Preye Ejendibia, Barileé B. Baridam },
title = { String Searching with DFA-based Algorithm },
journal = { International Journal of Applied Information Systems },
issue_date = { October 2015 },
volume = { 9 },
number = { 8 },
month = { October },
year = { 2015 },
issn = { 2249-0868 },
pages = { 1-6 },
numpages = {9},
url = { https://www.ijais.org/archives/volume9/number8/822-2015451415/ },
doi = { 10.5120/ijais2015451415 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2023-07-05T19:00:35.094115+05:30
%A Preye Ejendibia
%A Barileé B. Baridam
%T String Searching with DFA-based Algorithm
%J International Journal of Applied Information Systems
%@ 2249-0868
%V 9
%N 8
%P 1-6
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
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
  1. 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
  2. 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.
  3. E. Gribkoff “Applications of Deterministic Finite Automata” ECS 120 UC Davis, Spring 2013.
  4. 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.
  5. G. A. Stephen, “String Searching Algorithms” Singapore: World Scientific, Chapter 2, pp. 5-37, 2001.
  6. S. Mitra, T. Acharya “Data Mining: Multmedia, Soft Computting and Bioinformatics” New Jersey: Wiley-Interscience, Chapter 4, pp. 143-169, 2003.
  7. J. D. Ullman, Video Lecture “Informal Introduction to finite automata” Stanford University, May 2012, www.coursera.com
  8. 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.
  9. D. Knuth, J. Morris and V. Pratt “Fast pattern matching in strings” SIAM journal of Computting, Volume 6, pp. 323-350, 1977.
  10. 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.
  11. R. S. Boyer, J. S. Moore “A fast string searching algorithm” Communications of the ACM, Volume 20, No. 10 pp.762-772, October 1977.
  12. R. N. Hoorspool “Practical fast searching in strings” Software – Practice and Experience, Volume 10 No. 6, pp. 501-506, 1980.
  13. 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.
  14. D. M. Sunday “A very fast substring searchalgorithm” Communications of the ACM, Volume 33, No. 8, pp. 132-142, August 1990.
  15. 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.
  16. 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

Computer Science
Information Sciences

Keywords

Brute-force DFA Algorithms String Searching.

Powered by PhDFocusTM