Parameterized DAWGs: Efficient constructions and bidirectional pattern searches
Parameterized DAWGs: Efficient constructions and bidirectional pattern searches
复制标题
参数化 DAWG：高效构造和双向模式搜索
DOI：
10.1016/j.tcs.2022.09.008
复制
发表时间：
2022
影响因子：
1.1
通讯作者：
Masayuki Takeda
中科院分区：
文献类型：
--
作者：
Katsuhito Nakashima;Noriki Fujisato;Diptarama Hendrian;Yuto Nakashima;Ryo Yoshinaka;Shunsuke Inenaga;Hideo Bannai;Ayumi Shinohara;Masayuki Takeda
如果在Σ∪Π上存在一个重命名双射f： Σ∪Π→Σ∪Π，它是Σ上的恒等并将x转换为y（反之亦然），那么两个长度相等的字符串x和y就被称为参数化匹配（p-match）。p匹配问题是在文本中查找与给定模式p匹配的子字符串。本文提出了参数化后缀自动机（p-suffix automata）和参数化有向无环词图（PDAWGs），它们是后缀自动机和DAWGs的p匹配版本。虽然后缀自动机和dawg对于标准字符串是等效的，但我们证明p-后缀自动机可以有Θ （n 2）个节点和边，而pdawg只有O (n)个节点和边，其中n是输入字符串的长度。我们还给出了一个O (n| Π| log (| Π|+| Σ|))- O (n)-空间算法，该算法以从左到右的在线方式构建PDAWG。结果表明，参数化后缀树也可以在相同的时间和空间中以从右向左的在线方式构建。这种对偶性还使我们得到了两种更有效的p匹配算法：给定输入字符串T的反转T的参数化后缀树，可以以离线方式在O (n)时间内构建T的PDAWG；可以使用O (n)空间在O （m log (| Π|+| Σ|)+ occ）时间内执行双向p匹配，其中m表示模式长度，occ是文本T中模式出现的次数。
Two strings x and y over Σ∪ Π of equal length are said to parameterized match (p-match) if there is a renaming bijection f: Σ∪ Π→ Σ∪ Π that is identity on Σ and transforms x to y (or vice versa). The p-matching problem is to look for substrings in a text that p-match a given pattern. In this paper, we propose parameterized suffix automata (p-suffix automata) and parameterized directed acyclic word graphs (PDAWGs) which are the p-matching versions of suffix automata and DAWGs. While suffix automata and DAWGs are equivalent for standard strings, we show that p-suffix automata can have Θ (n 2) nodes and edges but PDAWGs have only O (n) nodes and edges, where n is the length of an input string. We also give an O (n| Π| log(| Π|+| Σ|))-time O (n)-space algorithm that builds the PDAWG in a left-to-right online manner. As a byproduct, it is shown that the parameterized suffix tree for the reversed string can also be built in the same time and space, in a right-to-left online manner. This duality also leads us to two further efficient algorithms for p-matching: Given the parameterized suffix tree for the reversal T‾ of the input string T, one can build the PDAWG of T in O (n) time in an offline manner; One can perform bidirectional p-matching in O (m log(| Π|+| Σ|)+ occ) time using O (n) space, where m denotes the pattern length and occ is the number of pattern occurrences in the text T.