Where are Huffman encoding applications?

Weng Tianxiang wrote:
> Andy,
> No. I want to know the hash function.
> 
> For example, I have a Huffman encoding table as follows:
> 
> name  Fre  encode
> ...
> Andy   15, "011",
> Ray     20, "110",
> ...
> 
> Now a text string "Andy Ray wrote" is incoming, I want to know how to
> match the incoming "Andy" and the table entry "Andy".
> 
> One must establish a 1-to-1 relationship between the incoming word and
> the table entry.
> 
> What I can imagine to do in software is to create a hash function, then
> if there are more entries responding to one entry, further string match
> must be made.
> 
> I am wondering about whether or not a hardware design can does it.
> 


Ok - you're asking about decoding, not encoding.

I don't think there's a hash function for huffman codes, though I'd love 
to be proven wrong.

You can, however, decode huffman codes with a binary search tree encoded 
into a rom/ram.  This works because no code is a prefix of another.  You 
can alter the tree to take more than one input bit at a time at the 
expense of hardware.

A fully parallel hardware solution needs CAM (with don't cares), but 
that's really expensive to implement.

Cheers,

Andy.

Hi Andy,
"Ok - you're asking about decoding, not encoding."

No, It is encoding!

Weng

Weng Tianxiang wrote:
> Your method is interesting, but is far from what I am looking for.
> It is too slow.
> I found that almost all Huffman encoding applications are static as in
> FAX, electronic books, ZIP files, JPEG, MPEG and so on.

You are wrong there. ZIP files and most EBooks use some variant of LZ
encoding using a suffix tree (which might be feasible in hardware),
followed by Huffman coding - static *or* dynamic - on the resultant
symbols. Zip in particular uses the deflate algorithm, which can emit
either static or dynamically-generated Huffman data on each block.
But AFAIK, the Huffman table is *not* updated with each symbol. There
was a kid on sci.crypt a while back banging on about a per-symbol
dynamic Huffman technique he'd invented, perhaps look there.

JPEG and MPEG use a DCT (and optionally in MPEG, motion compensation)
before applying further compression. The DCT is *not* huffman by
another name, its a discrete cosine transform.

Also, look for information on Suffix Trees (used in Lempel-Zif
encoding), and you might find it can be done in a limited way in
hardware. The tree is built incrementally, and looks kinda like
Logan's trie, except that the first symbol of a sequence is at
the leaf, with the last symbol at the root. Kinda...

In general, though Huffman coding was thought to be "optimal" two
decades ago, newer techniques have been shown to be better. For
example, arithmetic coding (needs two passes over the data though),
and the Burrows-Wheeler transform (used in bzip).

There should be enough terms for you to go googling and perhaps find
a more suitable algorithm than Huffman. Don't forget - compression is
simply the process of removing whatever is predictable from a data
stream. The better you understand your data, the better an algorithm
can predict it, and the better your compressor can be.

Good luck!

Clifford Heath.

Hi Cliffor,
I appreciate your response very much and you are an experienced expert
in the field.

I am a newbie in the field and really like to learn more. But I am
determined to learn all those things you have mentioned better.

What books can you suggest for me to buy and read about the fields?

I have a book "Data Compression Book" by Mark Nelson.

I want to learn two arithmatic algorithm too.

Thank you.

Weng



Clifford Heath wrote:
> Weng Tianxiang wrote:
> > Your method is interesting, but is far from what I am looking for.
> > It is too slow.
> > I found that almost all Huffman encoding applications are static as in
> > FAX, electronic books, ZIP files, JPEG, MPEG and so on.
>
> You are wrong there. ZIP files and most EBooks use some variant of LZ
> encoding using a suffix tree (which might be feasible in hardware),
> followed by Huffman coding - static *or* dynamic - on the resultant
> symbols. Zip in particular uses the deflate algorithm, which can emit
> either static or dynamically-generated Huffman data on each block.
> But AFAIK, the Huffman table is *not* updated with each symbol. There
> was a kid on sci.crypt a while back banging on about a per-symbol
> dynamic Huffman technique he'd invented, perhaps look there.
>
> JPEG and MPEG use a DCT (and optionally in MPEG, motion compensation)
> before applying further compression. The DCT is *not* huffman by
> another name, its a discrete cosine transform.
>
> Also, look for information on Suffix Trees (used in Lempel-Zif
> encoding), and you might find it can be done in a limited way in
> hardware. The tree is built incrementally, and looks kinda like
> Logan's trie, except that the first symbol of a sequence is at
> the leaf, with the last symbol at the root. Kinda...
>
> In general, though Huffman coding was thought to be "optimal" two
> decades ago, newer techniques have been shown to be better. For
> example, arithmetic coding (needs two passes over the data though),
> and the Burrows-Wheeler transform (used in bzip).
>
> There should be enough terms for you to go googling and perhaps find
> a more suitable algorithm than Huffman. Don't forget - compression is
> simply the process of removing whatever is predictable from a data
> stream. The better you understand your data, the better an algorithm
> can predict it, and the better your compressor can be.
> 
> Good luck!
> 
> Clifford Heath.

Weng Tianxiang wrote:
> I am a newbie in the field and really like to learn more. But I am
> determined to learn all those things you have mentioned better.
> What books can you suggest for me to buy and read about the fields?

Hmm. Not sure I'd recommend books - they tend to be too theoretical.
If I were you I'd enter some of the search words into wikipedia and
google and read any technical papers you find that look authoritative.
<http://en.wikipedia.org/wiki/Data_compression> is a good start.
Code can also be useful, though often very cryptic - people who write
compressors are often very bad at writing readable code.

What's the source of your data? Are the 64 bits broken into fields,
say 4x16-bit fields? What patterns might you expect? Do the values
tend to cluster around a certain range, or tend to be close to
previous readings? All these things affect the predicability of your
data and so are intimately connected with the compression approach
you must choose.

Weng Tianxiang wrote:
> 
> Your method is interesting, but is far from what I am looking for.
> 
> It is too slow. My target is 64-bit inputs on every clock and one must
> find its entry within 1-2 clocks and resolve entry conflicts if any at
> the same time.
> 
> This design, if succeeded, can be widely used for any dynamic Huffman
> encoding.
> 
> I think there is no such hardware design so far in the world and why I
> found that almost all Huffman encoding applications are static as in
> FAX, electronic books, ZIP files, JPEG, MPEG and so on.

Please do not top-post.  Your reply belongs after, or intermixed
with, the *snipped* material to which you reply.

Huffman encoding is rarely used today.  Adaptive Huffman is more
common.  For a complete review see: "The Compression Book" by Mark
Nelson and Jean-Loup Gailly, M & T Books, ISBN 1-5581-434-1.

-- 
Chuck F (cbfalconer@yahoo.com) (cbfalconer@maineline.net)
   Available for consulting/temporary embedded and systems.
   <http://cbfalconer.home.att.net> USE maineline address!

CBFalconer wrote:
> Weng Tianxiang wrote:
> >
> > Your method is interesting, but is far from what I am looking for.
> >
> > It is too slow. My target is 64-bit inputs on every clock and one must
> > find its entry within 1-2 clocks and resolve entry conflicts if any at
> > the same time.
> >
> > This design, if succeeded, can be widely used for any dynamic Huffman
> > encoding.
> >
> > I think there is no such hardware design so far in the world and why I
> > found that almost all Huffman encoding applications are static as in
> > FAX, electronic books, ZIP files, JPEG, MPEG and so on.
>
> Please do not top-post.  Your reply belongs after, or intermixed
> with, the *snipped* material to which you reply.
>
> Huffman encoding is rarely used today.  Adaptive Huffman is more
> common.  For a complete review see: "The Compression Book" by Mark
> Nelson and Jean-Loup Gailly, M & T Books, ISBN 1-5581-434-1.
>
> --
> Chuck F (cbfalconer@yahoo.com) (cbfalconer@maineline.net)
>    Available for consulting/temporary embedded and systems.
>    <http://cbfalconer.home.att.net> USE maineline address!

Hi Chuck,
Thank you for your advice.

I have bought the book "The Compression Book". 

Weng