허프만 코드 < 허프만 트리 > (Huffman Codes < Huffman Tree >)

[Example_1]
[Input – input.txt]
AAXUAXZ // input text string (A ~ Z, 26 characters)
[Output – output.txt]
76.79% // compression ratio (suppose each character takes 8 bits of space)
A(3) 0 // each character(its frequency) and its huffman code
U(1) 110
X(2) 10
Z(1) 111

[Example_2]
[Input – input.txt]
ABBAAAACFDFEEEB
[Output – output.txt]
70.00%
A(5) 11
B(3) 00
C(1) 1010
D(1) 1011
E(3) 01
F(2) 100


main.cpp

#include "item.h"

int main(void)
{

 priority_queue<item> heap; // priority queue..
 queue<item> q; // queue..
 item temp;
 item* x1;
 item* x2;
 int token,original,result;
 double ratio;

 ifstream input;
 ofstream output;

 // read input.txt 문자열 빈도수 체크 후circular queue에 push
 input.open("input.txt");

 for(char s;input.get(s);)
 {
  token = false;
  for(unsigned int i=0;i<q.size();i++)
  {
   temp = q.front();
   q.pop();
   if(temp.s == s) 
   {
    temp.amount++;
    q.push(temp);
    token = true;
    break;
   }
   q.push(temp);
  }
 
  if(!token)
  {
   temp.replace(s,1,NULL,NULL);
   q.push(temp);
  }

 }
 input.close();

 // priority queue! (operator overloading..)
 // 우선순위가 높은 노드가 queue의 top이 됩니다.
 for(unsigned int i=0,s=q.size();i<s;i++)
 {
  heap.push(q.front());
  q.pop();
 }
  
 // create huffman tree from priority queue!!
 token = 1;
 while(heap.size() != 1)
 {
  x1 = new item();
  x2 = new item();

  // priority queue에서 두개의 노드를 pop
  *x1 = heap.top();
  heap.pop();
  *x2 = heap.top();
  heap.pop();
  
  // 두개의 노드를 새로운 노드에 연결
  temp.replace(-1,x1->amount+x2->amount,x1,x2);
  temp.id = token;
  // 새로운 노드를 priority queue에 push
  heap.push(temp);

  token++;
 }
 // now heap.top() is huffman tree's root!!
 // if item::s is less than 0, this object is unused character. 

 // create code (ex: 010, 1101..)
 heap.top().create_code("");

 // write output.txt
 temp = heap.top();
 heap.pop();

 // alphabet sorting
 temp.join_heap(heap);

 // evaluate compression ratio
 while(!heap.empty())
 {
  q.push(heap.top());
  heap.pop();
 }
 
 result = original = 0;

 for(int i=0,s=q.size();i<s;i++)
 {
  original += q.front().amount*8;
  result += q.front().amount*q.front().code.size();
  q.push(q.front());
  q.pop();
 }
 ratio = static_cast<double>(100*(original-result))/original;


 // write output.txt
 output.open("output.txt");

 output.precision(2); // 2 digit
 output.setf(ios::fixed,ios::floatfield);
 cout.precision(2);
 cout.setf(ios::fixed,ios::floatfield);
 // http://www.cplusplus.com/reference/iostream/ios_base/precision/

 output << ratio;
 output << "%" << endl;

 cout << ratio;
 cout << "%" << endl;
 while(!q.empty())
 {
  output << q.front().s << "(" << q.front().amount << ")\t" << q.front().code << endl;
  cout << q.front().s << "(" << q.front().amount << ")\t" << q.front().code << endl;
  q.pop();
 } 

 output.close();

 return 0;
}

Item.h

#ifndef ITEM_H
#define ITEM_H

#include <iostream>
#include <fstream>
#include <queue> 
#include <string>
//#include <sstream>
using namespace std;


class item
{
public:
 int id;
 char s;
 int amount;
 item* left;
 item* right;
 string code;
 
 // constructor!!
 item()
 { 
  id = 0;
  s = NULL;
  amount = 0;
  left=right=NULL; 
 }
 //item(char in,int num) : s(in) , amount(num) {};
 void replace(char in, int num, item* l, item* r)
 {
  s = in;
  amount = num;
  left=l;
  right=r;
 }

 // operator overloading
 item& operator=(const item& rhs) 
 {
  if(this == &rhs)
   return *this;
 
  id = rhs.id;
  s = rhs.s;
  amount = rhs.amount;
  left = rhs.left;
  right = rhs.right;
  code = rhs.code;

  return *this;
 }
 

 // 비교 연산자 오버로딩 <
 bool operator < (const item& target) const
 {
  if(code.empty()) // 코드 부여 전에는
  {
   if(this->id > 0 || target.id > 0) // 문자열이 부여되지 않은 (노드를묶는데사용된) 노드와 비교 할때
    // 빈도수가 같으면 id값이 작은 노드에게 더 큰 우선순위 부여
    //  ㄴ 위 경우는 묶는데 사용된 노드의 id를 먼저 생성된 노드부터 하나씩 증가시키며 부여하기 때문
    // 빈도수가 다르면 빈도수가 작은쪽이 더 큰 우선순생위 부여 
    return ((this->amount == target.amount)? this->id > target.id : this->amount > target.amount);
   else // 둘다 문자열이 있는 노드일때
    // 빈도수가 같으면 char 데이터 값이 작은쪽이 더 큰 우선순위 부여 (알파벳순!)
    // id 비교 하지 않음. 이미 문자열이 없는 노드는 생각하지않음.
    return ((this->amount == target.amount)? this->s > target.s : this->amount > target.amount);
  }
  else // 코드 부여 후에는
  {
   return (this->s > target.s); // 빈도수에 상관없이 알파벳순 (빈도수생각안함)
  }
 }

 // 비교 연산자 오버로딩 > ( 연산자 < 오버로딩 부분과 알고리즘이 같음 )
 bool operator > (const item& target) const
 {
  if(code.empty())
  {
   if(this->id > 0 || target.id > 0)
    return ((this->amount == target.amount)? this->id < target.id : this->amount < target.amount);
   else
    return ((this->amount == target.amount)? this->s < target.s : this->amount < target.amount);
  }
  else
  {
   return (this->s < target.s);
  }
 }


 // huffman code를 부여하는 코드
 void create_code(string parent_code)
 {

  if(parent_code.empty()) // 부모의 huffman code가 비어있을 경우
        //  ㄴ 즉 huffman tree의 최상위 노드일 경우
  {
   if(left) // 왼쪽 노드가 존재하면
   {
    left->code = "0"; // 0을 부여
    left->create_code(left->code); // 재귀함수.. parent_code는 "0"
   }

   if(right) // 오른쪽 노드가 존재하면
   {
    right->code = "1"; // 1을 부여
    right->create_code(right->code); // 재귀함수.. parent_code는 "1"
   }
  }
  else // huffman tree가 최상위 노드가 아닐때!
  {
   if(left) // 왼쪽노드가 존재하면
   {
    left->code = parent_code + "0"; // 부모의 코드에 0을 붙인다
    left->create_code(left->code); // ex) 부모코드:010 -> code:0100
   }

   if(right) // 오른쪽 노드가 존재하면
   {
    right->code = parent_code + "1"; // 부모의 코드에 1을 붙인다
    right->create_code(right->code);
   }
  }

 }

 // huffman tree를 다시 priority queue에 넣는 함수.
 void join_heap(priority_queue<item> &h)
 {
  if(s > 0)
   h.push(*this);
 
  if(left)
   left->join_heap(h);

  if(right)
   right->join_heap(h);
 }

};

#endif