Subject: Re: Question: How to choose bit strings in arithmetic compression

From: [email-masked] (Frank Bauernoeppel)
Date: Fri, 7 Oct 1994 14:09:17 GMT

In article <[email-masked]>, Spencer Low <[email-masked]> wrote:
>DOYLE  PATRICK ([email-masked]) wrote:
>>   I read the FAQ for this section, and I was wondering if someone
>> could clarify this: in arithmetic compression, how, exactly, are the 
>> bit strings assigned to the symbol sequences?  I understand that 
>> each symbol sequence will cover a range (within the interval [0, 1]) 
>> which is proportional to its probability.  I just don't see how one
>> gets from there to the bit string.
>
>Several weeks ago I was looking for sample compression code and several 
>nice newsgroup watchers posted a reference to _The Data Compression Book_ 
>by Mark Nelson. This book is really good and definitely worth it for 
>$39.95 with disks. It explains how arithmetic coding works (order 0-N).
>
>Cool.
>
>Spencer

Lets try with a short explanation (before he buys a book): 

1. theoretical point of view
----------------------------
Let [a,b] be the interval you have finally obtained. You may choose any number
between a and b to represent your message and send the first say k binary
digits. You have to send as many bits as are necessary to distinguish
the interval from all others. The decoder reads the digits and can
find the interval by the same process of subdivision. The message length
should be transmitted separately. Some people include a special EOF code,
but this is very errorprone.

Note that if the interval is large, you are guaranteed to find a number
with a short binary representation (approx. log |b-a| bit).

2. not so theoretical point of view
-----------------------------------
There are problems when compressing on-line because you do not know
the final interval in advance. You cannot even send the
first digit if you are near 1/2 with your current interval. There are
methods to avoid such effects in the literature...

There are more issues (roundig, avoiding integer overflow,..)

3. practical point of view
--------------------------
Get the lds_11.zip package (garbo.uwasa.fi) and take a deeper look
at the source of lzari.c

	Greetings

		Frank
---
Frank Bauernoeppel, Carleton Univ., Ottawa
[email-masked]

--
[email-masked] --- Frank Bauernoeppel