반응형
1. 사용하는 이유
압축기법의 하나로써 문자의 빈도에 따라 자주 사용되는 문자에는 적은 비트값을,
자주 사용되지 않는 문자에는 많은 비트값을 주어 전체에 필요한 비트값을 줄이기 위해 사용.
영상 압축에 많이 사용된다.
2. 허프만 동작 원리
우선순위 큐에 Tree 구조를 계속 넣고 root값의 우선순위에 따라 Tree를 만든다.
이해 ㅇㅋ?
즉 11,22 33 이 있다고 가정하면 우선순위 큐안에 1,1,2,2,3,3 이 모두 들어간다.
그중 가장 작은 두수를 뺀다.
그렇게 되면 (1 1) - (2) 라는 트리가 생긴다. 그 후 우선순위 큐에 (1,1) - (2) 트리를 다시 집어넣는다.
그러면 우선순위 큐는 2, 2 , (1,1) - (2), 3 , 3 으로 정렬이 되고 그 이후
(2,2 ) - (4) 라는 트리를 만들게 된다. 다시 우선순위큐에 집어넣고 (1,1) - (2), 3, 3 (2,2) - (4) 로 정렬된다.
그러면 ((1,1) - (2)) - (3) - 5가 생성된다. 다시 우선순위 큐에 집어넣고 3 , (2,2) - (4), ((1,1) - (2)) - (3) - 5 가 된다.
3, 4를 빼와서 ((2,2) - (4), 3) - 5가 만들어진다.
대충 이러한 방식으로 만들어진다.
아래는 C언어 소스코드이다.
소스
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 | #include <stdio.h> #include <string.h> #include <stdlib.h> #define FILENAME "huffman.txt" #define MAX_TREE_HT 100 #define ALPHABET_SIZE 27 // A Huffman tree node typedef struct MinHeapNode { char data; int freq; int* array; struct MinHeapNode *left; struct MinHeapNode *right; }MinHeapNode; typedef struct MinHeap { int size; int capacity; MinHeapNode **array; }MinHeap; typedef struct Table{ char data; char huffmancode[MAX_TREE_HT]; }Table; MinHeapNode* ALLOCATE_NODE(char data, int freq); void SWAP_NODE(MinHeapNode** a,MinHeapNode** b); void MIN_HEAPIFY(MinHeap* minHeap, int index); int IS_HEAP_SIZE_ONE(MinHeap* minHeap); MinHeapNode* EXTRACT_MIN(MinHeap* minHeap); void INSERT_MIN_HEAP(MinHeap* minHeap, MinHeapNode* minHeapNode); void printArr(int* arr, int n); int IS_LEAF(MinHeapNode* root); MinHeap* BUILD_MIN_HEAP(char* data, int* freq, int size); MinHeapNode* BUILD_HUFFMAN_TREE(char* data, int* freq, int size); void MAKE_HUFFMAN_CODE(MinHeapNode* root, int* arr, int top); void ENCODING(char* story, int size); MinHeapNode* HUFFMAN(char* data, int* freq, int size); void DECODING(); int compare(const void *A, const void *B); MinHeapNode* root; Table* table; int k=0; int main(){ FILE *fp_r; //파일 입출력 변수 FILE *fp_table; int cnt = 0; //파일 입력 변수 개수 int i,ascii_number; char *story = (char*)malloc(sizeof(char)); //문자열 배열 char *letter = (char*)malloc(sizeof(char)*27); //' ' ~ 'Z' 까지 저장하는 배열 int *frequency = (int*)malloc(sizeof(int)*27); //위의 배열에 대한 빈도수를 저장하는 배열 table = (Table*)malloc(sizeof(Table)*27); //알파벳과 빈도수에 대한 테이블을 저장하는 구조체 배열 fp_r = fopen(FILENAME,"rt"); //파일 읽기 if(fp_r==NULL) //파일 없다면 에러 처리 { //printf("**** File open error ****\n"); system("pause"); exit(1); } //story라는 배열로 알파벳을 받아옴. while (!feof(fp_r)) { story = (char*)realloc(story, sizeof(char)*(cnt+1)); fscanf(fp_r, "%c", &story[cnt]); cnt++; } //모든 데이터와 빈도수의 배열을 0으로 초기화 해줌. for(i=0; i<27; i++) { letter[i] = ' '; frequency[i] = 0; } //받아온 문자열을 알파벳을 저장하는 배열과 빈도수를 저장하는 배열로 나누어서 저장해준다. for(i=0; i<cnt; i++) { ascii_number = story[i]-97; //띄어쓰기 ' '일때는 따로 관리해줘야한다. if(story[i] ==' '){ letter[26] = story[i]; frequency[26]++; } else{ if(ascii_number != -148){ letter[ascii_number] = story[i]; frequency[ascii_number]++; } } } root = HUFFMAN(letter, frequency, ALPHABET_SIZE); //허프만 트리를 만들고 ROOT값을 가져온다. fclose(fp_r); qsort(table, ALPHABET_SIZE, sizeof(Table), compare); //테이블을 알파벳기준 정렬을 한다. printf("*******TABLE********\n"); fp_table = fopen("week10_table.txt","w"); //테이블을 텍스트 파일로 만들어준다. for(i=0; i<ALPHABET_SIZE; i++){ fprintf(fp_table,"%c, %s\n",table[i].data, table[i].huffmancode); printf("%c, %s\n",table[i].data, table[i].huffmancode); } printf("-----------------------------------\n"); ENCODING(story,cnt-1); //인코딩 DECODING(); //디코딩 return 0; } //허프만트리를 만들기 위한 함수이다. MinHeapNode* HUFFMAN(char* data, int* freq, int size) { int i=0; MinHeapNode* root = BUILD_HUFFMAN_TREE(data, freq, size); //허프만 트리를 만든다. int top = 0; root->array = (int*)malloc(MAX_TREE_HT); MAKE_HUFFMAN_CODE(root, root->array, top); return root; } //허프만 트리를 만드는 함수 MinHeapNode* BUILD_HUFFMAN_TREE(char* data, int* freq, int size) { MinHeapNode *left, *right, *top; //트리에 필요한 top과 left,right를 만들어준다. MinHeap* minHeap = BUILD_MIN_HEAP(data, freq, size); //허프만트리를 만들기위한 Min Heap을 만들어준다. //minHeap의 size가 1일때까지 반복한다. 허프만 트리 만드는 과정 while (!IS_HEAP_SIZE_ONE(minHeap)) { //가장 빈도수 낮은 두 값을 빼온다. left = EXTRACT_MIN(minHeap); right = EXTRACT_MIN(minHeap); //printf("left : %d right : %d\n",left->data,right->data); //$는 leaf노드와 아닌 노드들을 구별하기위해서 만들었다. //허프만 트리를 만들어준다. //빈도수 대로 추출해서 왼쪽 오른쪽으로 계속해서 추가해 나간다. //가장 작은 노드들 두개를 더해서 하나의 노드 TOP 로 놓는다. top = ALLOCATE_NODE('$', left->freq + right->freq); top->left = left; top->right = right; INSERT_MIN_HEAP(minHeap, top); } printf("%c\n\n",EXTRACT_MIN(minHeap)->data); //return minHeap->array[0]; return EXTRACT_MIN(minHeap); } //새로운 노드를 만들어준다. MinHeap에 저장을 하기 위해서. MinHeapNode* ALLOCATE_NODE(char data, int freq) { MinHeapNode* temp = (MinHeapNode*) malloc(sizeof(MinHeapNode)); temp->left = NULL; temp->right = NULL; temp->data = data; temp->freq = freq; return temp; } //MIN_HEAP으로 만드는 HEAPIFY과정을 보인다. void MIN_HEAPIFY(MinHeap* minHeap, int index) { int smallest = index; int left = 2 * index + 1; int right = 2 * index + 2; if (left < minHeap->size &&minHeap->array[left]->freq < minHeap->array[smallest]->freq) { smallest = left; } if (right < minHeap->size &&minHeap->array[right]->freq < minHeap->array[smallest]->freq) { smallest = right; } if (smallest != index) { SWAP_NODE(&minHeap->array[smallest], &minHeap->array[index]); MIN_HEAPIFY(minHeap, smallest); } } //힙의 사이즈가 1인지 아닌지 판단해주는 함수 int IS_HEAP_SIZE_ONE(MinHeap* minHeap) { return (minHeap->size == 1); } //Root에 있는 원소를 추출후 다시 MinHeap을 만드는 과정이다. MinHeapNode* EXTRACT_MIN(MinHeap* minHeap) { MinHeapNode* temp = minHeap->array[0]; minHeap->array[0] = minHeap->array[minHeap->size-1]; minHeap->size--; MIN_HEAPIFY(minHeap,0); return temp; } //구성된 MIN_HEAP에 새로운 NODE(top,left,right)를 추가시켜주는 과정이다. void INSERT_MIN_HEAP(MinHeap* minHeap, MinHeapNode* minHeapNode) { int i; minHeap->size++; //Min Heap의 사이즈를 하나 추가시켜준다. i = minHeap->size-1; //마지막 인덱스 //빈도수를 비교해가며 어디에 들어가야할지 인덱스를 찾는 과정이다. while (i && minHeapNode->freq < minHeap->array[(i-1)/2]->freq) { minHeap->array[i] = minHeap->array[(i-1)/2]; i = (i - 1)/2; } minHeap->array[i] = minHeapNode; } //MIN_HEAP 만든다. MinHeap* BUILD_MIN_HEAP(char* data, int* freq, int size) { int i,n; MinHeap* minHeap =(MinHeap*) malloc(sizeof(MinHeap)); minHeap->size = size; minHeap->capacity = size; minHeap->array =(MinHeapNode**)malloc(minHeap->capacity * sizeof(MinHeapNode*)); //만들어준 MinHeap의 각 노드에 알파벳과 빈도수를 넣어준다. for (i = 0; i < size; i++) { minHeap->array[i] = ALLOCATE_NODE(data[i], freq[i]); } //minHeap을 Heapify등을 해서 넘겨준다. n = (minHeap->size-1)/2; for (i=n; i>=0; i--) { MIN_HEAPIFY(minHeap, i); } return minHeap; } //허프만코드를 만드는 과정이다. //leaf일때까지 찾아간다. void MAKE_HUFFMAN_CODE(MinHeapNode* root, int* arr, int top) { int i; //왼쪽이 있다면 배열에 0을 추가하고 왼쪽 자식으로 이동한다. if (root->left) { arr[top] = 0; MAKE_HUFFMAN_CODE(root->left, arr, top+1); } //오른쪽이 있다면 배열에 1을 추가하고 오른쪽 자식으로 이동한다. if (root->right) { arr[top] = 1; MAKE_HUFFMAN_CODE(root->right, arr, top+1); } //leaf일때 그에 해당하는 알파벳과 허프만코드를 저장한다. if (IS_LEAF(root)) { //root->data 에는 허프만코드의 알파벳 table[k].data = root->data; //arr에는 허프만코드가 들어있음. for (i = 0; i < top; i++){ table[k].huffmancode[i] = arr[i]+48; //printf("%c\n",table[k].huffmancode[i]); } table[k].huffmancode[i] = '\0'; k++; } } //인코딩 함수 void ENCODING(char* story, int size){ int i =0; FILE *fp = fopen("week10_incoing_output.txt","w"); //테이블에 index값으로 접근하여 문자열들을 허프만코드로 바꾸어준다. for(i=0; i<size; i++){ //띄어쓰기 ' '일때는 아스키코드로 바로 index 접근을 할수 없기때문에 따로 만들어준다. if(story[i] == ' '){ fprintf(fp, "%s",table[0].huffmancode); } else{ fprintf(fp, "%s",table[story[i]-96].huffmancode); } } fclose(fp); printf("*******ENCODING SUCCESS********\n"); } //디코딩 함수 void DECODING(){ int i, size = 0; char temp_char; MinHeapNode* tempNode = root; int *code = (int*)malloc(sizeof(int)); FILE *fp = fopen("week10_incoing_output.txt", "r"); FILE *fop = fopen("week10_decoding_output.txt", "w"); //허프만 코드를 가져온다. while (!feof(fp)) { code = (int*)realloc(code, sizeof(int)*(size+1)); fscanf(fp, "%c", &temp_char); code[size] = temp_char-48; size++; } //가져온 허프만민트리를탐색하는데 0이면 left로 1이면 right로 이동하여 //leafNode일 경우 텍스트파일에 저장한다. for(i=0; i < size; i++){ if(IS_LEAF(tempNode)){ fprintf(fop, "%c",tempNode->data); tempNode = root; } if(code[i] == 0){ tempNode = tempNode->left; } else if(code[i] ==1){ tempNode = tempNode->right; } } fclose(fp); fclose(fop); printf("*******DECODING SUCCESS********\n"); } //leaf 노드인가 아닌가에 대해 판단해주는 함수이다. int IS_LEAF(MinHeapNode* root) { return !(root->left) && !(root->right) ; } void SWAP_NODE(MinHeapNode** a,MinHeapNode** b) { MinHeapNode* t = *a; *a = *b; *b = t; } int compare(const void *A, const void *B) { Table* ptrA = (Table*)A; Table* ptrB = (Table*)B; char a = ptrA->data, b = ptrB->data; if(a == b) return 0; else if(a > b) return 1; else return -1; } | cs |
반응형
'개인 공부 > 자바' 카테고리의 다른 글
| HashMap 해쉬맵 들어온 순서대로 (0) | 2018.02.13 |
|---|---|
| 모든 경우의 수 (백 트래킹) (0) | 2018.02.08 |
| int vs Integer (Wrapper 클래스) (1) | 2018.01.17 |
| 인터프리터 vs 컴파일러 (0) | 2018.01.17 |
| for each (자바) - for문을 통한 배열 간단히 출력하기 (0) | 2018.01.10 |
