论文标题
SLP的空间效率转换
Space-efficient conversions from SLPs
论文作者
论文摘要
我们给出算法，给定一个直线程序（SLP），具有$ g $规则的规则（仅）$ t [1..n] $，在$ o（g）$ space内构建$ o（lz）$ t $ of $ t $（of z $ z $ phrases of $ z $ phrass）的时间$ o（n \ log^2 n）$ o（n \ log^2 n）$ o（n \ log o o（g z），我们还展示了如何从$ o（g+g_ {lc}）$ o（g+g_ {lc}）$ slap中构建最佳尺寸$ g_ {lc} = o（δ\ log \ frac {n}δ）$的局部一致的语法（lcg）的局部语法（lcg）。最后，我们展示了如何从$ o（g_ {lc}）$ space和时间$ o（z \ log^2 n \ log^2（n/z））构建$ t $的LZ解析。我们所有的结果都具有很高的可能性。
We give algorithms that, given a straight-line program (SLP) with $g$ rules that generates (only) a text $T [1..n]$, builds within $O(g)$ space the Lempel-Ziv (LZ) parse of $T$ (of $z$ phrases) in time $O(n\log^2 n)$ or in time $O(gz\log^2(n/z))$. We also show how to build a locally consistent grammar (LCG) of optimal size $g_{lc} = O(δ\log\frac{n}δ)$ from the SLP within $O(g+g_{lc})$ space and in $O(n\log g)$ time, where $δ$ is the substring complexity measure of $T$. Finally, we show how to build the LZ parse of $T$ from such a LCG within $O(g_{lc})$ space and in time $O(z\log^2 n \log^2(n/z))$. All our results hold with high probability.
