오래 못 할 짓 하지 않기
[ 알고리즘 ] 8. Huffman 알고리즘 본문
우리는 문자를 0과 1로 표시하여 나타내려고 한다.
Huffman 알고리즘은 Text Encoding 을 위한 알고리즘이다.
: 문자의 출현 빈도에 따라 다른 길이를 사용하여 압축한다.
= 많이 나오는 문자는 짧은 길이로, 그렇지 않으면 길게 표현하여 비트 수를 줄인다.
우선 이걸 이해하기 전에 Prefix라는 개념을 이해해야한다.
Prefix (free) code
: 어느 하나의 코드가 다른 하나 코드의 접두code가 되지 않아야 한다.
- 목적 : 모호성( Ambiguity ) 을 피하기 위해
- 원인 : Huffman 코드는 각 문자마다 다른 길이를 사용하기에 어느 길이만큼 잘라야 하는지에 대한 Ambiguity 이 있다.
ex) [ A, B, C, D ] 라는 문자를 각각 [ 0, 01, 10 ,1 ] 이라는 code로 나타내보자.
" 001 " 이 나타내는 문자는 무엇일까?
▶ 이걸 어떻게 자르느냐에 따라 달라진다.
0/0/1 로 잘랐다면 AAD가 되고
0/01 로 잘랐다면 AB가 된다.
0은 01의 prefix이므로 이런 Ambiguous한 상황이 발생한다.
▶ 해결법 : 어떠한 문자도 다른 문자의 Prefix를 가지지 않으면 된다.
[ A, B, C, D ] = [ 0, 10, 110, 111 ]
다음과 같이 code를 설정해두었다면 , 어떠한 문자도 다른 문자에 대해 prefix가 생기지 않는다.
다음과 같이 비슷한 모양이 하나도 없으므로 헷갈릴 일이 없다.
고정된 길이의 문자일 때는 다음과 같다.
3(bit) * ( 45,000 + 13,000 + 12,000 + 16,000 ...) 이럴 거임
빈도수에 따라 길이를 다르게 하면 이렇다.
1bit * 45,000 + 3 * 12,000 ...
= 더 save됨
Encoding의 Cost는 다음과 같다.
B(T) = 인코딩에 필요한 bit 수
d(c) = 트리에서 c가 있는 depth
f(c) = c가 나오는 빈도
▶ 결론적으로 빈도수 * depth(비트 수)
(Min Heap을 사용한다)
▶1. n = 문자의 개수
▶2. Q = 문자들을 priority queue에 넣는다.
반복문
▶4. z라는 node 생성
▶5,6 현재 heap에서 cost가 가장 작은 노드 두 개를 z의 양쪽에 둔다.
▶7. 합한 값을 z의 값으로 둔다.
▶8. 넣는다.
답▼
현재 트리에서 가장 작은 값들 2개끼리만 더한다고 생각하면 된다.
Running Time : O(n log n)
▶1. n = 문자의 개수 = θ(n)
▶2. Q = queue에 넣는 거 = O(n log n)
반복문 = θ(n)
▶4. z라는 node 생성
▶5,6 현재 heap에서 cost가 가장 작은 노드 두 개를 z의 양쪽에 둔다.
- 가장 작은 거 찾는 데 걸리는 시간 O(log n)
▶7. 합한 값을 z의 값으로 둔다. θ(1)
▶8. 넣는다. O (log n)
(출처)
한동대학교 용환기교수님 - 알고리즘
(참고)
'3학년 1학기 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| [ 알고리즘 ] 10. Knapsack (0) | 2024.04.13 |
|---|---|
| [ 알고리즘 ] 9. DP / Greedy 문제 풀기 (0) | 2024.04.13 |
| [ 알고리즘 ] 7. Greedy 알고리즘 (2) (0) | 2024.04.07 |
| [ 알고리즘 ] 6. Greedy 알고리즘 (0) | 2024.04.02 |
| [ 알고리즘 ] 5. DP - MCM 알고리즘 (0) | 2024.03.31 |
