허프만 압축 언제 쓰나, zlib 전략·코드 길이 제한·작은 데이터 손익 계산

압축 설정을 고를 때 "허프만이 최적이라니까 그것만 쓰면 되지 않나", "레벨 9가 제일 좋겠지", "작은 JSON도 gzip 하면 줄겠지" 같은 생각이 들기 쉬워요. 결론부터 말하면 허프만은 혼자서는 기호 빈도만 줄이는 마지막 단계라, 실제 압축률은 반복 문자열을 찾는 LZ77 쪽이 대부분 정하고, 100바이트 안팎 데이터는 헤더 때문에 오히려 커질 수 있어요. 직접 허프만을 구현해야 한다면 최적성보다 코드 길이 상한과 비트 순서가 더 자주 문제를 일으켜요.

이 글은 "가장 드문 두 개를 합친다"는 원리 설명은 짧게 줄이고, 그 원리가 설정값과 운영 판단에서 어떤 숫자로 나타나는지를 모았어요. 측정은 Apple M1, 파이썬 3.14.8(내장 zlib 1.2.12, compression.zstd의 zstd 1.5.7)로 직접 했어요(2026-10-30). 재료는 이 사이트 저장소에 실제로 있는 파일(JS 294KB, JSON 150KB, 한국어 마크다운 194KB, PNG 274KB)과 무작위 바이트 300KB예요. 절대 시간은 기기마다 다르니 배수로 읽어 주세요.

허프만 코딩 언제 쓰나, 데이터 모양별 판단표

실무에서 "허프만을 쓸지"는 보통 "어떤 압축기와 설정을 쓸지"의 문제예요. DEFLATE(gzip·zlib·PNG·zip)와 zstd 리터럴 모두 마지막 단계에 허프만을 쓰니, 앞단과 묶어서 고르면 돼요.

전략 이름의 뜻은 zlib 공식 매뉴얼의 deflateInit2 설명에 있어요. Z_HUFFMAN_ONLY는 문자열 일치를 쓰지 않고 허프만만 강제하고, Z_RLE은 일치 거리를 1로 제한해 PNG 이미지 데이터에서 Z_HUFFMAN_ONLY만큼 빠르면서 더 잘 줄이도록 설계했다고 적어요. Z_FIXED는 동적 허프만 코드를 막아 단순한 해제기를 쓸 수 있게 해요. 매뉴얼은 전략이 압축률에만 영향을 주고, 잘못 골라도 출력의 정확성에는 영향이 없다고 못 박아요. 그러니 전략은 마음 편히 실험해도 돼요.

허프만만으로 얼마나 줄어드나, 파일 종류별 실측

같은 파일을 허프만만, zlib 레벨 1·6·9, zstd 레벨 3으로 압축해 원본 대비 크기를 쟀어요. 각 방식을 5번 돌려 가장 빠른 값을 적었어요.

숫자를 읽는 법은 이래요.

• 허프만만의 한계는 엔트로피로 미리 계산돼요. 바이트 빈도로 구한 0차 엔트로피는 JS 5.72비트/바이트(71.5%), JSON 5.16비트(64.5%), 한국어 마크다운 6.04비트(75.5%)였어요. Z_HUFFMAN_ONLY 결과(71.6%, 64.8%, 75.6%)가 이 값과 0.3%p 안쪽이에요. 블록마다 표를 새로 만들어서 파일 전체 한 표로 계산한 이상값(71.9%)보다도 조금 작았어요. 즉 허프만 단계는 이미 거의 끝까지 짜낸 상태예요.
• 나머지 39~47%p는 LZ77이 만들어요. 같은 키 이름·태그·구문이 반복되는 텍스트에서 앞단이 (길이, 거리) 쌍으로 바꿔 주는 몫이 훨씬 커요. 한국어 마크다운은 UTF-8 3바이트 글자가 많아 바이트 분포가 넓어서 세 텍스트 중 가장 덜 줄었어요. 한글 바이트 구조는 UTF-8·EUC-KR 바이트 글에 정리해 뒀어요.
• PNG는 이미 DEFLATE로 압축된 파일이에요. 바이트 엔트로피가 7.99비트로 8비트에 붙어 있어서 어떤 방식도 의미 있게 못 줄여요. 이런 파일을 응답마다 gzip 하면 CPU만 써요.

