허프만 코드

Huffman Coding

허프만 코드는 손실이 적은 데이터 압축 알고리즘이다. 기본 아이디어는 가변길이 코드를 문자로 할당하는 것이다. 할당된 코드의 길이는 일치하는 문자의 빈도에 기본으로 한다. 가장 빈도수가 많은 문자는 가장 작은 코드를 할당 받고 가장 빈도가 적은 문자는 큰 코드를 할당 받는다.

입력문자에 할당 된 가변 길이 코드는 접두사 코드이다. 이는 한 문자에 할당된 코드가 다른 문자에 할당 된 코드의 접두사가 아닌 방식으로 코드가 할당되었음을 의미한다. 이것은 허프만 코딩가 생성 된 비트 스트림을 디코딩 할 때 애매함이 없는지 확인하는 방법이다.

카운터 예제로 접두사 코드를 이해해보자. a,b,c,d의 카운터가 있고 각각 일치하는 코드는 00, 01, 0, 1이다. c 코트가 a와 b의 접두사이기 때문에 이 코드는 모호하다. 만약 0001의 압축된 비트 스트림이 있다면 디코딩된 코드 스트림은 "cccd", "ccb", "acd", "ab" 일 수 있다.

허프만 코드의 응용은 다음과 같다.

• 호프만 코드는 두개의 주요 부분이 있다.

  1. 주어진 input 문자로 부터 허프만 트리를 작성한다.
  2. 허프만 트리를 순회하면서 코드에 문자를 할당한다.

 

허프만 트리 만드는 방법

고유 한 문자의 배열과 해당 문자의 빈도이며 출력은 허프만 트리이다.

1. 고유 문자와 빈도를 담는 리프노드를 만들어 최소 힙에 저장한다(최소힙은 우선순위 큐를 사용하다. 최소 힙을 구성하기위해 빈도수를 비교 대상으로 한다. 빈도가 낮은 문자가 최소힙의 루트이다.)
2. 빈도가 낮은 2개의 노드를 구한다.
3. 두 노드를 좌, 우 자식으로 하는 새로운 노드를 만든다. 부모노드의 값은 두 노드의 빈도의 합과 같다. 이 노드를 다시 최소 힙에 넣는다.
4. 최소 힙이 1개의 노드를 갖을 때까지 #2, #3번 과정을 반복한다. 남은 노드는 완성된 트리의 루트이다.

 

 

​x
character   Frequency
    a            5
    b           9
    c           12
    d           13
    e           16
    f           45
   

step 1

각 노드가 트리의 루트를 대표하는 싱글 노드 6개로 최소 힙을 만든다.

 

Step 2

최소 힙에서 최소 빈도의 두개의 노드를 꺼낸다. 두 노드의 빈도의 합을 루트로 하는 노드를 생성한다. 생성된 노드를 다신 최소힙에 넣는다.

4개의 노드와 3개의 노드를 같는 1개의 트리를 갖는다.

xxxxxxxxxx
character           Frequency
       c               12
       d               13
 Internal Node         14
       e               16
       f                45

 

Step 3

힙으로 부터 두개의 노드를 얻어와 step2의 과정을 반복한다.

이제 최소 힙은 다음과 같다.

xxxxxxxxxx
character           Frequency
Internal Node          14
       e               16
Internal Node          25
       f               45

 

Step 4

이제 최소 힙은 세개의 노드를 갖는다.

xxxxxxxxxx
character          Frequency
Internal Node         25
Internal Node         30
      f               45 

 

Step 5

xxxxxxxxxx
character     Frequency
       f         45
Internal Node    55

 

Step 6

마지막으로 최소힙이 하나의 노드를 갖는다.

최소힙이 하나일 경우 알고리즘을 멈춘다.

xxxxxxxxxx
character      Frequency
Internal Node    100

 

허프만 트리를 출력하는 방법

루트부터 시작하여 완성된 트리를 순회한다. 왼쪽 자식으로 이동하면 배열에 '0'을 쓴다. 오른쪽자식으로 이동하면 배열에 '1'을 쓴다. 리프노드를 만나면 배열을 출력한다.

*해당 페이지는 https://www.geeksforgeeks.org/huffman-coding-greedy-algo-3/ 를 해석한 글입니다.