알고리즘 이론 16강(3). 그리디 알고리즘 예제2 - Huffman Code Problem

 

[허프만 코드 문제(Huffman code problem)]

: 데이터를 효율적으로 압축하는 문제로 그리디 알고리즘의 대표적 예제중 하나이다.

: 자주 나타나는 문자열을 찾아 짧은 비트로 표현하고, 비교적 덜 나타나는 문자열은 긴 비트로 표현한다.

: 허프만 코드는 접두사가 없는(prefix-free) 코드다.

 

 

[허프만 코드(Huffman Code)]

: 최초의 압축시에 사용되는 알고리즘

: 데이터 크기를 일반적으로 20~90% 정도 줄일 수 있다.

 

 

 

[허프만 코드 문제 개요]

: Variable-length codeword가 허프만 코드를 이용해 압축한 데이터 길이이다.

 

# 허프만 코드 이용해 빈도별 가변 데이터 크기 추출

(좌)고정 길이 코드워드 / (우) 가변 길이 코드워드

: 각 문자별 사용 빈도를 기준으로, 상향식 이진 트리형태로 만들고, 각 문자의 위치에 따라 가변 코드를 부여한다.

 

# 문자와 빈도수 주어졌을때 각 문자의 가변길이 코드워드를 구하는 예시

ex) [f:5] [e:9], [c:12], [b,13], [d,16], [a:45]

: 우선 작은 노드들부터 합쳐나가는데, (c)번에서와 같이 두 노드의 합보다 작은 노드가 2개 이상있으면, 그것들끼리 합하고, 1개이하면 두노드의 합과 비교한다.

 

 

 

[허프만 코드의 구조]

HUFFMAN(C)      // C는 문자들의 집합   n <- |C|   Q <- C            // Q는 이진 최소힙, O(n)   for i <- 1 to n-1     do allocate a new node z       left[z] <- x <- EXTRACT-MIN(Q)        // O(logn)       right[z] <- y <- EXTRACT-MIN(Q)      // O(logn)       f[z] <- f[x] + f[y]       INSERT(Q,z)    // O(logn)   return EXTRACT-MAIN(Q)

: 수행시간 O(nlogn)

 

 

 

[Prefix Code(접두사 코드)]

: 앞서 말했듯 허프만 코드는 prefix code를 사용하기위해 이진트리를 사용한다.

# 인코딩 : abc => 0 101 100 = 0101100     // 인코딩은 매우쉬움

# 디코딩 : 001011101 => aabe   //디코딩은 중복되는 표현 문제 발생 가능한데 이를 prefix 방식으로 해결한 것.

 

 

---

[분할정복 vs 동적 프로그래밍 vs 그리디 알고리즘]

	분할과 정복	동적 프로그래밍	그리디 알고리즘
큰문제를 작은문제의 집합으로써 본다	O	O	O
"재귀" 기반 해결	O	O	O
부분문제들간의 독립성	O	겹치는부분 존재	순차적인 부분문제
부분문제의 개수	자르는 기준에 따라 달라진다	비교적 적다	순차적인 부분문제..
일반적인 수행 시간	logn	부분문제의 난이도와 개수에 따라 다르다	nlogn 정도..
최적화 문제 해결용?		O	O (dp하고 그리디 조건맞으면 수행)
최적화된 부분구조(문제)		O	O
지역적 탐욕 선택			O
경험 지식하에 값 최적화에 적절			O