zlib 레벨 1·6·9와 zstd, 시간까지 보면

레벨 6에서 9로 올리면 크기는 0.2%p 줄고 시간은 2배가 됐어요. JSON에서도 26.2%→25.6%에 10.3ms→30.0ms였어요. 미리 한 번 압축해 두고 여러 번 내려보내는 정적 파일이면 9가 손해가 아니지만, 요청마다 압축하는 동적 응답이면 6이나 그 아래가 맞아요. 허프만만 쓰는 모드가 레벨 1과 비슷한 시간에 크기는 2.5배라, 텍스트에 Z_HUFFMAN_ONLY를 쓸 이유는 거의 없어요.

작은 데이터 압축 손익, 헤더 비용 계산

허프만을 쓰는 블록은 해제기에게 코드표를 알려 줘야 해요. RFC 1951의 DEFLATE 블록은 세 종류예요.

• 저장(BTYPE=00): 압축하지 않고 길이 필드만 붙여요. 블록당 약 5바이트가 늘어요.
• 고정 허프만(BTYPE=01): RFC에 정해진 표(리터럴 0~143은 8비트, 144~255는 9비트 등)를 써서 헤더에 표가 없어요.
• 동적 허프만(BTYPE=10): HLIT·HDIST·HCLEN 필드와 코드 길이 목록을 싣고, 그 목록도 다시 허프만으로 줄여요. 표가 데이터에 맞는 대신 헤더가 붙어요.

zlib은 블록을 내보낼 때 세 방식의 크기를 모두 계산해 가장 작은 것을 골라요(zlib trees.c의 _tr_flush_block). 그래서 원시 DEFLATE는 아무리 나빠도 "원본 + 5바이트" 근처에서 멈춰요. 여기에 감싸는 형식이 더해져요. zlib 형식은 앞 2바이트·뒤 Adler-32 4바이트로 6바이트, gzip 은 RFC 1952 기준 앞 10바이트·뒤 CRC-32와 길이 8바이트로 최소 18바이트예요.

JSON 파일의 같은 위치에서 크기만 바꿔 잘라 압축해 봤어요.

이 숫자로 정하면 이래요.

• 약 100바이트 미만은 압축하지 마세요. 64바이트 조각은 원시 DEFLATE로도 64바이트, gzip은 82바이트가 됐어요. 짧은 API 응답이나 웹소켓 메시지에 무조건 압축을 걸면 CPU를 쓰고 바이트도 늘어요.
• 128바이트에서 동적 블록이 이기기 시작해요. 128바이트 조각은 동적 91바이트, 고정 92바이트로 거의 같았고, 1KB부터는 동적이 확실히 작았어요. 동적 헤더가 수십 바이트라는 뜻이에요.
• 작은 메시지가 많으면 사전을 쓰세요. zlib은 deflateSetDictionary로 미리 정한 문자열을 앞에 둔 것처럼 압축할 수 있고, zstd도 사전 기능이 있어요. 같은 키 이름이 반복되는 짧은 JSON 수백만 건이라면 메시지마다 따로 압축하는 것보다 효과가 커요.

크기를 바이트·KB 단위로 바꿔 가며 볼 때는 데이터 용량 변환기를 쓰면 편해요.

코드 길이 제한 비용, 15비트·11비트를 넘는 경우 직접 계산

교과서 허프만에는 코드 길이 상한이 없지만, 실제 포맷에는 있어요. DEFLATE는 리터럴·거리 코드를 최대 15비트로, RFC 8878(Zstandard)은 허프만 코드를 최대 11비트로 제한해요. RFC 8878은 비트가 많을수록 정확하지만 헤더가 커지고 메모리나 복호화 비용이 늘어난다고 이유를 적어요.

언제 상한을 넘나

트리가 가장 깊어지는 분포는 빈도가 피보나치 수열(1, 1, 2, 3, 5, 8 …)을 따를 때예요. 직접 계산하면 이래요.

• 빈도가 피보나치인 기호 13개, 빈도 합 609면 최장 코드가 12비트가 되어 zstd의 11비트를 넘어요.
• 기호 17개, 빈도 합 4,180이면 16비트가 되어 DEFLATE의 15비트를 넘어요.

