Fast decoders for variable-length codes

Thread View: comp.compression.research

3 messages

[T] Back to Threads [V] Tree View [G] Group Articles

3 total messages Started by Ove Edfors Fri, 02 Oct 1992 20:24

#86

Author: Ove Edfors
Date: Fri, 02 Oct 1992 20:24

15 lines
1228 bytes

  Is there anyone out there, who have information on fast decoders for
variable-length codes, e.g. Huffman codes. I'm currently taking a closer
look at fast decoding, and I would be very grateful for any information
on the subject.
  Pointers to books, reports and articles on the subject are of particular
interest.

--------------------------------------------------------------------
Ove Edfors                          PHONE:    Int. +46 920 910 65
Div. of Signal Processing                     Dom.  0920 - 910 65
University of Lulea                 FAX:      Int. +46 920 720 43
S-951 87  LULEA                               Dom.  0920 - 720 43
SWEDEN                              E-MAIL:   edf@sm.luth.se
--------------------------------------------------------------------

Re: Fast decoders for variable-length codes

#87

Author: "D. Hugh Redelmeier"
Date: Sat, 03 Oct 1992 03:10

22 lines
1319 bytes

edf@sm.luth.se (Ove Edfors) writes:
|  Is there anyone out there, who have information on fast decoders for
| variable-length codes, e.g. Huffman codes.

My program "huf" quickly decodes Huffman codes.  It can be ftped from
ftp.cs.toronto.edu:/pub/hugh/huf*.

It uses a static code table, i.e. the code is the same for an entire
file.  This allows the decoder to "leap" into the code tree based on
the first n bits by using an auxilliary table with 2^n entries.

One reason that this is effective is that huf uses words as symbols,
not ASCII characters.  Thus each symbol is represented by a larger
string of bits.

I haven't thought hard about whether this technique would work well
with an adaptive Huffman program.

Hugh Redelmeier
hugh@mimosa.com or {utcsri, yunexus, utzoo, scocan}!redvax!hugh
When all else fails: hugh@csri.toronto.edu
+1 416 482-8253

Re: Fast decoders for variable-length codes

#89

Author: Nico E de Vries
Date: Mon, 05 Oct 1992 13:37

19 lines
1275 bytes

In <1309@my.sm.luth.se> edf@sm.luth.se (Ove Edfors) writes:

>  Is there anyone out there, who have information on fast decoders for
>variable-length codes, e.g. Huffman codes. I'm currently taking a closer
>look at fast decoding, and I would be very grateful for any information
>on the subject.
>  Pointers to books, reports and articles on the subject are of particular
>interest.

The common way is a lookup table. Always "snoop" X bits from the compressed
stream and use a table lookup to find out the value and the actual
length. Many sources (e.g. INFO-Zip UNZIP) us table lookup for Huffman
decompression.

Nico E. de Vries
 _ _
 O O  USENET nevries@cc.ruu.nl This text reflects MY opinions, nothing else.
  o   This text is supplied 'AS IS', no waranties of any kind apply.
 \_/  Don't waste your time on complaining about my hopeless typostyle.

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads