Algorithmics on SLP-compressed strings: A survey
Algorithmics on SLP-compressed strings: A survey
复制标题
DOI：
10.1515/gcc-2012-0016
复制
发表时间：
2012-12-01
影响因子：
--
通讯作者：
Lohrey, Markus
中科院分区：
文献类型：
--
作者：
Lohrey, Markus
对通过直线程序以压缩形式给出的字符串的算法问题的结果进行了综述。直线程序是一种上下文无关的语法，它只生成一个字符串。通过这种方式，可以实现指数压缩率。其中，我们研究了压缩串的模式匹配，各种形式语言中压缩串的成员问题，以及压缩串的查询问题。文中还讨论了它在组合群论和计算拓扑学中的应用，以及在字方程求解中的应用。最后，考虑了对压缩树和图的扩展。
Results on algorithmic problems on strings that are given in a compressed form via straight-line programs are surveyed. A straight-line program is a context-free grammar that generates exactly one string. In this way, exponential compression rates can be achieved. Among others, we study pattern matching for compressed strings, membership problems for compressed strings in various kinds of formal languages, and the problem of querying compressed strings. Applications in combinatorial group theory and computational topology and to the solution of word equations are discussed as well. Finally, extensions to compressed trees and pictures are considered.