Cover Image

Engineering Fast and Space-Efficient Recompression from SLP-Compressed Text

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Adudodla, Ankith Reddy, Kempa, Dominik
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Word Break on SLP-Compressed Texts
by: De, Rajat, et al.
Published: (2025)

Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
by: Kempa, Dominik, et al.
Published: (2023)

Tight Lower Bounds for Central String Queries in Compressed Space
by: Kempa, Dominik, et al.
Published: (2025)

Optimal Random Access and Conditional Lower Bounds for 2D Compressed Strings
by: De, Rajat, et al.
Published: (2025)

Engineering Select Support for Hybrid Bitvectors
by: Chiu, Eric, et al.
Published: (2025)

Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data
by: De, Rajat, et al.
Published: (2023)

On the Hardness Hierarchy for the $O(n \sqrt{\log n})$ Complexity in the Word RAM
by: Kempa, Dominik, et al.
Published: (2025)

Explaining the Inherent Tradeoffs for Suffix Array Functionality: Equivalences between String Problems and Prefix Range Queries
by: Kempa, Dominik, et al.
Published: (2025)

Wavelet Forests Revisited
by: Chiu, Eric, et al.
Published: (2026)

Lempel-Ziv (LZ77) Factorization in Sublinear Time
by: Kempa, Dominik, et al.
Published: (2024)

LZ78 Substring Compression in Compressed Space
by: Shibata, Hiroki, et al.
Published: (2025)

Space-efficient SLP encoding for $O(\log N)$-time random access
by: Takasaka, Akito, et al.
Published: (2024)

Substring Compression Variations and LZ78-Derivates
by: Köppl, Dominik
Published: (2024)

Provably Fast and Space-Efficient Parallel Biconnectivity
by: Dong, Xiaojun, et al.
Published: (2023)

Space-Efficient k-Mismatch Text Indexes
by: Kociumaka, Tomasz, et al.
Published: (2025)

LZD-style Compression Scheme with Truncation and Repetitions
by: Götz, Linus, et al.
Published: (2025)

Compressed Index with Construction in Compressed Space
by: Kosolobov, Dmitry
Published: (2026)

Space-Efficient Text Indexing with Mismatches using Function Inversion
by: Bibbens, Jackson, et al.
Published: (2026)

Fast Practical Compression of Deterministic Finite Automata
by: Bille, Philip, et al.
Published: (2023)

Dynamic Suffix Array in Optimal Compressed Space
by: Nishimoto, Takaaki, et al.
Published: (2024)

Engineering Optimal Parallel Task Scheduling
by: Akram, Matthew, et al.
Published: (2024)

Revisiting the Sparse Matrix Compression Problem
by: Jugé, Vincent, et al.
Published: (2026)

Dynamic Grammar-Compressed Self-Index in $δ$-Optimal Space
by: Nishimoto, Takaaki, et al.
Published: (2026)

NP-Completeness for the Space-Optimality of Double-Array Tries
by: Bannai, Hideo, et al.
Published: (2024)

Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts
by: Duyster, Anouk, et al.
Published: (2025)

Space-time Trade-offs for the LCP Array of Wheeler DFAs
by: Cotumaccio, Nicola, et al.
Published: (2023)

Engineering Compressed Matrix Multiplication with the Fast Walsh-Hadamard Transform
by: Andersson, Joel, et al.
Published: (2026)

Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Space-Efficient Graph Kernelizations
by: Kammer, Frank, et al.
Published: (2020)

Engineering an Efficient Approximate DNF-Counter
by: Soos, Mate, et al.
Published: (2024)

Fast and Memory Efficient Multimodal Journey Planning with Delays
by: Katkalo, Denys, et al.
Published: (2026)

Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks
by: Bilò, Davide, et al.
Published: (2024)

Fast Iteration of Spaced k-mers
by: Czech, Lucas
Published: (2026)

Suffixient Arrays: a New Efficient Suffix Array Compression Technique
by: Cenzato, Davide, et al.
Published: (2024)

AutoCSF: Provably Space-Efficient Indexing of Skewed Key-Value Workloads via Filter-Augmented Compressed Static Functions
by: Ramos, David Torres, et al.
Published: (2026)

An Efficient Data Structure and Algorithm for Long-Match Query in Run-Length Compressed BWT
by: Sanaullah, Ahsan, et al.
Published: (2025)

Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
by: Bergougnoux, Benjamin, et al.
Published: (2023)

Space-Efficient Algorithm for Integer Programming with Few Constraints
by: Rohwedder, Lars, et al.
Published: (2024)

Space-Efficient Online Computation of String Net Occurrences
by: Mieno, Takuya, et al.
Published: (2024)

Faster Space-Efficient STR-IC-LCS Computation
by: Yonemoto, Yuki, et al.
Published: (2022)