Help needed...maybe dynamic huffman codes?

[Harry Potter]

I've been doing *everything* with file compression to get a better ratio. I have several "signature" techniques, i.e. ones of my own design; I've been tweaking figures; I've been advancing old techniques, all to no avail. Only one technique worked at all. The best I can do is approach the ratio of the ZIP deflate technique--.6% off on a highly-compressible test file. I remember hearing about dynamic Huffman codes in the documentation of the zip format and am wondering if it would help. I looked in Wikipedia about it and don't see it. Can anybody out there point me to it? Any help would be appreciated. I don't want to reveal my signature techniques or theories until after I publish my software.

[Robert Wessel]

On Mon, 21 Jan 2013 15:51:57 -0800 (PST), Harry Potter
<rose.j...@yahoo.com> wrote:

>I've been doing *everything* with file compression to get a better ratio. I have several "signature" techniques, i.e. ones of my own design; I've been tweaking figures; I've been advancing old techniques, all to no avail. Only one technique worked at all. The best I can do is approach the ratio of the ZIP deflate technique--.6% off on a highly-compressible test file. I remember hearing about dynamic Huffman codes in the documentation of the zip format and am wondering if it would help. I looked in Wikipedia about it and don't see it. Can anybody out there point me to it? Any help would be appreciated. I don't want to reveal my signature techniques or theories until after I publish my software.

Does section 5.3 of the following help?

http://www.pkware.com/documents/casestudies/APPNOTE.TXT

But Dynamic Huffman (usually called Adaptive Huffman) has a page with
a number of reference on Wikipedia:

http://en.wikipedia.org/wiki/Adaptive_Huffman_coding

But in general, an adaptive arithmetic technique usually works better
than adaptive Huffman.

http://en.wikipedia.org/wiki/Arithmetic_coding#Adaptive_arithmetic_coding

[Harry Potter]

The APPNOTE.txt article was a bit confusing, but the wikipedia article should be useful. As for arithmetic coding being better, I plan to do better with Huffman before implementing better techniques. BTW, I am also working on 8-bit techniques. Where can I go for useful ideas for that?

[Jim Leonard]

On Jan 22, 12:27 pm, Harry Potter <rose.josep...@yahoo.com> wrote:
> BTW, I am also working on 8-bit techniques.  Where can I go for useful ideas for that?

Do you mean techniques for 8-bit input symbols (ie. you are
compressing bytes serially) or do you mean techniques for 8-bit
computers such as the C64, Apple II, etc?

[Harry Potter]

On Tuesday, January 22, 2013 2:02:13 PM UTC-5, Jim Leonard wrote:
> On Jan 22, 12:27 pm, Harry Potter <rose.josep...@yahoo.com> wrote: > BTW, I am also working on 8-bit techniques.  Where can I go for useful ideas for that? Do you mean techniques for 8-bit input symbols (ie. you are compressing bytes serially) or do you mean techniques for 8-bit computers such as the C64, Apple II, etc?

The latter.

[Harry Potter]

I read about Adaptive Huffman codes on wikipedia.com and am having a hard time undestanding it. Right now, I get some writes of >=20 bits per symbol and poor overall compression ratio. I'd better look at wikiedia for the Shannon-Fano technique in Deflate. Right now, my technique hovers around the compression ratio of the deflate technique. And as for Adaptive Huffman codes, I can't figure out how to properly swap the nodes. Can anybody explain it for me better? The following is the code for handling the update process for the update routine:
------------------------
//c=code of current input
void UpdateHuffCode (unsigned char c)
{
//ch=current node.
//HuffEnv.entrynum[] contains the node # for a given value, or -1 if
//unused.
unsigned i, n, ch=HuffEnv.entrynum[c];
do
{
//n=highest node with ch's weight.
//GetHuffGreatestInBlock() returns it.
n=GetHuffGreatestInBlock (ch);
//If not highest node w# same weight
if (n!=ch &&
//or child of such,
HuffEnv.parent[ch]!=n){
//swap nodes && entry values.
//I wrote memswap: it is quick-and-dirty, though.
//(I assume the relationships between the
//nodes are static.)
memswap ((char*)&HuffEnv.Entry[ch],
(char*)&HuffEnv.Entry[n],
sizeof(struct HuffEnv_Entry));
memswap ((char*)&HuffEnv.entrynum[ch], (char*)&HuffEnv.entrynum[n], 4);
}
//Increase weight of current node. (I call it occurences.)
HuffEnv.Entry[n].occur++;
ch=HuffEnv.parent[ch];
//Get parent and loop if top.
} while (ch!=-1);
}
-----------------------

