Sublinear time Lempel-Ziv (LZ77) factorization
From MaRDI portal
Publication:6545423
DOI10.1007/978-3-031-43980-3_14MaRDI QIDQ6545423
Publication date: 29 May 2024
lossless compressionapproximation algorithmsstring algorithmsLempel-Ziv factorizationLZ77sublinear timeword packing
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Approximation algorithms (68W25) Algorithms on strings (68W32)
Cites Work
- Title not available (Why is that?)
- Online timestamped text indexing
- On compressing and indexing repetitive sequences
- Dictionary-symbolwise flexible parsing
- Lempel-Ziv factorization powered by space efficient suffix trees
- Computing longest previous factor in linear time and applications
- Orthogonal range searching in linear and almost-linear space
- Efficient parallel algorithms to test square-freeness and factorize strings
- Lempel-Ziv index for \(q\)-grams
- Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
- Time-space trade-offs for Lempel-Ziv compressed indexing
- Towards a definitive measure of repetitiveness
- Lempel-Ziv-like parsing in small space
- On the approximation ratio of Lempel-Ziv parsing
- Dynamic index and LZ factorization in compressed space
- Approximate pattern matching in LZ77-compressed texts
- Sublinear algorithms for approximating string compressibility
- LZRR: LZ77 parsing with right reference
- On the Bit-Complexity of Lempel--Ziv Compression
- Computing Lempel-Ziv Factorization Online
- Lempel Ziv Computation in Small Space (LZ-CISS)
- Faster Lightweight Lempel-Ziv Parsing
- Hybrid indexes for repetitive datasets
- Faster Compact On-Line Lempel-Ziv Factorization
- Lempel-Ziv Factorization Revisited
- LRM-Trees: Compressed Indices, Adaptive Sorting, and Compressed Permutations
- Suffix Arrays: A New Method for On-Line String Searches
- Approximating LZ77 via Small-Space Multiple-Pattern Matching
- An Online Algorithm for Finding the Longest Previous Factors
- The Smallest Grammar Problem
- Linear Algorithm for Data Compression via String Matching
- Data compression via textual substitution
- On the Complexity of Finite Sequences
- A universal algorithm for sequential data compression
- Range Predecessor and Lempel-Ziv Parsing
- Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
- Lempel-Ziv Compression in a Sliding Window
- Most Recent Match Queries in On-Line Suffix Trees
- String synchronizing sets: sublinear-time BWT construction and optimal LCE data structure
- At the roots of dictionary compression: string attractors
- Optimal Construction of Compressed Indexes for Highly Repetitive Texts
- LZ77-Based Self-indexing with Faster Pattern Matching
- Fully Dynamic Orthogonal Range Reporting on RAM
- String Indexing with Compressed Patterns.
- LZ77 via prefix-free parsing
This page was built for publication: Sublinear time Lempel-Ziv (LZ77) factorization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6545423)
