[c++] 프로그래밍 실습3

문제

 

생성된 허프만 코드로부터 원래의 문자열을 복원

 

[출력 예]

문자열 입력 : ABRACADABRA

허프만 코드 : 01011001110011110101100

복원된 문자열 : ABRACADABRA

 

 

 

허프만코드란?

- 문자의 출현 빈도수에 따라 가변 길이를 배정. 트리구조를 사용하여 도출. 빈도수가 많은 문자는 적은 길이를 배정받는다.

 

 

 

소스코드

 

#include <iostream> 

using namespace std;

 

class Huffman

{

private:

 int *heap, *infomation;

 int n;

public:

 Huffman(int size=100) {

  heap = new int[size]; 

  infomation = new int[size]; 

  n = 0;

 }

 ~Huffman() { delete heap; }

 void putIn(int v, int x);

 int dele();

 bool isEmpty() { if (n == 0) return true; else return false; }

};

 

void Huffman::putIn(int v, int x)

{

 int i;

 n++;

 for (i = n; ; ) {

  if (i == 1) break;

  if (v >= heap[i/2]) break;

  heap[i] = heap[i/2];

  infomation[i] = infomation[i/2];

  i /= 2;

 }

 heap[i] = v;

 infomation[i] = x;

}

 

int Huffman::dele()

{

 int i, j, x, temp_v, temp_x;

 x = infomation[1];

 temp_v = heap[n];

 temp_x = infomation[n];

 n--;

 i = 1;

 j = 2; 

 while (j <= n) {

  if (j < n && heap[j] > heap[j+1]) j++;

  if (temp_v <= heap[j]) break;

  heap[i] = heap[j];

  infomation[i] = infomation[j];

  i = j;

  j *= 2;

 }

 heap[i] = temp_v;

 infomation[i] = temp_x;

 return x;

}

 

int index(char c)

{

 if (c == 32) return 0;

 else return (c-64);

}

 

int huff_encode(char *text, int *dad, int *huff, int *n)

{

 int count[100], len[27], code[27];

 Huffman hffm(100);

 int i, M, t, t1, t2, k, x, j, l = 0, cnt = 0, max_k; 

 M = strlen(text);

 for (i = 0; i < 100; i++) {

  count[i] = 0;

  dad[i] = 0;

 }

 for (i = 0; i < M; i++) count[index(text[i])]++;

 

 for (i = 0; i <= 26; i++)

  if (count[i]) hffm.putIn(count[i], i);

 for ( ; !hffm.isEmpty(); i++) {

  t1 = hffm.dele(); t2 = hffm.dele();

  dad[i] = 0; dad[t1] = i; dad[t2] = -i;

  count[i] = count[t1] + count[t2];

  if (!hffm.isEmpty()) hffm.putIn(count[i], i);

 }

 max_k = i-1;

 

 for (k = 0; k <= 26; k++) {

  i = 0; x = 0; j = 1;

  if (count[k])

   for (t = dad[k]; t; t = dad[t], j += j, i++)

    if (t < 0) {

     x += j; t = -t;

    }

    code[k] = x; len[k] = i;

 }

 for (j = 0; j < M; j++)

  for (i = len[index(text[j])]; i > 0; i--)

   huff[l++] = code[index(text[j])] >> (i-1) & 1;

 *n = l;

 cout << "Huffman Code : ";

 for (i = 0; i < *n; i++) {

  cout << huff[i];

  if (++cnt % 70 == 0) cout << endl;

 }

 cout << endl;

 

 return max_k;

}

 

void huff_decode(int *dad, int *huff, int max_k, int n)

{

 int temp = max_k; //루트노드 숫자계산 변수

 

 cout<<"dad Array : ";

 for(int i=0; i<max_k; i++)

  cout<<dad[i]<<' ';

 cout<<endl;

 cout<<n<<endl;

 cout<<"max_k : "<<max_k<<endl;

 

 //0이면 양수 1이면 음수 없으면 --

 for(int i=0; i<n;i++)

 {

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

  {

   if(huff[i]==0) //양수를 찾음

   {

    if(dad[j]==temp)

    {

     cout<<(char)(j+64)<<' ';

     temp=max_k;

     break;

    }

   }

   else //음수를 찾음

   {

    if(dad[j]==temp*(-1))

    {

     cout<<(char)(j+64)<<' ';

     temp=max_k;

     break;

    }

    if((j+1)==n)

    {

     temp--;

     break;

    }

   }

  }

 }

}

 

void main()

{

 char text[100];

 int dad[100], huff[500];

 int max_k, n;

 

 cout << "Input : "; //문자열 입력

 cin >> text;

 cout << text << endl;

 max_k = huff_encode(text, dad, huff, &n);

 huff_decode(dad, huff, max_k, n);

}