♟ 최소한의 비트로 압축하기, 허프만 코딩(Huffman Coding)

관련글 :

그리디	https://waydd.tistory.com/91
활동 선택 문제	https://waydd.tistory.com/111

 

 

1. 허프만 코딩 (Huffman Coding)

 

주어진 문자들의 빈도에 따라 최소 길이의 이진 코드를 만드는/할당하는 그리디 알고리즘, 트리 기반의 압축 알고리즘(이자 문제 이름)

→ 그리디 알고리즘의 대표 예시로, 매 단계에서 가장 비용이 적은 두 항목을 선택하여 병합

→ 트리 구조 생성 + 그 트리 바탕으로 이진 코드 부여

• 자주 나오는 문자는 짧게, 드물게 나오는 문자는 길게 빈도 기반 인코딩
  → 빈도 수 큰 문자가 많은 비중을 차지, 짧게 표현함으로서 전체 평균 길이 (혹은 전체 데이터 크기) 를 최소화
      (무손실 압축이므로 나중에 복원도 가능)
  ※ 인코딩이란? 다른 환경에 해석 가능하도록 데이터를 특정 형식으로 바꿈 (원래 정보 보존 + 저장, 전송, 압축, 보안 등)
  → 가변 길이 이진 인코딩 (문자마다 길이가 다른 이진수 코드로 바꾸는 인코딩 방식)
• 우선순위 큐(PriorityQueue), 최소 힙 사용
• 빈도 낮은 것부터 병합해 최소 비용 트리 구성 (최소 이진트리)
  ①  각 문자 빈도를 계산 후, 빈도 낮은 것끼리(최소 두개) 합쳐서 트리 생성 (최소 힙 구조에 활용)
      (전체 비트 수의 총합이 최소가 되도록 트리를 구성함)
  ②  이후 루트에서 왼쪽 = 0, 오른쪽 = 1 로 경로를 따라가며 이진 코드 생성
  ③  각 문자에 겹치지 않는 (prefix-free) 코드 할당 으로 인코딩 완성
  → 압축(최소한의 비트로 표현)을 통해 최단 비트 수 ( = 데이터를 표현하는데 필요한 전체 비트 길이를 가장 작게 만듦 )
  → 실제 문자는 리프 노드에 존재, 비트 경로 = 리프 노드의 문자
      (이때 부모 노드의 빈도는 두 자식 노드의 빈도 합)
  → 결과 자체에는 빈도수 정보는 들어있지 않음, 전체 트리가 정렬 트리는 아니지만 경로 길이가 짧을 수록 빈도는 적음(비례)
      (트리 좌우 위치 : 빈도 기준 X / 비트 코드 : 사전순 정렬 X, 길이순 정렬 X)
• 허프만 코딩 ≈ 허프만 인코딩
  → 다 같은 알고리즘에서 비롯,  코딩은 알고리즘, 인코딩은 그 결과나 행위/과정 을 강조
• 파일 압축 (JPEG, MP3, ZIP 등) 에 사용됨
• 로프 연결 / 병합 최소 비용 / 압축 / 이진 트리 응용 문제로 간접적으로 출제 (트리나 PQ 활용 문제로 변형됨)

※ 인코딩의 반대는 다시 복원하는 복호화 (Decoding)
※ 대부분의 인코딩은 원래대로 되돌릴 수 있어야(가역성) 함 (비손실/무손실 압축)  ex) Base64, 허프만 코딩

※ prefix-free 만족이란?
- 아무 코드도 다른 코드의 앞부분이 아님을 뜻함
- 예시) 0 은 10, 110 의 시작이 아님 등
- 다른 코드의 접두어가 되는 코드가 있으면 디코딩할 수 없음
- 허프만 코디은 트리 구조를 통해 prefix-free 조건을 자동 보장

※ 허프만 트리 구성 단계 설명 (① ~ ④, 위에도 설명 있음)
①  빈도수 계산
  → 각 문자의 등장 횟수를 계산  ex) A(7), B(3), C(2), D(1)
②  우선순위 큐 생성
  → 각 문자를 노드로 만들고 최소 힙(min-heap)에 삽입
③  트리 병합 반복
  → 최소 빈도수 2개를 꺼내 새로운 부모 노드로 병합(합침) + 다시 큐에 삽입 (최소 힙 구조)
④  최종 트리(= 하프만 트리) 생성
  →  노드가 하나 남을 때까지 반복, 최종 루트 노드 완성
