Data Compression Using Adaptive Coding and Partial String Matching

By J. Cleary, Ian H. Witten. 1984

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Optimization & Training

Citations in the corpus

Generating Sequences With Recurrent Neural Networks (2013, methodology): “This distinguishes them from n-gram models and compression algorithms such as Prediction by Partial Matching [5], whose predictive distributions are determined by counting exact matches between the recent history and the training set.”
A four-stage algorithm for updating a Burrows-Wheeler transform (2009, methodology): “LF [0] = CT [G] + rankG(L, 0)− 1 = 3 + 1− 1 = 3 LF [1] = CT [$] + rank$ (L, 1)− 1 = 0 + 1− 1 = 0 LF [2] = CT [G] + rankG(L, 2)− 1 = 3 + 2− 1 = 4 LF [3] = CT [C] + rankC(L, 3)− 1 = 2 + 1− 1 = 2 LF [4] = CT [T] + rankT(L, 4)− 1 = 5 + 1− 1 = 5 LF [5] = CT [A] + rankA(L, 5)− 1 = 1 + 1− 1 = 1 i F L LF 0 ”
On Prediction Using Variable Order Markov Models (2004, methodology): “The Prediction by Partial Match (ppm) algorithm (Cleary & Witten, 1984) is considered to be one of the best lossless compression algorithms.7 The algorithm requires an upper bound 6.”
Approximate Data Collection in Sensor Networks using Probabilistic Models (2006, methodology): “, Prediction by Partial Matching (PPM) [3]) combine arithmetic encoding [30] with Markov Models to achieve very high compression rates.”
Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform .2. With context models (2000, methodology): “These include the prediction by partial match algorithm [4], dynamic Markov modeling [5], context gathering algorithm [24], [26], and context-tree weighting method [27], [28].”
Introduction to Data Compression (2005, methodology): “The best-known context-based algorithm is the ppm algorithm, first proposed by Cleary and Witten [65] in 1984.”
Distributed source coding for sensor networks (2004, background): “ing, Lempel-Ziv coding [60], PPM [ 61 ] and CTW [62]) have dominated so far.”
A Machine Learning Perspective on Predictive Coding with PAQ8 (2012, methodology): “Noncontiguous context matches improve noise robustness in comparison to PPM.”
Data compression algorithms for energy-constrained devices in delay tolerant networks (2006, background): “In more traditional arenas, a large variety of compression algorithms have been proposed including string-based techniques [19][32][43], entropy-based techniques [11][15][40], and others.”
Binary RDF representation for publication and exchange (HDT) (2013, methodology): “We choose a predictive high-order compressor, PPM [34], which identifies this type of redundancy to improve the encoding of the dictionary.”
COMET: adaptive context-based modeling for ultrafast HIV-1 subtype identification (2014, methodology): “The approach of COMET is inspired by the Prediction by Partial Matching compression algorithm (31), which has repeatedly and independently been shown to provide high classification accuracy for biological sequences (32,33).”
Efficient universal lossless data compression algorithms based on a greedy sequential grammar transform - Part one: Without context models (2000, methodology): “These include the prediction by partial match algorithm [4], dynamic Markov modeling [5], context gathering algorithm [24], [26], and context-tree weighting method [27], [28].”
How smart are our environments? An updated look at the state of the art (2007, background): “This approach assumes that the inhabitants' itineraries are inherently compressible and allow application of universal data compression algorithms [12] [46], which make very basic and broad assumptions , and yet minimize the source entropy for stationary Ergodic stochastic processes [70].”
this paper (2009, unknown): “For traditional standard quality RTC, the time required to decode a frame is much shorter than the interarrival time of frames.”
A Machine Learning Perspective on Predictive Coding with PAQ (2011, methodology): “PAQ is a family of open-source compression algorithms closely related to the better known Prediction by Partial Matching (PPM) algorithm (Cleary and Witten, 1984).”