# Question about the definition of “Prefix free”

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?

-
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
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
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
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

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\qquada}$$ 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.

-
Excellent response. –  Quaternary Aug 10 '11 at 4:08

An example of a non-prefix-free set of codewords for which the boundary between words can't be determined is the set $\{\text{cat}, \text{catsup}, \text{supply}, \text{ply}\}$. If we get the message $\text{catsupply}$ we can't tell if it means $\text{cat supply}$ or $\text{catsup ply}$.

The issues with André Nicolas's examples are caused by the set of some messages formed by concatenating codewords not being prefix-free, which is different than whether or not the set of codewords itself is. It is possible for either property to hold without the other, or both, or neither, depending on which concatenations of codewords are considered to be valid messages. For example, we could add a codeword $\text{endoftransmission}$ and require that every message end with it, and with that definition of "message" the set of messages constructed from the codewords $\{\text{cat},\text{catapult},\text{endoftransmission}\}$ is prefix-free even though the set of codewords itself is not. Alternatively, the set of codewords $\{\text{a}, \text{b}\}$ is prefix-free, but we need some restrictions on what constitutes a message for the set of messages to be prefix-free, because $\text{aa}$ and $\text{a}$ cannot both be messages.

-