허프만 코드 < 허프만 트리 > (Huffman Codes < Huffman Tree >)
Sample
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
Source Code
main.cpp
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
cpp
#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