ㄷㅣㅆㅣ's Amusement

huffman code 작성법 본문

Programming

huffman code 작성법

ㄷㅣㅆㅣ 2015. 11. 21. 16:51

huffman code 작성법

반응형
문제. 다음은 파일 압축에 활용하기위한 huffman code 작성의 단계이다.
 1) A,B로만 이루어진 파일일 때. (A -> B 순서로 빈도수 내림차순)
      0
   /      \
  0        1
 --> A : 00, B: 01

2) A,B,C로 이루어진 파일일 때.
      0
   /      \
  0        1
            / \
           0   1
--> A: 00, B:010, C:011, (A -> B -> C 순서로 빈도수 내림차순)

문제 : A,B,C,D,E로 이루어진 파일일 때 "E"의 코드로 알맞은 것은? (단, A -> B -> C -> D -> E  순서로 빈도수 내림차순)
가. 0010
나. 0100
다. 0111
라. 0011


위와 같은 문제는 IT기업의 신입 개발자 선발을 위한 필기 문제로 다분히 많이 출제된다.

왜냐하면... 누구나 다 트리를 읽는것은 할줄 알지만, 트리를 만드는 것을 할줄 아는 사람은 드물기 때문.


허프만 코드에서 어째서 트리얘기가 나오는가? 하는 의문이 든다면... 당장 "파일구조"시간에 배운 허프만 코드를 복습해보자.

허프만코드는 "botom - up 구조의 트리"로 만들어진다. (https://en.wikipedia.org/wiki/Huffman_coding)


앞에서 말한대로, B트리, B+트리 등등을 중위 후위 전위 등등 순서에 맞게 순회하는 것은 누군들 못하겠는가? 하지만 이런 식으로 트리를 구성할 줄 아는 사람은 그 자체로 "코딩을 해본 사람"이라고 평가될 수 있다.

그렇기 때문에 지금은 절대로 쓰이지 않을 "허프만 코딩에 의한 파일 압축"을 어거지로 땡겨와서 문제에 출제하는 것이다.


그럼 어떻게 구성할 것인지 알아보자.

허프만 코드를 bottom up방식이라고 하는 이유는, B,B+트리처럼 (무론 이것도 bottom up 으로 구성하기도 한다) 들어오는대로 트리를 구성하고 나중에 균형을 맞추는 작업을 하지 않고, 레코드의 종류가 어떤 것들이 있는지 미리 파악하고 나서 트리를 구성하는 방식이기 때문이다.  또한 개념적으로도 트리를 구성할 때, 레코드의 이름을 먼저 적고나서 선을 긋는다.


결론 - 허프만 부호화 방법

준비) 모든 문자를 빈도수로 정렬하여 나열한다. (위의 예에서는 모든 문자의 빈도가 같으므로 출현 순서대로 한다)

1) 가장 낮은 빈도가 낮은 문자 2개를 골라 부모노드를 가지는 부트리를 구성하고 자식 노드를 생성한다. --> 이것이 문제의 예시에서나온 1)번 구성이라고 보면 된다.

2) 부모노드단 문자들의 빈도수를 더하여 주 노드에 할당하고 순서에 맞도록 삽입한다.

3) 정렬한 문자열에서 부모가된 문자를 삭제한다.


글로 쓰면 어렵다.. 그런데 문제의 예시에 나와있는 것처럼 점진적으로 트리를 정리해 나가면 결과적으로는 다음과 같다.

                         0

              /    \
            A       1
                    /    \
                  0       1

                           / \      / \

                         B  C  D  E


허프만 코딩처럼 원시적이고 간단한 트리 구성법도 드물다. 그러니 이런 기초적인 트리구성은 알고 시험에 임하자.

반응형

'Programming' 카테고리의 다른 글

[VoIP] WebRTC Components  (0) 2021.05.16
[AI] AVS Architecture - Alexa Voice Service SDK  (0) 2018.04.11
네이버 웹마스터 도구에서 robotDenied 오류 해결  (1) 2015.11.26
엑박의 압박  (0) 2015.10.31
Comments