Tuesday, February 25, 2014

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
 
(In code 3, the code for B is a prefix of the code for D; the code for C is a prefix of the code for E. In code 4, the code for A is a prefix of the codes for C and D; the code for C is a prefix of the code for D).

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