Edge case fail in all Huffman Encoding implementations.

[Trashtalk217]

Whenever any (or most) of the Huffman Encoding implementations receive a string with only one character multiple times (think 'aaaaaaaaaaaaa', or 'bbbb'). The functions fail and give either errors, or weird empty output. Here are some examples of Python, Java and Lua respectively. I assume this has to be fixed because it nowhere states in the chapter that it shouldn't work on one-character-strings.

[c252]

These are the ones so far that we know are broken (I or another maintainer have personally tested them)

• C
• C++
• C#
• Go
• Java
• Javascript
• Julia
• Lua
• Python
• Rust

and those that are untested

• x86-64 Assembly
• Clojure
• Haskell
• Scala

[berquist]

Here is a first stab at fixing the Python implementation:

diff --git a/contents/huffman_encoding/code/python/huffman.py b/contents/huffman_encoding/code/python/huffman.py
index 1e1cc54..75700cd 100644
--- a/contents/huffman_encoding/code/python/huffman.py
+++ b/contents/huffman_encoding/code/python/huffman.py
@@ -11,6 +11,9 @@ def build_huffman_tree(message):
     frequencies = Counter(message)
     trees = frequencies.most_common()
 
+    if len(trees) == 1:
+        return [trees[0][0]]
+
     # while there is more than one tree
     while len(trees) > 1:
 
@@ -37,6 +40,9 @@ def build_codebook(tree, code=''):
 
     codebook = []
 
+    if len(tree) == 1:
+        return [(tree[0], '0')]
+
     # split the tree
     left_tree, right_tree = tree
 

I figure it's ok to not handle the case where the input is empty. Or should that be handled?

[leios]

Right, this should catch it. I'm wondering it. I'll fix the ones I can soon!

[Kroppeb]

https://stackoverflow.com/questions/22429854/huffman-code-for-a-single-character

[Kroppeb]

I don't like the solution of using 1 bit to encode the solution. Mostly cause it makes the Kotlin implementation more complex than I feel it needs to be.

[rishvic]

I think that, for the edge case, the empty string isn't suitable, since it doesn't give us the full description of the text. And, I also think that representing the only character with a 1 or a 0 is wasteful, since we are not using the other character at our disposal. So, I think the best way to go about with this is, if there is only one character in the text, the Huffman code becomes the binary representation of the number of occurrences of the single character in the given text (I think for simplicity, the representation should be in little endian order). Then, while decoding, if we see the code-book has only one entry (only one root node containing the character), we simply take the encoded text as the number of the occurrences of the character in the code-book. Although, this increases the complexity of the encoding & decoding functions, this method ensures,

1. A complete description of the text
2. The most efficient of the given text using only 1s and 0s

[thecnoNSMB]

The way I see it, while making an encoding edge case where the codebook indicates "this string has only the letter A" and the bitstring instead encodes the amount of characters would be the optimal thing to do, the algorithmically correct implementation would be instead for the codebook to say "the character A corresponds to a 0" and then the bitstring has as many zeroes as the original string has A's, as that would be internally consistent with how this algorithm handles all other cases.

[Kroppeb]

The way I see it, while making an encoding edge case where the codebook indicates "this string has only the letter A" and the bitstring instead encodes the amount of characters would be the optimal thing to do, the algorithmically correct implementation would be instead for the codebook to say "the character A corresponds to a 0" and then the bitstring has as many zeroes as the original string has A's, as that would be internally consistent with how this algorithm handles all other cases.

That's actually not correct. Most implementations (eg DEFLATE) don't have a marker for the end of the bitstring, and instead, store the length of the uncompressed data. Because we are storing the bits into a string we had an implicit end marker (end of the string). IMHO the correct encoding result is the empty string, but the decode function should somehow be told what the target length is. This can be done by example by making the encoder return an Encoded object that stores the length and bits.

[thecnoNSMB]

Yes, because those implementations operate down at the metal, where there needs to be some way to determine when to stop reading and interpreting bits, and as such either encode the length upfront or include an "end of string" token just like any other kind of string. For the version of the algorithm being discussed in this book, those extra details can and maybe should be mentioned in the chapter text, but I don't think this kind of handling should be done in the actual code just because it's often done elsewhere, since these implementations are meant to be illustrative of the main principle at work without any optimizations. Since the text does mention that the algorithm "guarantees the smallest possible bit length", that may be a good reason to implement this kind of optimization, though I am unconvinced, since any means to actually achieve that in our example implementations will involve either encoding the length or encoding the "end of string" token, both of which involve very low-level concepts that distract from the point of the chapter and may confuse a reader.

For the simplified version of the algorithm that is actually described in the chapter, the correct behavior would be:

• An empty string should be encoded with an empty codebook and an empty bytestring,
• a should be encoded with a codebook indicating that "a" is 0 (for example) and the bytestring should be 0,
• and aaaaa should be encoded with the same codebook and the bytestring should be 00000.

[Kroppeb]

For the simplified version of the algorithm that is actually described in the chapter, the correct behavior would be:

• An empty string should be encoded with an empty codebook and an empty bytestring,
• a should be encoded with a codebook indicating that "a" is 0 (for example) and the bytestring should be 0,
• and aaaaa should be encoded with the same codebook and the bytestring should be 00000.

That's incorrect, the algorithm as described would encode "aaaaaa" as the empty string. Honestly, I would just explicitly disallow those strings in the implementation.

[thecnoNSMB]

That's incorrect, the algorithm as described would encode "aaaaaa" as the empty string. Honestly, I would just explicitly disallow those strings in the implementation.

Then the algorithm as described has a bug in it, and we should figure out whether to just disallow all strings that would cause that bug or to fix it and if so how.

[thecnoNSMB]

In any case, I sent Leios the original paper the algorithm originated in to read, so we'll see if there are any answers to this there.