Generalized substring compression

DOI10.1016/J.TCS.2013.10.010MaRDI QIDQ2437745zbMATH OpenOpenAlexFDO

Authors Orgad Keller, Tsvi Kopelowitz, Shir Landau, Moshe Lewenstein

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

range searchingdata compressionsuffix treeLempel-Ziv compression

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Recommendations

• Substring compression problems
• Longest common extensions with recompression
• Time-space trade-offs for Lempel-Ziv compressed indexing
• Time-space trade-offs for Lempel-Ziv compressed indexing

Cites work

• scientific article; zbMATH DE number 6146456 (Why is no real title available?)
• A Space-Economical Suffix Tree Construction Algorithm
• A unified algorithm for accelerating edit-distance computation via text-compression
• A universal algorithm for sequential data compression
• Application of Lempel-Ziv factorization to the approximation of grammar-based compression.
• Approximating the smallest grammar
• Comparing DNA sequence collections by direct comparison of compressed text indexes
• Computing longest previous factor in linear time and applications
• Dynamic Text Indexing under String Updates
• Fast Algorithms for Finding Nearest Common Ancestors
• Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
• Multi-method dispatching: a geometric approach with applications to string matching problems
• On position restricted substring searching in succinct space
• On-line construction of suffix trees
• Orthogonal range searching for text indexing
• Orthogonal range searching on the RAM, revisited
• Position-Restricted Substring Searching
• Range Non-overlapping Indexing and Successive List Indexing
• Relative Lempel-Ziv compression of genomes for large-scale storage and retrieval
• Sorted range reporting
• Substring Range Reporting
• Substring compression problems
• Text Indexing and Dictionary Matching with One Error
• The level ancestor problem simplified
• Using persistent data structures for adding range restrictions to searching problems

Cited in

(19)

• String Indexing with Compressed Patterns
• Internal pattern matching queries in a text and applications
• Bicriteria data compression
• A linear-space data structure for range-LCP queries in poly-logarithmic time
• Substring compression problems
• Internal dictionary matching
• Finding characteristic substrings from compressed texts
• Sublinear algorithms for approximating string compressibility
• Sublinear Algorithms for Approximating String Compressibility
• Adaptive learning of compressible strings
• The Efficient Computation of Complete and Concise Substring Scales with Suffix Trees
• CONCUR 2003 - Concurrency Theory
• An upper bound and linear-space queries on the LZ-End parsing
• Computing minimal and maximal suffixes of a substring revisited
• Internal masked prefix sums and its connection to fully internal measurement queries
• Generalized substring selectivity estimation
• Internal shortest absent word queries in constant time and linear space
• Computing minimal and maximal suffixes of a substring
• Longest common extensions with recompression

Describes a project that uses

Uses Software

• BEETL
• LZ77

This page was built for publication: Generalized substring compression

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437745)