MODELING FOR TEXT COMPRESSION
Date
1988-10-25
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
The best schemes for text compression employ large models
to help them predict which characters will come next. The actual
next characters are coded with respect to the prediction, resulting
in compression of information. Models are best formed adaptively,
based on the text seen so far. This paper surveys successful
strategies for adaptive modeling which are suitable for use in
practical text compression systems.
The strategies fall into three main classes: finite-context modeling, in
which the last few characters are used to condition the probability
distribution for the next one; finite-state modeling, in which the
distribution is conditioned by the current state (and which subsumes
finite-context modeling as an important special case); and dictionary
modeling, in which strings of characters are replaced by pointers into an
evolving dictionary. A comparison of different methods on the same sample
texts is included, along with an analysis of future research directions.
Description
Keywords
Computer Science