Arithmetic Coding ? How is the output Stored ?
Posted On March 31, 2011
Question by leonidas: Arithmetic Coding ? How is the output Stored ?
Now i just saw an example of it and it compresses a string “Bill Gates” to 0.2572167752. I Understand the general idea behind it but the string is 10 bytes and the number is also stored as a 10 digit number,so where has it saved bits ? and how much has it actually reduced ?
Answer by DogmaBites
Arithmetic coding has two ways of saving space.
First you can assign different sized intervals to different source symbols according to their frequency of use. This is similar to Huffman coding. This uses fewer bits to store the more common source symbols and on average uses fewer bits for the whole message.
Second, Arithmetic coding doesn’t waste bits on unused range. If you use a fixed number of bits for each symbol, unless you have exactly a power of 2 of source symbols you will waste some of your coding range. If you use 7 bits per symbol and you don’t have 128 possible symbols, then you are wasting space. By using a base set equal to the number of possible source symbols, arithmetic coding perfectly uses the range you need.
In your example, the number is 10 digits long, but we would not use 10 bytes to store it. A simple storage method could do it in 5 bytes (e.g. binary coded decimal). Converting it to a binary fraction, you can store that value in 34 bits.
Both are smaller than the 80 bits used by the text string.
Add your own answer in the comments!