Indexing text using the Ziv--Lempel trie

DOI10.1016/S1570-8667(03)00066-2zbMath1118.68443OpenAlexW2646645486MaRDI QIDQ876708

Gonzalo Navarro

Publication date: 26 April 2007

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s1570-8667(03)00066-2

zbMATH Keywords

succinct data structuresauthor keywords: self-indexingcompressed pattern matchingcompressed text

Mathematics Subject Classification ID

Data structures (68P05)

Related Items

Comparison of LZ77-type parsings, Self-indexed Text Compression Using Straight-Line Programs, Approximate string matching with compressed indexes, Indexing text using the Ziv--Lempel trie, Semi-dynamic Compact Index for Short Patterns and Succinct van Emde Boas Tree, On compressing and indexing repetitive sequences, New algorithms on wavelet trees and applications to information retrieval, Sensitivity of string compressors and repetitiveness measures, Stronger Lempel-Ziv based compressed text indexing, Worst-case efficient single and multiple string matching on packed texts in the word-RAM model, Wavelet trees for all, Worst Case Efficient Single and Multiple String Matching in the RAM Model, Rank and select revisited and extended, Self-indexing Based on LZ77, Space-efficient construction of Lempel-Ziv compressed text indexes, Lempel-Ziv compressed structures for document retrieval, Unnamed Item, Lempel-Ziv factorization powered by space efficient suffix trees, Compressed Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space, A faster algorithm for the computation of string convolutions using LZ78 parsing, LZ-End Parsing in Linear Time, A SIMPLE ALPHABET-INDEPENDENT FM-INDEX, Linked dynamic tries with applications to LZ-compression in sublinear time and space

Cites Work

• Indexing text using the Ziv--Lempel trie
• Space Efficient Suffix Trees
• Suffix Arrays: A New Method for On-Line String Searches
• Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract)
• Compression of individual sequences via variable-rate coding
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• Compression of Low Entropy Strings with Lempel--Ziv Algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item