Space-Efficient SLP Encoding for O(log N)-Time Random Access

doi:10.1007/s00224-025-10243-w

2026-04-13

Takasaka, Akito

Tomohiro, I *

DOI：10.1007/s00224-025-10243-w

原文链接

原文求助

摘要

En 中文

给定字符串T的一个直线程序（SLP）G是一种上下文无关文法（CFG），它仅推导出T，可以被视为T的一种压缩表示。在本文中，我们展示了如何用n inverted right perpendicular lg N inverted left perpendicular + (n + n ')inverted right perpendicular lg(n + sigma) inverted left perpendicular + 4n - 2n '+ o(n)比特来编码G，以支持在最坏情况下O(log N + q - p)时间内提取T[p..q]的随机访问查询，其中N是T的长度，sigma是字母表大小，n是G中的变量数量，且n ' <= n是G的DAG表示中的对称中心路径数量。该时间复杂度几乎是最优的，因为Verbin和Yu [CPM 2013]证明了在一般情况下，使用poly(n)-space数据结构无法显著改进O(log N)项。我们还提出了替代编码，它们以n inverted right perpendicular lg N inverted left perpendicular + n inverted right perpendicular lg(n + rho) inverted left perpendicular + 5n + n ' + o(n)或n inverted right perpendicular lg N inverted left perpendicular + ninverted right perpendicular lg(n + sigma) inverted left perpendicular + 5n - n ' + sigma + o(n + sigma)比特的空间实现了相同的随机访问时间。

Keyword:

Data compression

Grammar compression

Random access data structures