Efficient dynamic dictionary matching with DAWGs and AC-automata
Efficient dynamic dictionary matching with DAWGs and AC-automata
复制标题
与 DAWG 和 AC 自动机进行高效动态字典匹配
DOI：
10.1016/j.tcs.2018.04.016
复制
发表时间：
2019
影响因子：
1.1
通讯作者：
Ayumi Shinohara
中科院分区：
文献类型：
--
作者：
Diptarama Hendrian;Shunsuke Inenaga;Ryo Yoshinaka;Ayumi Shinohara
字典匹配是在文本$T$上找到集合$D$（称为字典）中所有模式的任务。Aho-Corasick自动机AC自动机是一种数据结构，它使我们能够在O（d\log\sigma）$预处理时间和$O（n\log\sigma+occ）$匹配时间，其中$d$是$D$中模式的总长度，$n$是文本的长度，$\sigma$是字母表大小，而$occ$是文本中所有模式出现的总次数。动态字典匹配是一种变体，其中模式可以动态地插入到$D $中或从$D$中删除。如果只允许插入，这个问题被称为半动态字典匹配。在本文中，我们提出了两个有效的算法。对于长度为$m$的模式，我们的第一个算法支持$O中的插入（m\log\sigma+\log d/\log\log d）$时间和模式匹配，以$O为单位（n\log\sigma+occ）$ time用于半动态设置，并支持$O中的插入和删除（\sigma m+\log d/\log\log d）$时间和模式匹配在$O（n（\log d/\log\log d+\log\sigma）+occ（\log d/\log\log d））$时间中进行动态设置。该算法基于有向无环词图。第二种算法是基于AC自动机的，对于半动态设置支持O（m\log \sigma+u_f+u_o）$时间的插入操作，对于动态设置支持O（\sigma m+u_f+u_o）$时间的插入和删除操作，其中$u_f$和$u_o$分别表示失效函数和输出函数需要更新的状态数。该算法在两种设置下都能在O（n\log\sigma+occ）$时间内完成模式匹配。我们的算法实现了最佳的更新时间AC-自动机为基础的方法在恒定大小的字母表，因为任何算法，显式维护AC-自动机需要$\欧米茄（m+u_f+u_o）$更新时间。
The dictionary matching is a task to find all occurrences of patterns in a set $D$ (called a dictionary) on a text $T$. The Aho-Corasick-automaton (AC-automaton) is a data structure which enables us to solve the dictionary matching problem in $O(d\log\sigma)$ preprocessing time and $O(n\log\sigma+occ)$ matching time, where $d$ is the total length of the patterns in $D$, $n$ is the length of the text, $\sigma$ is the alphabet size, and $occ$ is the total number of occurrences of all the patterns in the text. The dynamic dictionary matching is a variant where patterns may dynamically be inserted into and deleted from $D$. This problem is called semi-dynamic dictionary matching if only insertions are allowed. In this paper, we propose two efficient algorithms. For a pattern of length $m$, our first algorithm supports insertions in $O(m\log\sigma+\log d/\log\log d)$ time and pattern matching in $O(n\log\sigma+occ)$ time for the semi-dynamic setting and supports both insertions and deletions in $O(\sigma m+\log d/\log\log d)$ time and pattern matching in $O(n(\log d/\log\log d+\log\sigma)+occ(\log d/\log\log d))$ time for the dynamic setting by some modifications. This algorithm is based on the directed acyclic word graph. Our second algorithm, which is based on the AC-automaton, supports insertions in $O(m\log \sigma+u_f+u_o)$ time for the semi-dynamic setting and supports both insertions and deletions in $O(\sigma m+u_f+u_o)$ time for the dynamic setting, where $u_f$ and $u_o$ respectively denote the numbers of states in which the failure function and the output function need to be updated. This algorithm performs pattern matching in $O(n\log\sigma+occ)$ time for both settings. Our algorithm achieves optimal update time for AC-automaton based methods over constant-size alphabets, since any algorithm which explicitly maintains the AC-automaton requires $\Omega(m+u_f+u_o)$ update time.