극단적인 경우만의 이야기도 아니에요. 이 저장소의 JS 파일 바이트 빈도로 상한 없는 허프만을 만들면 최장 17비트, 한국어 마크다운은 16비트가 나왔어요. 드물게 한두 번 나오는 바이트가 있으면 금방 깊어져요. 그래서 인코더는 상한 처리를 반드시 가져야 해요. zlib은 gen_bitlen에서 넘친 잎을 15로 자르고 짧은 잎 하나를 한 단 내려 길이 분포를 다시 맞추는 빠른 근사를 쓰고, 최적 해를 원하면 package-merge 알고리즘을 써요.

상한이 압축률에 주는 손실

package-merge로 상한마다 최적 길이를 구해 상한 없는 허프만과 총 비트를 비교했어요.

판단은 간단해요. 15비트와 11비트 상한의 압축률 비용은 무시해도 될 수준이에요. 상한을 정하는 진짜 이유는 해제 쪽 메모리와 속도예요.

해제기 조회 표 크기

해제기는 보통 비트 몇 개를 한 번에 읽어 표에서 기호를 찾아요. 한 단계 표로 최장 코드까지 덮으면 항목이 2의 상한제곱 개 필요해요. zlib의 표 항목 하나는 4바이트(op·bits 각 1바이트, val 2바이트)라서 이렇게 계산돼요.

zlib의 inftrees.h는 리터럴/길이 852개, 거리 592개, 합 1,444개가 동적 표의 최대 크기라고 적어요. zlib 설계 문서 algorithm.txt는 첫 표를 9비트로 둔 이유를 설명해요. DEFLATE는 수십 KB마다 표를 새로 만드는데, 2¹⁵ 항목 표를 매번 채우면 해제보다 표 채우기에 시간이 더 든다는 거예요. 직접 해제기를 만든다면 "짧은 코드는 한 번에, 긴 코드는 두 번째 표로"가 기본 설계예요.

치우친 분포의 한계, 기호 묶기와 산술 부호화·ANS

허프만은 기호마다 정수 비트를 줘서 기호당 최소 1비트가 들어요. 0과 1 두 기호만 있는 비트열에서 이 바닥이 얼마나 비싼지 계산해 봤어요. 기호 k개를 묶어 2ᵏ개짜리 알파벳으로 허프만을 만드는 흔한 우회법도 같이 넣었어요.

단위는 원래 기호 하나당 비트예요. 묶으면 엔트로피에 가까워지지만 두 가지 대가가 있어요. 알파벳이 2⁸=256개로 커져 표가 커지고, 최장 코드가 24~38비트로 길어져 15비트나 11비트 상한에 바로 걸려요. 확률 0.99에서는 8개를 묶어도 엔트로피의 약 2배예요.

그래서 이런 데이터는 다른 길로 가요.

• 연속 길이 부호화(RLE) 후 허프만: 0이 길게 이어지면 "0이 몇 개"를 기호로 바꾸면 분포가 덜 치우쳐요. zlib의 Z_RLE, DEFLATE 코드 길이 목록의 16·17·18 반복 기호가 같은 발상이에요.
• 산술 부호화·ANS: 여러 기호를 하나의 수로 누적해 기호당 소수 비트를 쓸 수 있어요. zstd가 리터럴에는 허프만을, 시퀀스에는 FSE(ANS 계열)를 쓰는 것도 이 차이 때문이에요.

반대로 바이트 분포가 그리 치우치지 않은 일반 텍스트에서는 앞의 측정처럼 허프만이 엔트로피와 0.5%p 안쪽이라, 산술 부호화로 바꿔 얻을 몫이 작아요.

직접 구현할 때 자주 나는 문제와 확인 순서

포맷을 직접 읽고 쓰는 일은 드물지만, 임베디드 해제기·커스텀 바이너리 프로토콜·학습용 구현에서는 생겨요. 증상별로 이 순서로 보세요.

