Compressed automata for dictionary matching
Compressed automata for dictionary matching
复制标题
用于字典匹配的压缩自动机
DOI：
10.1016/j.tcs.2015.01.019
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Masayuki Takeda
中科院分区：
文献类型：
--
作者：
Tomohiro I;Takaaki Nishimoto;Shunsuke Inenaga ;Hideo Bannai; Masayuki Takeda
我们解决一个变体的字典匹配问题的字典是由一个直线程序（SLP）。对于给定的大小为n、高度为h的SLP压缩字典D，代表总长度为N的m个模式，我们提出了Aho-Corasick自动机的O（n 2 log N）大小表示，该自动机在摊销O（h+ m）中识别D中模式的所有出现每个字符的运行时间。我们还提出了一个算法来构造这种压缩Aho-Corasick自动机在O（n3 log n log N）时间和O（n2 log N）空间。在一个空间的情况下，D只代表一个单一的模式，我们提出了一个O（n log N）大小的表示的莫里斯-普拉特自动机，使我们能够找到所有出现的模式在摊销O（h）运行时间每个字符，我们展示了如何构建这种表示在O（n 3 log n log N）的时间与O（n 2 log N）的工作空间。
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.