https://en.wikipedia.org/wiki/Huffman_coding 참고
압축에서 많이 사용하는 개념으로 가변 길이 부호화를 하는 방법을 말합니다.
트리를 생성하는 방법은 다음과 같습니다.
15,7,6,6,5 빈도수와 코드값 A,B,C,D,E 이 아래와 같이 주어진다고 할때 허프만 트리를 만드는 과정은 아래와 같습니다.
설명 b : 빈도가 가장 작은 두개 노드를 선택하고 이 두 노드를 자식으로 하는 부모 노드 를 만듭니다. D,E가를 가지고 트리를 만들고 새로운 노드는 11이라는 자식노드의 합이 새로운 빈도가 됩니다.
설명 c : 빈도가 가장 작은 두개 노드를 선택하고 이 두 노드를 자식으로 하는 부모 노드 를 만듭니다. 제일 아래 B 7, C 6 이 제일작은 빈도가 됩니다. 그래서 B C노드를 만듭니다.
설명 d : 빈도가 가장 작은 두개 노드를 선택하고 이 두 노드를 자식으로 하는 부모 노드 를 만듭니다. 15,13,11 중 작은 두개는 13,11이 됩니다. 13과 11은 BC,DE입니다. 그래서 새로운 24짜리 node가 만들어집니다.
설명 e : 빈도가 가장 작은 두개 노드를 선택하고 이 두 노드를 자식으로 하는 부모 노드 를 만듭니다. 15,24 인 노드가 남았습니다. 39가 완성된 node입니다.
아래와 같이 부호화가 가능합니다.
위설명을 코드로 구현하였습니다. 순수하게 C언어로만 되어 있고 pointer를 사용하지 않고 구현하였습니다.
C, pasted 1 second ago:
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
| #include <stdio.h>
#define NODE_MAX 5
#define SymbolIdx 0
#define FrequencyIdx 1
int innode[NODE_MAX][2]={
{'A',15},
{'B',7},
{'C',6},
{'D',6},
{'E',5},
};
#define NodeMax 5
#define NodeFrequency 4
#define NodeSymbol 3
#define NodeChild1 2
#define NodeChild2 1
#define NodeParent 0
int pqnode[NODE_MAX*5];
#define QMAX NODE_MAX*5
int qpool[QMAX][NodeMax];
int qinfo[NodeMax];
int pqcount=0;
int realpqcount=0;
int init()
{
int i;
for(i=0;i<QMAX;i++){
qpool[i][NodeFrequency] = -1;
}
return 0;
}
int pqput(int idx)
{
int i;
for(i=0;i<pqcount;i++){
if(pqnode[i]==-1) break;
}
if(i==pqcount){
pqcount++;
}
realpqcount++;
pqnode[i]=idx;
return 0;
}
int getfreepool()
{
int i;
for(i=0;i<QMAX;i++){
if( qpool[i][NodeFrequency] == -1 ) return i;
}
return -1;
}
int setqpool(int idx,int symbol,int freq,int parent,int child1,int child2)
{
printf("setq:%d %d %d\n",idx,symbol,freq);
qpool[idx][NodeSymbol]=symbol;
qpool[idx][NodeFrequency]=freq;
qpool[idx][NodeParent]=parent;
qpool[idx][NodeChild1]=child1;
qpool[idx][NodeChild2]=child2;
return idx;
}
int getpoolNodeFrequency(int idx)
{
return qpool[idx][NodeFrequency];
}
int getpqcount()
{
return realpqcount;
}
int pqget()
{
int i;
int minidx = -1;
int minvalue = 100000;
int curr;
int pid = -1;
if( realpqcount== 0 ) return -1;
for(i=0;i<pqcount;i++){
if(pqnode[i]==-1) continue;
curr = getpoolNodeFrequency(pqnode[i]);
if( curr < minvalue ){
minidx = i;
pid = pqnode[i];
minvalue = curr;
}
}
pqnode[minidx] = -1;
realpqcount--;
if( pqcount-1==minidx ) pqcount--;
return pid;
}
int codes[10];
int DFS(int node,int depth)
{
int i;
if(node == -1) return 0;
if(qpool[node][NodeSymbol]!=-1){
printf("%c:",qpool[node][NodeSymbol]);
for(i=0;i<depth;i++){
printf("%d",codes[i]);
}
printf("\n");
return 0;
}
codes[depth]=0;
DFS(qpool[node][NodeChild1],depth+1);
codes[depth]=1;
DFS(qpool[node][NodeChild2],depth+1);
return 0;
}
int main()
{
int i;
int chk1,chk2,root;
int tmpq[NodeMax];
init();
for(i=0;i<NODE_MAX;i++){
pqput(setqpool(getfreepool(),innode[i][SymbolIdx],innode[i][FrequencyIdx],-1,-1,-1));
}
for(;;){
if(getpqcount()==1) {
// queue에 node가 하나남으면 root node 하나만 남은 상태임
break;
}
chk1 = pqget();
chk2 = pqget();
pqput(setqpool(getfreepool(),-1,getpoolNodeFrequency(chk1)+getpoolNodeFrequency(chk2),-1,chk1,chk2));
}
root = pqget();
DFS(root,0);
return 0;
}
|
Output:
setq:0 65 15
setq:1 66 7
setq:2 67 6
setq:3 68 6
setq:4 69 5
setq:5 -1 11
setq:6 -1 13
setq:7 -1 24
setq:8 -1 39
A:0
E:100
C:101
D:110
B:111
|
댓글 없음:
댓글 쓰기