[알고리즘] Huffman Code

Huffman Code

• 암호처럼 한 문자를 2진수로 변환하여 사용하는 것
• 어떤 수도 다른 수의 접두어(prefix)가 아니어야 한다.
• 숫자는 가능한 짧은게 좋다. 특히 자주 사용하는 문자일수록 짧아야한다.

잘 만든 예시

• 접두어(frefix)로 겹치는 2진수가 없음

잘못된 예시

• i의 10인지, n의 1010인지 알 수 없다.

과정 (Two-Way Optimal merge pattern 사용)

• 빈도 값 순으로 오름차순 정렬
• 정렬 된 리스트에서 가장 작은 두 값을 합함 (Greedy)
• 위의 두 값 대신, 새 값(두 값의 합)을 리스트에 포함 후 비교
• 위 과정을 반복함

1단계 ) 가장 작은 값 10과 10 병합

2단계 ) 가장 작은 값 15와 20 병합

3단계 ) 가장 작은 값 20과 20 병합

4단계) 가장 작은 값 25와 35 병합

5단계) 가장 작은 값 40과 60 병합

6단계) 트리 형태로 뒤집어 왼쪽 요소에는 0, 오른쪽 요소에는 1 부여

⇒ 많이 등장하는 문자일수록 읽힌 횟수가 적음

⇒ Huffman code가 짧아짐