Stronger Lempel-Ziv based compressed text indexing
From MaRDI portal
Publication:2428663
DOI10.1007/s00453-010-9443-8zbMath1241.68061OpenAlexW1967156765MaRDI QIDQ2428663
Gonzalo Navarro, Diego Arroyuelo, Kunihiko Sadakane
Publication date: 26 April 2012
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-010-9443-8
Combinatorics on words (68R15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05) Algorithms on strings (68W32)
Related Items
Grammar-compressed indexes with logarithmic search time ⋮ Composite Repetition-Aware Data Structures ⋮ On compressing and indexing repetitive sequences ⋮ On compressing permutations and adaptive sorting ⋮ Engineering Practical Lempel-Ziv Tries ⋮ Hybrid indexes for repetitive datasets ⋮ Simple and efficient LZW-compressed multiple pattern matching ⋮ LZ78 Compression in Low Main Memory Space ⋮ Space-efficient construction of Lempel-Ziv compressed text indexes ⋮ Flexible indexing of repetitive collections ⋮ Lempel-Ziv compressed structures for document retrieval ⋮ Lempel-Ziv-78 compressed string dictionaries ⋮ Orthogonal Range Searching for Text Indexing ⋮ Space-efficient substring occurrence estimation
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Space-efficient construction of Lempel-Ziv compressed text indexes
- Representing trees of higher degree
- Large alphabets and incompressibility
- Indexing text using the Ziv--Lempel trie
- A space and time efficient algorithm for constructing compressed suffix arrays
- Rank and select revisited and extended
- Succinct Representation of Balanced Parentheses and Static Trees
- Compressed representations of sequences and full-text indexes
- Suffix Arrays: A New Method for On-Line String Searches
- An analysis of the Burrows—Wheeler transform
- A Lempel-Ziv Text Index on Secondary Storage
- Indexing compressed text
- Rank/select operations on large alphabets
- Squeezing succinct data structures into entropy bounds
- On the Complexity of Finite Sequences
- 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
- Compression of Low Entropy Strings with Lempel--Ziv Algorithms
- Dynamic entropy-compressed sequences and full-text indexes
- 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
- Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
- Algorithms and Computation