[Algorithm] 허프만 코드(Huffman code)

안녕하세요! 여러분 오늘은 허프만 코드(Huffman code)에 대해서 공부해 봅시다:)

---

Huffman code란 무엇일까?

압축(compression)은 자료의 크기를 줄이기 위해서 사용합니다.

이 압축을 하는 방식에 따라서 압축된 파일의 용량이 달라질 수 있는데,

그 중 Huffman code는 문자의 출현 빈도에 따라서 다른 길이를 사용하여 압축하는 그리디 알고리즘(greedy algorithm)입니다.

 

Huffman code는 데이터를 매우 효율적으로 압축합니다. 경우에 따라 20%~90%의 용량을 아낄 수 있습니다.

 

Huffman code는 prefix-free* codes로 표현됩니다.

prefix-free코드는 어떠한 문자라도 항상 최적의 데이터 압축을 보장합니다.

(*prefix codes가 표준 표기입니다.)

 

---

Compression의 예시

다음의 숫자를 압축한다고 생각해 봅시다.

0000000000000001111111000000011111111111

0: 15개, 1: 7개, 0: 7개, 1: 11개로 이루어져 있습니다.

 

이를 4bit로 변환하여 나타낼 때,

1111 0111 0111 1011로 나타낼 수 있습니다.

 

이는 기존의 숫자를 저장하려면 40bit가 필요한 것에 비해,

16bit만 필요로 하기 때문에 저장용량 측면에서 효율이 좋습니다.

만약 4bit의 한계인 15를 넘는다면 숫자 중간에 0000을 삽입하여 알려줄 수 있습니다.

 

ex) 19 : 1111 0000 0100 = 15 + 4와 같은 방식

 

---

Huffman code

Huffman code의 특징 중 하나는 문자마다 모두 다른 비트 수를 사용해서 압축을 한다는 것입니다.

그렇기 때문에 발생할 수 있는 문제점이 바로 Ambiguity 모호성입니다.

 

아래 예시를 봅시다.

 

Suppose Σ = {A, B, C, D} is encoded using variable-length code {0, 01, 10, 1}. 
What is 001 an encoding of?

 

A) AB     B) CD       C) AAD      D) Not enough information to answer the question

 

001을 주어진 2진수로 표현할 경우 0-0-1 그리고 0-01 두 가지로 표기할 수 있게 됩니다.

그렇기 때문에 모호성이 생깁니다.

 

모호성은 Huffman code가 문자마다 다른 길이의 코드를 사용하기 때문에어디서부터 다음 문자가 시작하는지 모르기 때문에 발생합니다.

그렇기 때문에, 어떠한 문자도 다른 문자의 prefix를 가지지 않으면 안 됩니다.

 

prefix-free code의 예시를 살펴보자.

{ A, B, C, D } = { 0, 10, 110, 111 }

 

위와 같이 표기할 경우 어떠한 문자도 다른 문자의 prefix가 되는 경우가 없습니다.

그렇기 때문에, 문자의 시작을 명확하게 구분할 수 있는 것입니다.

---

Huffman code의 또 다른 특징은 바로 문자의 출현 빈도에 따라 나타내는 비트 수가 다르다는 것이다.

A	60%	00	0
B	25%	01	10
C	10%	10	110
D	5%	11	111
합계	frequencies	fixed-length	variable-length(prefix-free)

위의 표는 문자의 출현 빈도에 상관없이 고정된 길이를 사용하는 코드와
문자의 출현 빈도에 따라 길이가 다른 길이를 사용하는 varible-length코드와의 비교입니다.
 
fixed-length코드를 사용하면 2비트 만을 필요하기 때문에 공간적인 측면에서 절약이 가능하지만
한 코드가 다른 코드의 prefix가 될 수 있기 때문에 모호성이 발생합니다.
 
variable-length코드의 경우는 문자에 따라 사용하는 비트가 1~3 비트로 각각 다르며, 공간적인 절약을 항상 보장할 수 없지만
prefix-free 코드이기 때문에 모호성이 발생하지 않습니다.
 
