해당 글은 Algorithms. by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani를 정리한 스터디 노트입니다. 해석하면서 정리한 글입니다.

5.2 Huffman encoding

MP3 audio compression scheme에서, 음성신호는 3가지 단계로 인코딩 됩니다.

1. 일정 간격을 기준으로 샘플링하여 digitized 됩니다. 실수값의 수열로 표현됩니다.
   • 초마다 44,100개의 샘플을 추출한다면, 50분 동안 총 $T = 50 * 60 * 44,100 ≈ 130$ million
2. 실수 값을 가지는 각 샘플 $s_t$는 quantiezed 됩니다.
   • finite set $T$로부터 근방에 있는 숫자를 approximate
   • 이때, 이 집합은 사람 귀로 구별할 수 있는 근사된 값의 나열로 표현합니다.
3. 길이가 $T$인 문자열은 binary로 인코딩 됩니다.(Huffman encoding part)

Huffman encoding이 탄생한 이유

위의 예시를 살펴보겠습니다. ($T = 130M$)

• $T$ 집합은 총 4가지 값을 가지고 있으며, 간략하게 기호로 A, B, C, D라고 하겠습니다.
• AACBAACDCAA..와 같은 긴 길이의 문자열을 binary로 바꾸려면 어떻게 해야 될까요?
• 가장 경제적인 방법은 각 기호를 2bit로 encoding하는 것입니다. (00, 10, 01, 11)
• 따라서 260 megabits are needed in total(130 * 2)

여기서 더 나은 인코딩 방법을 살펴보겠습니다.

• 더 자세히 살펴보면, 각 기호마다 frequency가 다릅니다.
• 자주 나오는 문자는 더 적은 bit로, 덜 나오는 문자는 더 많은 bit로 표현한다면 어떻게 될까요?
• = {0, 01, 11, 001}와 같이 표현한다면?
• 001의 표현이 애매할 수 있으니, prefix-free encoding을 살펴 보겠습니다.

• prefix - free property: no codeword can be a prefix of another codeword.
• prefix-free encoding은 a full binary tree로 표현됩니다.(full = 모든 노드들은 자식이 없거나, 2개이거나)
• 이처럼 인코딩한 결과, 17% 개선효과가 있었습니다. (213 megabits)

Find optimal coding tree

주어진 n개의 기호 $f_1, f_2, …, f_n$에 대해서 최적의 트리는 어떻게 찾을 수 있을까요?

이는 leaves들이 모든 symbol을 대응시킬 수 있고, 인코딩의 전체 길이를 최소화하는 트리를 찾으면 끝입니다. 1) 2) cost of tree = 트리의 비용은 루트를 제외한 모든 리프와 내부 노드의 주파수의 합계입니다.

• 식 1에 따라, 가장 적은 빈도수를 가진 2개의 symbols는 OPT tree의 bottom에 위치해야 합니다.
• 이 방식을 greedily하게 접근하여 트리를 만들어갈 수 있습니다.

Huffman(greedy)