Huffman code

허프만 부호화 또는 허프만 코딩(Huffman coding)은 입력 파일의 문자 빈도 수를 가지고 최소힙을 이용하여 파일을 압축하는 과정이다. 허프만 코드(이진코드)는 Unix에서 파일압축에 사용되고, JPEG 이미지 파일 또는 MP3 음악 파일을 압축하기 위한 서브루틴으로도 활용된다.

 

주어진 문자열을 트리를 이용해 2진수로 압축하는 알고리즘 중 하나이다. 최소 힙을 이용한다.

고정 길이 코드(fixed length code) vs 접두어 코드(prefix code)

고정 길이 코드는 대표적으로 아스키 코드가 있다. 아스키 코드는 항상 8bit의 길이를 가지고있다. 다루기에는 간단하지만, 저장 공간 활용에 있어서 제한이 있다. 이를 해결하기 위해서 가변 길이 코드(variable length code)가 존재한다.

가변 길이 코드 중에서도 접두어 코드는, 앞서 나온 문자가 다음에 나올 문자의 접두어가 되면 안되는 특징을 가진 코드다. 예를 들면 다음은 접두어 코드가 아닌 예다.

위 코드에서 01은 010의 접두어이기 때문에 접두어 코드가 아니다. 반면 다음은 접두어 코드의 예다.

 

접두어 속성(prefix property) : 코드 집합의 어느 코드도 다른 코드의 접두어가 되지 않는 속성을 가지는 코드이다

 

예를 들어, 코드 집합 {"0","1","01","010"}은 접두어 코드가 아니다

 

{"00", "010", "100", "101"}은 어느 코드도 다른 코드의 접두어가 되지 않아 접두어 코드이다.

 

a = 00
b = 010
c = 100
d = 101
위 코드 대로라면 'abcd'는 00010100101로 표현한다
아스키 코드로 한다면 8비트가 4개 있으므로 32비트가 필요하지만 접두어 코드로 표현하면 11비트만 필요하다

 

 

이 접두어 코드를 아스키코드로 한다면? 총 24bit의 저장 공간을 소비한다. 반면에 압축한 상태 그대로 이진코드로 표현한다면 0110111로 7bit로 압축이 가능하게된다. 이처럼 입력 문자의 빈도수를 가지고 압축하는 것이 허프만 코딩이다.

 

 

 

 

 

 

 

허프만 코딩(Huffman coding)

 

 

 

인코딩

허프만 트리를 이용해서, 루트에서부터 순환한다. 이 때 왼쪽 자식을 탐색할 때는 0, 오른쪽 자식을 탐색할 때는 1을 출력한다. 리프 노드를 만나면 리프 노드에 저장되어 있는 문자를 출력한다. 그렇게 하면 숫자가 출력된 후, 그 숫자에 해당하는 문자가 나오게 된다.

압축 예제 abcacbcdcbcacdcacddd 문자열을 압축해 보자(총 글자수 20개, 20byte) 각 문자당 중복되는 갯수를 샌다 a - 4, b - 3, c - 8, d - 5 가장 작은 두 값을 골라낸다 a - 4, b - 3         ↓     [7]      │ ┌───┐ [a:4]   [b:3] 다시 가장 작은 두 값을 골라낸다 a+b - 7, d : 5           ↓           [12]            │      ┌───┐     [7]        [d:5]      │ ┌───┐ [a:4]   [b:3] 또 고른다 a+b+d - 12, c - 8               ↓                  [20]                   │             ┌───┐           [12]        [c:8]            │      ┌───┐     [7]        [d:5]      │ ┌───┐ [a:4]   [b:3] 이제 트리가 완성되었다 각 트리의 가지(edge)에, 왼쪽 가지에는 0, 오른쪽 가지에는 1을 부여합니다.                  [20]                   │            0┌───┐1           [12]        [c:8]            │     0┌───┐1     [7]        [d:5]      │ 0┌───┐1 [a:4]   [b:3] 상위 노드부터 순차적으로 훑어내린다 a = 000 b = 001 c = 1 d = 01 이제 아까 문자열을 압축해보자 abcacbcdcbcacdcacddd  => 000001100010011011001100010110001010101  총 47bit = 5byte 7bit이다 20byte였던 문자열이 1/4로 줄어들었다

  

디코딩

0101001같은 숫자가 주어졌다고 가정하자. 허프만 트리를 이용해서 주어진 숫자를 순서대로 하나씩 0이면 왼쪽 자식 Node를 탐색하고, 1이면 오른쪽 자식 Node를 탐색한다. 주어진 숫자를 끝까지 다 순회했을 때, 해당 노드에 저장된 알파벳이 디코딩 된 문자이다.

압축 해제 예제                  [20]                   │            0┌───┐1           [12]        [c:8]            │     0┌───┐1     [7]        [d:5]      │ 0┌───┐1 [a:4]   [b:3] 000001100010011011001100010110001010101  압축된 문자열에서 0이면 왼쪽으로, 1이면 오른쪽으로 검색한다                  [20]             ↓    │            0┌───┐1           [12]        [c:8]     ↓     │     0┌───┐1     [7]        [d:5] ↓   │ 0┌───┐1 [a:4]   [b:3] 압축된 문자열의 첫 글자는 'a' 라는 걸 알 수 있다 그 다음 문자는 'b' 이다

 

 

 

 

 

 

 

 

---

huffman 우선순위 큐 사용해서 구현

Huffman Codes Using Greedy Algorithm