8.11 섀넌-파노 부호화(Shannon-Fano Coding) 알고리즘

1. 역사적 배경

섀넌-파노 부호화(Shannon-Fano Coding)는 가변 길이 부호 설계의 최초의 체계적 알고리즘 중 하나이다. Claude Shannon과 Robert Fano가 각각 독립적으로 제안한 방법으로, Shannon은 1948년 논문 “A Mathematical Theory of Communication“에서 부호어 길이를 l_i = \lceil -\log_2 p_i \rceil로 설정하는 방법을 기술하였고, Fano는 하향식 이분할(top-down binary partitioning) 알고리즘을 제시하였다. 현대적 문헌에서는 두 방법을 함께 섀넌-파노 부호화로 지칭하나, 엄밀히는 서로 다른 알고리즘이다. 본 절에서는 두 방법을 각각 서술한다.

2. 섀넌 부호화(Shannon Coding)

2.1 알고리즘

섀넌 부호화는 누적 분포 함수(cumulative distribution function)를 이용하여 부호어를 결정론적으로 구성한다.

입력: 정보원 기호 x_1, x_2, \dots, x_M과 확률 p_1 \geq p_2 \geq \cdots \geq p_M > 0 (비증가 순서로 정렬)

절차:

1. 각 기호의 부호어 길이를 l_i = \lceil -\log_2 p_i \rceil로 설정한다.
2. 누적 확률을 F_i = \sum_{k=1}^{i-1} p_k로 계산한다. (F_1 = 0)
3. F_i를 이진 소수(binary fraction)로 전개하고, 소수점 이하 l_i자리까지 취하여 부호어 c_i를 결정한다.

형식적으로, c_i는 F_i의 이진 표현의 소수점 이하 l_i비트를 추출한 것이다:

c_i = \lfloor F_i \cdot 2^{l_i} \rfloor \text{의 이진 표현 (}l_i\text{비트)}

2.2 접두사 조건의 증명

이 구성이 접두사 부호를 생성함을 보이자. F_i에 대응하는 구간은 [F_i, F_i + 2^{-l_i})이다. 2^{-l_i} \leq 2^{\log_2 p_i} = p_i이므로,

F_i + 2^{-l_i} \leq F_i + p_i = F_{i+1}

따라서 서로 다른 기호에 대응하는 구간들이 겹치지 않으며, 이는 접두사 조건이 만족됨을 의미한다.

2.3 성능 보장

섀넌 부호의 평균 부호어 길이는 다음을 만족한다:

H(X) \leq L_{\text{Shannon}} < H(X) + 1

이는 -\log_2 p_i \leq l_i < -\log_2 p_i + 1로부터 직접 도출된다.

3. 파노 부호화(Fano Coding)

3.1 알고리즘

파노 부호화는 하향식 재귀적 이분할 방법이다.

입력: 정보원 기호 x_1, x_2, \dots, x_M과 확률 p_1 \geq p_2 \geq \cdots \geq p_M > 0

절차:

1. 기호 집합을 확률의 합이 가능한 한 균등하게 되도록 두 부분 집합 S_0와 S_1로 분할한다. 즉, \left\lvert \sum_{x_i \in S_0} p_i - \sum_{x_i \in S_1} p_i \right\rvert를 최소화하는 분할점을 찾는다.
2. S_0에 속하는 기호의 부호어에 비트 0을, S_1에 속하는 기호의 부호어에 비트 1을 추가한다.
3. 각 부분 집합에 기호가 2개 이상이면, 해당 부분 집합에 대하여 단계 1-2를 재귀적으로 반복한다.
4. 부분 집합에 기호가 1개만 남으면 해당 기호의 부호어가 확정된다.

3.2 구체적 예

알파벳 \mathcal{X} = \{a, b, c, d, e\}이고 확률이 p(a) = 0.35, p(b) = 0.25, p(c) = 0.20, p(d) = 0.12, p(e) = 0.08인 경우를 고려하자.

1단계: \{a, b\}와 \{c, d, e\}로 분할. 각 부분 집합의 확률 합은 0.60과 0.40이다.

2단계: \{a, b\}를 \{a\}와 \{b\}로 분할. \{c, d, e\}를 \{c\}와 \{d, e\}로 분할.

3단계: \{d, e\}를 \{d\}와 \{e\}로 분할.

결과 부호:

평균 부호어 길이는 L = 0.35 \times 2 + 0.25 \times 2 + 0.20 \times 2 + 0.12 \times 3 + 0.08 \times 3 = 2.20 비트이다. 엔트로피는 H(X) \approx 2.151 비트이므로, 파노 부호의 평균 길이가 엔트로피보다 약 0.049 비트 크다.

3.3 접두사 조건

파노 부호화의 재귀적 이분할 과정은 이진 트리를 구성하며, 각 기호는 잎 노드에 대응한다. 따라서 파노 부호는 항상 접두사 부호이다.

4. 섀넌 부호와 파노 부호의 비교

두 방법의 핵심적 차이는 다음과 같다.

파노 부호화는 실용적으로 섀넌 부호보다 대체로 더 짧은 평균 부호어 길이를 제공하지만, 이론적으로 최적성이 보장되지는 않는다. 두 방법 모두 허프만 부호화보다 열등한 성능을 보일 수 있다.

5. 섀넌-파노 부호화의 의의와 한계

섀넌-파노 부호화의 이론적 의의는, 엔트로피에 가까운 평균 부호어 길이를 달성하는 체계적 알고리즘이 존재함을 최초로 보인 것이다. 특히 섀넌 부호화는 무잡음 부호화 정리의 구성적 증명(constructive proof)에 해당한다.

그러나 섀넌-파노 부호화는 단일 기호 부호화에서 최적이 아니라는 한계를 갖는다. 최적 접두사 부호의 구성은 허프만 알고리즘에 의해 해결되며, 이는 탐욕적(greedy) 상향식 트리 구성을 통해 평균 부호어 길이를 최소화하는 부호를 생성한다.