Linear Algorithm for Data Compression via String Matching

DOI10.1145/322234.322237MaRDI QIDQ3912479zbMATH OpenOpenAlexFDO

Authors Michael Rodeh, Shimon Even, Vaughan R. Pratt

Publication date 1981

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/322234.322237

zbMATH Keywords

suffix treecodinguniversal representation of the integers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Communication, information (94A99) Software, source code, etc. for problems pertaining to information and communication theory (94-04)

Cited in

(35)

• Redundancy estimates for the Lempel–Ziv algorithm of data compression
• Block trees
• Sublinear approximate string matching and biological applications
• Compressed Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space
• Optimal parallel suffix tree construction
• The use and usefulness of numeration systems
• Linear-time computation of local periods
• Finding approximate repetitions under Hamming distance.
• Order-preserving indexing
• Optimal data compression algorithm
• Optimal encoding of non-stationary sources
• Finite automata based algorithms on subsequences and supersequences of degenerate strings
• On the complexity and approximability of bounded access Lempel Ziv coding
• The smallest automaton recognizing the subwords of a text
• Data compression with factor automata
• Forty Years of Text Indexing
• Universal Data Compression Algorithm Based on Approximate String Matching
• Lempel-Ziv data compression on parallel and distributed systems
• Textual data compression in computational biology: algorithmic techniques
• Linear-time construction of two-dimensional suffix trees
• Computing the longest previous factor
• Linear time algorithms for finding and representing all the tandem repeats in a string
• On-line construction of two-dimensional suffix trees
• Searching and encoding for infinite ordered sets
• Minimum cost multi-product flow lines
• Hardness and approximability of bounded access Lempel Ziv coding
• Bat-LZ out of hell
• Approximation algorithms for the shortest common superstring problem
• Scalability and communication in parallel low-complexity lossless compression
• On-line string matching with feedback
• Truncated suffix trees and their application to data compression.
• Distance measures for biological sequences: some recent approaches
• Lempel-Ziv Factorization Revisited
• Text compression methods
• Sublinear time Lempel-Ziv (LZ77) factorization

This page was built for publication: Linear Algorithm for Data Compression via String Matching

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