LZ78 substring compression in compressed space

DOI10.1007/S00224-025-10245-8MaRDI QIDQ7233447zbMATH OpenFDO

Authors Hiroki Shibata, Dominik Köppl

Publication date 27 April 2026

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00224-025-10245-8

zbMATH Keywords

CDAWGlossless data compressionLZ78 factorizationsubstring compression

Mathematics Subject Classification ID

Theory of data (68Pxx) Theory of computing (68Qxx) Algorithms in computer science (68Wxx)

Cites work

• Collapsing the hierarchy of compressed data structures: suffix arrays in optimal compressed space
• Composite repetition-aware data structures
• Compressed text indexes, from theory to practice
• Compression of individual sequences via variable-rate coding
• Constructing LZ78 tries and position heaps in linear time for large alphabets
• Converting SLP to LZ78 in almost Linear Time
• Delta-fast tries: local searches in bounded universes with linear space
• Fully functional suffix trees and optimal text searching in BWT-runs bounded space
• Generalized substring compression
• scientific article; zbMATH DE number 6850405 (Why is no real title available?)
• scientific article; zbMATH DE number 2226805 (Why is no real title available?)
• scientific article; zbMATH DE number 7695994 (Why is no real title available?)
• Lempel-Ziv factorization powered by space efficient suffix trees
• LZD factorization: simple and practical online grammar compression with variable-to-fixed encoding
• On maximal repeats in strings
• On two LZ78-style grammars: compression bounds and compressed-space computation
• Optimal-Time Dictionary-Compressed Indexes
• Optimally computing compressed indexing arrays based on the compact directed acyclic word graph
• Random access to grammar-compressed strings and trees
• Representing the suffix tree with the CDAWG
• Self-adjusting binary search trees
• Substring compression problems
• Suffix Arrays: A New Method for On-Line String Searches
• The macro model for data compression (extended abstract)
• The smallest automaton recognizing the subwords of a text
• The structure of subword graphs and suffix trees of Fibonacci words
• Toward a Definitive Compressibility Measure for Repetitive Sequences
• Wavelet trees meet suffix trees
• Weighted ancestors in suffix trees

This page was built for publication: LZ78 substring compression in compressed space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7233447)