[알고리즘] Huffman code / 허프만코드

📕Huffman code 란?

---

압축은 자료의 크기를 줄이기 위해서 사용된다.
그리고 이 압축을 하는 방식에 따라서 압축된 파일의 용량이 달라질 수 있는데, 
그 중 Huffman code는 문자의 출현 빈도에 따라서 다른 길이를 사용하여 압축하는 알고리즘이다.
Huffman code도 그리디 알고리즘의 일종이다.
 
허프만코드는 데이터를 매우 효율적으로 압축하는데, 20~90%의 용량을 아낄 수 있다.
 
허프만 코드는 prefix-free* codes로 표현된다.
prefix-free코드는 어떠한 문자라도 항상 최적의 데이터 압축을 보장한다.
(*prefix codes가 표준 표기이긴 하지만, prefix-free codes가 좀 더 맞는 이름이기 때문에 여기에서는 prefix-free codes로 표기하겠다)
 
참고로 '데이비드 허프만'이라는 사람이 '박사과정 중'에 처음으로 논문을 발표하여 소개된 알고리즘이라고 한다.
 

📕압축의 예시 : Run-length encoding, genomic code

---

다음과 같은 숫자를 압착한다고 생각해보자.
0000000000000001111111000000011111111111
위의 숫자는 15개의 0, 7개의 1, 다시 7개의 0, 11개의 1로 이루어져있다.
 
이를 4비트로 변환하여 나타낸다고 하면
1111 0111 0111 1011으로 나타낼 수 있다. (1과 0을 구분하는 것을 제외하고)
 
이는 기존의 숫자를 저장하려면 40비트가 필요한 것에 비해, 16비트만을 필요로하기 때문에 저장용량 측면에서 큰 이점이 있다.
만약 4비트의 한계인 15를 넘는다면 숫자 중간에 0000을 삽입하여 알려줄 수 있다.
19 -> 1111 0000 0100 => 15 + 4 = 19 와 같은 방식으로 말이다.
 

---

유전자 코드의 경우를 살펴보자.
우리의 염기서열은 DNA는 A(아데닌), C(사이토신), T(티민), G(구아닌)으로 이루어져있다.
염기서열을 ASCII코드로 변환하여 이진수로 나타내면 다음과 같다.



이렇게 이진수로 표현하기 위해서는 8비트가 필요하다.
이와는 다른 방법인 이진수 코드로 지정해서 나타내면 다음과 같이 나타낼 수 있을것이다.
 

위와 같이 나타낼 경우 2비트만을 필요로 한다.
그렇기 때문에 첫번째 경우로 표기하는 것보다 두 번째 경우로 표기하는 것이 훨씬 공간을 절약할 수 있다.
 

📕Huffman coding

---

허프만 코드에  특징 중 하나는 문자마다 모두 다른 비트 수를 사용해서 압축을 한다는 것이다.
그렇기 때문에 발생할 수 있는 문제점이 하나 있는데, 바로 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  두가지로 표기 할 수 있게 된다.
그렇기 때문에 모호성이 생긴다.
 
모스부호 역시 비슷한 예시이다.
 
그렇다면 이러한 문제를 어떻게 제거할 수 있을까?
이때 필요한 것이 바로 prefix-free codes의 개념이다.
 
모호성은 허프만 코드가 문자마다 다른 길이의 코드를 사용하기 때문에  
어디서 부터 다음 문자가 시작하는 지 모른다기 때문에 발생한다.
그렇기 때문에, 어떠한 문자도 다른 문자의 prefix를 가지지 않으면 된다.
 
prefix-free code의 예시를 살펴보자.
{A, B, C, D} = {0, 10, 110, 111}
 
위와 같이 표기할 경우 어떠한 문자도 다른 문자의 prefix가 되는 경우가 없다.
그렇기 때문에, 문자의 시작을 명확하게 구분할 수 있는 것이다.
 

---

허프만 코드의 또 다른 특징은 바로 문자의 출현 빈도에 따라 나타내는 비트 수가 다르다는 것이다.
아래의 표를 보자.

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)이다.