허프만 코딩

허프만 코딩

---

• 문자의 빈도를 이용해 압축하는 방법으로 빈도가 높은 문자는 적은 비트로, 빈도가 낮은 문자는 높은 비트로 표현하여 필요한 비트 수를 줄여 압축하는 방식(-> 높은 압축률)
• 문자열 압축을 위해 허프만 트리를 사용함
  • 각 문자에 대한 출현 빈도수를 구하여 내림차순으로 정렬한 뒤 빈도수가 가장 낮은 두 값을 자식 노드로, 빈도수의 합을 부모노드로 하는 연산을 반복적으로 수행하여 트리를 구성함
  • 허프만 트리를 구성하면 모든 문자열은 리프노드에 위치함
  • 왼쪽가지를 1, 오른쪽 가지를 0으로 표현하여 리프노드(문자열)에 노드에 도달하는데 거쳐가는 비트로 문자열 표기
    -> 문자열이 모두 리프노드에 위치하므로 문자열 간에 접두부가 겹치지 않음
    -> 문자열을 표현하는데 겹치는 비트가 없으므로 압축 이후 데이터 손실이 발생하지 않음
• http2 헤더 압축에 사용됨
• 구현이 단순하여 복원에도 효과적

 

허프만 압축 과정

아래 문자를 허프만 코딩을 통해 압축해보자.

apple banana

 

빈도수 기반으로 정렬하면 아래와 같을 결과를 얻는다.

 

[1회전]

1. 빈도수 내림차순 정렬

a(4), p(2), n(2), l(1), e(1), 공백(1), b(1)

 

2. 가장 마지막 값 두개로 허프만 트리 구성

 

3. 허프만 트리 포함하여 재정렬

 

[2회전]

 

[3회전]

 

[3회전]

[4회전]

 

[5회전]

 

위와 같이 연산을 수행하면 최종적으로 위의 허프만 트리를 구성하게 된다.

각 문자열에 표현되는 비트를 보면

a: 01
p: 101
n: 100
공백: 1111
b: 1110
l: 1101
e: 1100

 

빈도수가 가장 높은 문자열이 적은 비트수로 표현되고, 접두부가 겹치는 문자열이 하나도 없기에 복원과정에서 데이터 손실 가능성이 없다.

허프만 트리는 최대힙의 구조를 보인다.

따라서 시간복잡도 또한 힙정렬과 같은 O(NlogN)이다.