论文标题
计算参数化的洞穴 - 在线旋转器变换
Computing the Parameterized Burrows--Wheeler Transform Online
论文作者
论文摘要
参数化的字符串是字符串的概括，因为它们的字符是从两个不同的字母中绘制的，其中一个字母被认为是静态字符的字母，另一个被认为是参数字符的字母。如果在所有字符上进行两次试验，则两个参数化的字符串是一个参数化的匹配，使得两者在保持静态字符的同时将一个字符串转换为另一个字符串（即，它作为静态字母上的身份）。 Ganguly等。 [SODA 2017]提出了参数化的洞穴 - 轮毂变换（PBWT）作为洞穴的变体 - 旋转器转换，以进行空间有效的参数化模式匹配。在本文中，我们提出了一种用于在线计算PBWT的算法，通过从右到左右读取给定输入字符串的字符。我们的算法在$ o（|π| \ log n / \ log \ log n）$ to a $ o（| \ log n / \ log \ log n）$对于每个输入字符的时间，其中$ n $和$π$分别表示输入字符串的大小和参数字符的字母。
Parameterized strings are a generalization of strings in that their characters are drawn from two different alphabets, where one is considered to be the alphabet of static characters and the other to be the alphabet of parameter characters. Two parameterized strings are a parameterized match if there is a bijection over all characters such that the bijection transforms one string to the other while keeping the static characters (i.e., it behaves as the identity on the static alphabet). Ganguly et al. [SODA 2017] proposed the parameterized Burrows--Wheeler transform (pBWT) as a variant of the Burrows--Wheeler transform for space-efficient parameterized pattern matching. In this paper, we propose an algorithm for computing the pBWT online by reading the characters of a given input string one-by-one from right to left. Our algorithm works in $O(|Π| \log n / \log \log n)$ amortized time for each input character, where $n$ and $Π$ denote the size of the input string and the alphabet of the parameter characters, respectively.
