Name
Abstract | ||
|---|---|---|
We address a variant of the dictionary matching problem where the dictionary is represented by a straight line program (SLP). For a given SLP-compressed dictionary D of size n and height h representing m patterns of total length N, we present an O ( n 2 log ¿ N ) -size representation of Aho-Corasick automaton which recognizes all occurrences of the patterns in D in amortized O ( h + m ) running time per character. We also propose an algorithm to construct this compressed Aho-Corasick automaton in O ( n 3 log ¿ n log ¿ N ) time and O ( n 2 log ¿ N ) space. In a spacial case where D represents only a single pattern, we present an O ( n log ¿ N ) -size representation of the Morris-Pratt automaton which permits us to find all occurrences of the pattern in amortized O ( h ) running time per character, and we show how to construct this representation in O ( n 3 log ¿ n log ¿ N ) time with O ( n 2 log ¿ N ) working space. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.tcs.2015.01.019 | Theor. Comput. Sci. |
Keywords | Field | DocType |
dictionary matching,aho-corasick automaton,pattern matching,morris-pratt automaton,straight line program | Discrete mathematics,Computer science,Automaton,Algorithm,Uncompressed video | Journal |
Volume | Issue | ISSN |
578 | C | 0304-3975 |
Citations | PageRank | References |
2 | 0.37 | 16 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tomohiro I | 1 | 148 | 22.06 |
| Takaaki Nishimoto | 2 | 23 | 3.54 |
| Shunsuke Inenaga | 3 | 595 | 79.02 |
| Hideo Bannai | 4 | 620 | 79.87 |
| Masayuki Takeda | 5 | 902 | 79.24 |