17
$\begingroup$ 
Char        Code
====        ====
E           0000
i           0001
y           0010
l           0011
k           0100
.           0101
space       011
e           10
r           1100
s           1101
n           1110
a           1111

Original text:

Eerie eyes seen near lake

Encoded:
0000101100000110011100010101101101001111101011111100011001111110100100101

Why is there no need for a separator in the Huffman encoding?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Because when you decode a binary value, you take the "left to right" chunk of bits whichever first matches the value from the original text. Like in this case, you see the leftmost chunk (0000) matches E. If there were any symbol with a value of 000 in your char code, you would replace the 000 with that symbol, and then start to search again from remaining bits in a "left to right" manner. That's why you don't need any separation. $\endgroup$ – Syed Ali Hamza Apr 27 '16 at 20:45
  • 1
    $\begingroup$ The question implies that separators are usually needed. You already know that you don't need separators in Eerie eyes seen near lake (well, except for the space character). But the characters themselves don't need separators. Why isn't that? $\endgroup$ – MSalters Apr 28 '16 at 13:38
  • $\begingroup$ try to decode it yourself, there is never any ambiguity. $\endgroup$ – njzk2 Apr 28 '16 at 20:29
  • $\begingroup$ @MSalters: But separators are usually needed with variable-length words: cat cheat for mice ≠ catch eat form ice.  Your analogy is flawed: each letter is atomic; letters are trivially distinguished and intrinsically separable.  A better analogy would be "Why can you read cursive (handwritten) script, when each word is just one long, squiggling, self-intersecting line?", and even that is a poor analogy, since you can look at a handwritten word (or even a portion of one) and discern the individual letters — whereas a Huffman-encoded string is gibberish if you can't see the beginning. $\endgroup$ – G-Man Apr 28 '16 at 23:29
  • $\begingroup$ @MSalters I don't see yout point. I don't need separators for the characters because we're using a fixed-width encoding: each successive block of eight bits corresponds to one character. But Huffman coding isn't fixed-width, hence the question. $\endgroup$ – David Richerby Apr 29 '16 at 5:53
50
$\begingroup$

You don't need a separator because Huffman codes are prefix-free codes (also, unhelpfully, known as "prefix codes"). This means that no codeword is a prefix of any other codeword. For example, the codeword for "e" in your example is 10, and you can see that no other codewords begin with the digits 10.

This means that you can decode greedily by reading the encoded string from left to right and outputting a character as soon as you've seen a codeword. For example, 0, 00 and 000 don't code anything so you keep reading bits. When you read 0000, that encodes "E" and, because the code is prefix-free, you know there's no other codeword 0000x, so you can now output "E" and start to read the next codeword. Again, 1 doesn't encode anything but 10 encodes "e". No other codewords begins with "10", so you can output "e". And so on.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Prefix codes are also commonly known as Instantaneous Codes (see for example, Elements of Information Theory by Cover & Thomas). I think the term Prefix code comes up far more often than prefix-free code. $\endgroup$ – Batman Apr 28 '16 at 1:45
  • 3
    $\begingroup$ It is also worth mentioning that in order to decode a sequence of concatenated Huffman codes, one must be given the correct codeword boundary to begin with. If one tries to decode the sequence at a wrong codeword boundary, the decoding process will generate a wrong sequence of output symbols. $\endgroup$ – rwong Apr 28 '16 at 6:45
  • $\begingroup$ @rwong: If the Huffman code starts out incorrectly synchronized, it may continue to output wrong symbols indefinitely, but any time it incorrectly determines a symbol's length the number of possible wrong states will be reduced. $\endgroup$ – supercat Apr 28 '16 at 19:00
  • $\begingroup$ @supercat I guess I would phrase it in a different way: If a Huffman decoder is initially set at a wrong codeword boundary and starts processing, there is a possibility (which may be zero or anything, and may depend on both the dictionary and the bit stream content) that it might land on a correct codeword boundary by coincidence in finite time, and when that happens it will produce correct decoding result for subsequent symbols. There has been some research into the properties (on the codeword dictionary, and on the bit stream) that would guarantee this re-synchronization. $\endgroup$ – rwong Apr 29 '16 at 5:48
  • $\begingroup$ @rwong: If the original data was random with a distribution such that the bits of the stream would each have an independent probability of being one or zero, the probability of remaining out of sync for more than N symbols would decay exponentially with increasing N. Actual data is more likely to contain patterns that might prevent resynchronization, but in practice it's unlikely that an error at the start of a 100MB text file would corrupt all 100MB of text. $\endgroup$ – supercat Apr 29 '16 at 14:18
13
$\begingroup$

It's helpful to imagine it as a tree. You are simply traversing the tree until you hit a leaf node, and then restarting from the root. From the algorithm which does huffman coding, you can see that this sort of structure is created in the process.

https://en.wikipedia.org/wiki/File:HuffmanCodeAlg.png

|cite|improve this answer
$\endgroup$
  • 6
    $\begingroup$ The important aspect here is that all the valid code words are leafs. You'd need separators if you had symbols on inner nodes as well. $\endgroup$ – MvG Apr 28 '16 at 11:59
3
$\begingroup$

No code other than E starts with 0000. No code other than i starts with 0001. And so on. As an extreme case, no code other than e starts with 01. You don't have things like E = 0000, space = 000, where you wouldn't know what to do if you find three zeroes.

Look at your encoded string: 0000101100000...

You read the first zero. You know the code is one of E, i, y, l, k, comma, or space. The next zero means it's not k, comma or space, but E, i, y or l. The next zero means it is E or i. The next zero means it's an E. When you know which code it is, you know you have parsed all the bits for that code.

Then you have 101100000... The 1 means you have e, r, s, n or a. The next bit is 0, so the code is e. Again, you're done with that character.

|cite|improve this answer
$\endgroup$
-2
$\begingroup$

We cant use separator in Huffman encoding because every letter's binary equivalent doesn't matches the prefixed code of any letter, so we can do without even using separator.

|cite|improve this answer
$\endgroup$
  • 3
    $\begingroup$ Didn't I already say that, only without the confusing levels of many nested negations. (And, by the way, it's not that we can't use a separator; just that we don't need to.) $\endgroup$ – David Richerby Apr 28 '16 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.