[컴퓨터알고리즘] 13.2. 그리디 알고리즘 - 허프만 압축

Huffman Codes 허프만 압축 (허프만 코드)

- Binary character code. 각 문자는 고유 이진 문자열로 표현됨.

* Fixed-length code: 고정길이 방식 (6개 문자 나타내는데 3bit 필요.)

* Variable-length code: 가변길이 방식 (등장 빈도수 고려해 codeword 부여 가능. 자주등장-짧은 codeword. 굿)

 

Prefix Codes: 어떤 codeword도 다른 codeword의 접두사가 아님

- 인코딩과 디코딩에 용이. 각 문자를 나타내는 코드워드를 차례대로 concat하고 쪼개면 됨.

  (인코딩) "abc" -> 0.101.100 = 0101100 | (디코딩) 001011101 = 0.0.101.1101 -> "aabe"

- 문자는 이진트리의 리프노드로 달림. root~leaf 가는길에 0: 왼쪽자식으로, 1: 오른쪽자식으로.

- Prefix Codes의 BST 표현 (고정 길이, 가변 길이)

 

최적 가변 길이 코드에 대응되는 이진트리는 정이진트리 Fully Binary Tree (모든 내부 노드가 왼, 오 자식 가짐)

FBT -> |C| 개의 리프노드 가짐. C = {a,b,..,f}

C개의 외부노드 갖는 FBT는 C-1개의 내부노드를 갖는다.

 

허프만 코드 구성

- C를 바탕으로 우선순위 큐 Q를 구성한다.

- 가장 빈도수 적은 노드(EXTRACT-MIN(Q)) 두개를 골라 새 노드 z의 자식으로 연결한다.

   // 둘 중 왼쪽자식(0으로 연결)의 빈도 <= 오른쪽자식(1으로 연결)보다 빈도.  // z의 빈도 = x, y의 빈도 합

- 빈도수 높을수록 나중에 연결되며, 우선순위가 높다.

- 우선순위 같으면 알파벳순

Huffman(C)
    n = |C|
    Q = C
    for i = 1 to n-1
        new node z allocate()
        z.left = x = EXTRACT-MIN(Q)
        z.right = y = EXTRACT-MIN(Q)
        z.freq = x.freq + y.freq
        INSERT(Q,z)
    return EXTRACT-MIN(Q)

 

 

허프만 코드 알고리즘

- greedy choice 특성, optimal substructure 특성 가짐.

 

문제풀이

- 주어진 입력에 대해 허프만 압축을 수행하면 총 bit 수는?

- 글자를 허프만코드로 비트화시키고 (같은 빈도의 경우 알파벳순으로 함) 구현 코드로 인코딩, 디코딩하기