무손실 데이터 압축 허프만 코딩의 이진 트리 알고리즘

디지털 세계의 모든 정보는 궁극적으로 0과 1이라는 비트의 나열로 저장되고 전송된다. 사진 한 장, 문서 한 편, 음악 스트리밍 파일에 이르기까지 우리가 매일 소비하는 디지털 데이터의 용량은 천문학적으로 팽창하고 있다. 만약 데이터를 있는 그대로 크기 제한 없이 전송한다면 전 세계 통신망은 순식간에 트래픽 폭주로 마비될 것이다. 원본 데이터를 단 1비트의 손실도 없이 원상 복구하면서도 파일 크기를 획기적으로 줄여주는 무손실 데이터 압축 기술은 인터넷 정보 고속도로를 지탱하는 보이지 않는 인프라이다.

1952년 MIT의 대학원생이었던 데이비드 허프만이 기말 과제를 작성하는 과정에서 창안한 '허프만 코딩(Huffman Coding)'은 오늘날 ZIP 압축, JPEG 이미지 포맷, MP3 오디오 코덱의 근간을 이루는 컴퓨터 과학 역사상 가장 우아한 알고리즘 중 하나이다.

고정 길이 코드의 비효율성과 가변 길이 접두사 코드

전통적인 아스키(ASCII) 코드는 알파벳 A부터 Z까지 모든 문자에 예외 없이 동일하게 8비트(1바이트)의 고정된 길이를 할당한다.

그러나 실제 영문 텍스트에서 모음 'E'나 자음 'T'는 빈번하게 등장하는 반면, 문자 'Z'나 'Q'는 거의 쓰이지 않는다. 모든 문자의 등장 빈도가 판이하게 다른데도 똑같은 비트 길이를 부여하는 것은 막대한 저장 공간의 낭비를 초래한다. 자주 나타나는 기호에는 23비트 수준의 아주 짧은 비트열을 부여하고, 드물게 나타나는 기호에는 78비트의 긴 비트열을 할당한다면 텍스트 전체의 평균 비트 수를 대폭 축소할 수 있다.

압축 방식 비교	비트 할당 메커니즘	디코딩 모호성 해결책	평균 비트 수 및 압축률
고정 길이 코드 (Fixed-Length)	모든 문자에 8비트 등 균등 할당	비트 수 단위로 균일하게 자름	중복성이 제거되지 않아 압축률 제로
일반 가변 길이 코드	빈도별 임의 가변 길이 비트 부여	코드 간 구분이 모호하여 해석 불가	경계선 혼선으로 역복원 실패 위험
허프만 접두사 코드 (Prefix Code)	어떤 코드도 다른 코드의 접두어가 안 됨	트리를 따라 단방향 즉각 디코딩	샤논 정보 엔트로피에 근접하는 최적 압축
사전 기반 압축 (LZW 계열)	반복되는 문자열 패턴을 인덱스화	런타임 동적 사전 테이블 구성	대용량 텍스트와 반복 패턴에 탁월

가변 길이 코드를 사용할 때 발생하는 치명적인 문제는 어디서 문자가 끝나고 다음 문자가 시작되는지 구분하기 어렵다는 점이다. 허프만 코딩은 '어떤 유효한 부호도 다른 부호의 시작 부분(접두사, Prefix)이 되지 않는다'는 접두사 코드 규칙을 만족하도록 설계하여, 비트열 사이에 별도의 구분 기호를 넣지 않고도 왼쪽부터 읽으며 유일무이하게 디코딩할 수 있는 완벽한 가독성을 보장한다.

탐욕 알고리즘을 통한 허프만 트리 구축 절차

허프만 알고리즘은 최적 부분 구조를 활용하는 대표적인 탐욕 알고리즘(Greedy Algorithm)에 기반하여 상향식(Bottom-Up)으로 이진 트리를 완성해 나간다.

압축할 데이터 전체를 스캔하여 각 문자의 출현 빈도를 카운트한 뒤, 모든 문자를 빈도값을 가중치로 갖는 독립된 리프 노드로 선언하고 우선순위 큐에 담는다. 큐에서 빈도수가 가장 작은 두 개의 노드를 꺼내어 이 둘을 자식으로 거느리는 새로운 부모 노드를 생성한다. 부모 노드의 가중치는 두 자식 노드 가중치의 합이 되며, 이 부모 노드를 다시 큐에 집어넣는다. 이 과정을 노드가 단 하나만 남을 때까지 반복하면 완벽한 계층적 이진 트리가 완성된다.

트리가 완성되면 루트 노드에서 출발하여 왼쪽 가지로 내려갈 때는 비트 '0'을, 오른쪽 가지로 내려갈 때는 비트 '1'을 부여한다. 루트에서 각 리프 노드까지 도달하는 경로의 0과 1을 순서대로 적으면 그것이 바로 해당 문자의 고유한 압축 코드가 된다. 빈도가 높은 문자는 자연스럽게 루트 가까이에 위치하여 짧은 코드를 얻고, 빈도가 낮은 문자는 깊숙한 바닥으로 밀려나 긴 코드를 얻게 된다.

샤논의 무손실 코딩 정리와 현대 압축 기술의 융합

허프만 코딩이 달성할 수 있는 압축의 이론적 극한은 클로드 샤논이 정립한 정보이론의 '엔트로피(Entropy)' 한계에 정밀하게 수렴한다.

데이터가 지닌 무작위성과 불확실성의 척도인 엔트로피보다 더 작은 평균 비트 수로 데이터를 손실 없이 압축하는 것은 물리적으로 불가능하다. 허프만 코딩은 개별 기호 단위로 비트를 할당하는 방식 중에서 이 샤논의 엔트로피 상한선에 가장 근접하는 수학적 최적성을 수학적으로 엄밀하게 증명해 냈다. 현대의 소프트웨어 아키텍처와 최적화 알고리즘에 대한 실전 구현 가이드는 일본 동전파스 에서도 다양하고 체계적으로 확인해 볼 수 있다.

현대의 실무 압축 알고리즘(Deflate 등)은 허프만 코딩을 단독으로 사용하지 않고, 텍스트 내에서 중복되는 문자열 패턴을 찾아 오프셋 거리로 치환하는 LZ77 알고리즘과 결합하여 2단계 파이프라인으로 구동된다. 70여 년 전 한 대학원생의 번뜩이는 수학적 기지가 탄생시킨 허프만 코딩은 클라우드 분산 저장소부터 스마트폰 모바일 앱 통신에 이르기까지 전 세계 디지털 비트의 부피를 줄여주는 최고의 압축 엔진으로 쉼 없이 고동치고 있다.