The Computer Journal · 1997 · 14 citations · 14 references
ComputingComputer ScienceComputational LinguisticsInformation RetrievalNatural Language ProcessingData CompressionLossy Data CompressionText Similarity AnalysisAdaptive CompressionCompressionCompression AlgorithmsCompression Performance EvaluationContext-based CompressionLempel-ziv CompressionSequence CompressionSorting
Every symbol in the data can be predicted by taking the immediately preceding symbols, or context, into account. This paper proposes a new adaptive data-compression method based on a context similarity measure. We measure the similarity of contexts using a context sorting mechanism. The aim of context sorting is to store a set of contexts in a specific order so that contexts more similar to the current one are more accessible. The proposed method predicts the next symbol by ranking the previous context–symbol pairs in order of context similarity. The codeword for the next symbol represents the rank of the symbol in this ordered sequence. The compression performance is evaluated both analytically and empirically. Although the proposed method uses no probability distribution to make a prediction, it gains good compression. It also reveals a strong relation between symbol-ranking compression and the Ziv–Lempel textual substitution method.
14
Prediction and Entropy of Printed English
Claude E. Shannon · Bell System Technical Journal · 1951 · 2.7K citations
A Block-sorting Lossless Data Compression Algorithm
Michael T. Burrows, D. J. Wheeler · 1994 · 2.4K citations