DATA COMPRESSION USING ADAPTIVE CODING AND PARTIAL STRING MATCHING
Abstract
The recently-developed technique of arithmetic coding, in
conjunction with a Markov model of the source, is a powerful method of data
compression in situations where a linear treatment is inappropriate. Adaptive
coding allows the model to be constructed dynamically by both encoder and
decoder during the course of the transmission, and has been shown to
incur a smaller coding overhead than explicit transmission of the model's
statistics. But there is a basic conflict between the desire to use
high-order Markov models and the need to have them formed quickly as the
initial part of the message is sent. This paper describes how the
conflict can be resolved with partial string matching, and reports experimental
results which show that English text can be coded in as little as 2.2
bits/character with no prior knowledge of the source.
Description
Keywords
Computer Science