A fast algorithm for multi-string matching based on automata optimization
Authors:
- 1 January 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 2, V2-379-V2-383
Abstract
Multi-string matching requires to handle massive amount of data in pattern recognition, intrusion detection, and biological sequence analysis applications. This paper proposes a new algorithm to construct an optimal automation to achieve fast string matching. The algorithm consists of five steps: sorting, forming subtrees, encoding all subtrees, similarity checking, and completing all transitions. The algorithmic complexity is proven O(umk), where u is the number of the symbols in the alphabet set and m and k are the average length and the number of strings being matched. We report analytical results on the matching complexity. These results prove the efficiency and effectiveness of the optimized automata generated for fast matching of multiple strings.Keywords
This publication has 13 references indexed in Scilit:
- Scalable Multigigabit Pattern Matching for Packet InspectionIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2008
- Extension of Aho-Corasick Algorithm to Detect Injection Attacks2008
- Efficient implementation of Aho–Corasick pattern matching automata using UnicodeSoftware: Practice and Experience, 2006
- Fast and Scalable Pattern Matching for Network Intrusion Detection SystemsIEEE Journal on Selected Areas in Communications, 2006
- Algorithms to accelerate multiple regular expressions matching for deep packet inspection2006
- Bit-split string-matching engines for intrusion detection and preventionACM Transactions on Architecture and Code Optimization, 2006
- High-throughput linked-pattern matching for intrusion detection systems2005
- A Fast Algorithm for Approximate String Matching on Gene SequencesLecture Notes in Computer Science, 2005
- Scalable Pattern Matching for High Speed Networks2004
- Speed-up of Aho-Corasick pattern matching machines by rearranging states2001