patternMinor
What is the meaning of a prefix-free language?
Viewed 0 times
meaningthewhatfreelanguageprefix
Problem
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
Is my thinking correct? or am I missing anything?
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?
Solution
You are correct:
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
taking every word as soon as you see it you're going to read this as
since you can't do anything with the string
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, 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 likeACONNECTICUTYANKEEINKINGARTHURSCOURTtaking 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 COURTCode Snippets
ACONNECTICUTYANKEEINKINGARTHURSCOURTA, CONNECT, I, CUT, YANK, (error)A CONNECTICUT YANKEE IN KING ARTHURS COURTContext
StackExchange Computer Science Q#84777, answer score: 7
Revisions (0)
No revisions yet.