8.6 접두사 부호(Prefix-Free Code)의 정의와 성질

1. 접두사 부호의 정의

알파벳 $\mathcal{X} = \{x_1, x_2, \dots, x_M\}$ 위의 부호 $C$ 가 접두사 부호(prefix-free code) 또는 **순시 부호(instantaneous code)**라 함은, 부호어 집합 $\{c_1, c_2, \dots, c_M\}$ 중 어떤 부호어도 다른 부호어의 접두사(prefix)가 되지 않는 것이다. 형식적으로,

$\forall\, i \neq j: \quad c_i \text{는 } c_j\text{의 접두사가 아니다}$

를 만족하는 부호를 접두사 부호라 한다. 문자열 $u$ 가 문자열 $v$ 의 접두사라 함은 $v = u w$ 를 만족하는 문자열 $w$ 가 존재하며 $w \neq \epsilon$ (빈 문자열이 아님)인 것을 뜻한다.

접두사 부호는 문헌에 따라 접두사 없는 부호(prefix-free code), 접두사 조건 부호(prefix condition code), 또는 **순시 부호(instantaneous code)**로도 불린다. “순시 부호“라는 명칭은 부호열을 왼쪽에서 오른쪽으로 읽어가면서 부호어의 끝을 즉시(instantaneously) 인식할 수 있다는 복호 특성에서 유래한 것이다.

2. 이진 트리 표현

접두사 부호는 이진 트리(binary tree)와 자연스러운 대응 관계를 갖는다. 완전 이진 트리의 근(root)에서 출발하여 왼쪽 자식으로의 이동을 비트 $0$ , 오른쪽 자식으로의 이동을 비트 $1$ 로 대응시키면, 트리의 각 노드는 하나의 이진 문자열에 대응한다.

접두사 부호의 부호어 집합은 이진 트리의 잎 노드(leaf node) 집합과 정확히 대응한다. 어떤 부호어가 다른 부호어의 접두사가 되지 않는다는 조건은, 트리에서 어떤 부호어 노드의 후손(descendant)에 다른 부호어 노드가 존재하지 않는다는 것과 동치이다. 따라서 모든 부호어는 반드시 잎 노드에 위치하게 된다.

이 트리 표현을 이용하면 접두사 부호의 구성과 분석이 직관적으로 이루어진다. 부호어 $c_i$ 의 길이 $l_i$ 는 근에서 해당 잎 노드까지의 경로 길이(depth)와 같다.

3. 접두사 부호의 즉시 복호 가능성

접두사 부호의 가장 중요한 성질은 **즉시 복호 가능(instantaneously decodable)**하다는 것이다. 연접 부호열 $b_1 b_2 b_3 \cdots$ 를 왼쪽에서 오른쪽으로 한 비트씩 읽어 나갈 때, 현재까지 읽은 비트열이 어떤 부호어 $c_i$ 와 일치하는 순간, 그것이 바로 해당 위치의 정보원 기호 $x_i$ 에 대응하는 부호어임을 확정할 수 있다. 이는 접두사 조건에 의하여, 현재 인식된 부호어가 다른 더 긴 부호어의 접두사가 될 가능성이 배제되기 때문이다.

정리. 접두사 부호는 고유 복호 가능(uniquely decodable)하다.

증명. 접두사 부호 $C$ 에 대하여, 임의의 유한 기호열 $x_{i_1} x_{i_2} \cdots x_{i_n}$ 의 연접 부호화 $c_{i_1} c_{i_2} \cdots c_{i_n}$ 이 주어졌다고 하자. 부호열의 첫 비트부터 읽어 나가면, 접두사 조건에 의하여 가장 먼저 일치하는 부호어 $c_{i_1}$ 이 유일하게 결정된다. $c_{i_1}$ 을 제거한 나머지 부호열에 같은 과정을 반복하면 $c_{i_2}, c_{i_3}, \dots, c_{i_n}$ 이 순차적으로 유일하게 결정된다. 따라서 확장 부호 사상 $C^n$ 은 단사이며, $C$ 는 고유 복호 가능하다. $\blacksquare$

4. 접두사 부호와 고유 복호 가능 부호의 관계

접두사 부호의 집합은 고유 복호 가능 부호의 진부분 집합이다. 즉, 고유 복호 가능하면서 접두사 부호가 아닌 부호가 존재한다.

예를 들어, $\mathcal{X} = \{a, b\}$ 이고 $C(a) = 0$ , $C(b) = 01$ 인 부호를 고려하자. $C(a) = 0$ 은 $C(b) = 01$ 의 접두사이므로 이 부호는 접두사 부호가 아니다. 그러나 이 부호는 고유 복호 가능하다. 연접 부호열에서 비트 $1$ 이 나타나면 직전의 $0$ 과 합쳐 $01$ 로 복호하고, 부호열의 끝에 도달했을 때 남은 $0$ 은 기호 $a$ 로 복호하면 유일한 복호가 가능하기 때문이다. 다만 이 경우 복호를 위해 후속 비트를 확인해야 하므로 즉시 복호는 불가능하다.

그럼에도 불구하고, 맥밀런 부등식에 의하여 고유 복호 가능 부호의 부호어 길이가 만족해야 하는 조건은 접두사 부호의 경우와 동일하다. 따라서 평균 부호어 길이의 관점에서 접두사 부호만을 고려하여도 최적성을 잃지 않는다.

5. 접두사 부호의 구성 방법

주어진 부호어 길이 집합 $\{l_1, l_2, \dots, l_M\}$ 이 크래프트 부등식

$\sum_{i=1}^{M} 2^{-l_i} \leq 1$

을 만족하면, 해당 길이를 갖는 접두사 부호를 항상 구성할 수 있다. 구성 절차는 다음과 같다.

부호어 길이를 비감소 순서로 정렬한다: $l_{\sigma(1)} \leq l_{\sigma(2)} \leq \cdots \leq l_{\sigma(M)}$ .
첫 번째 부호어를 $c_{\sigma(1)} = 0^{l_{\sigma(1)}}$ (길이 $l_{\sigma(1)}$ 의 전영(all-zero) 문자열)로 설정한다.
$k \geq 2$ 에 대하여, 이전 부호어 $c_{\sigma(k-1)}$ 을 이진수로 해석하여 $1$ 을 더한 뒤, $l_{\sigma(k)} - l_{\sigma(k-1)}$ 만큼 오른쪽으로 비트를 시프트(좌측에서 $0$ 을 채움)하여 $c_{\sigma(k)}$ 를 얻는다.

이 절차를 정전 부호(canonical code) 구성법이라 하며, 크래프트 부등식이 충족되는 한 접두사 조건이 자동으로 만족됨을 증명할 수 있다.

6. 접두사 부호의 최적성에 관한 기본 정리

정리. 정보원 $X$ 의 확률 분포 $\{p_1, p_2, \dots, p_M\}$ 에 대하여, 평균 부호어 길이를 최소화하는 고유 복호 가능 부호 중 접두사 부호인 것이 반드시 존재한다.

이 정리는 최적 부호 설계 문제에서 탐색 범위를 접두사 부호로 한정하여도 무방함을 보장한다. 이로써 접두사 부호는 이론적 분석의 편의와 실용적 구현의 용이함을 동시에 제공하며, 허프만 부호화 등 실제 압축 알고리즘의 이론적 기반이 된다.