Cover Image

LZ78 Substring Compression in Compressed Space

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Shibata, Hiroki, Köppl, 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

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

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

LZBE: an LZ-style compressor supporting $O(\log n)$-time random access
by: Shibata, Hiroki, et al.
Published: (2025)

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

Counting distinct (non-)crossing substrings
by: Umezaki, Haruki, et al.
Published: (2025)

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
by: Fujie, Yuto, et al.
Published: (2025)

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

Near-real-time Solutions for Online String Problems
by: Köppl, Dominik, et al.
Published: (2026)

Smallest suffixient set maintenance in near-real-time
by: Köppl, Dominik, et al.
Published: (2026)

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

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

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

String Representation in Suffixient Set Size Space
by: Shibata, Hiroki, et al.
Published: (2026)

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

Extending the Burrows-Wheeler Transform for Cartesian Tree Matching and Constructing It
by: Osterkamp, Eric M., et al.
Published: (2024)

Engineering Fast and Space-Efficient Recompression from SLP-Compressed Text
by: Adudodla, Ankith Reddy, et al.
Published: (2025)

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

Bijective BWT based compression schemes
by: Badkobeh, Golnaz, et al.
Published: (2024)

Efficient Algorithms to Compute Closed Substrings
by: Jain, Samkith K, et al.
Published: (2025)

Faster Algorithms for Longest Common Substring
by: Charalampopoulos, Panagiotis, et al.
Published: (2021)

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

Hardness Results on Characteristics for Elastic-Degenerated Strings
by: Köppl, Dominik, et al.
Published: (2024)

Counting Distinct Square Substrings in Sublinear Time
by: Charalampopoulos, Panagiotis, et al.
Published: (2025)

Dynamic Longest Common Substring in Polylogarithmic Time
by: Charalampopoulos, Panagiotis, et al.
Published: (2020)

Faster Algorithms for Shortest Unique or Absent Substrings
by: Charalampopoulos, Panagiotis, et al.
Published: (2026)

BAT-LZ Out of Hell
by: Lipták, Zsuzsanna, et al.
Published: (2024)

Algorithms for Galois Words: Detection, Factorization, and Rotation
by: Hendrian, Diptarama, et al.
Published: (2024)

An Algorithm for the Longest Common Subsequence and Substring Problem for Multiple Strings
by: Li, Rao
Published: (2024)

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

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

Edit and Alphabet-Ordering Sensitivity of Lex-parse
by: Nakashima, Yuto, et al.
Published: (2024)

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

Packed Acyclic Deterministic Finite Automata
by: Shibata, Hiroki, et al.
Published: (2024)

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

RLZ-r and LZ-End-r: Enhancing Move-r
by: Dinklage, Patrick, et al.
Published: (2025)

Computing the LZ-End parsing: Easy to implement and practically efficient
by: Dinklage, Patrick
Published: (2024)

The Complexity of Dynamic LZ77 is $\tildeΘ(n^{2/3})$
by: Boneh, Itai, et al.
Published: (2025)

Maximal Closed Substrings
by: Badkobeh, Golnaz, et al.
Published: (2022)

Fast and Optimal Differentially Private Frequent-Substring Mining
by: Guo, Peaker, et al.
Published: (2026)

Compressed Game Solving
by: Considine, Jeffrey
Published: (2024)