Author: Gerd Isenberg
Date: 03:34:31 01/04/06
Go up one level in this thread
On January 04, 2006 at 00:26:24, Ratko V Tomic wrote:
>On January 03, 2006 at 16:15:11, James T. Walker wrote:
>
>>I don't understand a word you wrote and yet I find your story the most
>>facinating thing I've read lately. Amazing!?
>
>The report [T1] should be quite readable ([T3] is very consise due
>to severa space limitations). Also, the EC.exe program (included with
>the source) has command line option 'cd' which shows enumerative
>coding step by step, with all binary strings and numbers shown in full
>as they transform. The enumerative coding is actually much simpler than
>arithmetic coding. Consider the encode & decode (of a 32 bit dword x)
>right out of the EC32.c source file:
>
>//-- Encode bit-string x to enum index I
>
>dword enc32(dword x)
>{ int k,n; // k=count of 1's, n=0 based offset of next bit=1
> dword I;
> k=1; I=0; // Index I is 0, k=count of 1's
> while(x) // unused/higher bits in dword x are set to 0
> {
> n=loBit(x); // get bit offset n=0...NB-1 of the lowest bit=1
> x&=x-1; // clear the lowest bit=1 in the "buffer" x
> I+=bc32(n,k++); // add binomial C(n,k) to the index
> } // increment count of ones, k
> return I; // return enumerative index I
>}
Hi Ratko,
this is all very interesting - but i need some more time to understand and to
play with the code. I found the explanation with Lattice walks on the Pascal
triangle quite instructive.
One question to the implementation of the binary 32-bit Encoder/Decoder - i
think beside the path-index as "main" compressed data also the number of one
bits (if variable) is required. I don't see how "k" is passed from Encoder to
Decoder!? Is there a reason why you initialize K with one in the C-code of the
Encoder - in opposition to the pseudo code?
I=0; // init cumulative path index
for(k=n=0; n<M; ++n) // M is the number of input bits
{ // or a block size
if (getbit(n)==1) // get bit at 0-based offset n
{ // skip on b=0, add on b=1
++k; // increment count of 1’s found
I=I+C(n,k); // add binomial to the path index
}
} // k is now the final count of 1’s
Thanks,
Gerd
>
>//-- Decode enum index I to bit-string x
>
>dword dec32(dword I,int n,int k)
>{ dword x,b;
> x=0; // clear outpurt buffer (with most frequent bit)
> do{
> x<<=1; // fill in decoded bit as 0 (at position 0 in x)
> b=bc32(n,k); // find the largest binomial coefficient b=C(n,k)<=I
> if (I>=b) // check if we can subtract b from I
> { // ==> yes, decoded bit is 1
> I-=b; ++x; // reduce index I and set decoded bit=1
> if (!--k) // decrement count of 1's and stop if no more 1's left
> {
> x<<=n; // pad the rest of output with 0 bits (in the low bits)
> break; // leave the decoding loop
> }
> } // ==> no, decoded bit is 0; try next smaller b(n,k)
> }
> while(--n>=0); // this loop can be made faster using binary search
> return x; // instead of sequential "(--n)" for "if (I>=b)" case
>}
>
>That's how simple it is -- it looks almost like radix conversion using a table
>of powers of 10 (instead of binomial table). Rissanen's paper [27] elaborates
>this parallel with radix conversion in depth. The tricky part, which stayed
>unsolved for four decades, was getting this to work in limited precision. But
>even that is quite simple, at least within the lattice walk approach &
>enumeration conventions I used.
>
>The referance page: http://www.1stworks.com/ref/RefLib.htm
>has most of the papers and textbooks available online. See
>especially:
>
>3. N. Abramson "Information Theory and Coding" (37 Mb) McGraw-Hill 1963
> http://kh.bu.edu/qcl/pdf/abramson1963100c606e.pdf
>
>38. F. Ruskey "Combinatorial Generation"
> Textbook for CSC-425/520 Univ. of Victoria CA,2003
> http://www.1stworks.com/ref/RuskeyCombGen.pdf
>
>23. L. Öktem "Hierarchical Enumerative Coding and Its Applications
> in Image Compressing" Ph.D. thesis, TUT Finland, 1999
> http://www.1stworks.com/ref/oktemThesis.pdf
>
>36. T.J. Tjalkens "Efficient and fast data compression codes for
> discrete sources with memory"
> Ph.D. thesis, Eindhoven University of Technology, Sep 1987
> http://alexandria.tue.nl/extra3/proefschrift/PRF5B/8709277.pdf
>
>25. W. Myrvold, F. Ruskey
> "Ranking and Unranking Permutations in Linear Time"
> Information Processing Letters, 79, 281-284, 2001
> http://citeseer.ist.psu.edu/myrvold00ranking.html
>
> Also other Ruskey papers at:
> http://www.cs.uvic.ca/~ruskey/Publications/
>
> especially the excerpt from his Ph.D. thesis on trees enumeration:
> http://www.cs.uvic.ca/~ruskey/Publications/Thesis/Thesis.html
>
>27. J. Rissanen "Arithmetic codings as number representations"
> Acta Polyt. Scandinavica, Math. & Comp. Sc. Vol. 31 pp 44-51, 1979
> http://www.1stworks.com/ref/ariNumRepr.pdf
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.