무손실 압축에서 Huffman·LZW·RLE를 고르는 기준

압축 방식은 데이터의 반복과 분포에서 갈린다

무손실 압축은 원본 데이터를 완전히 복원할 수 있도록 비트 수를 줄이는 부호화 방식이다. 정보 이론의 엔트로피 한계를 바탕으로 하지만, 실제 선택은 데이터가 어떤 형태로 반복되는지와 시스템이 감당할 수 있는 자원에 따라 달라진다.

Huffman Coding은 심볼의 발생 확률을 이용해 가변 길이 접두부 코드를 만든다. LZW는 입력에서 발견한 문자열 패턴을 동적 사전에 쌓아 코드로 바꾼다. Run-Length Encoding(RLE)은 같은 심볼이 이어지는 구간의 길이를 기록한다.

세 방식은 대체로 입력 스트림을 분석하고, 모델·사전·반복 구간을 찾은 뒤 토큰 또는 코드를 출력한다. 이후 컨테이너 헤더와 메타데이터를 포함해 비트스트림을 구성한다.

부호화 구조와 운영 제약

Huffman에서는 심볼 빈도를 집계한 뒤 최적 이진 트리를 만들고, 트리에서 각 심볼의 코드 길이를 정한다. LZW는 가장 긴 일치 접두어를 찾아 사전을 키우며 코드 폭 증가를 관리한다. RLE는 반복 구간을 어떤 기준으로 토큰화할지, 짧은 반복을 리터럴로 둘지 정해야 한다.

동기화 방식도 압축 포맷 설계의 일부다. Huffman의 접두부 코드, LZW의 고정폭 코드워드, RLE의 런 토큰은 서로 다른 오류 특성을 가진다. 블록 경계, LZW의 클리어 코드, 재동기 마커를 두면 오류가 이어지는 범위를 줄일 수 있다.

헤더에는 알파벳, 코드 길이 또는 canonical code 길이, 초기 사전 크기, 런 임계값 같은 정보가 들어갈 수 있다. 실시간 처리와 랜덤 접근 요구가 다르면 블록 기반 처리와 스트리밍 처리 중 선택도 달라진다.

성능 관점에서는 일반적으로 LZW ≥ Huffman >> RLE의 압축률 관계가 나타나지만 데이터 의존성이 크다. 자원 소모는 RLE가 가장 낮고 Huffman이 그 다음이며, LZW는 사전 메모리와 해시 비용을 고려해야 한다.

Huffman은 심볼 분포를 코드 길이로 바꾼다

압축 과정에서는 입력 심볼의 빈도를 모아 최소 힙으로 이진 트리를 구성하고, 각 심볼에 접두부 코드를 할당한다. canonical Huffman을 사용하면 코드 길이 테이블만 보관한 뒤 디코더 쪽에서 테이블을 다시 구성할 수 있다. 블록 단위로 적용하면 데이터 분포 변화에 맞출 수 있지만 헤더 오버헤드는 관리해야 한다.

복원할 때는 코드 길이 또는 트리를 읽은 뒤 비트스트림을 트리로 따라가며 심볼을 되살린다. 비트 경계가 깨지면 다음 블록 경계까지 오류가 전파될 수 있으므로 블록 마커가 이를 제한하는 역할을 한다.

알려진 분포에서는 최적 접두부 부호를 보장하며, PNG와 DEFLATE의 동적·정적 Huffman 단계처럼 널리 쓰인다.

LZW는 발견한 문자열을 사전에 축적한다

LZW는 단일 바이트 또는 알파벳으로 초기 사전을 채운다. 입력에서 최장 일치 문자열을 찾으면 해당 코드워드를 출력하고, 일치 문자열과 다음 문자를 새 사전 항목으로 추가한다. 코드 폭의 비트 수를 늘리는 정책과 사전이 포화됐을 때 클리어 코드로 리셋할지 고정할지도 정해야 한다.

복원기 역시 같은 초기 사전에서 시작한다. 코드워드를 해석하면서 이전 출력과 첫 글자를 결합해 사전을 같은 순서로 성장시키며, 사전에 아직 없는 코드가 나타나는 KWK 케이스의 처리 규칙도 필요하다.

텍스트와 단순 그래픽에서는 높은 압축률과 양호한 속도를 보인다. GIF와 TIFF의 LZW로 표준화됐고, 과거 특허 이슈는 현재 대부분 만료됐다.

RLE는 반복 구간을 길이와 값으로 기록한다

RLE는 동일 심볼이 이어지는 run을 찾은 다음 (길이, 값) 토큰으로 출력한다. 반복이 짧다면 리터럴로 내보내거나 이스케이프 기반 변형을 적용할 수 있다. 해제 과정은 토큰을 읽어 길이만큼 값을 반복 출력하고, 리터럴은 그대로 전달하는 방식이다.