1. 비트 순서. RFC 1951 3.1.1절은 일반 데이터 요소는 바이트의 최하위 비트부터 채우지만, 허프만 코드는 코드의 첫 비트부터 담는다고 적어요. 길이 계산은 맞는데 gzip이 못 푼다면 대개 여기예요. 비트를 손으로 확인할 때는 진법 변환기로 바이트를 2진수로 펼쳐 보면 빨라요.
2. 기호가 하나뿐인 입력. 합치기가 한 번도 일어나지 않아 길이 0이 나와요. 0으로 채운 버퍼, 같은 문자만 반복되는 로그에서 터져요. 1비트를 강제로 주세요.
3. 헤더에 무엇을 싣나. 빈도가 같은 노드를 어떤 순서로 합치느냐에 따라 트리 모양이 달라져요. "빈도만 보내고 양쪽에서 트리를 다시 만든다"는 설계는 동점 처리 하나만 달라도 깨져요. 길이를 싣고 정규 코드로 다시 만드세요.
4. 상한을 넘는 기호. 작은 테스트 입력에서는 절대 안 나와요. 피보나치 빈도로 만든 입력(빈도 합 4,180 이상)을 테스트에 넣어 두세요.
5. 크라프트 합. 길이 목록에서 2^(-길이)를 모두 더하면 정확히 1이어야 빈틈없는 접두 코드예요. zlib의 inflate_table도 넘치거나(over-subscribed) 모자란(incomplete) 길이 목록을 거절해요. 단, 거리 코드가 하나뿐인 경우처럼 RFC가 허용하는 예외는 따로 처리해요. 해제기가 이 검사를 빼면 손상된 입력에서 표 바깥을 읽어요.
6. 양방향 왕복 시험. 내 인코더 출력을 zlib으로 풀고, zlib 출력을 내 해제기로 푸는 시험을 무작위 입력 수천 개로 돌려요. 한쪽만 하면 대칭으로 틀린 버그(인코더와 해제기가 똑같이 비트를 뒤집는 등)를 놓쳐요.

import random, zlib

def roundtrip(my_inflate, trials=3000):
    rnd = random.Random(0)
    for t in range(trials):
        n = rnd.choice([0, 1, 2, 17, 300, 5000])
        alphabet = rnd.choice([b"a", b"ab", bytes(range(256))])
        data = bytes(rnd.choice(alphabet) for _ in range(n))
        level = rnd.choice([0, 1, 6, 9])
        strategy = rnd.choice([0, zlib.Z_HUFFMAN_ONLY, zlib.Z_RLE, zlib.Z_FIXED])
        c = zlib.compressobj(level, zlib.DEFLATED, -15, 8, strategy)
        raw = c.compress(data) + c.flush()
        if my_inflate(raw) != data:
            return t, level, strategy, data   # 처음 틀린 입력을 돌려줘요
    return None

입력 길이에 0·1을, 알파벳에 한 글자짜리를, 전략에 Z_FIXED를 섞은 것이 핵심이에요. 저장·고정·동적 세 블록 종류와 기호 하나 경우를 모두 지나가요.

도입 전에 따질 것, 운영에서 압축을 켤 때

• 직접 만들지 말고 라이브러리를 쓰세요. zlib·zstd는 수십 년 동안 손상 입력 처리가 다듬어졌어요. 직접 구현은 위 점검표 1~6을 모두 통과해도 손상된 입력에서의 안전성을 따로 검증해야 해요.
• 해제 쪽 크기 제한을 함께 두세요. 허프만과 LZ77이 잘 맞물리면 작은 입력이 아주 크게 풀려요. 요청 본문을 풀 때 상한 없이 풀면 메모리를 다 써요. 설정 방법은 Content-Encoding 압축 해제 보안 글에 정리해 뒀어요.
• 이미 압축된 형식은 목록으로 제외하세요. 이미지·영상·zip·woff2 같은 형식에 gzip을 다시 걸면 위 PNG처럼 0.3% 줄이려고 수십 ms를 써요.
• 호환성이 먼저인지 속도가 먼저인지. 모든 클라이언트가 풀 수 있어야 하면 gzip(DEFLATE), 양쪽을 통제할 수 있고 속도가 중요하면 zstd예요. 이번 측정에서 zstd 레벨 3은 zlib 레벨 6보다 7.9배 빨랐고 크기는 0.9%p 컸어요.
• 허프만이 "최적"이라는 말의 범위를 기억하세요. 정해진 빈도에서 정수 비트 접두 코드 중 최적이라는 뜻이에요. 앞단 모델링이 바뀌면 결과는 얼마든지 달라져요. 그리디 선택이 언제 최적이 되는지 판단하는 법은 그리디 알고리즘 판단표 글에서 다뤘어요.

