Space-efficient construction of Lempel-Ziv compressed text indexes
DOI10.1016/J.IC.2011.03.001zbMATH Open1220.68051OpenAlexW2004543623MaRDI QIDQ549672FDOQ549672
Authors: 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
Recommendations
Data structures (68P05) Database theory (68P15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)
Cites Work
- Introduction to algorithms
- Stronger Lempel-Ziv based compressed text indexing
- Succinct representation of balanced parentheses and static trees
- Compressed representations of sequences and full-text indexes
- Compressed indexes for dynamic text collections
- Title not available (Why is that?)
- An analysis of the Burrows-Wheeler transform
- An Improved Succinct Representation for Dynamic k-ary Trees
- Indexing compressed text
- Title not available (Why is that?)
- Compression of individual sequences via variable-rate coding
- Title not available (Why is that?)
- Succinct Indexable Dictionaries with Applications to Encoding $k$-ary Trees, Prefix Sums and Multisets
- Succinct Trees in Practice
- Compressed text indexes, from theory to practice
- Fully-functional succinct trees
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- Representing trees of higher degree
- Practical entropy-compressed rank/select dictionary
- A universal algorithm for sequential data compression
- Suffix Arrays: A New Method for On-Line String Searches
- Title not available (Why is that?)
- A Functional Approach to Data Structures and Its Use in Multidimensional Searching
- Dynamic entropy-compressed sequences and full-text indexes
- Rank/select on dynamic compressed sequences and applications
- Space efficient suffix trees
- Rank and select revisited and extended
- Title not available (Why is that?)
- Fast BWT in small space by blockwise suffix sorting
- 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
- Title not available (Why is that?)
- New text indexing functionalities of the compressed suffix arrays
- Compression of Low Entropy Strings with Lempel--Ziv Algorithms
- Reducing the Space Requirement of LZ-Index
- Implementing the LZ-index, theory versus practice
- Title not available (Why is that?)
- Indexing text using the Ziv--Lempel trie
- A space and time efficient algorithm for constructing compressed suffix arrays
- Permuting in Place
- Engineering a lightweight suffix array construction algorithm
- Ultra-succinct representation of ordered trees
- A simple optimal representation for balanced parentheses
- Algorithms and Computation
- Algorithms and Computation
- In-Place Suffix Sorting
- Alphabet-independent linear-time construction of compressed suffix arrays using \(o(n \log n)\)-bit working space
- Faster suffix sorting
- Efficient generation of super condensed neighborhoods
- Title not available (Why is that?)
- Better external memory suffix array construction
- Practical approaches to reduce the space requirement of Lempel-Ziv-based compressed text indices
- Compressed Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space
- Experimental and Efficient Algorithms
Cited In (22)
- Succinct dynamic cardinal trees
- Algorithms and Computation
- Indexing text using the Ziv--Lempel trie
- Implementing the LZ-index, theory versus practice
- Lempel-Ziv-78 compressed string dictionaries
- Lempel-Ziv index for \(q\)-grams
- Compressed text indexes, from theory to practice
- Alphabet-independent compressed text indexing
- A Lempel-Ziv Text Index on Secondary Storage
- Practical approaches to reduce the space requirement of Lempel-Ziv-based compressed text indices
- LZ78 compression in low main memory space
- Engineering practical Lempel-Ziv tries
- Linked dynamic tries with applications to LZ-compression in sublinear time and space
- Practical evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch tries
- Stronger Lempel-Ziv based compressed text indexing
- Reducing space for index implementation.
- Distribution-aware compressed full-text indexes
- Distribution-aware compressed full-text indexes
- Time-space trade-offs for Lempel-Ziv compressed indexing
- Faster dynamic compressed \(d\)-ary relations
- Dynamic index and LZ factorization in compressed space
- Reducing the Space Requirement of LZ-Index
Uses Software
This page was built for publication: Space-efficient construction of Lempel-Ziv compressed text indexes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q549672)