C++ Code to find prefix codes
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;
}
Comments
Post a Comment