论文标题
在压缩字符串中最大重复序列的扩展
On Extensions of Maximal Repeats in Compressed Strings
论文作者
论文摘要
本文为压缩字符串中的几个最大重复序列和最大对的子集提供了上限，并在最大对和运行长度的毛burrows-wheeler变换之间提出了以前未知的关系。 这种关系用于获得burrows-wheeler猜想的不同证明，该猜想最近被Kempa和Kociumaka证明了“ burrows-wheeler Transform的解决”。 More formally, this paper proves that a string $S$ with $z$ LZ77-factors and without $q$-th powers has at most $73(\log_2 |S|)(z+2)^2$ runs in the run-length Burrows-Wheeler transform and the number of arcs in the compacted directed acyclic word graph of $S$ is bounded from above by $18q(1+\log_q | s |）（z+2）^2 $。
This paper provides an upper bound for several subsets of maximal repeats and maximal pairs in compressed strings and also presents a formerly unknown relationship between maximal pairs and the run-length Burrows-Wheeler transform. This relationship is used to obtain a different proof for the Burrows-Wheeler conjecture which has recently been proven by Kempa and Kociumaka in "Resolution of the Burrows-Wheeler Transform Conjecture". More formally, this paper proves that a string $S$ with $z$ LZ77-factors and without $q$-th powers has at most $73(\log_2 |S|)(z+2)^2$ runs in the run-length Burrows-Wheeler transform and the number of arcs in the compacted directed acyclic word graph of $S$ is bounded from above by $18q(1+\log_q |S|)(z+2)^2$.
