Huffman encoding algorithm24Jan07

The first version of Huffman encoding

#include <iostream>

#include <map> // a multimap will be used so we have to include it

using namespace std;

void binary(int number) { //thise procedure is used to convert a

int remainder; //number into a binary number

if(number <= 1) {

cout << number;

return;

}

remainder = number%2;

binary(number >> 1);

cout << remainder;

}

int main()

{

char ch, alphabet[31]; //store each char in ch, 31 chars used because of 26 alphabet, dot, comma, space

typedef multimap<int,char> huffman; //make a multimap that will be sorted by integers, we use a multimap

huffman sentence; //because some characters may have the same number of occurences

int i=0,j=0;

for(int j=0; j<31; j++) //alphabet[0..30] = 0;

alphabet[j]=0;

while((ch=getchar())!=‘\n‘) //insert chars into ch until enter(return) is pressed

{

if(ch==‘ ‘)

alphabet[28]++; //increment number of spaces

else if(ch==‘,’)

alphabet[29]++; //increment number of commas

else if(ch==‘.’)

alphabet[30]++; //increment number of dots

else{

ch = toupper(ch); //convert all chars to upper case

alphabet[(static_cast<int>(ch))-65]++;//increment (char ASCII value) - 65 (this is the index number)

}

}

for(int j=0; j<31; j++)

{

if(alphabet[j]>0) //check if char occured in the text

{

i++; //count the number of found chars, commas, dots, spaces

if(j==28)

sentence.insert(make_pair(alphabet[j],‘ ‘)); //make the pair from space and its occurences

else if(j==29)

sentence.insert(make_pair(alphabet[j],‘,’)); //make the part from comma and its occurences

else if(j==30)

sentence.insert(make_pair(alphabet[j],‘.’)); //make the pair from dot and its occurences

else

sentence.insert(make_pair(alphabet[j],static_cast<char>(65+j))); //make the pair from chars and its occurences

}

}

huffman::iterator pos; //make an iterator for the multimap

for(pos = sentence.begin(); pos!=sentence.end(); ++pos)

{

j++; //number of different chars

cout << “Letter “ << pos->second << ” “; //print out the letter and then its occurence code

binary(i-j); //convert the number to binary

cout << endl;

}

return 0;

}