alt Hacker NewsNot sure if this counts, but I learned Huffman coding the intuitive tree-based way. From memory it was O(nlogn), but you can just O(n) it in-place in an array.
Not sure if this counts, but I learned Huffman coding the intuitive tree-based way. From memory it was O(nlogn), but you can just O(n) it in-place in an array.
Huffman decoding you mean. All the fast decoders build tables processing N (8, 16, ...) bits at a time. If the next byte is 253 in state 6 that means output 15,28,28 and go to state 42...
There are probably even faster ways I don't know of.