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...
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
