TY - GEN
T1 - Compressed automata for dictionary matching
AU - I, Tomohiro
AU - Nishimoto, Takaaki
AU - Inenaga, Shunsuke
AU - Bannai, Hideo
AU - Takeda, Masayuki
N1 - Funding Information:
The research of Shunsuke Inenaga was in part supported by Grant-in-Aid of Inamori Foundation and by KAKENHI 23700022 . Hideo Bannai was supported by KAKENHI 25280086 . Masayuki Takeda was supported by KAKENHI 25240003 .
PY - 2013
Y1 - 2013
N2 - A variant of the dictionary matching problem is addressed where the dictionary is given in an SLP-compressed form. An Aho-Corasick automata-based algorithm is presented which pre-processes the compressed dictionary D in O(n4log n) time using O(n2 log N) space and recognizes all occurrences of the patterns in D in amortized O(h + m) running time per character, where n and N are, respectively, the compressed and uncompressed sizes of D, and h is the height of D, and m is the number of patterns in the dictionary.
AB - A variant of the dictionary matching problem is addressed where the dictionary is given in an SLP-compressed form. An Aho-Corasick automata-based algorithm is presented which pre-processes the compressed dictionary D in O(n4log n) time using O(n2 log N) space and recognizes all occurrences of the patterns in D in amortized O(h + m) running time per character, where n and N are, respectively, the compressed and uncompressed sizes of D, and h is the height of D, and m is the number of patterns in the dictionary.
UR - https://www.scopus.com/pages/publications/84881250412
UR - https://www.scopus.com/pages/publications/84881250412#tab=citedBy
U2 - 10.1007/978-3-642-39274-0_28
DO - 10.1007/978-3-642-39274-0_28
M3 - Conference contribution
AN - SCOPUS:84881250412
SN - 9783642392733
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 319
EP - 330
BT - Implementation and Application of Automata - 18th International Conference, CIAA 2013, Proceedings
PB - Springer Verlag
T2 - 18th International Conference on Implementation and Application of Automata, CIAA 2013
Y2 - 16 July 2013 through 19 July 2013
ER -