//공통 함수 void swap(int *p1, int *p2);
void bubbleSort(int *array, int size); void bubbleUp(int *array, int size);
void selectionSort(int *array, int size); void selection(int *array, int size);
void insertionSort(int *array, int size); void insertion(int *array, int size);
void heapSort(int *array, int size); void reheapDown(int *array, int size, int parent);
void mergeSort(int *array, int size); void merge(int *array, int middle, int size);
void quickSort(int *array, int size); int split(int *array, int size);
전체 글
- 정렬 - Sort.h 2010.09.15
- 해시 - HashMain.c 2010.09.15
- 해시 - Hash.c 2010.09.15
- [소스]호프만 코드를 이용한 압축 및 압축 푸는 프로그램 [출처] [소스]호프만 코드를 이용한 압축 및 압축 푸는 프로그램|작성자 바람향기 2010.09.15
- [강좌] 허프만 알고리즘 2010.09.15
- Huffman coding 2010.09.15
- 이진 탐색 트리 (Binary Search Tree) - 탐색 2010.09.15
- Bit handling #1 2010.09.15
정렬 - Sort.h
해시 - HashMain.c
해시 - Hash.c
Compressed/Decompressed Files Software
사용자로부터 주어진 텍스트 파일을 압축하고 반대로 압축된 파일은 압축을 푸는 프로그램으로 호프만 알고리즘(Huffman Code Algorithm)을 이용하여 호프만 테이블을 작성한다.
작성된 호프만 테이블로 입력된 텍스트 파일을 하나의 버퍼에 저장 후 파일에 출력 파일에 출력할 때 호프만 코드를 같이 출력한다.
파일 압축을 풀 때 하나의 버퍼에 파일의 내용을 저장 후 현재 프로그램의 버전과의 일치 여부와 코드 파일의 내용을 비교하면서 압축을 푼다.
참고로, 파일 압축시 50~75%정도 나온다.
특수문자, Multi Byte Code, 대용량 파일 처리를 하지 않았으니 참고하세요.
// 사용 방법
압축 할때
실행파일명 -e[E] text.txt output.txt
압축 풀때
실행파일명 -d[D] output.txt text.txt
/////////////////// 소스 코드 ////////////////////////////////
//********************************************
Version 1.0, October 2002.
Copyright(C) aroma_guy
Everyone is permitted to copy, modify or distribute this codes.
***********************************************//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define VERSION 1.0
#define MAX_SIZE
256
#define CHARBITS
8
#define MAX_CODE_LENGTH 16
#define MAX_CODE_NUMBER 256
#define MAX_STRING_LENGTH
1024*100 // maximum size of
compressed file is 100 kbyte
#define MAX_BIT_MASK_NUMBER
8
#define RIGHTBITS(n, x) ((x) & ((1U << (n)) -
1U))
typedef struct code_tag
{
int
ascii;
char
code[MAX_CODE_LENGTH];
int
lengthOfCode;
unsigned
frequency;
}
CODE;
int HuffmanCodeTable(CODE
codeTable[]);
void SetCode(CODE codeTable[], int
cnt);
int EncryptString(char original_string[],
int length_Of_Original_string,
CODE codeTable[], int cnt_of_Codes,
char encoded_String[]);
void WriteBitString(char encoded_String[],
int cnt_Of_EncodedBits);
int DecryptBitString(char encoded_String[],
int cnt_Of_EncodeBit,
CODE codeTable[], int cnt_Of_Codes,
char decoded_String[]);
int SearchAlphabet(char key, CODE codeTable[],
int cnt_Of_Codes);
void AttachCode(char encoded_String[], int cnt_Of_Bits,
char code[], int lengthOfCode);
int
SearchCode(char key[], CODE codeTable[], int
cnt_Of_Codes);
void WriteInFile(char encoded_String[],int cnt_Of_EncodedBits,
CODE codeTable[], int
cnt_of_codes);
void
PrnFreq(CODE codeTable[], int cnt_of_codes);
void
Error(char *msg);
void
DownHeap(int i);
void GetTableSizeAndCodeBits(int *size_of_table,
int
*cnt_Of_EncodeBit);
int
GetVersion();
void
GetCodeTable(CODE codeTable[], int cnt_of_codes);
void
GetCode(char encoded_string[]);
void
PrnCodeTable(CODE codeTable[], int cnt_of_codes);
void
WriteDecodedBit(char decoded_String[]);
char
bitMask_OR[MAX_BIT_MASK_NUMBER];
char
bitMask_AND[MAX_BIT_MASK_NUMBER];
int
heap_size, heap[2*MAX_SIZE-1], parent[2*MAX_SIZE-1], left[2*MAX_SIZE-1],
right[2*MAX_SIZE-1];
unsigned long int frequency[2*MAX_SIZE-1];
FILE
*ifp, *ofp;
int
main(int argc, char *argv[])
{
int i, j =
0;
char
Original_String[MAX_STRING_LENGTH];
char
encoded_String[MAX_STRING_LENGTH];
char
decoded_String[MAX_STRING_LENGTH];
int
lengthOfDecodedString;
int cnt_Of_EncodedBits =
0;
CODE codeTable[MAX_CODE_NUMBER];
int cnt_Of_Codes
= 0;
char
option;
if(argc != 4 || ((option = *argv[1]) != 'e'
&& option != 'E'
&& option != 'd' && option != 'D'))
{
printf("Usage : %s [e or E|d or D] input_file
output_file\n", argv[0]);
exit(1);
}
ifp =
fopen(argv[2], "rb");
if(ifp ==
NULL)
{
printf("Cannot open
file : %s", argv[2]);
exit(1);
}
ofp = fopen(argv[3],
"wb");
if(ofp ==
NULL)
{
printf("Cannot open
file : %s", argv[3]);
exit(1);
}
for(i=0; i < 8;
i++)
{
bitMask_OR[i] = 1
<< (7-i);
bitMask_AND[i] =
bitMask_OR[i] ^ 0xff;
}
if(option == 'e' || option
== 'E')
{
while((i =
getc(ifp)) != EOF)
{
Original_String[j++] = i;
if(j >=
MAX_STRING_LENGTH)
Error("Error : larger than
100kbyte!\n");
}
Original_String[j]='\0';
rewind(ifp);
cnt_Of_Codes =
HuffmanCodeTable(codeTable);
cnt_Of_EncodedBits = EncryptString(
Original_String, strlen(Original_String),
codeTable, cnt_Of_Codes,
encoded_String);
WriteInFile(encoded_String, cnt_Of_EncodedBits,
codeTable,
cnt_Of_Codes);
}
else
{
if(GetVersion())
Error("Error : The file isn't equivalent
the current program version!\n");
GetTableSizeAndCodeBits(&cnt_Of_Codes,
&cnt_Of_EncodedBits);
GetCodeTable(codeTable, cnt_Of_Codes);
GetCode(encoded_String);
lengthOfDecodedString = DecryptBitString(
encoded_String, cnt_Of_EncodedBits,
codeTable, cnt_Of_Codes,
decoded_String);
WriteDecodedBit(decoded_String);
}
fclose(ifp);
fclose(ofp);
return
0;
}
int
GetVersion()
{
int i, j =
0;
char
buffer[10];
while((i = getc(ifp)) !=
EOF && j < 3)
{
buffer[j++] =
i;
if(j >=
MAX_STRING_LENGTH)
Error("Error : larger than
100kbyte!\n");
}
if(atof(buffer) ==
VERSION)
return
0;
else
return
-1;
}
/*************************************************************
* 호프만 테이블
사이즈와 비트의 수 얻기
*
*************************************************************/
void
GetTableSizeAndCodeBits(int *size_of_table, int
*cnt_Of_EncodeBit)
{
int ch, i =
0;
char
buffer[10];
while((ch = getc(ifp)) !=
EOF && ch != 0x2F)
buffer[i++] =
ch;
buffer[i] =
'\0';
*size_of_table =
atoi(buffer);
i =
0;
while((ch = getc(ifp)) !=
EOF && ch != 0x20)
buffer[i++] =
ch;
*cnt_Of_EncodeBit =
atoi(buffer);
return;
}
/*************************************************************
* 호프만 코드 테이블을
메모리에 저장
*
*************************************************************/
void
GetCodeTable(CODE codeTable[], int cnt_of_codes)
{
int i = 0, j = 0, tmp,
is_block = 0;
while((tmp = getc(ifp)) != EOF || i < cnt_of_codes)
if(!is_block && tmp != '0' && tmp != '1')
{
codeTable[i].ascii = tmp;
}
else if(tmp == '0'
|| tmp == '1')
{
is_block =
1;
codeTable[i].code[j++] = tmp;
continue;
}
else if(is_block && tmp
!= '0' && tmp != '1')
{
codeTable[i].code[j] = '\0';
is_block = 0, j = 0;
if(cnt_of_codes == ++i)
break;
codeTable[i].ascii = tmp;
}
}
PrnCodeTable(codeTable,
cnt_of_codes);
}
/*************************************************************
* 호프만 코드로 작성된
내용을 버퍼에 저장
*
*************************************************************/
void
GetCode(char encoded_string[])
{
int ch, i =
0;
while((ch = getc(ifp)) !=
EOF)
{
encoded_string[i++]
= ch;
if(i >=
MAX_STRING_LENGTH)
Error("Error
: larger than 100kbyte!\n");
}
encoded_string[i] =
'\0';
}
void
Error(char *msg)
{
printf("%s",
msg);
exit(1);
}
void
PrnFreq(CODE codeTable[], int cnt_of_codes)
{
int i, k = 0, size =
0;
printf("텍스트 분석
중...\n");
printf("---------------------------------\n");
printf("alphabet\tfrequency\n");
printf("---------------------------------\n");
for(i = 0; i <= cnt_of_codes; i++)
{
if((codeTable[i].ascii >= 65 &&
codeTable[i].ascii <= 90) ||
(codeTable[i].ascii >= 97 &&
codeTable[i].ascii <=
122))
{
printf("%c\t\t%d\n", codeTable[i].ascii,
codeTable[i].frequency);
size +=
codeTable[i].frequency;
}
}
printf("---------------------------------\n");
printf("텍스트의 크기 : %d
byte\n", size);
printf("---------------------------------\n\n\n");
}
/*************************************************************
* 버퍼에 저장된 호프만
코드를 사용 빈도수에 맞게 버퍼에 저장
*
*************************************************************/
void
DownHeap(int i)
{
int j,
k;
while ((j = 2 * i) <=
heap_size)
{
if (j < heap_size && frequency[heap[j]] >
frequency[heap[j + 1]])
j++;
if (frequency[k]
<= frequency[heap[j]])
break;
heap[i] =
heap[j];
i =
j;
}
heap[i] =
k;
}
/*************************************************************
* 호프만 알고리즘을
이용한 코드 테이블 작성
*
*************************************************************/
int
HuffmanCodeTable(CODE codeTable[])
{
int i, j, k, avail,
cnt_of_codes;
unsigned long int
incount;
for(i = 0; i < MAX_SIZE;
i++)
frequency[i] = 0;
while ((i =
getc(ifp)) != EOF)
frequency[i]++;
heap[i] =
0;
heap_size = 0;
for(i = 0; i < MAX_SIZE; i++)
{
if(frequency[i] !=
0)
heap[++heap_size] = i;
for(i = 1; i <=
heap_size; i++)
{
codeTable[i-1].ascii
= heap[i];
codeTable[i-1].frequency =
frequency[heap[i]];
}
cnt_of_codes =
heap_size;
PrnFreq(codeTable,
cnt_of_codes);
for(i = heap_size / 2; i
>= 1; i--)
DownHeap(i);
for(i = 0; i < 2 *
MAX_SIZE - 1; i++)
parent[i] =
0;
k =
heap[1];
avail =
MAX_SIZE;
while (heap_size >
1)
{
i =
heap[1];
heap[1] =
heap[heap_size--];
DownHeap(1);
j =
heap[1];
k =
avail++;
frequency[k] =
frequency[i] + frequency[j];
heap[1] =
k;
DownHeap(1);
parent[i] =
k;
parent[j] =
-k;
left[k] =
i;
right[k] =
j;
}
incount =
0;
rewind(ifp);
SetCode(codeTable,
cnt_of_codes);
return
cnt_of_codes;
}
/*************************************************************
* 아스키 코드에 대한
코드 작성
*
*************************************************************/
void
SetCode(CODE codeTable[], int cnt_of_codes)
{
int i, j, k, val =
0;
char
temp[MAX_SIZE];
for(i = 0, j = 0, k = 0; i < cnt_of_codes; i++, j = 0,
k = 0)
{
val =
codeTable[i].ascii;
while ((val = parent[val]) != 0)
{
if (val >
0)
temp[j++] = '0';
else
{
temp[j++] = '1';
val =
-val;
}
while(--j >=
0)
{
codeTable[i].code[k] = temp[j];
k++;
}
codeTable[i].code[k]
= '\0';
codeTable[i].lengthOfCode = strlen(
codeTable[i].code);
}
PrnCodeTable(codeTable,
cnt_of_codes);
}
void
PrnCodeTable(CODE codeTable[], int cnt_of_codes)
{
int
i;
printf("Huffman code 생성
중...\n");
printf("---------------------------------\n");
printf("alphabet\tcode\n");
printf("---------------------------------\n");
for(i = 0; i <
cnt_of_codes; i++)
if((codeTable[i].ascii >= 65 && codeTable[i].ascii <=
90) || (codeTable[i].ascii >= 97 &&
codeTable[i].ascii <= 122))
printf("%c\t\t%s\n", codeTable[i].ascii,
codeTable[i].code);
printf("---------------------------------\n");
}
/*************************************************************
* 호프만 코드로 문자열
압축
*
*************************************************************/
int EncryptString(char original_String[],
int length_Of_Original_String,
CODE codeTable[],
int cnt_Of_Codes,
char encoded_String[])
{
int i, pos, cnt_Of_Bits =
0;
for(i = 0; i <
length_Of_Original_String; i++)
{
pos = SearchAlphabet(original_String[i],
codeTable,
cnt_Of_Codes);
if(pos >=
0)
{
AttachCode(encoded_String, cnt_Of_Bits,
codeTable[pos].code,
codeTable[pos].lengthOfCode);
cnt_Of_Bits +=
codeTable[pos].lengthOfCode;
}
else
{
printf("%c does not exist in code
table!!\n",
original_String[i]);
return
-1;
}
}
return
cnt_Of_Bits;
}
void WriteBitString(char encoded_String[],
int cnt_Of_EncodedBits)
{
int i, pos =
0;
char
a;
for(i=0; i <
cnt_Of_EncodedBits; i++)
{
if(i%8==0)
{
putchar('
');
a =
encoded_String[pos++];
}
putchar(((a &
bitMask_OR[0]) == 0) ? '0' : '1');
a <<=
1;
}
putchar('\n');
}
void
WriteDecodedBit(char decoded_String[])
{
int i, j, length, val, tmp
= 0, diff;
double progress =
0.0;
printf("압축 푸는 중
...\n");
length =
(int)strlen(decoded_String);
for(i =0; i < length;
i++)
{
progress = (double)(i+1) / (double)length *
100.0;
if((int)progress%10 == 0 && (int)progress != 0
&& (int)progress !=
100)
{
if((val =
(int)progress) != tmp)
{
if((diff = (val - tmp) / 10) > 1)
for(j = 1; j < diff; j++)
printf("%d %% 압축
품\n", tmp + j *
10);
printf("%d %% 압축 품\n", val);
tmp =
val;
}
}
else
if((int)progress/10 && (int)progress%10 >
5)
{
if((val =
((int)progress/10)*10) != tmp)
{
if((diff = (val - tmp) / 10) > 1)
for(j = 1; j < diff; j++)
printf("%d %% 압축 품
\n", tmp + j *
10);
printf("%d %% 압축 품\n", val);
tmp =
val;
}
}
else if((val = ((int)progress/10)*10) != tmp &&
(int)progress !=
100)
{
if((diff = (val - tmp) / 10) > 1)
{
for(j
= 1; j < diff; j++)
printf("%d %% 압축 품\n",
tmp + j * 10);
}
printf("%d
%% 압축 품\n", val);
tmp =
val;
}
putc(decoded_String[i], ofp);
}
printf("완료.\n");
}
void WriteInFile(char encoded_String[],
int cnt_Of_EncodedBits,
CODE codeTable[],
int cnt_of_codes)
{
int i, j, ch = 0, incount, outcount, pos = 0, val,
tmp = 0, diff;
double version = VERSION,
progress = 0.0;
char *p,
buffer[MAX_STRING_LENGTH];
printf("압축 중
...\n");
fseek(ifp, 0L,
SEEK_END);
incount =
ftell(ifp);
// write a
version
sprintf(buffer, "%.1f ",
version);
for(i =0; i <
(int)strlen(buffer); i++)
putc(buffer[i],
ofp);
// write a size of the code
tables
sprintf(buffer, "%d",
cnt_of_codes);
for(i =0; i <
(int)strlen(buffer); i++)
putc(buffer[i],
ofp);
sprintf(buffer, "/%d ",
cnt_Of_EncodedBits);
for(i =0; i <
(int)strlen(buffer); i++)
putc(buffer[i],
ofp);
// write contents of the
code tables
for(i = 0; i <
cnt_of_codes; i++)
{
putc(codeTable[i].ascii, ofp);
for(j = 0; j <
codeTable[i].lengthOfCode; j++)
putc(codeTable[i].code[j], ofp);
}
putc(' ',
ofp);
// write contents of
compressed file
p =
encoded_String;
for(i=0; (i < cnt_Of_EncodedBits) && (ch != EOF) &&
(*p != '\0'); i++)
{
progress = (double)i /
(double)cnt_Of_EncodedBits *
100.0;
if((int)progress%10 == 0 && (int)progress != 0
&& (int)progress !=
100)
{
if((val =
(int)progress) != tmp)
{
if((diff = (val - tmp) / 10) > 1)
{
for(j = 1; j < diff; j++)
printf("%d %% 압축\n",
tmp + j * 10);
}
printf("%d %% 압축\n", val);
tmp =
val;
}
}
else
if((int)progress/10 && (int)progress%10 >
5)
{
if((val =
((int)progress/10)*10) != tmp)
{
if((diff = (val - tmp) / 10) > 1)
{
for(j = 1; j < diff; j++)
printf("%d %% 압축\n",
tmp + j * 10);
}
printf("%d %% 압축\n", val);
tmp =
val;
}
}
else if((val = ((int)progress/10)*10) != tmp &&
(int)progress != 100)
{
if((diff = (val - tmp) / 10) > 1)
{
for(j
= 1; j < diff; j++)
printf("%d %% 압축\n",
tmp + j * 10);
}
printf("%d
%% 압축\n", val);
tmp =
val;
}
if(i%8==0)
ch = putc(
p[pos++], ofp );
}
printf("압축
완료.\n");
outcount =
ftell(ofp);
printf("---------------------------------\n");
printf("텍스트 파일 크기 : %u
bytes\n", incount);
printf("압축된 파일 크기 : %u
bytes\n", outcount);
printf("압축 비율 : %.3f(%u/%u - 1)\n",
((double)incount / (double)outcount -
1.0)
, incount,
outcount);
}
/*************************************************************
* 호프만 코드로 문자열
압축 풀기
*
*************************************************************/
int DecryptBitString(char encoded_String[],
int cnt_Of_EncodeBit,
CODE codeTable[],
int cnt_Of_Codes,
char decoded_String[])
{
int i, index, pos=0,
length_Of_DecodedString=0;
char code[MAX_CODE_LENGTH] = {'\0'};
char
a;
for (i = 0; i < cnt_Of_EncodeBit; i++)
{
if(i%8
==0)
a=encoded_String[pos++];
if(a &
bitMask_OR[0])
strcat(code,
"1");
else
strcat(code,
"0");
a <<=
1;
index=SearchCode(code, codeTable,
cnt_Of_Codes);
if(index !=
-1)
{
decoded_String[length_Of_DecodedString]
=
codeTable[index].ascii;
length_Of_DecodedString++;
code[0] =
'\0';
}
}
decoded_String[length_Of_DecodedString] =
'\0';
return
length_Of_DecodedString;
}
/*************************************************************
* 호프만 테이블 내의
주어진 알파벳 문자의 인덱스 찾기
*
*************************************************************/
int
SearchAlphabet(char key, CODE codeTable[], int
cnt_Of_Codes)
{
int i, index =
-1;
for (i = 0; i <cnt_Of_Codes; i++)
{
if(codeTable[i].ascii == key)
{
index=i;
break;
}
}
return
index;
}
/*************************************************************
* 호프만 테이블 내의
주어진 코드의 인덱스 찾기
*
*************************************************************/
int
SearchCode(char key[], CODE codeTable[], int
cnt_Of_Codes)
{
int i,
index=-1;
for (i = 0; i < cnt_Of_Codes; i++)
{
if(strcmp(codeTable[i].code, key) == 0)
{
index=i;
break;
}
}
return
index;
}
/*************************************************************
* 하나의 버퍼에 호프만 코드 저장
*
*************************************************************/
void
AttachCode(char encoded_String[], int cnt_Of_Bits, char
code[],
int
lengthOfCode)
{
int i,
lengthOfEncodedString, lastBitPosition;
lengthOfEncodedString =
cnt_Of_Bits/8;
lastBitPosition =
cnt_Of_Bits%8;
for (i = 0; i <
lengthOfCode; i++)
{
if(code[i]=='1')
encoded_String[lengthOfEncodedString] |=
bitMask_OR[lastBitPosition];
else
encoded_String[lengthOfEncodedString] &=
bitMask_AND[lastBitPosition];
lastBitPosition++;
if(lastBitPosition == 8)
{
lastBitPosition = 0;
lengthOfEncodedString =
lengthOfEncodedString +
1;
}
}
}
[강좌] 허프만 알고리즘
자주 쓰이는 문자에 가장 작은 bit 를 할당하고
한두번 쓰이는 문자에는 큰 bit 를 할당한다라는 것이다.
즉 간단하게 예를 들어서
AABBAC
라는 문자열이 있다고 예를 들어보자.
영문자 하나는 1byte 이므로 총 6byte 의 크기를 가지는 문자열이다.
자 그럼
각 문자들이 사용된 횟수를 알아보자.
머 짧으니까 한눈에 알 수 있을 것이다.
A 는 3번
B 는 2번
C 는 1번 사용되었다.
그러면 가장 많이 사용된 A 에게 0 이라는 1bit 를 부여하고
B 는 10, C 는 11 을 부여할 수 있다.
그러면 위 문자열은
A(0)A(0)B(10)B(10)A(0)C(11)
합쳐보면 001010011 로 나타낼 수 있다.
총 9 bit = 1 byte + 1 bit 으로 압축을 할 수 있다.
원래 문자열이 6 byte 즉 48 bit 를 차지하였는데 9/48 = 0.19
즉 약 20% 로 압축이 되었다. 압축률이 80% 라는 이야기다.
뭐 조금 띄엄띄엄 살펴본것 같지만 허프만 알고리즘의 핵심은 바로 이것이다.
물론 헤더도 붙고 하다보면 조금더 커지겠지만
큰 파일일 수록, 텍스트 기반일 수록, 자주 쓰이는 문자가 많을 수록 압축률은 높아지게 되어 있다.
2. 이진 트리
자 그렇다면 이론은 알겠는데
실제로는 어떻게 적용해야하는 걸까?
순서대로 한번 살펴보자.
대상 문자열 : CDDCACBCBCCCBBCDA
1. 각 문자열별로 빈도수를 검사한다.
2. 빈도수 순서대로 정렬한다. (repeat 1/2)
3. 가장 낮은 두 그룹을 묶어서 하나의 그룹으로 만든다. (repeat 2/2)
4. 빈도수 순서대로 정렬한다. (repeat 1/2)
5. 가장 낮은 두 그룹을 묶어서 하나의 그룹으로 만든다. (repeat 2/2)
6. 빈도수 순서대로 정렬한다. (repeat 1/2)
7. 가장 낮은 두 그룹을 묶어서 하나의 그룹으로 만든다. (repeat 2/2) 트리완성.
8. 이제 트리가 완성되었다.
가장 윗 트리에서부터 빈도수가 큰 트리에 0을 작은 트리에 1을 부여한다.
9. 위 트리를 기준으로 각 문자열의 비트를 참조한다.
부모노드에서 출발하여 문자열에 다다를때까지 비트를 더하여 참조한다. 즉,
A - 001 이 된다.
이와 같은 방법으로
B - 01, C - 1, D - 000 로 비트를 할당 할 수 있게 된다.
그러면 초기 문자열을 할당된 비트로 치환하여 보자.
1000000100110110111101011000001
위와 같이 치환되었다.
총 17문자, 17 byte 였던 원래 문자열이 31 bit 즉, 8 byte 로 압축이 된것이다.
물론 문자열 테이블도 붙고 헤더도 붙으면 약간 더 늘어나겠지만
이번 테스트에서의 압축률은 약 50%로 나타났다.
3. 디코딩은?
호프만 알고리즘을 이용하여 압축을 하면
어떤 문자가 어떤 bit 로 치환되었는지를 판단해야되기 때문에
호프만 테이블이라고 불리는 테이블을 추가해야한다.
호프만 테이블은 방금 우리가 만든 그 이진 트리를 말한다.
그 트리를 보고 복호화하는것이다.
한 bit 단위로 읽어서 테이블대로
문자가 나올때까지 트리를 타고 가면서 치환하는것이다.
예를 들어 00101 이라는 데이타는
AB 를 나타낸다는 것이다.
- 00101 을 복호화해보자
- 첫 비트 0 은 17로 표시되어 있는 트리에서 왼쪽, 즉 9 로 표시되어 있는 트리로 내려간다.
- 다음 0 은 역시 왼쪽, 5 로 표시되어 있는 트리로 내려간다.
- 다음 1 비트는 오른쪽, 즉 2로 표시되어 있는 트리, A 를 나타낸다.
- 문자를 하나 찾았으니 자 그럼 다시 처음부터
- 다음 0 은 17 트리에서 9 트리로
- 다음 1 은 오른쪽 4 트리로, 즉 B 를 나타낸다.
이런식으로 문자열을 치환해주면된다.
대단하지 않은가??
이게 바로 허프만 알고리즘의 원리인것이다.
Huffman coding
이진 탐색 트리 (Binary Search Tree) - 탐색
탐색 연산
- 탐색 알고리즘 (순환의 개념 이용)
> 비교한 결과가 같으면 탐색이 성공적으로 끝난다.
> 비교한 결과가 주어진 키 값이 루트 노드의 키값보다 작으면 탐색은 이 루트 노드의 왼쪽 자식을 기준으로 다시 시작한다.
> 비교한 결과가, 주어진 키 값이 루트 노드의 키값보다 크면 탐색은 이 루트 노드의 오른쪽 자식을 기준으로 다시 시작한다.
- 순환적인 탐색 함수
- 반복적인 탐색 함수