Generalized substring compression

DOI10.1016/J.TCS.2013.10.010zbMATH Open1295.68112OpenAlexW2037700329MaRDI QIDQ2437745FDOQ2437745

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

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

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)

Cites Work

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

Cited In (19)

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

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)