A Straight-Line Program (SLP) <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\mathcal {G}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">G</mi> </math></EquationSource> </InlineEquation> for a string <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\mathcal {T}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">T</mi> </math></EquationSource> </InlineEquation> is a context-free grammar (CFG) that derives <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\mathcal {T}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">T</mi> </math></EquationSource> </InlineEquation> only, which can be considered as a compressed representation of <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\mathcal {T}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">T</mi> </math></EquationSource> </InlineEquation>. In this paper, we show how to encode <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\mathcal {G}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">G</mi> </math></EquationSource> </InlineEquation> in <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$n \lceil \lg N \rceil + (n + n') \lceil \lg (n+\sigma ) \rceil + 4n - 2n' + o(n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mrow> <mo>⌈</mo> <mo>lg</mo> <mi>N</mi> <mo>⌉</mo> </mrow> <mo>+</mo> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <msup> <mi>n</mi> <mo>′</mo> </msup> <mo stretchy="false">)</mo> </mrow> <mrow> <mo>⌈</mo> <mo>lg</mo> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mi>σ</mi> <mo stretchy="false">)</mo> </mrow> <mo>⌉</mo> </mrow> <mo>+</mo> <mn>4</mn> <mi>n</mi> <mo>-</mo> <mn>2</mn> <msup> <mi>n</mi> <mo>′</mo> </msup> <mo>+</mo> <mi>o</mi> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> bits to support random access queries of extracting <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$\mathcal {T}[p..q]$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">T</mi> <mo stretchy="false">[</mo> <mi>p</mi> <mo>.</mo> <mo>.</mo> <mi>q</mi> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation> in worst-case <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$O(\log N + q - p)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>N</mi> <mo>+</mo> <mi>q</mi> <mo>-</mo> <mi>p</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> time, where N is the length of <InlineEquation ID="IEq11"> <EquationSource Format="TEX">$\mathcal {T}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">T</mi> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq12"> <EquationSource Format="TEX">$\sigma $</EquationSource> <EquationSource Format="MATHML"><math> <mi>σ</mi> </math></EquationSource> </InlineEquation> is the alphabet size, n is the number of variables in <InlineEquation ID="IEq13"> <EquationSource Format="TEX">$\mathcal {G}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">G</mi> </math></EquationSource> </InlineEquation> and <InlineEquation ID="IEq14"> <EquationSource Format="TEX">$n' \le n$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msup> <mi>n</mi> <mo>′</mo> </msup> <mo>≤</mo> <mi>n</mi> </mrow> </math></EquationSource> </InlineEquation> is the number of symmetric centroid paths in the DAG representation for <InlineEquation ID="IEq15"> <EquationSource Format="TEX">$\mathcal {G}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">G</mi> </math></EquationSource> </InlineEquation>. The time complexity is almost optimal because Verbin and Yu [CPM 2013] proved that <InlineEquation ID="IEq16"> <EquationSource Format="TEX">$O(\log N)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <mo>log</mo> <mi>N</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> term cannot be significantly improved in general with <InlineEquation ID="IEq17"> <EquationSource Format="TEX">$\textrm{poly}(n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mtext>poly</mtext> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>-space data structures. We also present alternative encodings that achieve the same random access time with <InlineEquation ID="IEq18"> <EquationSource Format="TEX">$n \lceil \lg N \rceil + n \lceil \lg (n+\sigma ) \rceil + 5n + n' + o(n)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mrow> <mo>⌈</mo> <mo>lg</mo> <mi>N</mi> <mo>⌉</mo> </mrow> <mo>+</mo> <mi>n</mi> <mrow> <mo>⌈</mo> <mo>lg</mo> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mi>σ</mi> <mo stretchy="false">)</mo> </mrow> <mo>⌉</mo> </mrow> <mo>+</mo> <mn>5</mn> <mi>n</mi> <mo>+</mo> <msup> <mi>n</mi> <mo>′</mo> </msup> <mo>+</mo> <mi>o</mi> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> or <InlineEquation ID="IEq19"> <EquationSource Format="TEX">$n \lceil \lg N \rceil + n \lceil \lg (n+\sigma ) \rceil + 5n - n' + \sigma + o(n+\sigma )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>n</mi> <mrow> <mo>⌈</mo> <mo>lg</mo> <mi>N</mi> <mo>⌉</mo> </mrow> <mo>+</mo> <mi>n</mi> <mrow> <mo>⌈</mo> <mo>lg</mo> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mi>σ</mi> <mo stretchy="false">)</mo> </mrow> <mo>⌉</mo> </mrow> <mo>+</mo> <mn>5</mn> <mi>n</mi> <mo>-</mo> <msup> <mi>n</mi> <mo>′</mo> </msup> <mo>+</mo> <mi>σ</mi> <mo>+</mo> <mi>o</mi> <mrow> <mo stretchy="false">(</mo> <mi>n</mi> <mo>+</mo> <mi>σ</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> bits of space.

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

期刊论文
出版模式：

开放获取
发表日期：

2026年4月13日

查看全文

Akito Takasaka,
Tomohiro I

摘要

A Straight-Line Program (SLP) $\mathcal {G}$ $G$ for a string $\mathcal {T}$ $T$ is a context-free grammar (CFG) that derives $\mathcal {T}$ $T$ only, which can be considered as a compressed representation of $\mathcal {T}$ $T$ . In this paper, we show how to encode $\mathcal {G}$ $G$ in $n \lceil \lg N \rceil + (n + n') \lceil \lg (n+\sigma ) \rceil + 4n - 2n' + o(n)$ $n ⌈ lg N ⌉ + (n + n^{'}) ⌈ lg (n + σ) ⌉ + 4 n - 2 n^{'} + o (n)$ bits to support random access queries of extracting $\mathcal {T}[p..q]$ $T [p . . q]$ in worst-case $O(\log N + q - p)$ $O (log N + q - p)$ time, where N is the length of $\mathcal {T}$ $T$ , $\sigma $ $σ$ is the alphabet size, n is the number of variables in $\mathcal {G}$ $G$ and $n' \le n$ $n^{'} \leq n$ is the number of symmetric centroid paths in the DAG representation for $\mathcal {G}$ $G$ . The time complexity is almost optimal because Verbin and Yu [CPM 2013] proved that $O(\log N)$ $O (log N)$ term cannot be significantly improved in general with $\textrm{poly}(n)$ $poly (n)$ -space data structures. We also present alternative encodings that achieve the same random access time with $n \lceil \lg N \rceil + n \lceil \lg (n+\sigma ) \rceil + 5n + n' + o(n)$ $n ⌈ lg N ⌉ + n ⌈ lg (n + σ) ⌉ + 5 n + n^{'} + o (n)$ or $n \lceil \lg N \rceil + n \lceil \lg (n+\sigma ) \rceil + 5n - n' + \sigma + o(n+\sigma )$ $n ⌈ lg N ⌉ + n ⌈ lg (n + σ) ⌉ + 5 n - n^{'} + σ + o (n + σ)$ bits of space.

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

摘要