<repo_name>aswinkumar1999/Huffman-Encoder<file_sep>/Makefile
compileRunAndDelete:
	@clear
	@g++ -std=c++11 main.cpp huffman.cpp
	@./a.out ${input} ${output}
	@rm -f ./a.out ./codes.dat
<file_sep>/huffman.h
using namespace std;

typedef struct charWithFreq
{
  //data
  char ch;
  int freq;

  //functions
  charWithFreq();
} charWithFreq;

typedef struct huffmanTreeNode
{
  //data
  charWithFreq data;
	struct huffmanTreeNode *left, *right;

  //functions
  huffmanTreeNode(charWithFreq temp);
} huffmanTreeNode;

typedef struct charWithCode
{
  //data
  char ch;
  string code;

  //functions
  charWithCode(char x = '~', string str = "");
} charWithCode;

//for the priority_queue comparing function.
typedef struct heapCompare
{
  //functions
  bool operator()(huffmanTreeNode* l, huffmanTreeNode* r);
} heapCompare;

//functions
void formHuffmanTree(vector<charWithFreq> contentDistinct);
bool freqOrder(charWithFreq a, charWithFreq b);
vector<charWithFreq> distinctCharactersAndFrequency(string sortedText);
void printCodes(huffmanTreeNode *root, string str);
string getCode(char x, vector<charWithCode> encode);
<file_sep>/README.md
# Huffman Coding

