Re: Huffman decoding table or the "codebook"


<jarhe@xxxxxxxxx> wrote in message
news:1156239000.072628.249600@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Hi,

I am doing experiments with Huffman coding. I know the principles of
how the coding and decoding work. The thing that I'm not sure about is
what the decoding table, or should it be denoted as the codebook,
should contain so that I could use the codeword to obtain the original
symbol? I suspect the codebook has to contain something more than just
the original symbols.

I used google-search engine to look for help on this issue, but it
seemed that all the pages that I found only described the decoding
procedure, i.e., how to obtain the codeword from the incoming bit
stream. I did not find any information about what the codebook should
contain. I know that there are several optimizations possible to
optimize the size of the codebook, but what I am interested is the
contents of the codebook in the most simplest case.


my case:
I used a few arrays with each element in the same location as the
appropriate coded symbol.

one array will contain the huffman code for the symbol;
the other will contain the symbol length.

a simple implementation for decoding is to scan along the table until a
matching code is found, and returning the current position in the array (the
symbol in question).

an optimization (as implemented in my coder) was to also build a linked list
for the symbols. this required a 3rd array, holding the value of the next
symbol.

then, another table was made which would use some of the high-order bits of
the code as an index into the array (the first symbol with the same
high-order bits).

in the case of shorter codes, this would only take a single step, but for
longer codes this wasn't quite as fast.


other ways are possible, but my approach works imo.


Cheers,
Jari



.

Relevant Pages

  • Huffman decoding table or the "codebook"
    ... I am doing experiments with Huffman coding. ... how the coding and decoding work. ... I suspect the codebook has to contain something more than just ... the original symbols. ...
    (comp.compression)
  • Re: [PHP] Array and Object
    ... Well anyways please let me handle the problems with decoding. ... => SimpleXMLElement Object ... back the same array structure. ... decoding UTF-8 to Latin1 ...
    (php.general)
  • Re: Melp1200 data memory
    ... This array was calculated by training codebooks during the MELPe vocoder ... But while you are focusing on the codebook, you may be creating a much ... Even if you intend to commercialize its derivative on ADSP-2188, ...
    (comp.dsp)
  • Re: Melp1200 data memory
    ... This array was calculated by training codebooks during the MELPe vocoder ... But while you are focusing on the codebook, you may be creating a much greater issue... ... The maximum segment which I ...
    (comp.dsp)
  • Re: Compressing a String?
    ... > Try to use a named charset when converting string to a byte array. ... > Try to use same charset decoding the array back to java unicode string. ...
    (comp.lang.java.programmer)