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

codingsuffix treeuniversal representation of the integers

Mathematics Subject Classification ID

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

Cited in

(35)

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

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)