Generalized substring compression

DOI10.1016/j.tcs.2013.10.010zbMath1295.68112OpenAlexW2037700329MaRDI QIDQ2437745

Moshe Lewenstein, Orgad Keller, Shir Landau, Tsvi Kopelowitz

Publication date: 13 March 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.10.010

zbMATH Keywords

data compressionrange searchingsuffix treeLempel-Ziv compression

Mathematics Subject Classification ID

Searching and sorting (68P10) 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 (8)

Computing minimal and maximal suffixes of a substring ⋮ Sublinear algorithms for approximating string compressibility ⋮ Internal shortest absent word queries in constant time and linear space ⋮ String Indexing with Compressed Patterns ⋮ Internal masked prefix sums and its connection to fully internal measurement queries ⋮ A linear-space data structure for range-LCP queries in poly-logarithmic time ⋮ Internal dictionary matching ⋮ Bicriteria Data Compression

Uses Software

• BEETL
• LZ77

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The level ancestor problem simplified
• Computing longest previous factor in linear time and applications
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• On-line construction of suffix trees
• On position restricted substring searching in succinct space
• Multi-method dispatching
• Orthogonal Range Searching for Text Indexing
• Sorted Range Reporting
• Substring Range Reporting
• Dynamic Text Indexing under String Updates
• Relative Lempel-Ziv Compression of Genomes for Large-Scale Storage and Retrieval
• Fast Algorithms for Finding Nearest Common Ancestors
• Position-Restricted Substring Searching
• Approximating the smallest grammar
• Range Non-overlapping Indexing and Successive List Indexing
• A Space-Economical Suffix Tree Construction Algorithm
• A universal algorithm for sequential data compression
• Using persistent data structures for adding range restrictions to searching problems
• Text Indexing and Dictionary Matching with One Error
• Comparing DNA Sequence Collections by Direct Comparison of Compressed Text Indexes
• Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
• Orthogonal range searching on the RAM, revisited

This page was built for publication: Generalized substring compression