Scholarlink

A Straight-Line Program (SLP) \(\mathcal {G}\) for a string \(\mathcal {T}\) is a context-free grammar (CFG) that derives \(\mathcal {T}\) only, which can be considered as a compressed representation of \(\mathcal {T}\) .In this paper, we show how to encode \(\mathcal {G}\) in \(n \lceil \lg N \rceil + (n + n') \lceil \lg (n+\sigma ) \rceil + 4n - 2n' + o(n)\) bits to support random access queries of extracting \(\mathcal {T}[p..q]\) in worst-case \(O(\log N + q - p)\) time, where N is the length of \(\mathcal {T}\) , \(\sigma \) is the alphabet size, n is the number of variables in \(\mathcal {G}\)  and \(n' \le n\) is the number of symmetric centroid paths in the DAG representation for \(\mathcal {G}\) .

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Akito Takasaka,
  • Tomohiro I

摘要

A Straight-Line Program (SLP) \(\mathcal {G}\) for a string \(\mathcal {T}\) is a context-free grammar (CFG) that derives \(\mathcal {T}\) only, which can be considered as a compressed representation of \(\mathcal {T}\) .In this paper, we show how to encode \(\mathcal {G}\) in \(n \lceil \lg N \rceil + (n + n') \lceil \lg (n+\sigma ) \rceil + 4n - 2n' + o(n)\) bits to support random access queries of extracting \(\mathcal {T}[p..q]\) in worst-case \(O(\log N + q - p)\) time, where N is the length of \(\mathcal {T}\) , \(\sigma \) is the alphabet size, n is the number of variables in \(\mathcal {G}\)  and \(n' \le n\) is the number of symmetric centroid paths in the DAG representation for \(\mathcal {G}\) .