그렇기 때문에 variable-length encoding 방식으로 압축할 경우
평균적으로 1.55의 공간을 필요로 하기 때문에 평균적으로는 fixed-length 인코딩 방식의 평균 2보다 
더 나은 효율성을 보여줍니다.

---

Code as Trees

위의 과정에서 어떻게 인코딩을 하는지 알아보았다면,
이제는 인코딩을 어떻게 더 효율적으로 하는지 알아보자.
 
문자열을 이진수로 변환한 코드는 이진트리로 나타낼 수 있다.
그리고 huffman코드를 이진 트리로 변환할 때는 아래의 규칙에 따라 변환한다.

1.  Characters in leaves
2. Codeword is path from root to leaf



첫 번째 트리는 {A, B, C, D}는 {0, 01, 10, 1} 로 표현된다. 하지만 이는 prefix-free코드가 아니기 때문에 모호성이 발생한다.
두 번째 트리는 {A, B, C, D} 는 {0, 10, 110, 111}로 표현되어 있다. 
첫 번째 트리는 허프만 코드 트리 구성의 첫 번째 규칙을 위반했다. 
두 번째 트리는 각각의 문자 모두 leaf node에 위치하고 있고, codword가 root에서 leaf로 가는 길목에 있기 때문에
이는 올바르게 구성한 트리이다.
 
트리를 살펴보면 목표 노드까지 거쳐온 간선에 표시된 코드가 바로 목표 노드의 코드임을 알 수 있다.
 
 

위의 두 코드가 있다.
둘 다 prefix-free codes로 작성되어 있지만
같은 문자열을 표기하는데 한 코드는 30bit를 필요로 하고, 다른 코드는 29비트를 필요로 한다.
 
어떤 코드가 더 효율적일까?
 
두 번째 코드가 효율적이라고 말하고 싶겠지만, 아쉽게도 더 효율적인 코드는 첫 번째 코드이다.
 

 
위의 사진은 각각의 문자열을 트리 형태로 나타낸 것이다.
첫 번째 코드가 더 효율적인 이유는 바로 트리의 평균 비용 때문이다.
 
L(T) = 𝜮 Pi * [depth of i in T]
ABRACADABRA! 의 문자열에서 총길이 12중 A가 5번, B가 2번, C가 1번, D가 1번, R이 2번,! 가 1번 출연헀다.
 
이 평균 출현율과 문자열 길이를 곱해서 평균 비용을 계산하면 첫 번째 트리로 구성한 비용이 두 번째 트리로 구성한 비용보다 저렴하다.
 
 

---

How to build a tree?

Huffman code가 그리디 알고리즘이라고 했는데, 
트리를 구성할 때 탐욕법이 사용된다.
 
우리는 Huffman code로 트리를 구성할때 Bottom-up방식으로 병합하며 트리를 구성한다.
 

위와 같은 방식으로 병합하는데, 병합하는 기준은 바로 출현 빈도이다.
위의 경우 A가 60%, B가 25%, C가 10%, D가 5%로 출현 빈도가 낮은 순으로 병합하여 트리를 구성한 것이다.

트리의 구성 방식을 의사 코드로 구현하면 다음과 같다.

HUFFMAN(C)
n = length of C
Queue = C

for i = 1 to n-1
	allocate a new node z
    z.right = x = Extract_Min(Queue)
    z.left = y = Extract_Min(Queue)
    z.freg = x.freq + y.freq
    Insert(Q,z)
  
return Extract_Min(queue)

그래서 우리는 huffman code를 사용할 때 주로 힙 자료구조를 사용한 우선순위 큐를 사용하며,
이때 사용되는 힙은 min_heap이다.
 

---

Time complexity

Using binary heap -> O(N*log N)
N is number of codeword
 
Min_heap을 구성하는데 필요한 시간은 O(n)이고
탐색에는 for 문을 활용하여 n-1번 반복하여 힙을 탐색하기 때문에 O(logn) 시간이 필요하므로
전체 실행 시간 복잡도는 O(n*log n)이다.