[![MIT license](https://img.shields.io/badge/License-MIT-blue.svg)](LICENSE)
[![Version](https://img.shields.io/badge/Version-1.0.0-orange.svg)](https://github.com/aklsh/huffman-coding)
[![Build status](https://img.shields.io/badge/Build-Passing-green.svg)](Makefile)
[![Downloads](https://img.shields.io/github/downloads/aklsh/huffman-coding/total.svg)](https://github.com/aklsh/huffman-coding/archive/master.zip)

This repository supplements my [blog post on huffman encoding](https://aklsh.me/Huffman-Encoding).

## Requirements
[![Language](https://img.shields.io/badge/Language-C++11-yellowgreen.svg)](https://en.wikipedia.org/wiki/C%2B%2B11)

This project is written in C++11. For user comfort, I have also included a makefile that uses g++ as the compiler. Install `g++` if you want to do an automatic compilation and running of the program.

## Install
* Clone this repository with `git clone https://github.com/aklsh/huffman-coding`
* You can also download this repository by clicking on the big green button near the top of this page.
![clone or download](/images/download.png)

## Usage
I have included a makefile that will automatically do all the compilation and running of the program. You have to only specify the input file and the output file to the program.
```bash
make input="<path of input file>" output="<path of output file>"
```
The files have to be *__TEXT FILES ONLY (.txt)__* .

## Organization of files
`main.cpp` - contains the `main()` for the program.  
`huffman.h` - contains declaration of all classes and functions.  
`huffman.cpp` - contains definitions for all functions (_including member functions of classes_) declared in `huffman.h`.  
`Makefile` - a bash script to automatically compile and run the program.  
`sample inputs/` - folder containing a few sample input text files.  

## Some example Outputs
![example file content](/images/example-content.png)
![example codes](/images/example-codes.png)
![example compressed file](/images/example-encoded-file.png)

## Contributing
![PRs-welcome](https://img.shields.io/badge/PullRequests-Welcome-green.svg)

Please feel free to submit pull requests to this repository!

## License
[MIT © <NAME>](LICENSE)
<file_sep>/main.cpp
#include <bits/stdc++.h>
#include <chrono>
#include "huffman.h"

using namespace std;

int main(int argc, char *argv[])
{
  //timing analysis - Credits: https://www.geeksforgeeks.org/measure-execution-time-with-high-precision-in-c-c/
  auto start = chrono::high_resolution_clock::now();
  ios_base::sync_with_stdio(false);

  //reading from input file
  ifstream textFile(argv[1]);
  string content((istreambuf_iterator<char>(textFile)), (istreambuf_iterator<char>()));
  textFile.close();

  //finding out the distinct characters and their frequency of appearance in file
  string contentSorted = content;
  sort(contentSorted.begin(),contentSorted.end());
  vector<charWithFreq> contentDistinct;
  contentDistinct = distinctCharactersAndFrequency(contentSorted);

  //displaying input file contents
  char userResponse;
  cout << "Do you want to display the input file contents (y/N)? ";
  cin >> userResponse;
  if(userResponse == 'y')
  {
    system("clear");
    cout << "Content in file:" << endl;
    cout << "-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------" << endl;
    cout << content << endl;
    cout << "-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------" << endl;
    cout << endl;
    cout << endl;
    cout << "Press c to continue...";
    //pause func
    do
    {
      for(int i = 0; i < 10; i++);
    }while(cin.get() != 'c');
  }

  //debugging statements
  /*
  cout << "Sorted Content:";
  cout << contentSorted;
  cout << endl;
  cout << "\nDistinct Sorted Content:";
  for(int i = 0;i < contentDistinct.size();i++)
    cout << contentDistinct[i].ch << contentDistinct[i].freq << " ";
  cout << endl;
  */

  //forming and displaying the huffman codes
  system("clear");
  cout << "The huffman codes for the characters in the file are:"  << endl;
  cout << "----------------------------------------------------" << endl;
  formHuffmanTree(contentDistinct);
  cout << "----------------------------------------------------" << endl;

  //checking codes.dat content
  /*
  charWithCode crap;
  ifstream crapFile("codes.dat", ios::binary);
  while(crapFile.read((char*) &crap, sizeof(crap)))
  {
    if(crap.ch != '\n')
      cout << crap.ch << " " << crap.code << endl;
    else
      cout << "\\n" << " " << crap.code << endl;
  }
  crapFile.close();
  */

  cout << endl;
  cout << "The output file has been generated." << endl;
  cout << endl;

  //reading from codes.dat
  vector<charWithCode> encoding;
  charWithCode crap2;
  ifstream crapFile2("codes.dat", ios::binary);
  while(crapFile2.read((char*) &crap2, sizeof(crap2)))
    encoding.push_back(crap2);
  crapFile2.close();

  //writing to compressed file
  ofstream encodeFile(argv[2]);
  for(int i = 0;i < content.size();i++)
    encodeFile << getCode(content[i], encoding);
  encodeFile.close();

  //timing analysis - Credits: https://www.geeksforgeeks.org/measure-execution-time-with-high-precision-in-c-c/
  auto end = chrono::high_resolution_clock::now();
  double timeTaken = chrono::duration_cast<chrono::nanoseconds>(end - start).count();
  timeTaken *= 1e-9;
  cout << "Time taken by program is : " << fixed << timeTaken << setprecision(9);
  cout << " sec" << endl;

  return 0;
}
<file_sep>/huffman.cpp
#include <bits/stdc++.h>
#include "huffman.h"

using namespace std;

charWithFreq::charWithFreq()
{
  ch = '~';
  freq = 0;
}

huffmanTreeNode::huffmanTreeNode(charWithFreq temp)
{

  left = right = NULL;
  this->data.ch = temp.ch;
  this->data.freq = temp.freq;
}

charWithCode::charWithCode(char x, string str)
{
  this->ch = x;
  this->code = str;
}

bool freqOrder(charWithFreq a, charWithFreq b)
{
  return (a.freq > b.freq);
}

bool heapCompare::operator()(huffmanTreeNode* l, huffmanTreeNode* r)
{
  return (l->data.freq > r->data.freq);
}

vector<charWithFreq> distinctCharactersAndFrequency(string sortedText)
{
  //sortedText contains text in sorted manner - for unique() to work
  string sortedTextCopy = sortedText;
  auto ip = unique(sortedTextCopy.begin(), sortedTextCopy.end());
  sortedTextCopy = string(sortedTextCopy.begin(), ip);
  vector<charWithFreq> distinct;
  charWithFreq temp;
  for(int i = 0;i < sortedTextCopy.size();i++)
  {
    temp.ch = sortedTextCopy[i];
    temp.freq = count(sortedText.begin(), sortedText.end(), temp.ch);
    distinct.push_back(temp);
  }
  return distinct;
}

void formHuffmanTree(vector<charWithFreq> contentDistinct)
{
  huffmanTreeNode *left, *right, *temp;
  priority_queue <huffmanTreeNode*, vector<huffmanTreeNode*>, heapCompare> huffmanHeap;
  for(int i = 0;i < contentDistinct.size();++i)
    huffmanHeap.push(new huffmanTreeNode(contentDistinct[i]));
  while(huffmanHeap.size() != 1)
  {
    left = huffmanHeap.top();
    huffmanHeap.pop();
    right = huffmanHeap.top();
    huffmanHeap.pop();

    charWithFreq idk;
    idk.freq = left->data.freq + right->data.freq;
    idk.ch = '~';
    temp = new huffmanTreeNode(idk);
    temp->left = left;
    temp->right = right;
    huffmanHeap.push(temp);
  }
  printCodes(huffmanHeap.top(), "");
}

void printCodes(huffmanTreeNode* root, string str)
{
  ofstream codeFile("codes.dat", ios::binary | ios::out | ios::app);
	if (!root)
		return;

	if (root->data.ch != '~')
  {
    if(root->data.ch != '\n')
    {
      cout << root->data.ch << ": " << str << endl;
      charWithCode temp(root->data.ch, str);
      codeFile.write((char*) &(temp), sizeof(temp));
    }
    else
    {
      cout << "\\n" << ": " << str << endl;
      charWithCode temp('\n', str);
      codeFile.write((char*) &(temp), sizeof(temp));
    }
  }

	printCodes(root->left, str + "0");
	printCodes(root->right, str + "1");
  codeFile.close();
}

string getCode(char x, vector<charWithCode> encode)
{
  for(int i = 0;i < encode.size();i++)
    if(encode[i].ch == x)
      return encode[i].code;
  return "";
}
