[Haskell-cafe] Abstraction leak

[Andrew Coppin]

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? :)
>   

Lists.

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...