압축 알고리즘: Huffman Coding과 LZW 알고리즘

압축 알고리즘은 데이터를 효율적으로 저장하고 전송하기 위한 핵심 기술입니다. 데이터를 압축하면 저장 공간을 절약하고 전송 속도를 높일 수 있습니다. 이번 글에서는 대표적인 압축 알고리즘인 Huffman Coding과 LZW(Lempel-Ziv-Welch) 알고리즘의 원리, 구현 방법, 그리고 활용 사례를 살펴보겠습니다.

압축 알고리즘이란?

 

압축 알고리즘은 데이터를 표현하는 데 필요한 비트를 줄여 데이터 크기를 감소시키는 기법입니다. 크게 두 가지 방식으로 분류됩니다:

• 무손실 압축: 원본 데이터를 복구할 수 있는 압축 방식.
• 손실 압축: 원본 데이터를 복구할 수 없지만, 사람이 인지하기 힘든 데이터를 제거.

 

1. Huffman Coding

 

Huffman Coding은 무손실 압축 알고리즘으로, 데이터의 각 문자를 이진 코드로 변환하여 저장 공간을 줄입니다. 자주 나타나는 문자는 짧은 코드로, 드물게 나타나는 문자는 긴 코드로 표현합니다.

작동 원리

• 빈도 분석: 입력 데이터에서 각 문자의 빈도를 계산.
• 우선순위 큐 생성: 빈도가 낮은 문자를 우선순위로 하는 큐 생성.
• 트리 생성: 빈도 순으로 두 노드를 병합하여 이진 트리를 만듦.
• 코드 생성: 트리에서 왼쪽은 0, 오른쪽은 1로 코드를 생성.

시간 복잡도

• O(n log n) (n은 고유 문자의 수).

Python 구현

import heapq
from collections import defaultdict

class HuffmanNode:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None

    def __lt__(self, other):
        return self.freq < other.freq

def huffman_encoding(data):
    if not data:
        return "", None

    freq = defaultdict(int)
    for char in data:
        freq[char] += 1

    heap = [HuffmanNode(char, freq[char]) for char in freq]
    heapq.heapify(heap)

    while len(heap) > 1:
        node1 = heapq.heappop(heap)
        node2 = heapq.heappop(heap)
        merged = HuffmanNode(None, node1.freq + node2.freq)
        merged.left, merged.right = node1, node2
        heapq.heappush(heap, merged)

    root = heap[0]
    huffman_codes = {}

    def generate_codes(node, code=""):
        if node:
            if node.char:
                huffman_codes[node.char] = code
            generate_codes(node.left, code + "0")
            generate_codes(node.right, code + "1")

    generate_codes(root)
    encoded_data = "".join(huffman_codes[char] for char in data)
    return encoded_data, root

# 사용 예제
data = "hello huffman"
encoded, tree = huffman_encoding(data)
print(f"압축된 데이터: {encoded}")

2. LZW (Lempel-Ziv-Welch)

 

LZW는 문자열에서 반복되는 패턴을 사전에 저장하고, 이를 참조하여 데이터를 압축하는 무손실 압축 알고리즘입니다.

작동 원리

• 사전 초기화: 입력 데이터의 고유 문자를 기반으로 초기 사전 생성.
• 패턴 탐색: 현재 패턴이 사전에 없을 경우, 이전 패턴을 저장하고 새 패턴을 추가.
• 출력: 각 패턴에 대한 사전의 인덱스를 출력.

시간 복잡도

• O(n) (n은 데이터 길이).

Python 구현

def lzw_compress(data):
    dictionary = {chr(i): i for i in range(256)}
    next_code = 256
    current = ""
    compressed = []

    for char in data:
        combined = current + char
        if combined in dictionary:
            current = combined
        else:
            compressed.append(dictionary[current])
            dictionary[combined] = next_code
            next_code += 1
            current = char

    if current:
        compressed.append(dictionary[current])
    return compressed

# 사용 예제
data = "ABABABABABABABAB"
compressed = lzw_compress(data)
print(f"LZW 압축 결과: {compressed}")

Huffman Coding vs LZW

특성	Huffman Coding	LZW
압축 방식	빈도 기반 가변 길이 코드 생성	반복 패턴 기반 사전 활용
효율성	고유 문자가 많은 경우 효율적	반복 패턴이 많은 데이터에 적합
사용 환경	텍스트 파일, 전송 데이터	이미지, 텍스트, 실행 파일
구현 난이도	상대적으로 쉬움	비교적 복잡

3. 활용 사례

1. Huffman Coding:

• 텍스트 파일 압축.
• 전송 데이터의 크기 감소.
• 이미지 포맷(예: PNG)의 압축 알고리즘.

2. LZW:

• GIF 이미지 압축.
• 데이터 전송 프로토콜.
• ZIP 파일 포맷 일부 구현.

결론

 

Huffman Coding과 LZW는 무손실 압축 알고리즘으로, 데이터 유형과 특성에 따라 적합한 방법을 선택할 수 있습니다. Huffman Coding은 문자 빈도가 명확한 경우 효율적이며, LZW는 반복 패턴이 많은 데이터에서 강력한 압축 성능을 발휘합니다. 이 두 알고리즘을 깊이 이해하면 데이터 저장 및 전송 효율성을 크게 향상시킬 수 있습니다.