3
$\begingroup$

Tried a bunch of resources to read about it, still don't really get it.

This is what Wikipedia says

A prefix code is a type of code system (typically a variable-length code) distinguished by its possession of the "prefix property", which requires that there is no whole code word in the system that is a prefix (initial segment) of any other code word in the system.

This is my understanding so far: I have a language L that has all these words L = {"a", "b"}. From my understanding, right now my language L is prefix free, but if I add a new word to it like "ac", so that my language becomes L = {"a", "b", "ac"}, its not prefix-free anymore?

Is my thinking correct? or am I missing anything?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Your example is correct. Paraphrasing your wiki quote, in order to be a prefix code, no "whole" code word can be the prefix (e.g. beginning) of any other code word. So {"aa", "ab", "ac"} would be a valid prefix code even though they all begin with "a". But we cannot add the code "a" to our system and maintain the prefix property. $\endgroup$
    – Justin Heath
    Dec 1, 2017 at 18:34

1 Answer 1

Reset to default
7
$\begingroup$

You are correct: {a, b} is prefix-free, but {a, b, ac} is not.

The idea of a prefix-free code is that once you recognize a word you know for sure it's a word. So for instance a code that includes both CONNECT and CONNECTICUT is not prefix-free, because if you start parsing a phrase like

ACONNECTICUTYANKEEINKINGARTHURSCOURT

taking every word as soon as you see it you're going to read this as

A, CONNECT, I, CUT, YANK, (error)

since you can't do anything with the string EEINKINGARTHURSCOURT. (That's assuming you don't also consider CON a word also; if so, things would be even worse.)

Note that adding spaces between words is basically a way of making a code prefix-free: if "connect" by itself isn't considered a word, but "connect " is, then you'll have no trouble parsing

A CONNECTICUT YANKEE IN KING ARTHURS COURT
Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Note that while the ungreedy algorithm (choose the first word you come across) will never recognize CONNECTICUT, it does resynchronise. YANKEE is actually the problem here. Otoh, the maximum munch (greedy, so to speak) algo will get this one right, but would fail on THEMAINEXAMPLE. All of those could be solved with backtracking, but MAINEVENT has two solutions, so it is strictly ambiguous. $\endgroup$
    – rici
    Dec 2, 2017 at 18:58
  • $\begingroup$ "YANKEE is actually the problem here." I would argue that "successfully" parsing something incorrectly is actually much worse than failing to parse it. $\endgroup$
    – Daniel McLaury
    Apr 27, 2022 at 5:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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