Algorithm. Greedy Algorithm

[Visual Studio과 C#으로 구현/허프만코드]

Algorithm Greedy Algorithm Coding // Week09

20211105_20615034

[ Greedy Algorithm Coding_Theory ]

[ 허프만 압축 ]

· 파일의 각 문자가 8bit 아스키 (ASCII) 코드로 저장되면, 

  그 파일의 bit 수는 8x(파일의 문자 수)임.

· 이와 같이 파일의 각 문자는 일반적으로 고정된 크기의 코드로 표현 됨.

​

 이러한 고정된 크기의 코드로 구성된 파일을 저장하거나 전송할 때 파일의 크기를 줄이고 필요 시 원래의 파일로 변환할 수 있으면 메모리 공간을 효율적으로 사용할 수 있고 파일 전송 시간을 단축시킬 수 있음.

 이를 이용하여 빈번힌 나타나는 문자에는 짧은 이진 코드를 할당, 드물게 나타나는 문자에는 긴 이진 코드를 할당하는 것이 허프만 압축임.

허프만 압축 방법으로 변환시킨 문자 코드들 사이에는 접두부 특성이 존재하여 특별한 구분자를 사용하지 않아도 됨.

[ 허프만 코드 ]

 입력 파일에 대해 각 문자의 출현 빈도수 (문자가 파일에 나타나는 횟수)에 기반을 둔 이진트리를 만들어서, 각 문자에 이진 코드를 할당. 이러한 이진 코드를가 허프만 코드임.

 이러한 허프만 코드에는 우선순위 큐(최소 힙으로 구현), 최대 힙 트리 총 두가지 자료구조가 사용 됨.

​

[ 우선순위 큐 ]

· 우선순위를 가진 항목들을 저장하는 큐

· 우선순위가 높은 데이터가 먼저 나가게 됨

· 힙을 이용한 구현

[ 힙 ]

· 완전 이진 트리(=> 배열로 구현 가능)

· 최대 힙, 최소 힙

· 최대 힙 = ( key(부모노드) >= key(자식노드) )인 완전 이진트리

· 최소 힙 = ( key(부모노드) <= key(자식노드) )인 완전 이진트리

배열로 구현한 최대 힙

최대 힙의 삽입 연산

- 최대 힙의 삽입 연산 순서

1. 트리의 가장 말단에 삽입하고자하는 데이터를 추가

2. 부모 노드와 비교하여 만약 현재 노드가 더 클 경우, 

부모 노드와 자리 교환

3. 현재 노드가 부모 노드보다 작으면 연산은 종료

최대 힙 삭제 연산

- 최대 힙의 삭제 연산 순서

1. 트리의 루트를 제거

2. 루트부터 자식 노드와 비교하면서 현재 노드가 더 작을 경우, 

자식 노드와 자리 교환

3. 현재 노드가 자식 노드보다 크면 연산 종료

[ 허프만 코드 알고리즘 ]

입력 : 입력 파일의 n개의 문자에 대한 각각의 빈도수

출력 : 허프만 트리

​

1. 각 문자 당 노드를 만들고, 그 문자의 빈도수를 노드에 저장

2. n개의 노드의 빈도수에 대해 우선순위 큐 Q를 만든다.

3. while ( Q에 있는 노드 수 >= 2 ) {

4. 빈도수가 가장 작은 2개의 노드 (A와 B)를 Q에서 제거

5. 새 노드 N을 만들고, A와 B를 N의 자식 노드로 만든다.

6. N의 빈도수 = A의 빈도수 + B의 빈도수

7. 노드 N을 Q에 삽입한다.

}

8. return Q

​

​

[ 최종 이진 코드 설정 ]

알고리즘을 수행한 뒤에 완성된 힙 트리는 위와 같은 규칙으로 이진 코드를 작성하여 저장하게 되고 이렇게 저장된 코드가 곧 압축된 부분이라고 할 수 있습니다.

- 허프만 코드의 시간 복잡도

Line 1 : n개의 노드를 만들고, 각 빈도수를 노드에 저장하므로 O(n) 시간이 걸린다.

Line 2 : n개의 노드로 우선순위 큐 Q를 만들고 이 큐는 힙으로 구현하므로 O(n) 시간이 걸린다.

Line 3~7 : 

최소 빈도수를 가진 노드 2개를 Q에서 제거하는 힙의 삭제 연산과 새 노드를 Q에 삽입하는 연산을 수행하므로 O(logn) 시간이 걸린다. 그런데 while() 루프는 (n-1)번 반복되므로

(n-1)*O(logn) = O(nlogn) 이 걸린다.

Line 8 : 트리의 루트를 리턴하는 것은 O(1)의 시간이 걸린다.

따라서 시간 복잡도

== O(n)*O(n)+O(nlogn)+O(1) = O(nlogn)