论文标题
平衡运行长度直线程序*
Balancing Run-Length Straight-Line Programs*
论文作者
论文摘要
最近证明，任何生成给定的字符串$ w $的SLP都可以在线性时间内变成相同渐近尺寸的等效平衡SLP。我们表明，此结果也适用于RLSLP，它们是SLP的slps，其$ a \ rightarrow b^t $的运行长度规则$ t> 2 $，从而导出$ \ texttt {exp} {exp}（a）= \ texttt {exptt {exp} {exp}（exp}（b）^t $。直接的结果是简化用于提取RLSLP压缩字符串的子字符串的算法。 We also show that several problems like answering RMQs and computing Karp-Rabin fingerprints on substrings can be solved in $\mathcal{O}(g_{rl})$ space and $\mathcal{O}(\log n)$ time, $g_{rl}$ being the size of the smallest RLSLP generating the string, of length $n$.我们将结果扩展到在字符串范围内求解更多的一般操作，以$ \ MATHCAL {o}（g_ {rl}）$ space和$ \ Mathcal {o}（\ log n）$ applications $ \ {rl}）$ space。通常，最小的RLSLP可以比最小的SLP渐近，最多可以使用$ \ Mathcal {O}（\ log n）$ factor，因此我们的结果可以在计算这些操作所需的空间方面有效地有效地对某些字符串族来差异。
It was recently proved that any SLP generating a given string $w$ can be transformed in linear time into an equivalent balanced SLP of the same asymptotic size. We show that this result also holds for RLSLPs, which are SLPs extended with run-length rules of the form $A \rightarrow B^t$ for $t>2$, deriving $\texttt{exp}(A) = \texttt{exp}(B)^t$. An immediate consequence is the simplification of the algorithm for extracting substrings of an RLSLP-compressed string. We also show that several problems like answering RMQs and computing Karp-Rabin fingerprints on substrings can be solved in $\mathcal{O}(g_{rl})$ space and $\mathcal{O}(\log n)$ time, $g_{rl}$ being the size of the smallest RLSLP generating the string, of length $n$. We extend the result to solving more general operations on string ranges, in $\mathcal{O}(g_{rl})$ space and $\mathcal{O}(\log n)$ applications of the operation. In general, the smallest RLSLP can be asymptotically smaller than the smallest SLP by up to an $\mathcal{O}(\log n)$ factor, so our results can make a difference in terms of the space needed for computing these operations efficiently for some string families.
