Quantized Indexing Update
Posted by Sachin Garg on 10th January 2006 | Permanent Link
There have been a lot of very long discussions on QI at comp.compression over last month 2 weeks (and are still going on).
As it wasn’ t really coming to an end, David A. Scott (known for his work on Bijective compressors) has proposed a simple challenge for QI, pitting it against Arithmetic Coding. In the nut shell, its nothing but asking the inventor “NightLight” to present code which can prove his claims.
The inventor had already published code for Quantized Indexing, but it is somehow not convincing enough for others at comp.compression, who want to see a direct comparison.
For those of you out of loop, Quantized Indexing is a new algorithm for entropy coding claiming to be much faster and having better compression efficiency than popularly used Arithmetic Coding, it was first introduced in November 2005.
January 12th, 2006 at 10:27 am
Hello
I suggest interested readers view the zip file
http://bijective.dogma.net/nitelite.zip
The files in there show a bijective huffman compressor to compress files A B C to the optimal huffman compression. Of course this is optimal if A occurs 1/2 the time and each of B and C occur 1/4 the time.
The batch file then has the optimal bijecitve arithmetic compressor compress the compressed huffman file to a compressed file of which appears to be the optimal length compressed file. For the equally propable case.
Your can pretend any file is a compressed optimal file and decompress first using unarbabc to get a compress huffman then run unahfabc to get the unque file of ABC of cousre you can recompress this file back to starting file.
As usually there is no gaps QI can do that well it if can I have not seen any thing to show that it can.
January 30th, 2006 at 11:49 am
Thomas Richter posted some results he obtained comparing AC and QI at comp.compression:
In this test, AC wins on both on speed and compression ratios. I must add that Thomas is comparing AC and QI coding using AC style modelling (he has explained his reasons) so the test isn’t exactly the end of discussion.
But atleast it confirms that QI is not a good choice for use with AC style modelling (didn’t we already knew that?).
The thread isnt dead yet, so check back for for more.
April 22nd, 2006 at 11:40 pm
Hi, I just read the “Fast, optimal entropy coder” paper. In it, they describe a QI coder for binary data. At the top of page 17, they show that their scheme encodes n binary symbols, k of which are known to be 1, in log2( C(n,k) ) bits. They call this the “main” compressed data on page 16, and pointed out that it is only the “sideband” information of “k” that pushed it over the entropy.
If you do arithmetic coding given the same sideband information using the obvious approach, you get the exact same results. If you know that there are “k” ones and you want to encode “n” symbols, but you have no idea which of the n symbols are 1, the most natural thing to do is to encode the first symbol as a 1 using probability “k/n”. If it is a 1, the next symbol codes with probability “(k-1)/(n-1)”; otherwise, it codes with probability “k/(n-1)”. It is possible to show that the total bits used for coding this information using this strategy is always “log2( C(n,k) )”, regardless of where the 1s end up.
So, at least in the binary case, QI gives theoretically identical compression ratios to AC if you give AC the same sideband information and you assume that the 1 bits are randomly distributed. From this I conclude that the differences between QI and AC compression ratios aren’t about how good they are at entropy coding, but about how good the statistical models used match actual symbol probabilities.
May 2nd, 2006 at 2:06 pm
> So, at least in the binary case,
> QI gives theoretically identical
> compression ratios to AC …
The comment above is correct only in the 1st order redundancies (for n->infinity) and for infinite precision coders (arithmetic & enumerative). For finite precision coders the redundancy of AC (in excess bits per input symbol) is 4 times larger than that of QI at the same arithmetic precision of the two coders (generally 2*A times larger, where A is alphabet size). There are also further differences in the 2nd and higher orders. The usenet post:
QI vs AC Comparison
has a more detailed comparison between QI and AC, including the precise redundancy expressions (with references) and their significance.