paper1

Best algorithm for LZW ..C language

that the encoded string falls within the final range.
Since $done_encoding( \| )$ (lines 119-123) can be sure that
$low$ and $high$ are constrained by either (1a) or (1b) above, it need only
transmit $01$ in the first case or $10$ in the second to remove the remaining
ambiguity.
It is convenient to do this using the $bit_plus_follow( \| )$ procedure
discussed earlier.
The $input_bit( \| )$ procedure will actually read a few more bits than were
sent by $output_bit( \| )$ as it needs to keep the low end of the buffer full.
It does not matter what value these bits have as the EOF is uniquely
determined by the last two bits actually transmitted.
.sh "Models for arithmetic coding"
.pp
The program of Figure\ 3 must be used with a model which provides
a pair of translation tables $index_to_char[ \| ]$ and $char_to_index[ \| ]$,
and a cumulative frequency array $cum_freq[ \| ]$.
The requirements on the latter are that
.LB
.NP
$cum_freq[ i-1 ] ~ >= ~ cum_freq[ i ]$;
.NP
an attempt is never made to encode a symbol $i$ for which
$cum_freq[i-1] ~=~ cum_freq[i]$;
.NP
$cum_freq[0] ~ <= ~ Max_frequency$.
.LE
Provided these conditions are satisfied the values in the array need bear
no relationship to the actual cumulative symbol frequencies in messages.
Encoding and decoding will still work correctly, although encodings will
occupy less space if the frequencies are accurate.
(Recall our successfully encoding \fIeaii!\fR according to the model of
Table\ 1, which does not actually reflect the frequencies in the message.)  \c
.rh "Fixed models."
The simplest kind of model is one in which symbol frequencies are fixed.
The first model in Figure\ 4 has symbol frequencies which approximate those
of English (taken from a part of the Brown Corpus, Kucera & Francis, 1967).
.[
%A Kucera, H.
%A Francis, W.N.
%D 1967
%T Computational analysis of present-day American English
%I Brown University Press
%C Providence, RI
.]
However, bytes which did not occur in that sample have been given frequency
counts of 1 in case they do occur in messages to be encoded
(so, for example, this model will still work for binary files in which all
256\ bytes occur).
Frequencies have been normalized to total 8000.
The initialization procedure $start_model( \| )$ simply computes a cumulative
version of these frequencies (lines 48-51), having first initialized the
translation tables (lines 44-47).
Execution speed would be improved if these tables were used to re-order
symbols and frequencies so that the most frequent came first in the
$cum_freq[ \| ]$ array.
Since the model is fixed, the procedure $update_model( \| )$, which is
called from both $encode.c$ and $decode.c$, is null.
.pp
An \fIexact\fR model is one where the symbol frequencies in the message are
exactly as prescribed by the model.
For example, the fixed model of Figure\ 4 is close to an exact model
for the particular excerpt of the Brown Corpus from which it was taken.
To be truly exact, however, symbols that did not occur in the excerpt would
be assigned counts of 0, not 1 (sacrificing the capability of
transmitting messages containing those symbols).
Moreover, the frequency counts would not be scaled to a predetermined
cumulative frequency, as they have been in Figure\ 4.
The exact model may be calculated and transmitted before sending the message.
It is shown in Cleary & Witten (1984a) that, under quite general conditions,
this will \fInot\fR give better overall compression than adaptive coding,
described next.
.[
Cleary Witten 1984 enumerative adaptive codes
%D 1984a
.]
.rh "Adaptive models."
An adaptive model represents the changing symbol frequencies seen \fIso far\fR
in the message.
Initially all counts might be the same (reflecting no initial information),
but they are updated as each symbol is seen, to approximate the observed
frequencies.
Provided both encoder and decoder use the same initial values (eg equal
counts) and the same updating algorithm, their models will remain in step.
The encoder receives the next symbol, encodes it, and updates its model.
The decoder identifies it according to its current model, and then updates its
model.
.pp
The second half of Figure\ 4 shows such an adaptive model.
This is the type of model recommended for use with Figure\ 3, for in practice
it will outperform a fixed model in terms of compression efficiency.
Initialization is the same as for the fixed model, except that all frequencies
are set to 1.
The procedure $update_model(symbol)$ is called by both $encode_symbol( \| )$
and $decode_symbol( \| )$ (Figure\ 3 lines 54 and 151) after each symbol is
processed.
.pp
Updating the model is quite expensive, because of the need to maintain
cumulative totals.
In the code of Figure\ 4, frequency counts, which must be maintained anyway,
are used to optimize access by keeping the array in frequency order \(em an
effective kind of self-organizing linear search (Hester & Hirschberg, 1985).
.[
Hester Hirschberg 1985
.]
$Update_model( \| )$ first checks to see if the new model will exceed
the cumulative-frequency limit, and if so scales all frequencies down by a
factor of 2 (taking care to ensure that no count scales to zero) and
recomputes cumulative values (Figure\ 4, lines\ 29-37).
Then, if necessary, $update_model( \| )$ re-orders the symbols to place the
current one in its correct rank in the frequency ordering, altering the
translation tables to reflect the change.
Finally, it increments the appropriate frequency count and adjusts cumulative
frequencies accordingly.
.sh "Performance"
.pp
Now consider the performance of the algorithm of Figure\ 3, both
in compression efficiency and execution time.
.rh "Compression efficiency."
In principle, when a message is coded using arithmetic coding, the number of
bits in the encoded string is the same as the entropy of that message with
respect to the model used for coding.
Three factors cause performance to be worse than this in practice:
.LB
.NP
message termination overhead
.NP
the used of fixed-length rather than infinite-precision arithmetic
.NP
scaling of counts so that their total is at most $Max_frequency$.
.LE
None of these effects is significant, as we now show.
In order to isolate the effect of arithmetic coding the model will be
considered to be exact (as defined above).
.pp
Arithmetic coding must send extra bits at the end of each message, causing a
message termination overhead.
Two bits are needed, sent by $done_encoding( \| )$ (Figure\ 3 lines 119-123),
in order to disambiguate the final symbol.
In cases where a bit-stream must be blocked into 8-bit characters before
encoding, it will be necessary to round out to the end of a block.
Combining these, an extra 9\ bits may be required.
.pp
The overhead of using fixed-length arithmetic
occurs because remainders are truncated on division.
It can be assessed by comparing the algorithm's performance with
the figure obtained from a theoretical entropy calculation
which derives its frequencies from counts scaled exactly as for coding.
It is completely negligible \(em on the order of $10 sup -4$ bits/symbol.
.pp
The penalty paid by scaling counts is somewhat larger, but still very
small.
For short messages (less than $2 sup 14$ bytes) no scaling need be done.
Even with messages of $10 sup 5$ to $10 sup 6$ bytes, the overhead was found
experimentally to be less than 0.25% of the encoded string.
.pp
The adaptive model of Figure\ 4 scales down all counts whenever the total
threatens to exceed $Max_frequency$.
This has the effect of weighting recent events more heavily compared with
those earlier in the message.
The statistics thus tend to track changes in the input sequence, which can be
very beneficial.
(For example, we have encountered cases where limiting counts to 6 or 7\ bits
gives better results than working to higher precision.)  \c
Of course, this depends on the source being modeled.
Bentley \fIet al\fR (1986) consider other, more explicit, ways of
incorporating a recency effect.
.[
Bentley Sleator Tarjan Wei 1986 locally adaptive
%J Communications of the ACM
.]
.rh "Execution time."
The program in Figure\ 3 has been written for clarity, not execution speed.
In fact, with the adaptive model of Figure\ 4, it takes about 420\ $mu$s per
input byte on a VAX-11/780 to encode a text file, and about the same for
decoding.
However, easily avoidable overheads such as procedure calls account for much
of this, and some simple optimizations increase speed by a factor of 2.
The following alterations were made to the C version shown:
.LB
.NP
the procedures $input_bit( \| )$, $output_bit( \| )$, and
$bit_plus_follow( \| )$ were converted to macros to eliminate
procedure-call overhead;
.NP
frequently-used quantities were put in register variables;
.NP
multiplies by two were replaced by additions (C ``+='');
.NP
array indexing was replaced by pointer manipulation in the loops
at line 189 of Figure\ 3 and lines 49-52 of the adaptive model in Figure\ 4.
.LE
.pp
This mildly-optimized C implementation has an execution time of
214\ $mu$s/262\ $mu$s, per input byte,
for encoding/decoding 100,000\ bytes of English text on a VAX-11/780, as shown
in Table\ 2.
Also given are corresponding figures for the same program on an
Apple Macintosh and a SUN-3/75.
As can be seen, coding a C source program of the same length took slightly
longer in all cases, and a binary object program longer still.
The reason for this will be discussed shortly.
Two artificial test files were included to allow readers to replicate the
results.
``Alphabet'' consists of enough copies of the 26-letter alphabet to fill
out 100,000\ characters (ending with a partially-completed alphabet).
``Skew-statistics'' contains 10,000 copies of the string
\fIaaaabaaaac\fR\^; it demonstrates that files may be encoded into less than
1\ bit per character (output size of 12,092\ bytes = 96,736\ bits).
All results quoted used the adaptive model of Figure\ 4.
.pp
A further factor of 2 can be gained by reprogramming in assembly language.
A carefully optimized version of Figures\ 3 and 4 (adaptive model) was
written in both VAX and M68000 assembly language.
Full use was made of registers.
Advantage was taken of the 16-bit $code_value$ to expedite some crucial
comparisons and make subtractions of $Half$ trivial.
The performance of these implementations on the test files is also shown in
Table\ 2 in order to give the reader some idea of typical execution speeds.
.pp
The VAX-11/780 assembly language timings are broken down in Table\ 3.
These figures were obtained with the U\s-2NIX\s+2 profile facility and are
accurate only to within perhaps 10%\(dg.
.FN
\(dg This mechanism constructs a histogram of program counter values at
real-time clock interrupts, and suffers from statistical variation as well as
some systematic errors.
.EF
``Bounds calculation'' refers to the initial part of $encode_symbol( \| )$
and $decode_symbol( \| )$ (Figure\ 3 lines 90-94 and 190-193)
which contain multiply and divide operations.
``Bit shifting'' is the major loop in both the encode and decode routines
(lines 95-113 and 194-213).
The $cum$ calculation in $decode_symbol( \| )$, which requires a
multiply/divide, and the following loop to identify the next symbol
(lines\ 187-189), is ``Symbol decode''.
Finally, ``Model update'' refers to the adaptive
$update_model( \| )$ procedure of Figure\ 4 (lines\ 26-53).
.pp
As expected, the bounds calculation and model update take the same time for
both encoding and decoding, within experimental error.
Bit shifting was quicker for the text file than for the C program and object
file because compression performance was better.
The extra time for decoding over encoding is due entirely to the symbol
decode step.
This takes longer in the C program and object file tests because the loop of
line\ 189 was executed more often (on average 9\ times, 13\ times, and
35\ times respectively).
This also affects the model update time because it is the number of cumulative
counts which must be incremented in Figure\ 4 lines\ 49-52.
In the worst case, when the symbol frequencies are uniformly distributed,
these loops are executed an average of 128 times.
Worst-case performance would be improved by using a more complex tree
representation for frequencies, but this would likely be slower for text
files.
.sh "Some applications"
.pp
Applications of arithmetic coding are legion.
By liberating \fIcoding\fR with respect to a model from the \fImodeling\fR
required for prediction, it encourages a whole new view of data compression
(Rissanen & Langdon, 1981).
.[
Rissanen Langdon 1981 Universal modeling and coding
.]
This separation of function costs nothing in compression performance, since
arithmetic coding is (practically) optimal with respect to the entropy of
the model.
Here we intend to do no more than suggest the scope of this view
by briefly considering
.LB
.NP
adaptive text compression
.NP
non-adaptive coding
.NP
compressing black/white images
.NP
coding arbitrarily-distributed integers.
.LE
Of course, as noted earlier, greater coding efficiencies could easily be
achieved with more sophisticated models.
Modeling, however, is an extensive topic in its own right and is beyond the
scope of this paper.
.pp
.ul
Adaptive text compression
using single-character adaptive frequencies shows off arithmetic coding to
good effect.
The results obtained using the program of Figures\ 3 and 4 vary from
4.8\-5.3\ bit/char for short English text files ($10 sup 3$\ to $10 sup 4$
bytes) to 4.5\-4.7\ bit/char for long ones ($10 sup 5$ to $10 sup 6$ bytes).
Although adaptive Huffman techniques do exist (eg Gallagher, 1978;
Cormack & Horspool, 1984) they lack the conceptual simplicity of
arithmetic coding.
.[
Gallagher 1978 variations on a theme by Huffman
.]
.[
Cormack Horspool 1984 adaptive Huffman codes
.]
While competitive in compression efficiency for many files, they are slower.
For example, Table\ 4 compares the performance of the mildly-optimized C
implementation of arithmetic coding with that of the U\s-2NIX\s+2
\fIcompact\fR program which implements adaptive Huffman coding using
a similar model\(dg.
.FN
\(dg \fICompact\fR's model is essentially the same for long files (like those
of Table\ 4) but is better for short files than the model used as an example
in this paper.
.EF
Casual examination of \fIcompact\fR indicates that the care taken in
optimization is roughly comparable for both systems, yet arithmetic coding
halves execution time.
Compression performance is somewhat better with arithmetic coding on all the