Chap 4-7. 허프만 압축

파일을 저장할 때 최대한 작게 저장하는 것이 효율적일 것이다.

데이터 압축 문제는 데이터를 코드화하는 효율적인 방법을 찾는 것이다.

(1) 허프만 코드라고 하는 코드화 방식

(2) 주어진 파일을 허프만 코드화하는 탐욕적인 알고리즘

 

파일은 기본적으로 이진코드를 사용해서 표현한다.

코드화 방식에서 각각의 문자는 코드워드라고 하는 유일한 이진 문자열로 각 문자를 표현한다.

이 중 길이가 고정된 이진 코드는 각각의 문자를 표현하는 bps가 일정하다.

 

예를 들어 a, b, c를 코드화한다.

a : 00, b: 01, c:11

ababcbbbc ⇒ 000100011101010111 (18비트가 필요함)

그러나 길이가 변하는 이진 코드를 사용하면 좀 더 효율적인 코드화 방식을 사용할 수 있다.

→ 각 문자를 다른 길이의 비트로 표현한다.

 

[변경후]

가장 빈번하게 나왔던 문자인 b를 0으로 한다면

a:10, b:0, c: 11

⇒ 1001001100011 (13비트만으로 표현 가능)

 

 

→ 주어진 파일의 구성 요소인 각 문자를 어떤 이진 코드로 나타내는 것이 파일을 저장할 때 가장 적은 공간을 필요로 하게 하는지 찾아내는 것이 “최적 이진 코드 문제”라고 함

 

이 문제를 그리디 알고리즘으로 풀 수 있고 대표적인 것이 허프만 압축이다.

 

- 파일의 각 문자가 8 bit 아스키 (ASCII) 코드로 저장되면, 그 파일의 bit 수는 8 x (파일의 문자 수)

- 파일의 각 문자는 일반적으로 고정된 크기의 코드로 표현

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

- 파일의 크기를 줄이는 방법을 파일 압축 (file compression)이라 함

 

아이디어

• 허프만 (Huffman) 압축은 파일에 빈번히 나타나는 문자에는 짧은 이진 코드를 할당하고, 드물게 나타나는 문자에는 긴 이진 코드를 할당
• 허프만 압축 방법으로 변환시킨 문자 코드들 사이에는 접두부 특성 (prefix property)이 존재

      *접두부 특성 = 문자를 헷갈리게 하지 않기 위해 (모호성 없애기)

           ⇒ 모호성 없이 쉽게 복호화하여 각 문자를 복호화할 수 있다.

 

각 문자에 할당된 이진 코드는 어떤 다른 문자에 할당된 이진 코드의 접두부 (prefix)가 되지 않는다.

이러한 성질을 만족하는 가변 길이 이진코드를 prefix code라고 한다.

[예제] 문자 ‘a’에 할당된 코드가 ‘101’이라면, 모든 다른 문자의 코드는 ‘101’로 시작되지 않으며 또한 ‘1’이나 ‘10’도 아니다.

 

• 문자의 이진화나 복호화 과정은 이진트리를 통해 쉽게 표현할 수 있다.

      루트로부터 단말 노드로 가는 경로에 의해서 이진코드가 표현되어 지는데 왼쪽으로 가면 0 오른쪽으로 가면 1로 해석하면 된다. 그렇게 단말노드까지 간다.

 

이진트리에 의해서 부호화해서 필요한 전체 비트 =  문자의 빈도수 * 문자의 길이 (2자리라면 노드가 2개 필요) 

 

계산식

a:10, b:0, c: 11 이라면 

⇒ 1001001100011 (13비트만으로 표현 가능)

 

빈도수 계산식

 

[알고리즘]

HuffmanCoding
입력: 입력 파일의 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 // 허프만 트리의 루트를 리턴

[구체적인 과정] 

typedef struct node {

	int freq; //빈도수 
	struct node* left, right;

}Node;

**ALg.HuffnamTree**

Input: freq of char n, PQ(우선순위 큐)
Output :HT(허프만 트리)

for i = 1 to n-1:
  remove(PQ, a)//빈도수가 작은 애 
  remove(PQ, b)//두 번째로 빈도수가 작은 애 
  r = new Node //새로운 노드를 만든다. r은 부모 노드임
  r-> left = a
  r -> right = b
  r-> freq = a-> freq + b-> freq
  insert(PQ, r)

 

- 먼저 빈도수가 가장 적은 글자와 그 다음 적은 글자를 골라서 노드에 넣는다.

- 이 둘의 빈도수를 더한 것이 부모노드의 값이 된다.

- 그리고 이 둘은 전체 집합에서 삭제한다.

- 이 과정을 반복하고 마지막에는 루트 노드를 반환한다.

 

압축률

할당된 코드들을 보면, 가장 빈도수가 높은 글자가 가장 짧은 코드를 가진다.

즉, 루트의 자식이 되어있는다.

하지만 빈도수가 낮은 문자는 루트에서 멀리 떨어지게 되어 긴 코드를 가진다.

• -이렇게 얻은 코드는 접두부 특성을 가지게 되므로 왼쪽부터 차례대로 읽기만 하면 어떤 글자인지 모호성없이 읽을 수 있다.
• 아스키코드로 한다면 8비트가 고정되어 있지만 압축을 한다면 고정되어있지 않으므로 압축 가능하다.

 

시간 복잡도

(알고리즘 한 줄 별 시간 복잡도)

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

           : n개의 노드를 만들고 각 빈도수를 노드에 저장 ⇒ O(n)

 

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

           : n개의 노드로 우선순위 큐Q를 만든다.

            여기서 우선순위큐로서 이진 힙 자료 구조를 사용하면 O(n) 시간이다. 

 

Line 3 ~ 7 =
3. while Q에 있는 노드 수 ≥ 2 
4. 빈도수가 가장 적은 2개의 노드 (A와 B)를 Q에서 제거
5. 새 노드 N을 만들고, A와 B를 N의 자식 노드로 만든다
6. N의 빈도수 = A의 빈도수 + B의 빈도수 7. 노드 N을 Q에 삽입

       : 최소 빈도수를 가진 노드 2개를 Q에서 제거하는 힙의 삭제 연산과 새 노드를 Q에 삽입하는 연산을 수행하므로             O(logn)시간 소요 (가장 아래 레벨까지 내려가야 하므로 트리의 높이 만큼의 시간이 걸림)

 

Line 8 =
트리의 루트를 반환하는 것이므로 O(1) 시간

    시간 복잡도 = O(n) + O(n) + O(nlogn) + O(1) = O(nlogn)