Browse Prior Art Database

Improved Algorithm Context

IP.com Disclosure Number: IPCOM000110689D
Original Publication Date: 1992-Dec-01
Included in the Prior Art Database: 2005-Mar-25
Document File: 2 page(s) / 88K

Publishing Venue

IBM

Related People

Furlan, G: AUTHOR [+2]

Abstract

This article describes an improvement of Algorithm Context [1,2,3] which enhances the compression in particular for half-tone images, while at the same time also improving the compression for other sources, albeit less dramatically.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Improved Algorithm Context

       This article describes an improvement of Algorithm
Context [1,2,3] which enhances the compression in particular for
half-tone images, while at the same time also improving the
compression for other sources, albeit less dramatically.

      In broad terms, Algorithm Context stores recursively in a tree
form all the possible states of an agreed type each symbol in the
source string can occur, just as if it would run in parallel a number
of Markov models for the string.  As the states are generated, all
the counts of the symbol occurrences in each state are also stored.
Finally, there is a rule for selecting the most efficient state out
of the several possible ones for each symbol, in which it can be
encoded with use of an arithmetic coder.  The improvements reported
here pertain to the way the states are formed as well as to the
optimal state selection rule itself.

      The prior-art optimal state selection rule is done by
calculating at each state z(i), identified with the ith node from the
root along the path xt, xt-1,...,xt-i+1 into the past string, the
index

                            (Image Omitted)

where E(xt,z(i)) = - log P(xt|z(i)) denotes the code length with
which symbol xt, is encoded in state z(i) using this state's
statistics, collected from the past symbol occurrences.  The optimal
state is taken as the farthest node from the root for which the index
is negative.  The index is initialized in each state, except the
root, to a positive value.  The root index is kept at a constant
negative number.  Notice that a negative index in a state means that
the cumulative past code length in this state is shorter than the
code length for the same symbol occurrences in the father node.

      For many types of source strings a state's effectiveness grows
with its distance form the root up to a point, after which it
decreases because of over-parameterization.  However...