[Harry Potter]

I am sorry for bugging you like this :( but I still have belief in my compression software. I implemented LZ77 and Huffman codes and did them my own way. Even though I have yet to debug the software, it seems to do about as well to a little worse than the ZIP deflate technique. :( I really think that, by adding Adaptive Huffman codes, I can do at least a little better than the deflate technique. I have plans for file compression and want to get them done. This is my own technique, so I am not asking for help to create a *better* compression technique but how a particular technique is done. I would appreciate any help as described.

[James Dow Allen]

On May 4, 8:25 pm, Harry Potter <rose.josep...@yahoo.com> wrote:
> ... I really think that, by adding Adaptive Huffman codes,

> I can do at least a little better than the deflate technique.
> I have plans for file compression and want to get them done.

I've never used adaptive huffman so can't help there.

I will suggest a simple way to bypass all coding and decoding
and estimate what compression you will achieve later, once
coding details are worked out.

I assume that at each point in the coding process you have
some set of possible tokens, each with an
estimated probability p_i. Of course the probabilities
must sum to 1:
p_1 + p_2 + p_3 + ... + p_99 = 1
If it is i, with probability p_i, that is the token
to be encoded, simply add (- log_2 p_i) to a running
estimate of bits-spent-in-the-compressed-file.
This is very easy to do. (It adds a sanity check,
even if your encoder is implemented.)

Sum (- log p) gives the encoding cost for a *perfect*
arithmetic coder. The cost of a *perfect* Huffman
coder will be about 0.03 bits additional per token.
I don't know about adaptive Huffman ...

James

[Harry Potter]

On Sunday, May 5, 2013 3:03:46 AM UTC-4, James Dow Allen wrote:
> I've never used adaptive huffman so can't help there.
>
> I will suggest a simple way to bypass all coding and decoding
> and estimate what compression you will achieve later, once
> coding details are worked out.
>

So I calculate compressibility of the *whole* file first rather than compress it without knowing the "future" of the file? (Sorry about the improper terminology; (I'm limited to a high school education. :( ) I did that with regular Huffman codes and added my own tweaks and it helped to bring my codec to around the deflate technique, but I won't be satisfied until I do *better* than what's out there.

> I assume that at each point in the coding process you have
> some set of possible tokens, each with an
> estimated probability p_i. Of course the probabilities
>

> This is very easy to do. (It adds a sanity check,
> even if your encoder is implemented.)
>

Again, I am limited to a high school education. However, I managed to do this with Huffman codes.

> Sum (- log p) gives the encoding cost for a *perfect*
> arithmetic coder. The cost of a *perfect* Huffman
> coder will be about 0.03 bits additional per token.
> I don't know about adaptive Huffman ...
>

I am going to work on arithmetic coding later. For now, I am developing for 8-bit and 16-bit computers--mainly 8-bit--and am trying to do better than the deflate technique on my own. I will then work my way up to advanced 32-/64-bit codecs.

The problem I'm having with my implementation of adaptive Huffman codes is that, no matter how hard I debug it, I get either 0 bits per byte to compress or an unreasonable number of bits per byte (i.e. 10, 20, +). I will look on wikipedia for Shannon-Fano lossless data compression now, as the deflate technique seems to use it.

[Harry Potter]

On Sunday, May 5, 2013 9:29:05 AM UTC-4, Harry Potter wrote:
> The problem I'm having with my implementation of adaptive Huffman codes is that, no matter how hard I debug it, I get either 0 bits per byte to compress or an unreasonable number of bits per byte (i.e. 10, 20, +). I will look on wikipedia for Shannon-Fano lossless data compression now, as the deflate technique seems to use it.

I just looked. The docs said it was *inferior* to Huffman codes. :( Maybe I'll look at the ZIP specs again.

[Harry Potter]

On Sunday, May 5, 2013 9:36:13 AM UTC-4, Harry Potter wrote:
> I just looked. The docs said it was *inferior* to Huffman codes. :( Maybe I'll look at the ZIP specs again.

I see my problem. Can somebody explain to me how the dynamic Huffman codes in the deflate technique work, or point me to the information online? The Appnote.txt file is unclear about this: the Deflate section points to the Implode section and the Implode section discusses Shannon-Fano codes instead. :(

[Thomas Richter]

http://en.wikipedia.org/wiki/Adaptive_Huffman_coding

and the links and references therein. By why waste your time with that?
Adaptive arithmetic is much simpler than adaptive Huffman, plus
compressed better, minus that it does not solve your problem. The
problem is not finding a better adaptive entropy coding scheme. These
are known. The problem is finding a good data model, i.e. define what
your probabilities actually are.

Greetings,
Thomas

[James Dow Allen]

On May 5, 8:46 pm, Harry Potter <rose.josep...@yahoo.com> wrote:
> ... and the Implode section discusses Shannon-Fano codes instead.  :(

Some may (incorrectly) use "Huffman code" as a generic term to
include Fano codes; perhaps adaptive Fano codes are easier to
implement than adaptive Huffman codes. I don't know the
disadvantage of Fano quantitatively, but it's probably not huge.

But, as Mr. Richter points out, you're making trouble for
yourself by worrying about it. There are two *UNRELATED*
parts of your method:
(1) the model which ultimately yields probability estimates, and
(2) the encoder (whether arithmetic or adaptive Huffman or
adaptive Fano) which converts tokens, with estimated probability,
into bits for the compressed file.
*These two pieces are unrelated to each other.* Since optimal
arithmetic coding *is a solved problem*, you should focus on
(1). I already presented a plan which allows you to ignore
the encoding for your initial experiments.

James

[Harry Potter]

On Sunday, May 5, 2013 10:19:55 AM UTC-4, Thomas Richter wrote:
> http://en.wikipedia.org/wiki/Adaptive_Huffman_coding and the links and references therein.

I already went to that web site and even made a soft and hard copy of some of the information there. The problem is with my implmentation of the technique. I used LZ77 and Huffman codes and did everything I could to make them better, including some tweaks and my own method of doing it. The best I could do is *almost.* I figure that maybe adaptive Huffman codes would help.

> By why waste your time with that? Adaptive arithmetic is much simpler than adaptive Huffman, plus compressed better, minus that it does not solve your problem. The problem is not finding a better adaptive entropy coding scheme. These are known. The problem is finding a good data model, i.e. define what your probabilities actually are. Greetings, Thomas

Yo're right that adaptive aritmetic coding is *better* than adaptive Huffman code. There are two reasons tht I don't use it--yet:

1. The first implementations of the codec are for 8-bit systems, and they can't multiply so easily.
2. I am building my codec in stages, where each stage is better and more coplx than the last.

About the data model, you're right. Thank you for the vocabulary correction. I really want to apply a technique of my own, though, i.e. a signature technique that achieves at least 3% on top of everyhing else. I reason that every bye counts. I applied several such. Some back-fired and the best gave me .6% better on one test file. This is not good enough. However, this is my technique, and as such, I only want help implementing what's already out there.

BTW, is the a probem with the code I posted at th beginning of this thread?

[Harry Potter]

James Dow Allen:
You're right. I *am* making alot of work for myself. I'm doing it for three reasons, though:

1. I want to create a *better* compression technique;
2. I want to work on more stuff with one package and do it better, and
3. I have a Win98 computer with a small FAT32 hard drive needing to be compressed--even though i wld be easier to pay for a hard drive upgrade. :)

If there is an easier way to do #1, I'm all ears.

[Thomas Richter]

Am 05.05.2013 17:28, schrieb Harry Potter:

> Yo're right that adaptive aritmetic coding is *better* than adaptive Huffman code. There are two reasons tht I don't use it--yet:
>
> 1. The first implementations of the codec are for 8-bit systems, and they can't multiply so easily.

But you are aware that there are multiplication-free arithmetic
encoders? Should I say "MQ-Coder" or "QM-Coder"? They are all adaptive,
and require addition, subtraction, comparison and shifts *only*. No
multiplication.

> 2. I am building my codec in stages, where each stage is better and more coplx than the last.
>
> About the data model, you're right. Thank you for the vocabulary correction. I really want to apply a technique of my own, though, i.e. a signature technique that achieves at least 3% on top of everyhing else. I reason that every bye counts. I applied several such. Some back-fired and the best gave me .6% better on one test file. This is not good enough. However, this is my technique, and as such, I only want help implementing what's already out there.
>
> BTW, is the a probem with the code I posted at th beginning of this thread?

Hard to say, as it's no longer on the news server.

Greetings,
Thomas

[Harry Potter]

On Sunday, May 5, 2013 1:50:54 PM UTC-4, Thomas Richter wrote:
> But you are aware that there are multiplication-free arithmetic encoders? Should I say "MQ-Coder" or "QM-Coder"? They are all adaptive, and require addition, subtraction, comparison and shifts *only*. No multiplication.

Can you point me to these techniques?

[Thomas Richter]

Actually, I did this many times, and google finds it, but for your
convenience, here is a C code:

/* snip */

#if 0
gcc-3.4 -o arthdeco -ggdb3 arthdeco.c
exit
#endif

/*
** Simple predictive arithmetic audio coding, (c) 2004 Thomas Richter,
** THOR Software.
** $Id: arthdeco.c,v 1.4 2004/10/10 20:06:33 thor Exp $
**
*/

#include <stdio.h>
#include <string.h>

/*
** context of the arithmetic coder: index into the probability table,
** most probable symbol
*/
struct MQContext {
unsigned char index;
unsigned char mp;
};

/*
** Arithmetic coder structure.
** The MQ coder is patented software, (c) IBM corp.
*/
struct MQCoder {
unsigned long a; /* the inverval */
unsigned long c; /* computation register */
int ct; /* bit counter */
int flag;
unsigned char b; /* b output register */
};

/*
** MQ coder lookup tables
*/
const unsigned short Qe_Value[] = {
0x5601,0x3401,0x1801,0x0ac1,0x0521,0x0221,0x5601,0x5401,0x4801,0x3801,
0x3001,0x2401,0x1c01,0x1601,0x5601,0x54ff,0x5401,0x527d,0x5101,0x4c5f,
0x4801,0x3f80,0x3801,0x35f7,0x3401,0x31f6,0x3001,0x2801,0x2401,0x2201,
0x1c01,0x1801,0x1601,0x1401,0x1201,0x1101,0x0ac1,0x09c1,0x08a1,0x0521,
0x0441,0x02a1,0x0221,0x0141,0x0111,0x0085,0x0049,0x0025,0x0015,0x0009,
0x0005,0x0001,0x5601
};

/*
** MSB/LSB switch flags
*/
const unsigned char Qe_Switch[] = {
1,0,0,0,0,0,1,0,0,0,
0,0,0,0,1,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0
};

/*
** Next state on MPS coding
*/
const unsigned char Qe_NMPS[] = {
1,2,3,4,5,44,7,8,9,10,
11,12,13,35,15,16,17,18,19,20,
21,22,23,24,25,26,27,28,29,30,
31,32,33,34,35,36,37,38,39,40,
41,42,43,44,45,45,47,48,49,50,
51,51,52
};

/*
** Next state on LPS coding
*/
const unsigned char Qe_NLPS[] = {
1,6,9,12,35,39,6,14,14,14,
20,22,25,27,14,14,14,15,16,17,
18,19,20,21,22,23,24,25,26,27,
28,29,30,31,32,33,34,35,36,37,
38,39,40,41,42,43,44,45,46,47,
48,49,52
};


/*
** Open the MQ coder for writing
*/
static void OpenForWrite(struct MQCoder *self)
{
self->a = 0x8000;
self->c = 0;
self->ct = 12;
self->b = 0;
self->flag = 0;
}

static void OpenForRead(struct MQCoder *self)
{
unsigned char t;

self->b = getchar();
self->c = self->b << 16;
t = getchar();
self->ct = 8;
if (self->b == 0xff) {
if (t < 0x90) {
self->c += t << 8;
self->ct--;
}
}
self->c += t << 8;
self->b = t;
self->c <<= 7;
self->ct -= 7;
self->a = 0x8000;
}

static int GetBit(struct MQCoder *self,struct MQContext *ctx)
{
unsigned long q = Qe_Value[ctx->index];
unsigned char t;
int d;

self->a -= q;
if ((self->c >> 16) >= q) {
/* MPS case */
self->c -= q << 16;
if (self->a & 0x8000) {
/* short MPS case, return immediately. */
return ctx->mp;
}
/* MPS exchange here */
d = (self->a < q); /* d == 1 on LPS */
} else {
/* LPS exchange here */
d = (self->a >= q); /* d == 1 on LPS */
self->a = q;
}
if (d) {
/* LPS decoding. Check for MPS/LPS exchange, adjust index */
d ^= ctx->mp;
if (Qe_Switch[ctx->index])
ctx->mp = d;
ctx->index = Qe_NLPS[ctx->index];
} else {
/* MPS decoding */
d = ctx->mp;
ctx->index = Qe_NMPS[ctx->index];
}
/* Now renormalize */
do {
if (self->ct == 0) {
t = getchar();
self->ct = 8;
if (self->b == 0xff) {
if (t < 0x90) {
self->c += t << 8;
self->ct--;
}
}
self->c += t << 8;
self->b = t;
}
self->a <<= 1;
self->c <<= 1;
self->ct--;
} while((self->a & 0x8000) == 0);

return d;
}

/*
** Put out a bit thru the MQ coder.
*/
static void PutBit(struct MQCoder *self,struct MQContext *ctx,int bitf)
{
unsigned long q = Qe_Value[ctx->index];
char bit = (bitf)?1:0;

self->a -= q;
/*
** Check for MPS/LPS coding
*/
if (bit == ctx->mp) {
/*
** MPS coding
*/
if (self->a & 0x8000) {
/* Short MPS case, no renormalization */
self->c += q;
return;
} else {
/* context change */
if (self->a < q) {
/* MPS/LPS exchange case */
self->a = q;
} else {
self->c += q;
}
ctx->index = Qe_NMPS[ctx->index];
}
} else {
/* LPS coding here */
if (self->a < q) {
self->c += q;
} else {
self->a = q;
}
ctx->mp ^= Qe_Switch[ctx->index];
ctx->index = Qe_NLPS[ctx->index];
}
/*
** Renormalize now.
*/
do {
self->a <<= 1;
self->c <<= 1;
if (--self->ct == 0) {
if (self->b < 0xff) {
if (self->c & 0x8000000) {
/* Overflow into the b register, remove
** carry bit and go on */
self->b++;
self->c &= 0x7ffffff;
}
}
if (self->b == 0xff) {
/* We either have an 0xff here, or generated one due to carry.
** in either case, must have buffered something or the overflow
** could not have happened.
*/
putchar(0xff);
self->b = self->c >> 20;
self->c &= 0xfffff;
self->ct = 7;
} else {
if (self->flag)
putchar(self->b);
self->b = self->c >> 19;
self->c &= 0x7ffff;
self->ct = 8;
}
self->flag = 1;
}
} while((self->a & 0x8000) == 0);
}

/*
** Flush out the remaining bits
*/
static void Flush(struct MQCoder *self)
{
int k;
/*
** Number of bits to push out is then in k.
*/
self->c <<= self->ct;
for(k = 12 - self->ct;k > 0;k -= self->ct,self->c <<= self->ct) {
if (self->b < 0xff) {
if (self->c & 0x8000000) {
self->b++;
self->c &= 0x7ffffff;
}
}
if (self->b == 0xff) {
putchar(0xff);
self->b = self->c >> 20;
self->c &= 0xfffff;
self->ct = 7;
} else {
if (self->flag)
putchar(self->b);
self->b = self->c >> 19;
self->c &= 0x7ffff;
self->ct = 8;
}
self->flag = 1;
}
if (self->b < 0xff) {
if (self->c & 0x8000000) {
self->b++;
}
}
if (self->b != 0xff && self->flag)
putchar(self->b);
}

int compress(void)
{
struct MQContext ctxt[256*8];
struct MQContext *cx;
struct MQCoder coder;
int c,code,i;
int last = 0;
int lb = 0;

/* reset all contexts */
memset(&ctxt,0,sizeof(ctxt));
OpenForWrite(&coder);

do {
c = getchar();
if (c == EOF)
break;
code = (c - last) & 0xff;
cx = ctxt + (lb << 3);
lb = code;
code ^= (code >> 1);
for(i = 0;i < 8;i++,cx++) {
PutBit(&coder,cx,code & (1 << i));
}
last = c;
} while(1);

Flush(&coder);

return 0;
}

int decompress(void)
{
unsigned char grey[256];
struct MQContext ctxt[256*8];
struct MQContext *cx;
struct MQCoder coder;
int code,i,last = 0,lb = 0;

/* reset all contexts */
memset(&ctxt,0,sizeof(ctxt));
/*
** Initialize the inverse grey coding table.
*/
for(i = 0;i < 256;i++)
grey[i ^ (i >> 1)] = i;

OpenForRead(&coder);
while(!feof(stdin)) {
cx = ctxt + (lb << 3);
for(i = 0,code = 0;i < 8;i++,cx++) {
if (GetBit(&coder,cx))
code |= (1 << i);
}
code = grey[code];
lb = code;
code += last;
last = code;
putchar(code);
}

return 0;
}

int main(int argc,char **argv)
{

if (argv[1] && !strcmp("-d",argv[1]))
return decompress();
else
return compress();
}

/* snip */

Note that the IBM and Mitsubishi patents on the MQ coder run on a couple
of years ago, thus no problem here anymore.

Greetings,
Thomas

[Harry Potter]

My 8-bit C compiler supports longs, but they're slow on an 8-bit computer. Any way to minimize this?

[Thomas Richter]

Am 06.05.2013 16:25, schrieb Harry Potter:
> My 8-bit C compiler supports longs, but they're slow on an 8-bit computer. Any way to minimize this?

The A register needs to be 16 bits wide, C is 32 bit wide, B is 8 bits
wide, ct needs only four bits, and the flag one. Of course, if coarser
probability estimates work for you, shorter registers would also work
(but compression gets worse, obviously). A good description of the QM
coder (a close relative) is found in the "Pink Book" by Pennebaker and
Mitchell. "JPEG" is the title. But if you google a bit, you'll find
quite some material by Mitchell on how the MQ coder works and why it was
designed this way. I believe IBM research has these.

But again, the art is not the arithmetic coder, but the data modeling.
What you see here is a very simple modeling that works ok for audio
data. But only that. Note that the MQ coder is a binary coder, you need
to binarize the data upfront and assign contexts carefully.

Greetings,
Thomas

[glen herrmannsfeldt]

Thomas Richter <th...@math.tu-berlin.de> wrote:

(snip)

> The A register needs to be 16 bits wide, C is 32 bit wide, B is 8 bits
> wide, ct needs only four bits, and the flag one. Of course, if coarser
> probability estimates work for you, shorter registers would also work
> (but compression gets worse, obviously). A good description of the QM
> coder (a close relative) is found in the "Pink Book" by Pennebaker and
> Mitchell. "JPEG" is the title. But if you google a bit, you'll find
> quite some material by Mitchell on how the MQ coder works and why it was
> designed this way. I believe IBM research has these.

> But again, the art is not the arithmetic coder, but the data modeling.
> What you see here is a very simple modeling that works ok for audio
> data. But only that. Note that the MQ coder is a binary coder, you need
> to binarize the data upfront and assign contexts carefully.

The tables look familiar as being those used in JBIG2. Some years ago
I wrote a JBIG2 coder from the standard documentation. The standard
includes how to generate the context.

I could use Adobe Reader to debug my code by testing its ability to
decode what I wrote. The results of mistakes in the coder can generate
some interesting patterns in the output.

-- glen

[Jim Leonard]

On May 6, 7:41 am, Thomas Richter <t...@math.tu-berlin.de> wrote:
> ** Simple predictive arithmetic audio coding, (c) 2004 Thomas Richter,

Wait, why "audio" coding? The posted routines (thanks, btw) look like
a standard arithmetic coder not related to audio compression...

[Thomas Richter]

The data modeling is. Not the actual AC coding, for that matter, which
is rather standard. It's really a demo of the MQ coder, not a high
performing WAV coder.

So long,
Thomas