pBWT: Achieving Succinct Data Structures for Parameterized Pattern Matching and Related Problems
pBWT: Achieving Succinct Data Structures for Parameterized Pattern Matching and Related Problems
复制标题
pBWT：实现参数化模式匹配和相关问题的简洁数据结构
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Sharma V. Thankachan
中科院分区：
文献类型：
--
作者：
Arnab Ganguly;Rahul Shah;Sharma V. Thankachan
在过去的二十年中，简洁数据结构和压缩文本索引领域取得了相当大的进展。一项重要成果（主要使用基于Burrows - Wheeler变换（BWT）的技术）是以最优比特数获得了后缀树的全部功能。允许使用BWT设计压缩索引的一个关键性质是保序后缀链接。具体来说，内部节点子树中两个后缀之间的相对顺序与截断这两个后缀的第一个字符所得到的后缀之间的相对顺序相同。不幸的是，在文本索引问题的许多变体中，例如参数化模式匹配、二维模式匹配和序同构模式匹配，这个性质并不成立。因此，基于BWT的压缩索引不能直接应用。此外，在简洁数据结构领域的发展过程中，针对这些变体中的任何一个的压缩索引一直难以实现。我们在其中一个这样的问题上，即参数化模式匹配问题，取得了积极的突破。设T是一个包含来自字母表Σ的n个字符的文本，Σ是两个不相交集合的并集：包含静态字符（s - 字符）的Σs和包含参数化字符（p - 字符）的Σp。一个模式P（也基于Σ）与T的等长子串S匹配，当且仅当s - 字符完全匹配，并且存在一个一一映射函数，将S中的p - 字符重命名为P中的p - 字符。任务是找到所有这样的子串S的起始位置（出现位置）。先前的索引[Baker，STOC 1993]，称为参数化后缀树，需要Θ(n log n)比特的空间，并且可以在时间O(|P|log σ + occ)内找到所有出现位置，其中σ = |Σ|。我们引入了一个n log σ + O(n)比特的索引，其查询时间为O(|P|log σ + occ·log n log σ)。其核心是一种新的类似于BWT的变换，我们称之为参数化Burrows - Wheeler变换（pBWT）。这些技术被扩展以获得针对Idury和Schaffer[CPM，1994]的参数化字典匹配问题的简洁索引。
The fields of succinct data structures and compressed text indexing have seen quite a bit of progress over the last two decades. An important achievement, primarily using techniques based on the Burrows-Wheeler Transform (BWT), was obtaining the full functionality of the suffix tree in the optimal number of bits. A crucial property that allows the use of BWT for designing compressed indexes is order-preserving suffix links. Specifically the relative order between two suffixes in the subtree of an internal node is same as that of the suffixes obtained by truncating the first character of the two suffixes. Unfortunately, in many variants of the text-indexing problem, for e.g., parameterized pattern matching, 2D pattern matching, and order-isomorphic pattern matching, this property does not hold. Consequently, the compressed indexes based on BWT do not directly apply. Furthermore, a compressed index for any of these variants has been elusive throughout the advancement of the field of succinct data structures. We achieve a positive breakthrough on one such problem, namely the Parameterized Pattern Matching problem. Let T be a text that contains n characters from an alphabet Σ, which is the union of two disjoint sets: Σs containing static characters (s-characters) and Σp containing parameterized characters (p-characters). A pattern P (also over Σ) matches an equal-length substring S of T iff the s-characters match exactly, and there exists a one-to-one function that renames the p-characters in S to that in P. The task is to find the starting positions (occurrences) of all such substrings S. Previous index [Baker, STOC 1993], known as Parameterized Suffix Tree, requires Θ(n log n) bits of space, and can find all occ occurrences in time O(|P|log σ+occ), where σ = |Σ|. We introduce an n log σ + O(n)-bit index with O(|Plog σ+occ·log n log σ) query time. At the core, lies a new BWT-like transform, which we call the Parameterized Burrows-Wheeler Transform (pBWT). The techniques are extended to obtain a succinct index for the Parameterized Dictionary Matching problem of Idury and Schaffer [CPM, 1994].