⑤  코드 매핑 생성
  → 루트에서 리프까지 경로에 따라가며 문자 ↔ 이진 코드 생성
⑥  원문 인코딩

 

 

- 용어 요약

허프만 트리 (Huffman Tree)	문자 + 빈도수로 구성된 이진 트리
병합 단계(Merge step)	최소 노드 2개를 꺼내 새로운 노드로 합치는 과정
우선순위 큐 (min-heap)	가장 낮은 빈도를 빠르게 선택하기 위한 자료구조
리프 노드	실제 문자가 위치하는 최종 노드
내부 노드	합쳐진 노드로, 빈도수는 자식 합, 문자는 없음

 

 

- 인코딩 예시 

• 원래 문자열 : AAAAAAABBBCCD 
  → 고정 길이 인코딩 (ASCII 8비트) : 13(총 문자수) × 8 = 104비트 (허프만 아님)
• 허프만 코딩 매핑 (압축할 때만 사용)  : A : 0, B : 10, C : 110, D : 111
• 압축 결과 (인코딩 결과) : 00000001010101110110111
  → 인코딩 후 전체 비트 수 = 7×1 + 3×2 + 2×3 + 1×3 = 7 + 6 + 6 + 3 = 22비트 (총합 기준 최적화)
  ※ 압축률: 22 / 104 ≈ 21.2%  (가변 길이 인코딩 중 최적)

※ 허프만 트리 구성 ( 우선순위 큐 기반 병합 단계 )
        (*)
      /      \
  A(7)     (*)
            /     \
        B(3)    (*)
                 /     \
             C(2)  D(1)

※ 위의 병합 순서는 아래와 같음
①  C(2) + D(1) → CD(3)
②  CD(3) + B(3) → BCD(6)
③  A(7) + BCD(6) → 루트(13)

※ 이진 코드 매핑표 생성 (빈도 기반 비트)
- 루트에서 왼쪽은 0, 오른쪽은 1, 문자마다 빈도수에 따라 짧고 긴 이진코드를 부여
  → 매핑 자체를 허프만 인코딩이라고 함 (= 어떤 문자에 어떤 비트 코드가 할당되었는가)
  → 이후, 매핑된 코드로 실제 데이터를 압축한 결과인 전체 비트열도, 허프만 인코딩
- A : 루트 → 왼쪽 = 0
- B : 루트 → 오른쪽 → 왼쪽 = 10
- C : 루트 → 오른쪽 → 오른쪽 → 왼쪽 = 110
- D : 루트 → 오른쪽 → 오른쪽 → 오른쪽 = 111
→ 문자는 항상 리프에만 위치, 내부 노드는 오직 빈도수 합산 역할만

※ 인코딩 결과 생성
00000001010101110110111
- A × 7 : 0 0 0 0 0 0 0 → 0000000
- B × 3 : 10 10 10 → 101010
- C × 2 : 110 110 → 110110
- D × 1 : 111 → 111

 

- 한계 및 주의점

• 이론적으로 최적에 가까운 무손실 압축률 + 구현이 비교적 단순 + 정적 데이터에 매우 효과적
• 문자 확률이 2의 제곱수에 가까울 때 최적
  → 이진 트리 구조로 인함
• 모든 입력에 대해 최적인 것은 아님
  → 빈도수에 따라 만들어진 트리 (또는 코드 테이블) 는 입력 데이터 전체에 고정적으로 사용
      (압축 및 복호화 속도가 빠름 + 구현 단순)
  → 데이터 특성이 구간별로 변할 때 비효율적임  ex) 문서의 앞부분은 영어, 뒷부분은 숫자가 많을
• 동적 상황(데이터가 계속 변할 때) 에서는 부적합
  → 데이터를 모두 분석 후, 전체 빈도수를 알아야 트리를 만들 수 있음 ( = 전체 입력을 미리 알아야 압축이 가능 )
  → 때문에 스트리밍/실시간 에 부적절
• 압축과 함께 빈도 정보, 트리 구조 또는 코드 매핑 정보도 저장해야 함
  → 복호화(디코딩)를 위해 코드 테이블 필요

 

 

2. 대표 예제 설명

 

- 구현 과정 및 설명

	핵심 기술	설명
