Literal Shuffle of Compressed Words
Literal Shuffle of Compressed Words
复制标题
压缩词的字面洗牌
DOI：
10.1007/978-0-387-09680-3_6
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
R. Radicioni
中科院分区：
文献类型：
--
作者：
A. Bertoni;C. Choffrut;R. Radicioni
直线程序(SLP)是一种广泛使用的词的压缩表示。在这项工作中，我们研究了通过SLP压缩的单词的有理变换和文字洗牌，证明了第一种变换保持了压缩比，而第二种不保持。因此，我们证明了通过SLP压缩的2D文本的描述复杂性的紧界。最后，我们观察到由压缩单词的文字洗牌表示的文本的模式匹配问题是NP完全的。然而，我们为这个问题提出了一个参数易处理的算法，当模式的长度与文本的长度多项式相关时，该算法以多项式的时间工作。
Straight-Line Programs (SLP) are widely used compressed representations of words. In this work we study the rational transformations and the literal shuffle of words compressed via SLP, proving that the first preserves the compression rate, while the second does not. As a consequence, we prove a tight bound for the descriptional complexity of 2D texts compressed via SLP. Finally, we observe that the Pattern Matching Problem for texts expressed by the literal shuffle of compressed words is NP-complete. However, we present a parameter-tractable algorithm for this problem, working in polynomial time whenever the length of the pattern is polynomially related to that of the text.