[알고리즘] 허프만 코드란?

 

✅Huffman code

데이터를 압축하는 알고리즘이다. 데이터의 각 글자 빈도수를 알고 있을 경우 데이터를 압축하는 데 효과적이다.

 

예를 들어 e : 15번 | t : 12번 | n : 8번 | i : 6번 | s : 4번 의 빈도로 나타난 데이터가 있다고 해보자. 이 데이터를 압축하고자 하는 것이 우리의 목적이며 이를 위해 허프만 트리를 사용할 것이다.

 

1️⃣ 빈도수가 작은 것부터 차례대로 정렬한다. s : 4번 | i : 6번 | n : 8번 | t : 12번 | e : 15번

2️⃣ 빈도가 가장 작은 것부터 모아 트리로 엮는다. 부모노드는 각 노드의 빈도수를 합친 수다.

3️⃣ 부모노드의 값보다 작은 것이 있을 경우 그 부모노드와 작은 값의 노드를 연결, 다시 두 값을 합친 트리를 만든다. 이때 부모노드 값보다 작은 것이 2개라면? 기존 부모 노드와 엮지 말고 새로운 자식-부모 관계를 만든다. 이를 반복한다.

이게 바로 우리가 원하는 모양의 허프만 트리다. 이때 왼쪽 자식은 1, 오른쪽 자식은 0을 가진다. 즉,

다음과 같은 모양이 된다. 이렇게 우리가 n을 찾는다면 값은 11이 된다. s는 101, i는 100, t는 01, e는 00이라는 값을 갖는다. 빈도가 높은 것은 짧은 코드를, 빈도가 낮은 것은 긴 코드를 가지니 효율적이다.

 

https://github.com/Jujinsol/algorithm/blob/3dbb65d7ac9e3ff82aba0ad80913076066f1f77b/etc/Huffman.c