허프만 코드와 접두어 없는 표현

문자마다 같은 길이의 비트열을 쓰면 다루기는 쉽지만, 자주 나오는 문자와 드물게 나오는 문자에 같은 길이를 쓰는 것은 낭비입니다. 자주 나오는 문자에 짧은 비트열을 주면 전체 길이를 줄일 수 있습니다. 다만 A = 0, B = 01처럼 한 코드가 다른 코드의 앞부분이면, 0을 읽은 순간 A인지 B의 시작인지 알 수 없습니다. 이 글은 선택 심화로, 트리와 이진 트리의 구조의 잎과 깊이를 써서 이 문제를 풀고 가장 짧은 코드를 만듭니다.

코드 트리의 잎에 문자를 놓는다

어떤 코드도 다른 코드의 앞부분, 곧 접두어(prefix)가 아닌 코드를 접두어 없는 코드(prefix-free code)라고 합니다. 접두어 코드(prefix code)라고 부르는 자료도 많은데, 같은 뜻입니다. 접두어 없는 코드는 이진 트리로 나타낼 수 있습니다. 왼쪽 간선에 0, 오른쪽 간선에 1을 붙이고, 루트에서 잎까지 지나는 비트를 그 잎에 놓인 문자의 코드로 삼습니다. 문자가 잎에만 있으면 한 문자의 경로가 다른 문자의 경로 중간에서 끝날 수 없으므로, 어떤 코드도 다른 코드의 접두어가 되지 않습니다.

이런 코드는 복호가 간단합니다. 루트에서 출발해 비트를 하나씩 읽으며 내려가다가 잎에 닿으면 그 문자를 내놓고 루트로 돌아갑니다. 앞을 미리 볼 필요 없이 읽는 즉시 문자가 정해집니다. 문자 s의 빈도를 f(s), 코드의 길이, 곧 잎의 깊이를 d(s)라고 하면 메시지 전체의 비트 수는 $\sum_s f(s)\,d(s)$입니다. 이 값을 가장 작게 만드는 트리를 찾는 것이 목표입니다.

가장 작은 두 빈도를 먼저 합친다

