[알고리즘] 허프만 코딩

허프만 코딩

원본 데이터에서 자주 출현하는 문자를 적은 비트, 출현 빈도가 낮은 문자를 많은 비트로 부호화해 데이터를 효과적으로 압축하는 방법입니다.

$C$를 $n$개의 문자로 이루어진 집합으로 두고 $c\in C$, $c.freq=c$의 빈도 수라고 둡니다. $Q$라는 $freq$가 key인 최소 우선순위 큐도 둡니다.

HUFFMAN(C)
n = |C| // n은 C의 크기
Q = C // Q를 C에 대해 초기화
for i=1 to n-1
  let z = new node; // 새로운 노드 z 할당
  z.left = x = EXTRACT_MIN(Q) // Q에서 최소 노드를 뽑아 x, z.left에 할당
  z.right = y = EXTRACT_MIN(Q) // Q에서 최소 노드를 뽑아 y, z.right에 할당
  z.freq = x.freq + y.freq // Q에서 freq이 최소인 원소 두 개를 빼 새로운 노드의 자식으로 두고, 새로운 노드의 freq를 두 노드의 freq의 합으로 함
  INSERT(Q, z) // Q에 z를 삽입함
return EXTRACT_MIN(Q) // 루트 노드 반환

$d_T(a)$는 $a$의 트리 $T$에서의 깊이, $B(T)$는 트리의 비용을 의미합니다.

보조 정리 1

$x, y$가 가장 낮은 빈도 수를 갖는 2개의 $C$의 문자일 때, $x$와 $y$에 대한 허프만 코드는 길이가 같고 마지막 비트만 다릅니다.

 

이를 증명하기 위해 $T$라는 $C$에 대한 임의의 최적 prefix 코드를 나타내는 트리를 생각해봅니다. 이 $T$에서 가장 큰 깊이를 가진 sibling을 $a, b$라고 둡니다. $(a.freq\le b.freq, x.freq\le y.freq)$ 그러면 $x.freq\le a.freq, y.freq\le b.freq$입니다. 이후 $T$에서 $a$와 $x$, $b$와 $y$의 위치를 교환합니다. 그러면 $x, y$가 최대 깊이의 sibling이 됩니다.

$\text{교환 비용} (x, y) = x.freq*d_T(x) + a.freq*d_T(a) - x.freq*d_{t'}(x) - a.freq*d_{T'}(a) = (a.freq - x.freq)(d_T(a)-d_T(x))\gt 0$입니다. $a.freq\ge x.freq$이고 $d_T(a)\ge d_T(x)$이기 때문입니다. $(b, y)$에 대해서도 마찬가지입니다. 따라서 $B(T'')\le B(T)$이고, 전제에서 $T$가 최적의 prefix 트리이므로 $B(T)\le B(T'')$, 따라서 $B(T'')$는 $x, y$를 최대 깊이의 sibling으로 갖는 최적 prefix 트리입니다.

 

보조 정리 2

$C'$를 $C$에서 최소 빈도수를 가진 두 문자 $x,y$를 제거하고 $z.freq=x.freq+y.freq$인 문자 $z$를 추가한 집합이라고 둡니다. $T'$라는 트리를 이 $C'$에 대한 최적의 prefix 트리라고 합시다. 이 때 $T'$에서 $z$에 해당하는 노드를 $x, y$를 자식으로 가진 노드로 교체한 트리 $T$는 $C$에 대한 최적의 prefix 트리입니다.

 

$c\in C - \{x, y\}$에 대해 $d_T(C)=d_T(C')$입니다. 또, $d_T(x)=d_T(y)=d_T(z)+1$임은 자명합니다. 따라서 $x.freq*d_T(x)+y.freq*d_T(y)=(x.freq+y.freq)(d_{T'}(z)+1)=z.freq*d_{T'}(z)+x.freq+y.freq$입니다. $B(T)=B(T')+x.freq+y.freq$인 것이죠. 이 때 만약 $T$가 $C$에 대한 최적 prefix 트리가 아니라고 가정해봅시다. $x$와 $y$를 sibling으로 갖는 $B(T'')<B(T)$인 트리 $T''$가 존재한다는 것입니다. 이 $T''$에서 $x$와 $y$의 공통 부모가 $z.freq=x.freq+y.freq$인 노드 z로 교체된 새로운 트리인 $T'''$를 생각해보면, $B(T''')=B(T'')-x.freq-y.freq<B(T)-x.freq-y.freq<B(T')$인 것인데요. $B(T')$가 $C'$에 대한 최적 prefix 트리이므로 모순이 생깁니다. 따라서 $T$가 $C$에 대한 최적 prefix 트리입니다.