3 ms·
> First, we just shorten any symbols that are longer than our maximum code length — 11 — to that value. This means that our tree will no longer be a Huffman tre
by nayuki 5y ago
> First, we just shorten any symbols that are longer than our maximum code length — 11 — to that value. This means that our tree will no longer be a Huffman tree, so we need to do a fixup pass to redistribute the error we've introduced.
This can in fact be solved directly and optimally: https://en.wikipedia.org/wiki/Package-merge_algorithm https://en.wikipedia.org/wiki/Package-merge_algorithm ; https://en.wikipedia.org/wiki/Huffman_coding#Length-limited_Huffman_coding https://en.wikipedia.org/wiki/Huffman_coding#Length-limited_...
- pwrrr 5y agoI've spend hours trying to understand how you apply this theory. The internet is surprisingly absent of actual examples showing how it's done. The best I've found that explains the packag-merge is this page: https://create.stephan-brumme.com/length-limited-prefix-codes/ https://create.stephan-brumme.com/length-limited-prefix-code...