Huffman Coding
ํํ๋ง ๋ถํธํ(Huffman coding)๋ ๋ฌด์์ค ์์ถ์ ์ฐ์ด๋ ์ํธ๋กํผ ๋ถํธํ์ ์ผ์ข ์ผ๋ก, ๋ฐ์ดํฐ ๋ฌธ์์ ๋ฑ์ฅ ๋น๋์ ๋ฐ๋ผ์ ๋ค๋ฅธ ๊ธธ์ด์ ๋ถํธ๋ฅผ ์ฌ์ฉํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
์์ถ์ด๋ ์์ฒญ๋๊ฒ ํฐ ๋ฌธ์ (๋ง์ ๋นํธ๋ฅผ ํ์๋ก ํ๋)์ ์ ๋ณด๋ฅผ ๊ณ ์ค๋ํ ํํํ๋ฉด์๋ ์ ์ฒด ๋นํธ๋์ ์ค์ผ ์ ์๋ ํจ๊ณผ์ ์ธ ๋ถํธํ ๊ธฐ์ ์ ๊ณผ์ ์ด๋ค.
๋ฌด์์ค ์์ถ์ ๋ฐ์ดํฐ ์์ถ์ ์ผ์ข ์ผ๋ก ์์ค ์์ถ์ ๋ฐ๋๋ง์ด๋ค. ์๋์ ์ ๋ณด๋ฅผ ๊ทธ๋๋ก ๋ณด์กดํด์ผ ํ๊ธฐ ๋๋ฌธ์, ์ ๋ณด ์ํธ๋กํผ์ ํ๊ณ๊ฐ ๊ทธ๋๋ก ๋ฐ์๋๋ค. ์ฌ๊ธฐ์์ ์ ๋ณด ์ํธ๋กํผ์ ํ๊ณ๋ ๊ฐ๋ณ ์ ๋ณด์ ํ๋ฅ ๊ฐ์ ์ํ์ฌ ๊ณ์ฐ๋๋ ๊ฐ์ด ์๋, ์ ์ฒด ์ ํธ์ ์๊ด๊ด๊ณ๋ฅผ ๋ฐ์ํ ํ๊ณ๊ฐ์ด๋ค.
์ํธ๋กํผ ์ธ์ฝ๋ฉ or ์ํธ๋กํผ ๋ถํธํ(entropy encoding) : ์ฌ๋ณผ์ด ๋์ฌ ํ๋ฅ ์ ๋ฐ๋ผ ์ฌ๋ณผ์ ๋ํ๋ด๋ ์ฝ๋์ ๊ธธ์ด๋ฅผ ๋ฌ๋ฆฌํ๋ ๋ถํธํ ๋ฐฉ๋ฒ
์ํธ๋กํผ๋ ๊ฐ ๊ธฐํธ๊ฐ ํฌํจํ๋ ํ๊ท ์ ๋ณด๋์ ์๋ฏธ
Shannon ๋ถํธํ ์ด๋ก ์์๋ ์ํธ๋กํผ๋ฅผ ์ฐ๋ฆฌ๊ฐ ํ ์ ์๋ ์ต์ ์ด๋ผ ๋งํ๋ค.
์์ฃผ ๋ฐ์ํ๋ ๊ธฐํธ๋ฅผ ์ฐพ์๋ด๋ ๋ฐ ๋ชฉ์ ์ด์๋ค.
๊ฐ๋ณ ๊ธธ์ด ๋ถํธํ(VLC) : ๋ ์์ฃผ ๋ฐ์ํ๋ ๊ธฐํธ๋ ๋ ์ ์ ๋นํธ๋ก ๋ถํธํ
์ฆ, ์์ฃผ ๋ฐ์ํ๋ ๊ธฐํธ๋ ๋นจ๋ฆฌ ์ ์ก๋ ์ ์๋ ์ฝ๋(์ ์ ๋นํธ), ์์ฃผ ๋ฐ์ํ์ง ์๋ ๊ฒ์ ๊ธด ์ฝ๋๊ฐ ๋ถ์ฌ๋๋ค.
ํํ๋ง ์๊ณ ๋ฆฌ์ฆ์ ๋ถํธํ ์์๋ ์๋์์ ์๋ก ์งํํ๋ ๋ฐฉ๋ฒ์ด๋ค.
์๊ณ ๋ฆฌ์ฆ

