Space-efficient construction of Lempel-Ziv compressed text indexes
From MaRDI portal
Publication:549672
DOI10.1016/j.ic.2011.03.001zbMath1220.68051OpenAlexW2004543623MaRDI QIDQ549672
Diego Arroyuelo, Gonzalo Navarro
Publication date: 18 July 2011
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2011.03.001
Database theory (68P15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)
Related Items (7)
Engineering Practical Lempel-Ziv Tries ⋮ Stronger Lempel-Ziv based compressed text indexing ⋮ LZ78 Compression in Low Main Memory Space ⋮ Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries ⋮ Lempel-Ziv-78 compressed string dictionaries ⋮ Linked dynamic tries with applications to LZ-compression in sublinear time and space ⋮ Succinct dynamic cardinal trees
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Rank/select on dynamic compressed sequences and applications
- Representing trees of higher degree
- A simple optimal representation for balanced parentheses
- Indexing text using the Ziv--Lempel trie
- A space and time efficient algorithm for constructing compressed suffix arrays
- Engineering a lightweight suffix array construction algorithm
- Stronger Lempel-Ziv based compressed text indexing
- Alphabet-independent linear-time construction of compressed suffix arrays using \(o(n \log n)\)-bit working space
- Fast BWT in small space by blockwise suffix sorting
- Faster suffix sorting
- Rank and select revisited and extended
- Efficient generation of super condensed neighborhoods
- Space Efficient Suffix Trees
- Succinct Representation of Balanced Parentheses and Static Trees
- Compressed representations of sequences and full-text indexes
- Compressed indexes for dynamic text collections
- Suffix Arrays: A New Method for On-Line String Searches
- An analysis of the Burrows—Wheeler transform
- An Improved Succinct Representation for Dynamic k-ary Trees
- Indexing compressed text
- Lightweight Data Indexing and Compression in External Memory
- Squeezing succinct data structures into entropy bounds
- Breaking a Time-and-Space Barrier in Constructing Full-Text Indices
- A universal algorithm for sequential data compression
- Compression of individual sequences via variable-rate coding
- New text indexing functionalities of the compressed suffix arrays
- A Functional Approach to Data Structures and Its Use in Multidimensional Searching
- Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
- Permuting in Place
- Compression of Low Entropy Strings with Lempel--Ziv Algorithms
- Dynamic entropy-compressed sequences and full-text indexes
- Algorithms and Computation
- Practical Entropy-Compressed Rank/Select Dictionary
- Succinct Trees in Practice
- Better external memory suffix array construction
- Reducing the Space Requirement of LZ-Index
- Implementing the LZ-index
- Compressed text indexes
- Practical approaches to reduce the space requirement of lempel-ziv--based compressed text indices
- In-Place Suffix Sorting
- Compressed Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- Experimental and Efficient Algorithms
- Algorithms and Computation
This page was built for publication: Space-efficient construction of Lempel-Ziv compressed text indexes
