Novel Results on the Number of Runs of the Burrows-Wheeler-Transform
Novel Results on the Number of Runs of the Burrows-Wheeler-Transform
复制标题
Burrows-Wheeler-变换运行次数的新结果
DOI：
10.1007/978-3-030-67731-2_18
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Toffanello Anna
中科院分区：
文献类型：
--
作者：
Giuliani Sara;Inenaga Shunsuke;Liptak Zsuzsanna;Prezza Nicola;Sciortino Marinella;Toffanello Anna
Burrows-Wheeler变换（BWT）是一种可逆的字符串变换，是当前字符串处理中许多数据结构的基本组成部分之一。 它是数据压缩的核心，也是序列数据（如网页、基因组和其他生物序列或实际上任何文本数据）的高效查询算法的核心。BWT非常适合压缩，因为它的等字母串（通常称为asr）的数量通常比原始字符串的数量少得多;特别是，它非常适合具有许多重复因子的字符串。事实上，这个参数作为重复性的度量，特别是用来评估压缩索引数据结构在空间和时间方面的性能，已经引起了人们的极大关注。Kempa和Kociumaka [FOCS 2020]给出了第一个非平凡的上限，对于任何长度n的字符串。然而，我们对这个上限的紧性一无所知。我们提出了无限家庭的二进制字符串，从而给出了第一个非平凡的下界，最大的所有字符串的长度为n。我们的结果表明，这不是一个理想的措施的重复字符串，因为重复的因素的数量是不变的字符串和它的反向。我们相信，有一个更复杂的关系之间的运行的BWT和字符串的组合属性的数量。
The Burrows-Wheeler-Transform (BWT), a reversible string transformation, is one of the fundamental components of many current data structures in string processing. It is central in data compression, as well as in efficient query algorithms for sequence data, such as webpages, genomic and other biological sequences, or indeed any textual data. The BWT lends itself well to compression because its number of equal-letter-runs (usually referred to asr) is often considerably lower than that of the original string; in particular, it is well suited for strings with many repeated factors. In fact, much attention has been paid to therparameter as measure of repetitiveness, especially to evaluate the performance in terms of both space and time of compressed indexing data structures.In this paper, we investigate, the ratio ofrand of the number of runs of the BWT of the reverse ofv. Kempa and Kociumaka [FOCS 2020] gave the first non-trivial upper bound as, for any stringvof lengthn. However, nothing is known about the tightness of this upper bound. We present infinite families of binary strings for whichholds, thus giving the first non-trivial lower bound on, the maximum over all strings of lengthn.Our results suggest thatris not an ideal measure of the repetitiveness of the string, since the number of repeated factors is invariant between the string and its reverse. We believe that there is a more intricate relationship between the number of runs of the BWT and the string’s combinatorial properties.
登录
查看更多内容
克里斯托弗课程
DOI：
10.1051/ita:2005038
发表时间：
2006
期刊：
RAIRO Theor. Informatics Appl.
影响因子：
--
作者：
J. Borel;C. Reutenauer
通讯作者：
C. Reutenauer
在线RLBWT的更快实现及其在LZ77解析中的应用
DOI：
10.1016/j.jda.2018.11.002
发表时间：
2018
期刊：
Journal of Discrete Algorithms
影响因子：
--
作者：
Ohno Tatsuya;Sakai Kensuke;Takabatake Yoshimasa;I Tomohiro;Sakamoto Hiroshi
通讯作者：
Sakamoto Hiroshi
影响因子：
2.5
作者：
Kieffer, JC;Yang, EH
通讯作者：
Yang, EH
字典压缩的根源：字符串吸引子
DOI：
10.1145/3188745.3188814
发表时间：
2017
期刊：
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Dominik Kempa;N. Prezza
通讯作者：
N. Prezza
标准 Sturmian 单词的组合
DOI：
10.1007/3-540-63246-8_15
发表时间：
1997
期刊：
Structures in Logic and Computer Science
影响因子：
--
作者：
A. Luca
通讯作者：
A. Luca