Generalized Straight-Line Programs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916199765377024 |
|---|---|
| author | Navarro, Gonzalo Olivares, Francisco Urbina, Cristian |
| author_facet | Navarro, Gonzalo Olivares, Francisco Urbina, Cristian |
| contents | It was recently proved that any Straight-Line Program (SLP) generating a given string can be transformed in linear time into an equivalent balanced SLP of the same asymptotic size. We generalize this proof to a general class of grammars we call Generalized SLPs (GSLPs), which allow rules of the form $A \rightarrow x$ where $x$ is any Turing-complete representation (of size $|x|$) of a sequence of symbols (potentially much longer than $|x|$). We then specialize GSLPs to so-called Iterated SLPs (ISLPs), which allow rules of the form $A \rightarrow Π_{i=k_1}^{k_2} B_1^{i^{c_1}}\cdots B_t^{i^{c_t}}$ of size $2t+2$. We prove that ISLPs break, for some text families, the measure $δ$ based on substring complexity, a lower bound for most measures and compressors exploiting repetitiveness. Further, ISLPs can extract any substring of length $λ$, from the represented text $T[1.. n]$, in time $O(λ+ \log^2 n\log\log n)$. This is the first compressed representation for repetitive texts breaking $δ$ while, at the same time, supporting direct access to arbitrary text symbols in polylogarithmic time. We also show how to compute some substring queries, like range minima and next/previous smaller value, in time $O(\log^2 n \log\log n)$. Finally, we further specialize the grammars to Run-Length SLPs (RLSLPs), which restrict the rules allowed by ISLPs to the form $A \rightarrow B^t$. Apart from inheriting all the previous results with the term $\log^2 n \log\log n$ reduced to the near-optimal $\log n$, we show that RLSLPs can exploit balance to efficiently compute a wide class of substring queries we call ``composable'' -- i.e., $f(X \cdot Y)$ can be obtained from $f(X)$ and $f(Y)$... |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_07057 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Generalized Straight-Line Programs Navarro, Gonzalo Olivares, Francisco Urbina, Cristian Data Structures and Algorithms It was recently proved that any Straight-Line Program (SLP) generating a given string can be transformed in linear time into an equivalent balanced SLP of the same asymptotic size. We generalize this proof to a general class of grammars we call Generalized SLPs (GSLPs), which allow rules of the form $A \rightarrow x$ where $x$ is any Turing-complete representation (of size $|x|$) of a sequence of symbols (potentially much longer than $|x|$). We then specialize GSLPs to so-called Iterated SLPs (ISLPs), which allow rules of the form $A \rightarrow Π_{i=k_1}^{k_2} B_1^{i^{c_1}}\cdots B_t^{i^{c_t}}$ of size $2t+2$. We prove that ISLPs break, for some text families, the measure $δ$ based on substring complexity, a lower bound for most measures and compressors exploiting repetitiveness. Further, ISLPs can extract any substring of length $λ$, from the represented text $T[1.. n]$, in time $O(λ+ \log^2 n\log\log n)$. This is the first compressed representation for repetitive texts breaking $δ$ while, at the same time, supporting direct access to arbitrary text symbols in polylogarithmic time. We also show how to compute some substring queries, like range minima and next/previous smaller value, in time $O(\log^2 n \log\log n)$. Finally, we further specialize the grammars to Run-Length SLPs (RLSLPs), which restrict the rules allowed by ISLPs to the form $A \rightarrow B^t$. Apart from inheriting all the previous results with the term $\log^2 n \log\log n$ reduced to the near-optimal $\log n$, we show that RLSLPs can exploit balance to efficiently compute a wide class of substring queries we call ``composable'' -- i.e., $f(X \cdot Y)$ can be obtained from $f(X)$ and $f(Y)$... |
| title | Generalized Straight-Line Programs |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2404.07057 |