구현이 단순하고 매우 빠르며, 긴 반복이 많은 흑백 비트맵·마스크·센서 제로 런에서 특히 효과적이다. 반대로 랜덤한 데이터에서는 오히려 크기가 늘 수 있어 사전 필터 또는 후단 부호화와 함께 쓰는 편이 낫다.

압축률만으로 결정할 수 없는 차이

알고리즘	압축률(전형)	속도(압축/해제)	메모리 사용	안정성/동기화	운영 편의
Huffman	중상: 20–40% 절감(텍스트/로그)	중/중상	낮음–중간(코드북)	블록 경계로 제한적 오류 전파	구현 용이, 광범위 채택
LZW	상: 30–60% 절감(텍스트/아이콘)	중/중상	중간–높음(사전)	클리어 코드로 재동기화 가능	특허 만료, 포맷 제약 유의
RLE	데이터 의존: 매우 높음(런 많음)–음수(역효과)	상/상	매우 낮음	토큰 단위 동기 용이	구현 최단, 필터로 적합

압축률과 속도는 데이터 분포, 블록 크기, 구현에 따라 변동한다.

⤢✕

파일 포맷과 스트림에서의 선택

GIF는 LZW 기반 인코딩을 사용하며 단순 그래픽과 아이콘에 적합하다. PNG와 DEFLATE는 LZ77과 Huffman을 결합해 텍스트와 이미지 전반에 적용된다. TIFF는 옵션별로 LZW와 PackBits(RLE)를 지원하며 스캐닝·팩스 워크플로에 맞는다.

센서와 텔레메트리에서는 0-런 RLE 필터 뒤에 Huffman을 붙이는 2단계 압축을 구성할 수 있다. 메모리가 제한된 환경에서는 RLE 또는 정적 Huffman을 채택하고 고정 헤더로 CPU를 절약한다. 로그, 설정, 소스코드처럼 반복 패턴이 많은 입력은 LZW 또는 Huffman에 유리하며, 블록 단위 처리는 재동기화에도 도움이 된다.

텍스트와 로그에서는 LZW로 30–60%, Huffman으로 20–40% 감소를 기대할 수 있다. 긴 런이 있는 바이너리 마스크와 흑백 이미지에서는 RLE가 5–10배 감소할 수 있다. CPU 예산이 제한된 환경에서는 RLE로 10–100x 처리량 향상이 가능하다. 블록과 마커를 설계하면 오류 전파 범위를 좁혀 장애 영향 반경을 줄일 수 있다.

조합할 때 확인할 운영 조건

길이-가중 분포가 뚜렷하면 Huffman, 반복 구간이 많으면 RLE, 일반 텍스트와 코드에는 LZW가 맞는다. RLE·Delta·Move-to-Front 같은 사전 필터 뒤에 Huffman을 붙이면 엔트로피 코딩과 결합할 수 있다.

LZW는 사전 크기 상한과 클리어 코드 정책을 명시해야 하며, Huffman은 canonical 코드로 테이블을 줄일 수 있다. 스트리밍 환경에서는 블록 경계, 체크섬, 재동기 마커와 함께 시간 창 기반 재시도 정책을 병행한다. 파일 포맷의 제약과 특허·라이선스 이력을 확인하고, PNG·DEFLATE 같은 현재 표준을 우선 도입하는 선택도 필요하다.

RLE 바이트열 구현

전제: Python 3.10+, 바이트열 대상, PackBits 유사 리터럴/런 혼합 방식 단순화.

def rle_encode(data: bytes) -> bytes:
    if not data:
        return b""
    out = bytearray()
    i = 0
    n = len(data)
    while i < n:
        # 런 탐지
        run_len = 1
        while i + run_len < n and data[i + run_len] == data[i] and run_len < 255:
            run_len += 1
        if run_len >= 3:  # 임계값: 3 이상만 런으로
            out.extend((255, run_len, data[i]))  # 255 = 런 마커
            i += run_len
        else:
            # 리터럴 버퍼링
            lit_start = i
            i += 1
            while i < n and (i + 1 >= n or data[i] != data[i + 1]) and (i - lit_start) < 255:
                i += 1
            lit = data[lit_start:i]
            out.extend((len(lit),))
            out.extend(lit)
    return bytes(out)

def rle_decode(data: bytes) -> bytes:
    out = bytearray()
    i, n = 0, len(data)
    while i < n:
        length = data[i]; i += 1
        if length == 255:  # 런 마커
            if i + 1 >= n:
                raise ValueError("Invalid RLE stream")
            run_len = data[i]; val = data[i + 1]; i += 2
            out.extend(bytes([val]) * run_len)
        else:
            if i + length > n:
                raise ValueError("Invalid RLE stream")
            out.extend(data[i:i + length]); i += length
    return bytes(out)

실제 적용에서는 마커 값 충돌 회피, 임계값 튜닝, 체크섬과 헤더 추가를 고려한다.