[알고리즘] 허프만 코드와 그리디 알고리즘 / Huffman code and greedy algorithm

문자열의 코드화

우리가 인터넷 상에서 쓰는 한글, abcd 알파벳.

컴퓨터는 우리처럼 글자 자체로 보지 않고, 결국 2진수 0과 1의 모음으로 이해를 한다! 

a는 01 로 약속, b는 10 으로 약속하면  ab라는 문자는  컴퓨터 내에 0110 으로 저장이되고

100110 이란 코드를 받아들이면 컴퓨터는 아, 이것은 bab 이구나 로 해석하는 것이다.

우리가 쓰는 문자를 컴퓨터 내에 저장한다고 할 때, 이 약속된 코드의 비트수가 적을 수록 (010101 이런게 짧을수록) 메모리적으로 이득일 것이다!

그렇다면 어떻게하면 문자열을 효율적으로 코드화를 할 수 있을까?

 

Fixed-length codeword / Variable-length codeword

 

abcdef 를 코드화하여 2진법으로 표현할때에는 아래와 같이 두가지 방법이 있다.

 

Variable-length 방법으로는, 효율성을 고려하여 코드를 지정해주어 메모리 손실을 줄일 수 있다.

많이 나오는 문자일수록 코드길이를 짧게, 조금나오는 문자는 코드길이를 길게 하면 된다.

 

이렇게 효율성을 좋게 하려고 구성할 때, 반드시! encoding과 decoding 에 오차가 있으면 안된다.

예를들어, 같은 100101010 을 어떤것은 abc 로 읽을 수도 있고, bcb 로 읽을수도 있으면 안된다는 뜻이다.

한 코드는 하나의 문자로 변환이 가능해야한다.

이런 조건을 만족시키는 메카니즘을 효율적으로 구성하는 알고리즘이 바로 허프만 코딩 알고리즘이다!

 

허프만 코드

트리를 이용한다. 효율성을 늘리기위해 트리는 항상 full-binary-tree 로 구성한다.

Top-down 방식, min-priority Queue 를 이용할 것이다!

 

현재 가장 작은 노드들끼리 묶어서 루트 노드 1개 남을때 까지 계속 묶어주는 방식의 수도코드이다. (정순영 교수님 ppt 참조)

코드가 어렵지 않으니 코드만 잘 읽어봐도 이해가 될 것이다!

 

출처 : 출처 : 고려대학교 정순영 교수님 알고리즘 수업,

introduction to algorithms 3rd edition - 토머스 H. 코르먼(Thomas H. Cormen) 찰스 E. 레이서슨(Charles E. Leiserson)