허프만 알고리즘(Huffman's algorithm)은 1952년 David Huffman이 제안한 방법입니다. 문자마다 잎 하나짜리 트리를 만들고, 빈도가 가장 작은 두 트리를 꺼내 하나의 부모 아래로 합친 뒤 두 빈도의 합을 부모의 빈도로 삼는 일을 트리가 하나 남을 때까지 반복합니다. 빈도 A = 8, B = 4, C = 2, D = 2로 해 보겠습니다.

가장 작은 C와 D를 합쳐 빈도 4인 정점을 만들고, 이것과 B의 4를 합쳐 8을 만든 뒤, 남은 A의 8과 합쳐 루트 16을 만듭니다. 합친 정점은 문자가 아니라 아래에 있는 빈도의 합일 뿐입니다. 코드는 A = 0, B = 10, C = 110, D = 111이 됩니다.

from heapq import heappop, heappush
from itertools import count


def huffman_codes(frequencies):
    order = count()
    heap = []
    for symbol, frequency in frequencies.items():
        heappush(heap, (frequency, next(order), symbol))
    while len(heap) > 1:
        f1, _, left = heappop(heap)
        f2, _, right = heappop(heap)
        heappush(heap, (f1 + f2, next(order), (left, right)))
    codes = {}

    def assign(node, prefix):
        if isinstance(node, str):
            codes[node] = prefix or "0"
            return
        assign(node[0], prefix + "0")
        assign(node[1], prefix + "1")

    assign(heap[0][2], "")
    return codes


def decode(bits, codes):
    symbol_of = {code: symbol for symbol, code in codes.items()}
    result, current = [], ""
    for bit in bits:
        current += bit
        if current in symbol_of:
            result.append(symbol_of[current])
            current = ""
    if current:
        raise ValueError("비트열이 문자 중간에서 끝났습니다")
    return "".join(result)


frequencies = {"A": 8, "B": 4, "C": 2, "D": 2}
codes = huffman_codes(frequencies)
print(codes)
total = sum(frequencies[s] * len(codes[s]) for s in frequencies)
print(total, total / sum(frequencies.values()))
bits = "".join(codes[s] for s in "ABCD")
print(bits, decode(bits, codes))
try:
    decode(bits[:-1], codes)
except ValueError as error:
    print("오류:", error)

{'A': '0', 'B': '10', 'C': '110', 'D': '111'}
28 1.75
010110111 ABCD
오류: 비트열이 문자 중간에서 끝났습니다

힙에는 (빈도, 순번, 트리)를 넣습니다. 빈도가 같을 때 튜플 비교가 트리끼리의 비교로 넘어가지 않도록, count()가 내는 순번을 가운데 두어 먼저 넣은 것이 먼저 나오게 했습니다. 합친 트리는 (왼쪽, 오른쪽) 튜플이고, assign은 트리를 내려가며 왼쪽에 0, 오른쪽에 1을 붙입니다. 문자가 하나뿐이면 루트가 곧 잎이라 경로가 빈 문자열이 되므로 "0"을 주었습니다. decode는 읽은 비트가 어떤 코드와 같아지는 순간 문자를 내놓는데, 접두어 없는 코드라서 이렇게 해도 잘못 끊는 일이 없습니다.

메시지 전체는 8·1 + 4·2 + 2·3 + 2·3 = 28비트이고, 문자 하나에 평균 28/16 = 1.75비트입니다. 네 문자를 고정 길이 2비트로 적으면 32비트이므로 4비트가 줄었습니다. 다만 실제 파일에서는 받는 쪽이 복호하려면 코드표나 트리도 함께 보내야 하므로, 이 숫자만으로 압축률을 말할 수는 없습니다. 비트열이 잎에 닿기 전에 끝나면 decode가 오류를 내는데, 정상 메시지로 처리하면 마지막 문자를 잃게 됩니다.

허프만 코드가 가장 짧은 이유

같은 빈도에서 합치는 순서나 좌우를 바꾸면 코드의 비트는 달라질 수 있지만, 전체 비트 수는 언제나 가장 작습니다. 증명은 두 단계의 교환 논증입니다. 먼저 빈도가 가장 작은 두 문자 x와 y가 가장 깊은 곳에서 형제인 최적 트리가 있습니다. 최적 트리에서 가장 깊은 곳의 형제 잎 두 개를 x, y와 맞바꾸면, 빈도가 작은 문자가 더 깊이, 큰 문자가 더 얕게 가므로 전체 비트 수가 늘지 않기 때문입니다. 내부 정점의 자식이 하나뿐인 최적 트리는 없으므로 가장 깊은 잎에는 언제나 형제가 있습니다.

다음으로 x와 y를 빈도가 f(x) + f(y)인 문자 하나로 합친 작은 문제를 생각합니다. 작은 문제의 트리에서 그 문자의 잎 아래에 x와 y를 달면 원래 문제의 트리가 되고, 비트 수는 정확히 f(x) + f(y)만큼 늘어납니다. 그래서 원래 문제의 최적 트리는 작은 문제의 최적 트리에 x와 y를 단 것이고, 허프만 알고리즘은 바로 이 일을 되풀이합니다. 문자 수에 대한 귀납법으로 정리하면 증명이 끝납니다. 이 관계에서 전체 비트 수가 합칠 때마다 만든 빈도의 합과 같다는 것도 나옵니다. 예제에서는 4 + 8 + 16 = 28입니다.

허프만 코드는 문자마다 고정된 빈도가 주어졌을 때, 문자 하나를 코드 하나로 바꾸는 접두어 없는 이진 코드 가운데 가장 짧다는 뜻입니다. 여러 문자를 묶어서 코드를 주거나 앞뒤 문맥을 이용하는 압축 방식은 이보다 더 짧게 만들 수도 있습니다.

정리

• 어떤 코드도 다른 코드의 접두어가 아닌 접두어 없는 코드는 문자를 잎에 놓은 이진 트리로 나타낼 수 있고, 비트를 읽는 즉시 복호할 수 있습니다.
• 메시지의 비트 수는 빈도와 잎의 깊이를 곱해 더한 값이며, 허프만 알고리즘은 빈도가 가장 작은 두 트리를 합치는 일을 반복해 이 값을 가장 작게 만듭니다.
• 동점을 처리하는 방법에 따라 코드의 비트는 달라질 수 있지만, 전체 비트 수는 같습니다.
• 허프만 코드가 최적인 이유는 가장 드문 두 문자를 가장 깊은 형제로 놓아도 손해가 없다는 교환 논증과, 둘을 합친 작은 문제로 줄이는 귀납법으로 설명합니다.

연습 문제

1. 인코딩하기

본문의 코드로 DABA를 인코딩하고 비트 수를 구하세요.

2. 접두어 조건 확인하기

A = 0, B = 01, C = 11은 접두어 없는 코드인가요?

3. 직접 만들어 보기

빈도 X = 5, Y = 2, Z = 1에 대한 허프만 코드를 만들고, 전체 비트 수와 문자당 평균 길이를 고정 길이 2비트 코드와 비교하세요.

허프만 트리를 손으로 만들 때는 단계마다 남은 빈도의 합이 처음 빈도의 합과 같은지 확인해 보세요. 문자당 평균 길이는 빈도를 확률로 본 기댓값이며, 확률변수, 기댓값과 분산에서 다시 만납니다. 다음 장의 부울 대수와 논리 회로에서는 참과 거짓의 계산을 회로로 옮깁니다.