Call for Paper - January 2024 Edition
IJCA solicits original research papers for the January 2024 Edition. Last date of manuscript submission is December 20, 2023. Read More

Streamlining of DFA based Pattern Matchers

Print
PDF
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Year of Publication: 2017
Authors:
Ashish Kumar Pandey, Amit Sinha
10.5120/ijca2017913212

Ashish Kumar Pandey and Amit Sinha. Streamlining of DFA based Pattern Matchers. International Journal of Computer Applications 161(6):10-13, March 2017. BibTeX

@article{10.5120/ijca2017913212,
	author = {Ashish Kumar Pandey and Amit Sinha},
	title = {Streamlining of DFA based Pattern Matchers},
	journal = {International Journal of Computer Applications},
	issue_date = {March 2017},
	volume = {161},
	number = {6},
	month = {Mar},
	year = {2017},
	issn = {0975-8887},
	pages = {10-13},
	numpages = {4},
	url = {http://www.ijcaonline.org/archives/volume161/number6/27151-2017913212},
	doi = {10.5120/ijca2017913212},
	publisher = {Foundation of Computer Science (FCS), NY, USA},
	address = {New York, USA}
}

Abstract

This paper presents an efficient algorithm for finding matches to a given regular expression in given text using optimization of DFA. To match a regular expression of length n, a serial machine requires 0(2^n) memory and takes 0(1) time per text character. The proposed approach requires only 0(n^2) space and still process a text character in 0(1) time (one clock cycle).The improvement is due to the optimization of DFA that means without converting it into the NFA, directly convert into the DFA. Finite Automaton (DFA) used to perform the matching. Furthermore, the paper presents a simple, fast algorithm that quickly constructs the DFA for the given regular expression.

References

  1. J. E. Hopcroft and J. D. Ullman, Introduction to automata theory,languages, and computation,” Addison Wesley, 1979.
  2. Y. Sun, H. Liu, V. Valgenti, and M. S. Kim, “Hybrid regular expression matching for deep packet inspection on multi-core architecture,” in Proceedings of the 19th International onference on Computer Communications and Networks, ICCCN’10, Aug. 2010, pp. 1–7.
  3. P.Jayaprabha and Rm. Somasundaram ,”Content Based Image Retrieval Methods Using Graphical Image Retrieval Algorithm (GIRA)”., Computer Science And Application, Vol. 1, No. 1, January, 2012.
  4. 1997,http://www.igm.univmlv.fr/~lecroq/string/index.html C. Charras and T. Lecroq: Exact String MatchingAlgorithms. Univ. de Rouen.
  5. Srikanthan, Sharanyan ,“Implementing the dynamic time warping algorithm in multithreaded environments for realtime and unsupervised pattern discovery”., Computer and Communication Technology (ICCCT), 2011 2ndInternational Conference on 394 – 398, 15-17 Sept. 2011.
  6. Stan Salvador & Philip Chan,”Fast DTW: Toward Accurate Dynamic Time Warping in Linear Time and Space”.KDDWorkshop on Mining Temporal and Sequential Data, pp. 70-80, 2004. (http://cs.fit.edu/~pkc/papers/tdm04.pdf).
  7. Chu, S., E. Keogh, D. Hart & Michael Pazzani. Iterative, Deepening Dynamic Time Warping for Time Series. In Proc.of the Second SIAM Intl. Conf. on Data Mining. Arlington, Virginia, 2002.
  8. Arcangel, Cory. "On Compression". Retrieved 6 March 2013.
  9. Jaiswal, R.C. Audio-Video Engineering. Pune, Maharashtra: Nirali Prakashan. p. 3.41. (2009).ISBN 9788190639675.
  10. "Video Coding". Center for Signal and Information Processing Research. Georgia Institute of Technology. Retrieved 6March 2013.

Keywords

DFA, NFA