Greedy 알고리즘 - Huffman Code

greedy 알고리즘 일곱 번째 문제

 

7.Huffman Code

-텍스트를 압축할때, 파일에 빈번히 나타나는 문자에는 짧은 이진 코드를 할당하고

드물게 나타나는 문자에는 긴 이진 코드를 할당하는 것이다.

-이 때 문자를 표현하기 위해 트리를 이용한다. 

 

-방법 1. min-priority queue를 사용하는 방법

1.각 문자 당 노드를 만들고, 그 문자의 빈도수를 노드에 저장
2.n개의 노드의 빈도수에 대해 우선순위 큐 Q를 만든다.
while(Q에 있는 노드 수 >=2){
  빈도수가 가장 작은 2개의 노드 (A와 B)를 Q에서 제거.
  새 노드 N을 만들고, A와 B를 N의 자식 노드로 만든다.
  N의 빈도수 = A의 빈도수 +B의 빈도수
  노드N을 Q에 삽입한다.}
return Q

-Time Complexity

n개 노드 만들기 : O(n)

+

heap 만들기. Insert n번 발생 : Nlogn

+

Q에 있는 노드 수가 1개 남을때까지 반복. : O(n)

 반복 안에서 Delete, Insert 수행 : O(logn)+O(logn)

 

=O(n)+O(nlogn)+n{O(logn)+O(logn)} = O(nlogn)

-전체 흐름

 

-방법2 Sorting을 사용하는 방법

1.Initial Sequence T sorted by frequency//빈도수에 따라 오름차순 정렬
2.while(#of T>=){//T가 하나 남을때까지 반복
3.  Combine lowest two into sub-tree //가장 작은 2개를 sub tree에 넣고 더해
4.  Move it correct place} //다시 insert
5.return T

-Time Complexity

1.정렬 : O(nlogn)

+

2.2line부터 n번 반복

3. constant

4.삽입 : O(logn)

 

=O(nlogn)+O(nlogn)=O(nlogn)

 

-전체 흐름