허프만 압축(Huffman Coding)

허프만 압축(Huffman Coding)

• 문자를 0과 1로 표현하여 압축하는 방법이다.

• 접두부 특성(Prefix Property)가 존재한다.

  • 압축된 이진 코드가 다른 이진 코드의 접두부가 되지 않는 특성을 의미한다.

  • https://ko.wikipedia.org/wiki/%EC%95%9E%EC%9E%90%EB%A6%AC_%EB%B6%80%ED%98%B8

  • 예를 들면, 변환된 이진 코드가 {1, 10} 두 가지라면 "1"은 "10"의 앞부분에 포함되므로 이는 접두부 특성이 없는 것이다.

  • 반면에 {0, 10} 의 경우 "0"과 "10"은 반드시 구분되므로 접두부 특성을 가진다.

---

알고리즘

• 각 문자의 출현 빈도수에 따라 이진 코드를 할당한다.

  • 빈도수가 많을수록 짧은 이진 코드를 할당하는게 효율적이다.

  • 이진 트리와 우선순위 큐를 사용한다.

    Pseudo Code

    HuffmanTree HuffmanCoding(문자 각각에 대한 빈도수)
    {
      각 문자에 대해 빈도수를 저장하는 노드를 생성한다.
      빈도수에 대한 우선순위 큐를 만들고 모든 노드를 큐에 넣는다.
      while (큐에 노드가 2개 이상일 경우)
      {
        빈도수가 가장 작은 2개의 노드를 큐에서 pop한다.
        새 노드를 만들어 위에서 pop한 2개의 노드를 자식 노드로 만든다.
        새 노드의 빈도수는 각 노드의 빈도수의 합이다.
        새 노드를 우선순위 큐에 삽입한다.
      }
      return (Q에 남은 노드);
    }

예제

• 문자 A, G, C, T에 대한 빈도수가 각각 450, 120, 270, 90일 경우 다음과 같은 순서를 따른다.

  

• 결과적으로 A, G, C, T는 각각 허프만 코드로 0, 100, 11, 101이 된다.

• 이진 트리의 특성에 따라 빈도수가 높을 수록 루트 노드와 가까우므로 짧은 코드에 대응되고, 접두부 특성을 지님을 알 수 있다.

• 압축비

  • 허프만 코드로 변환하기 전 문자들의 용량은 (450 + 120 + 270 + 90) * 1byte * 8bit/1byte = 7440bit이다.

  • 변환 후의 용량은 (450 * 1) + (120 * 3) + (270 * 2) + (90 * 3) = 1620bit이다.

  • 따라서 압축비 = (압축 전 크기) / (압축 후 크기) = 7440 / 1620 = 4.593 이다.

    • 약 1/4.6의 크기로 압축된 것을 알 수 있다.

---

시간 복잡도

• 각 빈도수를 노드에 저장할 때 O(n) 시간이 걸린다.

• 우선순위 큐로 힙 자료구조를 사용하면 O(n) 시간이 걸린다.

• 루프는 (n - 1)번 반복된다.

  • 큐에서 최소 빈도수 노드 2개를 삭제 후 새 노드를 큐에 다시 삽입하는 과정에서 O(logn)이 걸린다.

  • 즉 루프의 시간 복잡도는 O(nlogn)이다.

• 따라서 허프만 코딩의 시간 복잡도는 O(nlogn)이다.