Lempel-Ziv factorization powered by space efficient suffix trees
From MaRDI portal
Publication:724218
DOI10.1007/s00453-017-0333-1zbMath1392.68184OpenAlexW2737421126MaRDI QIDQ724218
Dominik Köppl, Kunihiko Sadakane, Johannes Fischer, Tomohiro I.
Publication date: 25 July 2018
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-017-0333-1
Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)
Related Items (6)
Strictly in-place algorithms for permuting and inverting permutations ⋮ Engineering Practical Lempel-Ziv Tries ⋮ Space-efficient algorithms for computing minimal/shortest unique substrings ⋮ Bidirectional Text Compression in External Memory ⋮ Dynamic index and LZ factorization in compressed space ⋮ Refining the \(r\)-index
Uses Software
Cites Work
- Unnamed Item
- Ultra-succinct representation of ordered trees with applications
- Linear-time computation of local periods
- Representing trees of higher degree
- Indexing text using the Ziv--Lempel trie
- Lempel-Ziv index for \(q\)-grams
- Linear time algorithms for finding and representing all the tandem repeats in a string
- Transducers and repetitions
- Detecting leftmost maximal periodicities
- Improved dynamic dictionary matching
- Constructing LZ78 tries and position heaps in linear time for large alphabets
- Linked dynamic tries with applications to LZ-compression in sublinear time and space
- Compressed suffix trees with full functionality
- Fully Functional Static and Dynamic Succinct Trees
- A Faster Grammar-Based Self-index
- Alphabet-Dependent String Searching with Wexponential Search Trees
- Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays
- Suffix Arrays: A New Method for On-Line String Searches
- Linear work suffix array construction
- Radix Sorting with No Extra Space
- Indexing compressed text
- Squeezing succinct data structures into entropy bounds
- Data compression via textual substitution
- A universal algorithm for sequential data compression
- Compression of individual sequences via variable-rate coding
- A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
- Range Predecessor and Lempel-Ziv Parsing
- Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time
- Raising Permutations to Powers in Place
- Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
- Optimal Dynamic Sequence Representations
- Linear time construction of compressed text indices in compact space
- LZ77-Based Self-indexing with Faster Pattern Matching
- Engineering a compressed suffix tree implementation
- Fully-Compressed Suffix Trees
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
This page was built for publication: Lempel-Ziv factorization powered by space efficient suffix trees
