Single-Pass Huffman Coding(doisinkidney.com)
doisinkidney.com
Single-Pass Huffman Coding
https://doisinkidney.com/posts/2018-02-17-single-pass-huffman.html
4 comments
> The algorithm isn’t single-pass in the sense of Adaptive Huffman Coding: it still uses the normal Huffman algorithm, but the input is transformed in the same traversal that builds the tree to transform it.
Limited understanding here too. Sounds like it's not really single pass anyway so it's not usable to process a stream in real-time either, before having all the data?
Limited understanding here too. Sounds like it's not really single pass anyway so it's not usable to process a stream in real-time either, before having all the data?
There's no (practical) advantage to the circular implementation; it's just a curiosity.
It is useful for understanding laziness and some interesting theoretical tools for traversing data structures, though. For a more in-depth look at the idea of circular programs for traversal, Bird's paper (linked in the post, https://link.springer.com/article/10.1007/BF00264249) is a good start.
It is useful for understanding laziness and some interesting theoretical tools for traversing data structures, though. For a more in-depth look at the idea of circular programs for traversal, Bird's paper (linked in the post, https://link.springer.com/article/10.1007/BF00264249) is a good start.
It's a weird claim about a single pass too. It's more of a "let's replace some iteration with building a tree of functions to call" and then pretends waking/executing that is not another pass.
Is it faster than the simple one? Does it use less memory? Is it easier to write? Is it easier to understand?
I think all of the above is false, but I have a limited understanding of Haskell. Please correct me if I'm wrong.