Author: Ratko V Tomic
Date: 21:26:24 01/03/06
Go up one level in this thread
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
}
//-- 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.