์ด๊ธฐํ : ๋ชจ๋ ๊ธฐํธ๋ฅผ ์ถํ ๋น๋์์ ๋ฐ๋ผ ๋์ดํ๋ค.
๋จ ํ ๊ฐ์ง ๊ธฐํธ๊ฐ ๋จ์ ๋๊น์ง ์๋ ๋จ๊ณ๋ฅผ ๋ฐ๋ณตํ๋ค.
๋ชฉ๋ก์ผ๋ก๋ถํฐ ๊ฐ์ฅ ๋น๋๊ฐ ๋ฎ์ ๊ฒ์ 2๊ฐ ๊ณ ๋ฅธ๋ค.
ํํ๋ง์ด ๋ ๊ฐ์ง ๊ธฐํธ๋ฅผ ๋ถ๋ชจ ๋ ธ๋๋ฅผ ๊ฐ์ง๋ ๋ถํธ๋ฆฌ๋ฅผ ๊ตฌ์ฑํ๊ณ ์์ ๋ ธ๋๋ฅด ์์ฑํ๋ค.
๋ถ๋ชจ ๋ ธ๋ ๋จ ๊ธฐํธ๋ค์ ๋น๋์๋ฅผ ๋ํ์ฌ ์ฃผ ๋ ธ๋์ ํ ๋นํ๊ณ ๋ชฉ๋ก์ ์์์ ๋ง๋๋ก ๋ชฉ๋ก์ ์ฝ์ ํ๋ค.
๋ชฉ๋ก์์ ๋ถ๋ชจ๋ ธ๋์ ํฌํจ๋ ๊ธฐํธ๋ฅผ ์ ๊ฑฐํ๋ค.
๋ฃจํธ๋ ธ๋๋ก๋ถํฐ์ ๊ฒฝ๋ก์์ ๊ฐ ๊ฐ์ง์ ์ฝ๋์๋๋ฅผ ๋ถ์ฌํ๋ค.
ํํ๋ง ์๊ณ ๋ฆฌ์ฆ์ ์ ๋ ฅ ๊ธฐํธ๋ฅผ ๋ฆฌํ ๋ ธ๋๋ก ํ๋ ์ด์ง ํธ๋ฆฌ๋ฅผ ๋ง๋ค์ด์ ์ ๋ ๋ถํธ๋ฅผ ๋ง๋ค์ด ๋ด๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
๊ตฌํ
Huffman ์๊ณ ๋ฆฌ์ฆ์ ์ต์๋น๋ ์๋ฅผ ์ถ๋ ฅํ๊ธฐ ์ํด์ ์ฐ์ ์์ ํ๋ฅผ ํ์๋กํ๋ค. ์ต์ํ์ ์ฌ์ฉํด์ ๊ตฌํํด๋ณด์๋ค.
๊ตฌ์กฐ์ฒด
// ๊ธฐ๋ณธ์ ์ผ๋ก ๋
ธ๋๋ data์ ๋ณด์ ๋น๋์๋ ์์๊ฐ์๋ int๊ฐ์ ๊ฐ๋๋ค.
// ํํ๋ง์ ์ด์งํธ๋ฆฌ ๊ตฌ์กฐ์ด๋ฏ๋ก left์ right์ ํฌ์ธํฐ๋ฅผ ๊ฐ๊ณ ์๋ค.
typedef struct node{
char data;
unsigned int frequency;
struct node * left, *right;
}Node;
// heap๋ heap์ ํฌ๊ธฐ, node array๋ฅผ ๊ฐ๊ณ ์๋ค.
// capacity๋ ๋ฐฐ์ด์ ํฌ๊ธฐ๋ฅผ ๋งํ๋ค.
typedef struct heap{
unsigned int size;
unsigned int capacity;
Node ** array;
}Heap;
new_node
Node * new_node(char data, unsigned freq){
Node * new = (Node*)malloc(sizeof(Node));
new->data=data;
new->frequency=freq;
new->left=new->right=NULL;
return new;
}
Heap ์ด๊ธฐํ
Heap * init(unsigned capacity){
Heap * heap = (Heap*)malloc(sizeof(Heap));
// ํ์ฌ heap์ ํฌ๊ธฐ๋ 0์ด๋ค.
heap->size=0;
heap->capacity=capacity;
// ๋ฐฐ์ด์ ํฌ๊ธฐ ๋งํผ ๊ณต๊ฐ์ ํ ๋นํด์ค๋ค.
heap->array = (Node**)malloc(heap->capacity*sizeof(Node*));
return heap;
}
heapify
๋ ๊ฐ์ subtree๊ฐ min heap์ผ๋ root์ ์ถ๊ฐ๋ ๋ ธ๋๋ฅผ ํฌํจํ ์ ์ฒด๊ฐ heap์ ์กฐ๊ฑด์ ๋ง์กฑํ๋๋ก ๊ฐ ๋ ธ๋์ ์์น๋ฅผ ์กฐ์
void swap_node(Node ** a, Node ** b){
Node * tmp = *a;
*a = *b;
*b = tmp;
}
// heapify : ๋ ๊ฐ์ subtree๊ฐ min heap์ผ๋ root์ ์ถ๊ฐ๋ ๋
ธ๋๋ฅผ ํฌํจํ ์ ์ฒด๊ฐ
// heap์ ๋ง์กฑํ๋๋ก ๊ฐ ๋
ธ๋์ ์์น๋ฅผ ์กฐ์
void heapify(Heap * h, int i){
int min = i;
int left = 2*i +1; // ์ผ์ชฝ ์์๋
ธ๋
int right = 2*i+2; // ์ค๋ฅธ์ชฝ ์์๋
ธ๋
// ์ผ์ชฝ ์์ ๋
ธ๋์ ์ธ๋ฑ์ค๊ฐ heap์ ํฌ๊ธฐ๋ณด๋ค ์๊ณ
// frequency๊ฐ์ด ์ต์๊ฐ์ frequency๋ณด๋ค ์์ผ๋ฉด ์ต์๊ฐ์ left๋ก ๋ณ๊ฒฝ
if(left < h->size && h->array[left]->frequency < h->array[min]->frequency)min=left;
// ์ค๋ฅธ์ชฝ ์์๋
ธ๋๋ ๋ง์ฐฌ๊ฐ์ง
if(right < h->size && h->array[right]->frequency < h->array[min]->frequency)min=right;
// ๋ง์ฝ ์ต์๊ฐ์ด i์ ๋ค๋ฅด๋ค๋ฉด ๋
ธ๋์์น๋ฅผ ๋ณ๊ฒฝํด์ค๋ค.
if(min!=i){
swap_node(&h->array[min], &h->array[i]);
heapify(h,min);
}
}
delete
Node * delete(Heap * h){
Node * tmp = h->array[0];
h->array[0]=h->array[--h->size];
heapify(h, 0);
return tmp;
}
insert
void insert(Heap * h, Node * node){
int p; //ํ์ฌ ์์น ์ ์ฅ
// ๋ง์ง๋ง ์์น์ ์ถ๊ฐ
p=++h->size-1;;
// ์์น ์กฐ์
while(node->frequency < h->array[(p-1)/2]->frequency){
h->array[p] = h->array[(p-1)/2];
p=(p-1)/2;
}
h->array[p]=node;
}
heap ์์ฑ
void build_heap(Heap * h){
int n = h->size-1;
int i;
for(i=(n-1)/2;i>=0;i--)
heapify(h, i);
}
Heap * create_heap(char data[], int freq[],int size){
//์ด๊ธฐํํด์ ์์ฑํ๋ค.
Heap * heap = init(size);
// ๋น๋์์ ๋ฐ์ดํฐ๊ฐ์ ๋ฃ์ ๋
ธ๋๋ฅผ ์์ฑํด์ค๋ค.
for(int i=0;i<size;i++)
heap->array[i]=new_node(data[i], freq[i]);
heap->size = size;
build_heap(heap);
return heap;
}
์ถ๋ ฅ
//๋ฐฐ์ด ์์ ๊ฐ ์ถ๋ ฅ
void print(int arr[],int n){
for(int i=0;i<n;i++)
printf("%d",arr[i]);
printf("\n");
}
int is_leaf(Node * root){
return !(root->left) && !(root->right);
}
// ์ต์ข
์ฝ๋ ์ถ๋ ฅ
void print_code(Node * root, int arr[], int top){
// ์ผ์ชฝ ์์๋
ธ๋(๊ฐ์ง)๋ 0์ ์ฅ
if(root->left){
arr[top]=0;
print_code(root->left, arr,top+1);
}
// ์ค๋ฅธ์ชฝ ์์๋
ธ๋(๊ฐ์ง)๋ 1์ ์ฅ
if(root->right){
arr[top]=1;
print_code(root->right, arr,top+1);
}
// ๋จ๋ง๋
ธ๋๋ฉด ์ฝ๋ ์ถ๋ ฅ
if(is_leaf(root)){
printf("%c: ",root->data);
print(arr, top);
}
}
Huffman ์์ฑ
// heap์ ํฌ๊ธฐ๊ฐ 1์ธ์ง ์๋์ง ๊ฒ์ฌ
int is_one(Heap * h){
return (h->size==1);
}
Node * build_huffman(char data[],int freq[], int size){
Node * left, *right, *top;
Heap * heap = create_heap(data, freq, size);
while(!is_one(heap)){
left = delete(heap);
right = delete(heap);
top = new_node('$',left->frequency+right->frequency);
top->left=left;
top->right= right;
insert(heap, top);
}
return delete(heap);
}
void huffman(char data[],int freq[],int size){
Node * root = build_huffman(data, freq, size);
int arr[MAX],top=0;
print_code(root, arr,top);
}
Main
int main(){
char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' };
int freq[] = { 5, 9, 12, 13, 16, 45 };
int size = sizeof(arr) / sizeof(arr[0]);
huffman(arr, freq, size);
}
๊ฒฐ๊ณผ
f: 0
c: 100
d: 101
a: 1100
b: 1101
e: 111
์์ฉ
ํฉ์ค
JPEG
MPEG
Last updated
Was this helpful?