Codes and the Prefix Property
Any code used for transmitting information must possess what is called the prefix property.If a code has the prefix property, it means that no word in the code is a prefix of any other word in the code: in other words, that no longer code words begin with the identical digits making up any of the shorter code words.
As an example, let's consider a code made of code words of varying length. If 0 is a valid code word, then no other code word can start with 0 if we wish to preserve the prefix property. If 10 is a valid code word, then no other code word can start with 10.
Therefore, a valid five-word "prefix code" containing these two code words might look like one of these codes:
Event | A | B | C | D | E |
Code 1 | 0 | 10 | 110 | 1110 | 1111 |
Code 2 | 1 | 00 | 011 | 0100 | 0101 |
The following codes, on the other hand, would be invalid because the prefix property does not hold:
Event | A | B | C | D | E |
Code 3 | 1 | 00 | 01 | 001 | 011 |
Code 4 | 0 | 10 | 01 | 011 | 100 |
The code below finds whether a given set of codes have prefix property or not.
/* * ---------------------------------------------------------------------------- * "THE BURGER-WARE LICENSE" (Revision 42): * <abybaddi009@gmail.com> wrote this file. As long as you retain this notice you * can do whatever you want with this stuff. If we meet some day, and you think * this stuff is worth it, you can buy me a burger in return. Abhishek Baddi * ---------------------------------------------------------------------------- */ #include<iostream> #include<cstring> using namespace std; void strcpy2(char *d, string s); bool mystrncmp(char const* s1, char const* s2, int n); int main() { cout << "Usage:\nEnter (upto 10 binary numbers): 0 10 110 1110 1111\nOutput: The given code is a prefix code.\n\nEnter (upto 10 binary numbers): 1 00 011 0100 0101\nOutput: The given code isn't a prefix code.\n\n"; string str1; char *num[10]; for(int i=0;i<10;++i) num[i]=new char[10]; cout << "Enter (upto 10 binary numbers): "; getline(cin,str1); int len=str1.size(); char s[len]; strcpy2(s,str1); char *pch = strtok (s," "); int i=0; while (pch != NULL) { strcpy(num[i],pch); pch = strtok (NULL, " "); i++; } len = i; int f=0,j; bool flag = true; for(i=0;i<len;++i) { f=strlen(num[i]); for(j=i+1;j<len;++j) { if(mystrncmp(num[i],num[j],f)) { flag=false; } } } if(flag) cout << "The given code is a prefix code.\n\n"; else cout << "The given code isn't a prefix code.\n\n"; } void strcpy2(char *d, string s) { int len=s.size(),i; for(i=0;i<len;++i) d[i]=s[i]; d[i]='\0'; } bool mystrncmp(char const* s1, char const* s2, int n) { for(int i=0; i < n; ++i){ if(s1[i] != s2[i]) return false; if(s1[i] == '\0' || s2[i] == '\0') break; } return true; }