빈도 분석	- 우선순위 큐 사용 (heapq 사용) - 클래스 / 튜플 우선순위 정의	- 최소 힙으로 트리를 구성해야 함 - Node(frequency, ...) 객체 정의
트리 생성	트리 병합 시뮬레이션 (최소 힙 기반 병합)	자식 노드 병합 및 새 노드 생성 구조
이진(비트) 코드 매핑	재귀 DFS	문자별 코드 매핑 생성
인코딩/디코딩	딕셔너리 활용	har → code, code → char 변환

※ 디코딩(복호화) 방식
- 이진 문자열을 앞에서부터 한 비트씩 따라감
- 트리의 왼쪽 또는 오른쪽으로 이동, 리프 노드에 도달하면 해당 문자를 출력, 다시 루트로 돌아가 다음 경로를 따라감
※ 디코딩 시 필요한 정보
- 허프만 트리 자체 또는 문자/비트 매핑 테이블 필요, 이중 하나를 함께 저장하거나 전송
- 아래 코드는 허프만 트리 자체를 넘겨줌 (root)

 

 

- 과정별 시간 복잡도

• 허프만 트리 생성 : O(n log n)
  → n은 서로 다른 문자 수 (보통 알파벳이면 26~128 정도)
• 전체 압축도 포함 : O(N + n log n)  (거의 선형)
  → 여기서 N은 전체 문자열 길이
• 실제 압축 시, 전체 텍스트를 순회하며 각 문자마다 매핑된 코드로 변환 → 인코딩: O(N)
• 복호화 시에는 트리를 따라 내려가므로 O(N)

	설명	시간 복잡도
빈도수 계산	문자열 한 번 순회	O(N) (문자열 길이)
최소 힙 초기화	힙에 n개 원소 삽입	O(n) (heapify)
트리 생성	힙에서 2개 pop + 삽입 반복 → n-1회	O(n log n)
코드 할당 (인코딩/디코딩)	트리 순회하며 각 문자에 이진 코드 부여	O(n) (DFS or BFS)

 

 

- 코드 구현

import heapq
from collections import defaultdict, Counter

# 트리 노드 클래스 정의
class Node:
    def __init__(self, char=None, freq=0, left=None, right=None):
        self.char = char      # 문자 (리프 노드만 가짐)
        self.freq = freq      # 빈도수
        self.left = left
        self.right = right

    def __lt__(self, other):
        return self.freq < other.freq  # heapq에서 빈도 비교

# 허프만 트리 생성 함수
def build_huffman_tree(text):
    freq_map = Counter(text)
    heap = [Node(char=c, freq=f) for c, f in freq_map.items()]
    heapq.heapify(heap)

    while len(heap) > 1:
        a = heapq.heappop(heap)
        b = heapq.heappop(heap)
        merged = Node(freq=a.freq + b.freq, left=a, right=b)
        heapq.heappush(heap, merged)

    return heap[0]  # 루트 노드

# 문자별 이진 코드 생성
def generate_codes(node, current_code="", code_map=None):
    if code_map is None:
        code_map = dict()
    if node.char is not None:
        code_map[node.char] = current_code
    else:
        generate_codes(node.left, current_code + "0", code_map)
        generate_codes(node.right, current_code + "1", code_map)
    return code_map

# 인코딩 함수
def huffman_encode(text):
    root = build_huffman_tree(text)
    code_map = generate_codes(root)
    encoded_text = ''.join(code_map[char] for char in text)
    return encoded_text, code_map, root

# 디코딩 함수
def huffman_decode(encoded_text, root):
    decoded = []
    node = root
    for bit in encoded_text:
        node = node.left if bit == '0' else node.right
        if node.char is not None:
            decoded.append(node.char)
            node = root
    return ''.join(decoded)

# 테스트
text = "AAAAAAABBBCCD"
encoded, code_map, root = huffman_encode(text)
decoded = huffman_decode(encoded, root)

print("원문:", text)
print("인코딩 결과:", encoded)
print("문자별 코드맵:", code_map)
print("디코딩 결과:", decoded)

 

 

3. 다른 압축 알고리즘과 비교

 

- 압축 알고리즘

• 크게 무손실 압축, 손실 압축(MP3, JPEG 등) 으로 나눔
• 무손실 압축 에는 통계 기반, 사전 기반(LZ77, LZ78), 반복 기반
• 통계 기반에는 허프만 코딩과 산술 코딩(Arithmetic Coding)
• 데이터 분석으로 정보량을 줄이는 건 아니지만, 같은 문자가 연속해서 나올 확률이 높아지는 구조 (패턴을 뭉침) 로 바꿔주는 BWT(회전 배열 → 사전 정렬 → 마지막 열 추출) 전처리 알고리즘(변환 알고리즘) 과 조합해서 사용
• 실제 압축 도구에서는 보완적으로 결합해서 사용   ex) ZIP 파일은 LZ77 + 허프만 (DEFLATE)

	허프만 코딩	LZW (Lempel–Ziv–Welch)	RLE (Run-Length Encoding)
