Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to understand the definition of "Prefix free", but I do not understand the definition nor the example that wikipedia provides. I was hoping for clarification. Below is an excerpt from wikipedia (http://en.wikipedia.org/wiki/Prefix_code):

"A prefix code is a type of code system (typically a variable-length code) distinguished by its possession of the "prefix property"; which states that there is no valid code word in the system that is a prefix (start) of any other valid code word in the set. For example, a code with code words {9, 59, 55} has the prefix property; a code consisting of {9, 5, 59, 55} does not, because "5" is a prefix of both "59" and "55". With a prefix code, a receiver can identify each word without requiring a special marker between words."

I do not understand the prefix property, nor do I understand why the first set satisfies the prefix property and the second fails it, since both sets have "59" and "55" as elements in the set.

Could someone explain the prefix property, explain the example I am confused about and provide another example?

share|improve this question
    
Yes, but $5$ is not a member of the first set, so there is no risk of confusion there. –  Zhen Lin Aug 9 '11 at 0:37
4  
The prefix property is a property of an entire set of code words. The first set satisfies it because $9$ is not a prefix of either $59$ or $55$, and the second doesn't because $5$ is a prefix of both $59$ and $55$. –  Qiaochu Yuan Aug 9 '11 at 0:43
1  
Would this be an example of a set that does not satisfy the prefix free property {5,7,77,89}? Would this be an example of a set that does satisfy the prefix free property {5,7,67, 89}? If so, then I believe I understand the definition and example now. –  Quaternary Aug 9 '11 at 0:48
1  
Yes on both counts. –  Qiaochu Yuan Aug 9 '11 at 0:57
    
Cool, thanks guys for the clarification! –  Quaternary Aug 9 '11 at 0:58
add comment

1 Answer 1

up vote 5 down vote accepted

Suppose we have a simple code consisting of the three words cat, catapult, and camel.

This set of codewords is not prefix-free, because a (whole) codeword, namely cat, is also a prefix of another codeword.

Here is a (fake) illustration of the problem this can cause. Suppose that cat encodes "run like h***", catapult encodes "having a good time", and "catenary" encodes "when's dinner?".

Imagine now that codewords come in kind of slowly, letter by letter. If you get the letters $$\text{c$\qquad$ a$\qquad$ t}$$ you don't know what to do, this might be the complete message, so you better stop staring at the computer screen and get out of there fast, or maybe it is the beginning of another codeword, and you better wait.

Suppose by contrast that the only codewords are catch, catapult, catenary, and catamount. This collection of codewords is prefix-free, since no (whole) codeword is the beginning part of another codeword. If $$\text{c$\qquad$ a$\qquad$ t} \qquad\qquad \text{or even} \qquad\qquad \text{c$\qquad$ a$\qquad$ t$\qquad$a}$$ comes in, you know you have to wait in order to get the message.

At a more programming level, suppose that letters come in in a steady stream, not separated into codewords. You want to be able to separate this stream of letters into codewords "on the fly."

If both cat and catapult are codewords, if you see cat you can't make the decision until you see the next letter. That's why the first example is not prefix-free.

In the second example, there is no problem, if you see cat, you know it is not in the codeword list, so you wait for the rest.

Comment: There are some good reasons to use variable-length codes. For example, suppose that our messages overwhelmingly consist of numerical information, with very brief pieces of text. Then it can increase throughput a lot to encode digits as very short bit strings, and letters of the alphabet as longer bit strings.

In a language meant to be interpreted by a computer, it is often convenient to have the prefix-free property, because it can mean that we can use a simpler parser. A parser that has to do a fair amount of "looking ahead" in order to interpret a string decreases efficiency.

share|improve this answer
    
Excellent response. –  Quaternary Aug 10 '11 at 4:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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