Name
Abstract | ||
|---|---|---|
The Aho-Corasick algorithm is a classic method for matching a set of strings. However, the huge memory usage of Aho-Corasick automaton prevents it from being applied to large-scale pattern sets. Here we present a simple but efficient table compression method to reduce the automaton's space. The basic idea of our method is based on equivalent rows elimination, which groups state rows into equivalent classes and eliminates the duplicates. Experiments demonstrate that the proposed method significantly reduces the memory usage and still runs at linear searching time comparable to that of extended Aho-Corasick algorithm. Our method provides good trade-off between memory usage and searching time. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-02979-0_12 | CIAA |
Keywords | Field | DocType |
aho-corasick algorithm,efficient table compression method,extended aho-corasick automaton,aho-corasick automaton,memory usage,classic method,table compression method,equivalent class,extended aho-corasick algorithm,equivalent rows elimination,huge memory usage,aho corasick | Row,Compression (physics),Computer science,Automaton,Algorithm,Theoretical computer science,Aho–Corasick string matching algorithm | Conference |
Volume | ISSN | Citations |
5642 | 0302-9743 | 2 |
PageRank | References | Authors |
0.38 | 12 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yanbing Liu | 1 | 56 | 10.17 |
| Yifu Yang | 2 | 22 | 1.45 |
| Ping Liu | 3 | 14 | 7.39 |
| Jianlong Tan | 4 | 132 | 22.14 |