论文标题
对数的同等字母为纯粹的形态词的bwt运行
Logarithmic equal-letter runs for BWT of purely morphic words
论文作者
论文摘要
在本文中，我们研究了由burrows-wheeler变换（$ bwt $）产生的等质运行的数字$ r_ {bwt} $，当它应用于纯粹的形态有限词，这是由迭代延长的形态产生的单词。这样的参数$ r_ {bwt} $非常重要，因为它提供了$ bwt $的性能，就可压缩性和索引而言。特别是，我们证明，当将$ bwt $应用于二进制字母上的任何纯形形的有限词时，$ r_ {bwt} $ is $ \ mathcal {o}（\ log log n）$，其中$ n $是单词的长度。此外，我们证明$ r_ {bwt} $是$θ（\ log n）$，对于由一大型延长的二进制形态产生的二进制单词。这些界限是通过提供此类词的\ emph {bispecial圆形因子}的一些新结构特性来证明的。
In this paper we study the number $r_{bwt}$ of equal-letter runs produced by the Burrows-Wheeler transform ($BWT$) when it is applied to purely morphic finite words, which are words generated by iterating prolongable morphisms. Such a parameter $r_{bwt}$ is very significant since it provides a measure of the performances of the $BWT$, in terms of both compressibility and indexing. In particular, we prove that, when $BWT$ is applied to any purely morphic finite word on a binary alphabet, $r_{bwt}$ is $\mathcal{O}(\log n)$, where $n$ is the length of the word. Moreover, we prove that $r_{bwt}$ is $Θ(\log n)$ for the binary words generated by a large class of prolongable binary morphisms. These bounds are proved by providing some new structural properties of the \emph{bispecial circular factors} of such words.
