A formula based approach to Arithmetic Coding

[arun-siara]

I have been doing research on entropy encoding for some time.. I found some interesting relationships between Arithmetic coding and other methods such as Huffman Coding. I made an article to explain them and am presenting here for review:

http://siara.cc/arithmetic_coding_new_approach/

I have also attached a PDF version for convenience.

Please let me know your ideas.

 

[chiro]

Hey arun-siara.

Just wanted to point out something that could be expanded on or mentioned when it comes to compression and that is the idea of a basis.

Most compression algorithms (particulary the lossy ones - but lossless ones do in one form or another) work by utilizing a basis that has represents the same information density but in a better way.

For example - images and movies like those based on JPEG or MPEG use bases based on the cosine transforms, wavelet transforms, Fourier transforms and other transforms. Each transform has its own basis and what tends to happen is that you retain so many coefficients for given basis vectors that contribute to most of the information density that is being described.

Even though chopping things off is how a lot of lossy algorithms do things, lossless methods also use their own basis. The difference between the two is that they retain all coefficients for all basis vectors that span the space and keep its dimension - so they aren't projections onto sub-spaces but a reconstruction of the information in some space.

If you can think about how the basis are represented and the context of that basis then it will help you relate the different techniques and also make sense of why they work and do the things they do in the way they do.

Just a couple of thoughts.

 

[arun-siara]

Hi chiro,

Thanks for taking time to go through the article. I agree with you, the basis needs to be mentioned. I thought I would leave it to the articles I have referred which make it abundantly clear. Even then probably the roots and connections would not be clear just by reading the article.

I will need to lookup lossy algorithms again as I don't recall Arithmetic Coding being used for lossy compression.

Thanks again for the constructive feedback. I believe it will make the article look richer.

Regards
Arun

Hey arun-siara.

Just wanted to...

 

[chiro]

AC usually isn't a lossy algorithm but the idea of a basis is what makes compression work.

If you understand the basis then you understand the nature of information and how it is actually compressed.

It helps understand that no matter what algorithm you use.