파일을 압축한다는 말은 같은 정보를 더 짧은 표현으로 바꾼다는 뜻입니다. 허프만 코딩(Huffman coding)은 기호마다 등장 빈도가 다르다는 점을 이용하는 대표적인 무손실 압축 방식입니다. 자주 나오는 기호에는 짧은 비트열을, 드물게 나오는 기호에는 긴 비트열을 배정해 전체 평균 길이를 줄입니다. 1952년 데이비드 허프먼이 발표한 논문은 주어진 기호의 확률에 대해 평균 코드 길이가 최소인 접두 부호를 구성하는 절차를 제시했습니다. 다만 여기서 ‘최적’은 모든 압축 기법 가운데 언제나 가장 작다는 뜻이 아닙니다. 기호 하나를 코드 하나로 바꾸는 방식, 알려진 확률, 정수 길이의 접두 부호라는 조건 안에서 성립하는 정확한 표현입니다.
접두 부호가 필요한 이유
기호 A, B, C에 각각 0, 01, 011을 배정하면 짧아 보이지만 문제가 생깁니다. 01을 읽었을 때 이것이 B인지, A 다음에 다른 비트가 이어지는지 즉시 결정할 수 없기 때문입니다. 접두 부호(prefix code)는 어떤 유효한 코드워드도 다른 코드워드의 앞부분이 되지 않도록 만듭니다. 예를 들어 A=0, B=10, C=110, D=111이면 011010을 왼쪽부터 읽어 A, C, B로 하나씩 확정할 수 있습니다. 별도의 구분 기호나 코드 길이 표지를 매번 넣지 않아도 되므로 복호화가 간단합니다. 이 성질은 모든 기호를 이진 트리의 잎에 놓았을 때 자연스럽게 얻어집니다. 왼쪽 가지에 0, 오른쪽 가지에 1을 붙이면 한 잎까지 내려간 경로가 그 기호의 코드가 됩니다.
두 개의 가장 작은 빈도를 계속 합친다
허프만 알고리즘의 핵심 절차는 놀랄 만큼 짧습니다. 먼저 각 기호의 출현 횟수 또는 확률을 준비합니다. 그중 값이 가장 작은 두 항목을 골라 형제 노드로 묶고 두 값을 더한 부모 노드를 만듭니다. 원래 두 항목을 목록에서 빼고 합친 노드를 다시 넣습니다. 항목이 하나만 남을 때까지 같은 일을 반복하면 이진 트리가 완성됩니다. 마지막에 각 왼쪽·오른쪽 가지에 0과 1을 배정합니다. 좌우에 어느 비트를 붙이는지는 평균 길이에 영향을 주지 않습니다. 빈도가 같은 항목을 고르는 순서도 여러 트리를 만들 수 있지만, 그 결과의 평균 코드 길이는 같을 수 있습니다.
간단한 예로 A 40회, B 30회, C 20회, D 10회가 등장했다고 하겠습니다. 가장 작은 D와 C를 합쳐 30을 만들면 목록은 40, 30, 30이 됩니다. 30 두 개를 합쳐 60을 만들고, 마지막으로 40과 60을 합쳐 100을 만듭니다. 가능한 코드 한 벌은 A=0, B=10, C=110, D=111입니다. 100개 기호를 고정 길이로 표현하면 기호당 2비트이므로 200비트가 필요합니다. 허프만 코드에서는 40×1+30×2+20×3+10×3=190비트입니다. 코드표를 전달하는 비용 등을 제외한 기호열 본체가 10비트 줄어듭니다.
평균 코드 길이를 계산하는 공식
기호 i의 확률을 pᵢ, 코드 길이를 lᵢ라고 하면 기호 하나당 평균 코드 길이는 L=Σpᵢlᵢ입니다. 위 예에서는 L=0.4×1+0.3×2+0.2×3+0.1×3=1.9비트입니다. 고정 길이 2비트보다 평균 0.1비트 짧습니다. 압축 효과는 빈도 분포가 얼마나 치우쳤는지에 따라 달라집니다. 네 기호가 각각 25%로 똑같이 나온다면 모두 2비트인 완전한 트리가 이미 알맞아 허프만 코딩으로 더 줄일 수 없습니다. 반대로 특정 기호가 압도적으로 자주 나오면 그 기호에 1비트를 배정해 평균을 크게 낮출 수 있습니다.
정보 이론에서는 분포의 엔트로피를 H=−Σpᵢlog₂pᵢ로 정의합니다. 이진 허프만 코드의 평균 길이 L은 일반적으로 H≤L<H+1 관계를 만족합니다. 엔트로피가 정수 비트 길이로 정확히 표현되지 않기 때문에 생기는 차이가 1비트보다 작다는 뜻입니다. 각 확률이 1/2의 거듭제곱이면 −log₂pᵢ가 정수가 되어 엔트로피와 평균 길이가 같아질 수 있습니다. 엔트로피는 가능한 평균 길이의 이론적 기준이고, 허프만 트리는 한 기호씩 독립적으로 부호화하는 접두 부호 안에서 그 기준에 가까운 최솟값을 만듭니다.
왜 가장 드문 두 기호를 형제로 묶는가
최적 접두 부호의 트리를 생각하면 깊이가 깊을수록 코드가 깁니다. 확률이 낮은 기호를 더 깊은 곳에 두고 확률이 높은 기호를 얕은 곳에 두어야 평균이 작아집니다. 최적 이진 트리에서는 가장 낮은 확률의 두 기호를 가장 깊은 수준의 형제로 배치할 수 있습니다. 이 두 기호를 하나의 합성 기호로 합치면 기호 수가 하나 줄어든 더 작은 최적화 문제가 됩니다. 작은 문제의 최적 트리를 구한 뒤 합성 잎을 다시 둘로 펼치면 원래 문제의 최적 트리가 됩니다. 이런 최적 부분 구조 때문에 ‘가장 작은 두 값을 합친다’는 탐욕적 선택이 전체 최적해로 이어집니다.
실제로 문자열을 복호화하는 방법
복호화는 트리의 뿌리에서 시작합니다. 입력 비트가 0이면 왼쪽, 1이면 오른쪽으로 이동하고 잎에 도착하면 해당 기호를 출력한 뒤 다시 뿌리로 돌아갑니다. 앞의 코드표에서 010111110은 0|10|111|110으로 끊겨 A, B, D, C가 됩니다. 코드워드 사이에 구분선이 없어도 유일하게 분해됩니다. 입력이 잎에 닿지 않은 채 끝나면 비트열이 잘렸거나 코드표가 맞지 않는 상태입니다. 압축 파일은 트리를 그대로 저장하거나, 각 기호의 코드 길이만 저장한 뒤 정해진 순서로 코드를 재구성하는 정규 허프만(canonical Huffman) 방식을 사용하기도 합니다. 정규형은 코드표 저장 공간과 복호화 표 구성을 줄이는 데 유리합니다.
빈도표까지 포함하면 항상 줄어드는 것은 아니다
압축된 비트열을 풀려면 어떤 기호에 어떤 코드를 배정했는지 알아야 합니다. 작은 파일에서는 빈도표나 트리 자체를 기록하는 헤더가 본문 절감량보다 클 수 있습니다. 또한 실제 분포와 빈도표가 맞지 않으면 기대한 압축률이 나오지 않습니다. 정적 허프만 코딩은 입력을 먼저 훑어 빈도를 센 뒤 코드를 만들고, 적응형 허프만 코딩은 읽는 동안 트리를 갱신합니다. 어느 방식을 쓰든 압축 크기는 코드 본체뿐 아니라 코드표, 파일 형식의 메타데이터, 블록 구분 비용까지 포함해 판단해야 합니다.
허프만 코딩이 최적이지 않은 경우
허프만 코딩은 주어진 기호별 확률에 대한 접두 부호의 평균 길이를 최소화합니다. 그러나 여러 기호를 묶어 부호화하거나 비트 단위가 아닌 구간을 표현하면 더 나은 압축이 가능할 수 있습니다. 산술 코딩과 범위 코딩은 한 기호에 반드시 정수 개의 비트를 배정해야 한다는 제약을 피합니다. 문맥 모델은 앞에 나온 기호에 따라 다음 기호의 확률이 달라지는 성질을 활용합니다. 반복 문자열을 사전 참조로 바꾸는 방식도 단순 기호 빈도만 보는 허프만 코딩과 다른 정보를 사용합니다. 그래서 실제 압축 형식은 사전 방식이나 변환 방식으로 중복을 먼저 줄인 다음 허프만 부호를 마지막 단계에 결합하기도 합니다.
시간 복잡도와 구현에서 확인할 점
기호 종류가 k개일 때 최소 힙을 사용하면 트리 구성은 보통 O(k log k) 시간에 처리할 수 있습니다. 매 단계에서 최소 두 항목을 꺼내고 합친 항목을 다시 넣기 때문입니다. 실제 데이터 인코딩과 디코딩은 입력 길이에 비례해 진행됩니다. 구현에서는 빈도가 0인 기호의 처리, 빈도가 같은 기호의 안정적인 순서, 하나의 기호만 존재하는 입력, 매우 긴 코드의 저장 형식을 따로 정해야 합니다. 하나의 기호만 나오는 파일에는 빈 비트열보다 0 같은 한 비트 코드를 배정하는 편이 파일 경계와 반복 횟수를 표현하기 쉽습니다. 빈도 합계가 정수 범위를 넘지 않도록 자료형도 확인해야 합니다.
허프만 코딩을 정확히 기억하는 방법
- 출현 빈도 또는 확률이 작은 두 항목을 고릅니다.
- 두 항목을 형제로 묶고 값을 더해 목록에 다시 넣습니다.
- 하나의 뿌리가 남을 때까지 반복한 뒤 가지에 0과 1을 붙입니다.
- 평균 길이는 L=Σpᵢlᵢ로 계산합니다.
- 최적성은 알려진 가중치에 대한 기호 단위 접두 부호라는 조건에서 이해합니다.
- 실제 파일 크기에는 코드표와 형식 정보의 비용도 포함합니다.
허프만 코딩의 장점은 ‘자주 나오면 짧게 쓴다’는 직관을 엄밀한 트리 절차로 바꾼 데 있습니다. 가장 작은 두 빈도를 반복해서 합치면 즉시 복호화할 수 있는 접두 부호가 만들어지고, 정해진 조건 안에서 평균 코드 길이가 최소가 됩니다. 압축률만 볼 때는 입력 분포와 헤더 비용, 문맥 활용 여부까지 함께 살펴야 하지만, 이진 트리와 탐욕 알고리즘, 정보 엔트로피를 한 번에 이해하기에 좋은 사례입니다.
코드표가 달라도 압축 길이는 같을 수 있다
같은 빈도의 기호가 여러 개 있으면 최소 두 항목을 고르는 순서가 하나로 정해지지 않습니다. 또한 완성된 트리에서 왼쪽과 오른쪽의 0·1을 맞바꿔도 각 코드워드의 길이는 바뀌지 않습니다. 따라서 같은 빈도표에서 서로 다른 허프만 코드표가 나올 수 있습니다. 어느 표가 유일한 정답이라기보다 평균 길이가 최소라는 성질이 핵심입니다. 압축기와 복호화기가 각각 임의로 트리를 만들면 동률 처리 순서가 달라질 수 있으므로, 파일에 트리 정보를 넣거나 정규 허프만 규칙처럼 코드 길이와 기호 순서로 같은 표를 재구성해야 합니다.
압축률을 비교할 때는 원본의 문자 수가 아니라 실제 바이트 수를 기준으로 삼아야 합니다. 유니코드 문자는 저장 인코딩에 따라 한 글자가 여러 바이트일 수 있고, 허프만 알고리즘의 ‘기호’를 문자·바이트·토큰 중 무엇으로 정했는지에 따라 빈도표가 달라집니다. 같은 문장도 UTF-8 바이트를 기호로 삼은 결과와 유니코드 코드 포인트를 기호로 삼은 결과가 같지 않습니다. 기호 정의, 코드표 비용, 마지막 바이트를 채우는 패딩 비트까지 포함한 최종 파일 크기를 밝혀야 압축 방식끼리 공정하게 비교할 수 있습니다. 압축률은 이 전체 크기를 원본 바이트 수와 비교해 계산합니다.
참고 자료
- David A. Huffman, A Method for the Construction of Minimum-Redundancy Codes (1952): https://doi.org/10.1109/JRPROC.1952.273898
- NIST Dictionary of Algorithms and Data Structures, Huffman coding: https://xlinux.nist.gov/dads/HTML/huffmanCoding.html