| cr88192 2006-07-19, 3:55 am |
|
"Simon G Best" <s.g.best@btopenworld.com> wrote in message
news:R4ednVWkN-HMWyfZnZ2dnUVZ8tKdnZ2d@bt.com...
> Hello!
>
> I'd like to check something.
>
> From my understanding of arithmetic coding and range coding, they're both
> the same. It's just that arithmetic coding happens to be one
> interpretation of the actual algorithms (and implementations thereof),
> while range coding is another interpretation of what are actually exactly
> the same algorithms (and implementations).
>
<snip>
> But I'd like to check that I really have understood this correctly. So:
> have I understood this correctly?
>
from what I can tell, most likely.
I think it is more that a person implements something, chooses from a range
of possible implementation decisions (symbol or bitstream for input, bit or
bytestream for output, ...), and then decides what they would rather call
it...
taking this a little further, one finds that some of the ideas used in
arithmetic coding also apply indirectly to huffman coding. this was partly
noticed when at one point while attempting to write an optimized
quasi-static arithmetic coder. part of the optimization involved making it a
fixed bitstream so that I could encode/decode via use of masking and shifts
(eliminating any multiplies or divides).
at this point, I realized that in order to generate the symbol mappings, I
needed to use either the huffman or shannon-fano algos (I opted for
shannon-fano in this case, as I could implement it as a recursive function,
absent needing tree balancing or similar).
after all this, I had realized I had figured out how to fairly efficiently
implement a huffman encoder/decoder, and at a later point I ended up using
this as the basis of a (newer) inflater/deflater (I had implemented one
previously, but it was buggy and not very efficient).
and, then, I discovered that I had largely rediscovered the algo used, eg,
in zlib...
actually, it is not the same exactly. zlib had used a funky algo for doing a
transposed increment, wheras I had been using a table to transpose the
value...
or such...
> :-)
>
> Simon G Best
|