자주 묻는 질문

Z_HUFFMAN_ONLY는 언제 쓰나요?

반복 문자열은 거의 없고 값 분포만 치우친 데이터에서 문자열 탐색 시간을 아끼고 싶을 때예요. 일반 텍스트에서는 이번 측정에서 레벨 1과 비슷한 시간에 크기가 2.5배라 쓸 이유가 없어요. 이미지 필터 잔차처럼 짧은 반복이 있으면 Z_RLE도 같이 재 보세요.

작은 JSON 응답도 gzip 하는 게 좋나요?

약 100바이트 미만은 하지 않는 게 나아요. 64바이트 조각이 원시 DEFLATE로도 64바이트, gzip으로는 82바이트가 됐어요. 128바이트부터 줄기 시작하고 1KB면 약 3분의 1이 되니, 최소 압축 크기를 수백 바이트 근처로 두면 돼요.

압축 레벨 9가 항상 좋은가요?

크기 차이는 작고 시간은 커요. JS 294KB에서 레벨 6 대비 0.2%p 줄고 시간은 2배였어요. 한 번 압축해 여러 번 내려보내는 정적 파일에만 쓰고, 요청마다 압축하는 응답에는 6 이하를 쓰세요.

코드 길이를 15비트로 제한하면 압축률이 많이 떨어지나요?

거의 안 떨어져요. 실제 파일 바이트 빈도로 계산하니 15비트 상한의 손실은 0.001%, zstd의 11비트도 0.1~0.2%였어요. 손실은 9비트 아래에서 1~7%로 커져요. 상한은 압축률보다 해제기 표 크기와 속도를 위한 거예요.

허프만 대신 산술 부호화를 써야 하는 경우는 언제인가요?

한 기호 확률이 0.9를 넘는 식으로 분포가 크게 치우칠 때예요. 확률 0.99인 비트열에서 허프만은 기호당 1비트로 엔트로피의 약 12배를 쓰고, 8개씩 묶어도 약 2배예요. 일반 텍스트처럼 분포가 넓으면 허프만도 엔트로피와 0.5%p 안쪽이라 바꿀 이득이 작아요.

직접 만든 DEFLATE 인코더가 gzip으로 풀리지 않아요.

먼저 비트 순서를 보세요. 허프만 코드는 첫 비트부터, 나머지 필드는 최하위 비트부터 담아요. 그다음 기호 하나뿐인 블록의 길이 0, 15비트를 넘는 길이, 크라프트 합이 1이 아닌 길이 목록을 차례로 확인하세요.

정리

• 허프만은 기호 빈도만 줄이는 마지막 단계예요. 텍스트에서 허프만만으로는 64~76%, LZ77을 더한 zlib 레벨 6은 24~36%였어요.
• 약 100바이트 미만은 압축하지 말고, 이미 압축된 형식은 제외하세요. 짧은 메시지가 많으면 사전 압축을 고려하세요.
• 15비트·11비트 길이 상한의 압축률 손실은 0.2% 안쪽이에요. 대신 상한 처리와 크라프트 합 검사를 빼면 해제가 깨지거나 손상 입력에 취약해져요.
• 한 기호 확률이 0.9를 넘으면 허프만의 1비트 바닥이 비싸지니 RLE·산술 부호화·ANS를 보세요.
• 직접 구현했다면 zlib과 양방향 왕복 시험으로 검증하고, 해제 쪽 크기 제한은 압축 해제 보안 글대로 함께 두세요.

더 깊이 읽기

이 글은 실무에서 판단할 때 필요한 것 위주로 정리했어요. 같은 주제의 내부 동작 원리는 devboi 기술 블로그의 허프만 코딩 원리 — 그리디 최적 증명과 DEFLATE 정규 코드에서 도식과 코드로 단계별로 풀었어요.