Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14]


Journal of Information Science and Engineering, Vol. 32 No. 2, pp. 403-424 (March 2016)


A Novel Algorithm for Pattern Matching Based on Modified Push-Down Automata


BILAL LOUNNAS1, BRAHIM BOUDERAH1 AND ABDELOUAHAB MOUSSAOUI2
1Computer Science Department
University of Msila
M'sila, 28000 Algeria
E-mail: lounnas.bilal@gmail.com; bouderah_b@yahoo.fr
2Computer Science Department
Ferhat Abbas University
Setif, 19000 Algeria
E-mail: moussaoui.abdel@gmail.com


In this paper we propose a new algorithm called MEPda (Motif Extraction algorithm based on Push-down automata) to solve the problem of finding patterns containing loops. These loop-patterns or loop-motifs are very known and used in many domains, especially in mathematics and bioinformatics. MEPda meant to find these kinds of patterns by using pushdown automata as a mechanism of matching process alongside with a counter to verify the acceptance length of loop in an optimistic way of looking. The results obtained from MEPda have shown high accuracy and much reduced runtime for finding patterns containing loops compared to using a push-down automata based algorithm without implementing a counter, a regular expression based algorithm, an Aho-Corasick algorithm, a KMP algorithm, and MoTeX algorithm.

Keywords: pattern matching, pattern, loop-pattern, loop-motif, motif, motif discovery, pushdown automata, algorithm

Full Text () Retrieve PDF document (201603_09.pdf)

Received September 26, 2014; revised December 14, 2014 & March 18, 2015; accepted May 7, 2015.
Communicated by Vincent S. Tseng.