압축 방식	빈도 기반 가변 길이 인코딩	사전 기반 문자열 치환	반복 문자 압축
원리	자주 나오는 문자는 짧게, 드문 문자는 길게 인코딩	문자열 패턴 → 사전에서 코드로 치환	연속된 동일 문자 → 문자 + 횟수로 치환
압축 단위	문자 단위 (Symbol)	문자열 (패턴)	연속된 동일 문자
대표 장점	평균 비트 수 최소화	반복되는 패턴에 효과적, 실시간 압축 가능	매우 단순, 속도 빠름
단점	트리 저장 필요, 실시간 처리 어려움	초기 사전 크기 제약, 복잡도 있음	반복 없으면 오히려 커짐
실전 예시	ZIP, JPEG, MP3 내부	GIF 파일 압축, Unix compress	흑백 이미지, 단순 텍스트

 

 

- 압축 효율 예시

	허프만 코딩	LZW	RLE
aaaaaaa	적당히 좋음	거의 동일 문자열이므로 적당히 좋음	매우 효율적
abababab	좋지 않음	효율적 (패턴 반복)	거의 차이 없음
abcdefg	별 차이 없음	비효율 (패턴 없음)	오히려 비효율

 

 

- 허프만의 위치적 특성 요약

역할	문자 빈도 기반 최적 압축 기법
강점	평균 코드 길이 최적화 (정보이론 기반), 고정된 코드 성능 보장
약점	패턴, 반복, 실시간 처리에는 약함
보완	다른 알고리즘과 결합되어 사용 (ex. BWT → MTF → RLE → 허프만)

 

 

- 산술 코딩 (Arithmetic Coding)

• 하나의 실수로 전체 메시지를 압축하는 고정밀 통계 기반 압축 알고리즘
• 압축률이 매우 뛰어남
  → 허프만은 문자 단위인 것에 비해 산술 코딩은 전체 메시지 단위
  → 각 문자마다 고정된 코드가 아닌 전체를 하나의 실수로 표현 + 접두사 조건 없음
  → 때문에 허프만보다 같거나 더 좋음
• But. 부동소수점 정밀도 문제 + 구현 복잡도 로 인해 일반적인 경우, 잘 쓰지 X
• 고급 압축 포맷이나 연구용 모델에서 주로 활용

정의	문자열 전체를 하나의 실수 구간 [0, 1) 안의 부구간(subinterval)으로 표현하여 압축하는 방식
압축 방식	전체 메시지를 하나의 부동소수점 값으로 인코딩함
동작 원리	각 문자의 등장 확률에 따라 [0,1) 구간을 분할하고, 입력 문자열을 읽으며 그 구간을 점점 좁혀나감
예시 (과정 요약)	① 문자별 확률 계산 ② [0,1) 구간을 확률에 따라 나눔 ③ 각 문자를 읽을 때마다 해당 구간으로 좁힘 ④ 마지막 구간 내의 실수 하나를 출력
압축 결과	최종적으로 특정 실수 하나를 이진수로 표현함 → 이 값 하나로 전체 문자열을 복원 가능
장점	- 압축률이 매우 높고 정밀함 - 문자 간 확률 차이가 적어도 효율 유지 - 부가 정보가 적음 (코드 테이블 불필요)
단점	- 부동소수점 오차 문제 존재 - 정밀한 연산이 필요하여 속도와 구현 난이도가 높음 - 정수 기반 재작성(Int-based version) 필요함
구현 방식	- 부동소수점 또는 정수 기반 산술 코딩 - 상한/하한을 반복적으로 계산하며 구간을 축소함
복호화 방식	동일한 확률 분포표를 이용해 실수 값을 다시 문자로 되돌리는 방식→ 실수값을 통해 문자 구간을 역추적
사용 예시	- JPEG2000 - H.264 - bzip2의 일부 변형 - 고정밀 압축 도구(PAQ, CM 등)
사용 목적	- 비트 단위까지 압축 효율을 극대화하고자 할 때 - 확률 모델 기반 통계 압축을 더 정밀하게 수행할 때