Open AccessA NOVEL PATTERN MATCHING METHOD FOR MEMORY REDUCTION APPLICATIONS USING AC ALGORITHM
Author(s) -
G.F. Harish Reddy,
S. Indira Priyadarsini,
J. Pratibha
Publication year - 2014
Publication title -
international journal of electronic signal and systems
Language(s) - English
Resource type - Journals
ISSN - 2231-5969
DOI - 10.47893/ijess.2014.1195
Subject(s) - computer science , correctness , string searching algorithm , reduction (mathematics) , data stream mining , pattern matching , algorithm , matching (statistics) , regular expression , theoretical computer science , data mining , mathematics , artificial intelligence , statistics , geometry , programming language
Advances in computer networks and storage subsystems continue to push the rate at which data streams must be processed between and within computer systems. Meanwhile, the content of such data streams is subjected to ever increasing scrutiny, as components at all levels mine the streams for patterns that can trigger time-sensitive action. The problem of discovering credit card numbers, currency values, or telephone numbers requires a more general specification mechanism. While there is a well developed theory for regular expressions and their implementation via Finite-State Machines (FSMs), the use of regular expressions for high-performance pattern matching is more difficult and is an area of ongoing research. In this Paper, a memory-efficient pattern matching algorithm which can significantly reduce the number of states and transitions by merging pseudo-equivalent states while maintaining correctness of string matching. In addition, the new algorithm is complementary to other memory reduction approaches and provides further reductions in memory needs.