[Haskell-cafe] Abstraction leak
andrewcoppin at btinternet.com
Sun Jul 1 05:18:16 EDT 2007
Bulat Ziganshin wrote:
> Hello Andrew,
> Saturday, June 30, 2007, 11:48:19 AM, you wrote:
>> Well anyway, speed is not my aim. My aim is to play with various
>> textbook algorithms an examine how well they work for various types of
>> data. As long as the code isn't *absurdly* slow that'll be just fine.
> yes, for studying algorithms Haskell is perfect tool
>> (I forget who it was, but a while back somebody pointed out the wisdom
>> of using Data.Map. It certainly makes the LZW implementation about 400%
>> faster! To say nothing of Huffman...)
> it seems that you've done first implementation with lists or immutable
> arrays? :)
In fact, I *believe* the code is still on the Wiki somewhere...
>> BTW, how do the pros do Huffman coding? Presumably not by traversing
>> trees of pointer-linked nodes to process things 1 bit at a time...
> encoding is simple - make this traversal one time and store bit
> sequence for each symbol. for decoding, you can find length of longest
> symbol MaxBits and build table of 2^MaxBits elements which allows to
> find next symbol by direct lookup with next input MaxBits. faster
> algorithms use two-level lookup, first lookup with 9-10 bits is best
> when your encoded symbols are bytes
I see. So build a table of codes and bitmasks and test against that...
More information about the Haskell-Cafe