Re: QI and MQ Coder: First real-life experiences

> > out encoding of N (or add the same figure for all coders and to
>> N*log(A))
>
> DYM N*log2(A) ?

Yep. Virtually all logs in compression are log2(). The number N*log(A)
is the log() of the number A^N, which is the number of distinct strings
of N symbols in alphabet of size A, which was our test set (call it
Set(A,N)) of 'messages'. Hence A*log(N) is the lower bound on length
(in bits) on any unique index for the elements of Set(A,N).

Unlimited precision enumerative coding (EC) achieves, of course, this
bound, which is simply the length in bits of a binary form for N digit
numbers in radix A (since EC or QI do this type of encoding as a
conversion from radix A to binary). The QI, limited to g bits precision
(the mantissa size for SW integers, in QIC g=32) produces output of
length which is on average (over Set(A,N)) longer by a D(g,A,N) bits
from N*log(A), where D(g,A,N) < N*2*log(e)/2^g bits. An arithmetic
coder (AC) limited to the same precision g will produce excess of
Da(g,A,N), which is on average 2*A times larger than QI's quantization
excess D(g,A,N) due to its less accurate quantization of codewords (the
enumerative addends).

On the Set(A,N), for A=3 and N=10^6, which is the most favorable A>2
value for AC, the QI's output size is only 1.6e-4 bits above the lower
bound N*log(A). As shown on p. 8 in [T3], this is, purely
mathematically, the closest that any coder using codewords (addends
with QI and AC) limited to length g=32 bits can get, there was no
results I was waiting for to hear (one might as well wait to see
whether someone can "beat" 2+2 and claim their "adder" can get 3 for
it). Since anyone can run the test with QI.exe provided, as described
in the posts:

M1. --- QI test results for coding on Set(A,N) for A=3 N=10^6
http://groups.google.com/group/comp.compression/msg/ff1ee67d18b63f5a

M2. --- Explanation for the bit fractions shown by QI
http://groups.google.com/group/comp.compression/msg/1e015f38d228969e

M3. Answers to further questions on test reported in [M3]
http://groups.google.com/group/comp.compression/msg/508e96ebcb4577f1

to verify the claim and check how it is computed and displayed in the
source code (or read [T1] on QI mixed radix coding), the matter is
closed at a rational level (the alleged "controversy" is being stirred
at the other level).


> he wasn't testing speed. speed is often not a big issue.

Tested or not, the execution times were reported and commented on in
their own little section.

>> You haven't explained as yet how does use of files change compression
>> ratios
>
> It doesn't it just makes them more easily measurable.

The point above was a response to the claims that compression ratios
obtained on memory buffers tests are not valid (how?) and that only
file tests will provide the "real" compression ratios (why?) of the
two entropy coding algorithms for which the _source is publicly
available_. The underlying theme of all that seemingly pointless song
and dance, the persistent assertions (without being able to explain
why) that only files somehow give the "real" compression ratios while
the buffers give the "unreal" ratios, is described in the earlier post:

http://groups.google.com/group/comp.compression/msg/8d62e372056d9d53

as method (b) (of the five frivolous ways to "win" a compression
contest against another coder).

.

Relevant Pages

  • Re: Compression filter for Loopback device
    ... filesystem is a *major* disadvantage. ... will be far worse for write compression. ... >With this NBD server I tested the compression ratios that my scheme ... I'm very surprised you got ratios better than CramFS, ...
    (Linux-Kernel)
  • Re: QI and MQ Coder: First real-life experiences
    ... > The point above was a response to the claims that compression ratios ... > obtained on memory buffers tests are not valid and that only ...
    (comp.compression)
  • Re: Need specific BootCamp/Vista advice please
    ... test to the one above would be expected to yield compression ratios up ... Erased 1.83 partition just for good measure. ... Wiped 1.83 GB partition with hex zeroes. ...
    (comp.sys.mac.system)
  • Re: Compression ratios of MJPEG, MPEG1, MPEG2, MPEG4, H.263, and H.264
    ... I guess I'm showing my newbieness when it comes to digital video. ... thought it it was as simple as each codec having a range of compression ... and of those compression ratios there was a range that provided ...
    (comp.compression)
  • Re: QI and MQ Coder: First real-life experiences
    ... >> ported for Unix (thanks Jasen Betts!) ... a static 0-order coder should do. ... > chariot against another chariot. ... My Compression code http://bijective.dogma.net/ ...
    (comp.compression)