공부 발표

압축은 왜 되는가

엔트로피에서 컬럼 저장까지 — 압축은 마법이 아니라 데이터에 이미 있는 편중을 회수하는 일이다
2026-09 · Rami · 실측: Python zlib, lzma, 20만 행 합성 데이터
시작

질문은 둘이다 — 왜 되는가, 그리고 왜 무한히는 안 되는가

왜 되는가
8MB짜리 파일이 0.5MB가 된다. 정보가 사라진 것도 아닌데 어떻게 크기가 16분의 1이 되는가. 그 여유 공간은 원래 어디에 있었나.
왜 무한히는 안 되는가
압축한 파일을 다시 압축하면 왜 안 줄어드는가. 어떤 파일이든 반드시 줄이는 알고리즘은 왜 만들 수 없는가.
두 번째 질문이 더 쉽다. 거기서 시작한다.
1부

왜 무한히는 안 되는가

셈만 할 줄 알면 증명되는 한계
1부 · 한계

모든 입력을 줄이는 무손실 압축기는 존재할 수 없다

n비트 문자열 2ⁿ 개 서로 다른 입력 전부 n비트보다 짧은 문자열 2ⁿ − 1 개 1 + 2 + 4 + … + 2ⁿ⁻¹ = 길이 0부터 n−1까지 전부 합쳐도 압축 = 단사 함수여야 칸이 하나 모자란다 비둘기 2ⁿ마리를 집 2ⁿ−1개에 넣으면 최소 두 마리가 한 집에 든다. 두 입력이 같은 출력을 갖는 순간 복원이 불가능하다. 그러므로 어떤 입력은 반드시 길어진다.
1부 · 한계

그러므로 압축기는 "줄이는 장치"가 아니라 "재분배하는 장치"다

모든 입력에 같은 길이를 주는 대신 자주 오는 입력 A 가끔 오는 입력 B 거의 안 오는 입력 C 빈도에 따라 길이를 다시 나눈다 A 짧게 B 비슷하게 C 길게 (손해 감수) 평균이 줄어드는 이유는 자주 오는 것에 짧은 부호를 몰아줬기 때문이다. 드문 입력은 오히려 길어진다. 압축된 파일을 다시 압축하면 안 줄어드는 이유도 이것이다 — 이미 편중이 회수된 데이터는 "자주 오는 것"이 없는, 균등에 가까운 데이터다.
1부 · 한계

그래서 첫 질문의 답: 실제 데이터는 균등하지 않기 때문이다

텍스트
한국어 문서에서 "의", "는", "다"는 수백 번 나오지만 "쮤"는 거의 안 나온다. 바이트 256개가 균등하게 쓰이는 문서는 없다.
로그와 테이블
status 컬럼은 값이 네 개뿐인데 한 값이 70%다. 타임스탬프는 바로 앞 값과 몇 초 차이다. 다음 값이 거의 예측된다.
이미지와 음성
이웃 픽셀은 거의 같은 색이다. 이웃 샘플은 거의 같은 진폭이다. 예측 가능한 부분을 빼면 남는 것이 적다.
편중과 규칙성이 곧 압축 가능성이다. 그 양을 정확히 재는 자가 있다. 다음 파트의 엔트로피다.
2부

정보량과 엔트로피

Shannon, A Mathematical Theory of Communication (1948)
2부 · 엔트로피

정보량은 놀람의 크기다 — 드문 일이 일어날수록 정보가 많다

I(x) = −log₂ p(x) 비트사건 x의 확률이 p일 때, 그 사건이 일어났다는 소식이 담는 정보의 양
"내일 해가 뜬다"
p ≈ 1 → I ≈ 0비트. 확실한 사건은 아무 정보도 주지 않는다.
"동전이 앞면이다"
p = 1/2 → I = 1비트. 둘 중 하나를 확정하는 데 정확히 1비트.
"주사위가 6이다"
p = 1/6 → I ≈ 2.58비트. 여섯 중 하나를 확정하는 데 2.58비트.
2부 · 엔트로피

왜 로그인가 — 독립 사건의 정보는 더해져야 하기 때문이다

// 독립 사건 두 개가 함께 일어날 확률은 곱
p(A ∧ B) = p(A) × p(B)

// 그런데 정보는 합이어야 자연스럽다
I(A ∧ B) = I(A) + I(B)

// 곱을 합으로 바꾸는 함수는 로그뿐이다
−log(p(A) × p(B)) = −log p(A) − log p(B)  ✓

// 밑이 2면 단위가 비트: 예/아니오 질문 횟수
동전 두 번의 결과를 알리는 데 1비트 + 1비트 = 2비트가 들어야 말이 된다. 확률은 1/4이고, −log₂(1/4) = 2다.
비트 단위의 직관: "예/아니오 질문을 최소 몇 번 해야 답을 확정하는가". 8개 중 하나면 3번, 확률 1/8, 3비트.
2부 · 엔트로피

엔트로피는 정보량의 기댓값이다 — 심볼 하나가 평균적으로 담는 비트

H = Σ p(x) · I(x) = −Σ p(x) · log₂ p(x)모든 심볼 x에 대해, 그 확률만큼 가중한 정보량의 합
균등할 때 최대
심볼이 k개고 전부 같은 확률이면 H = log₂k. 4개면 2비트, 256개면 8비트. 어떤 값이 올지 전혀 못 맞히는 상태다.
치우칠수록 작아진다
한 심볼이 확률 1이면 H = 0. 다음 값이 뭔지 이미 알면 알려줄 것이 없다. 편중이 곧 낮은 엔트로피다.
2부 · 엔트로피

동전 하나로 본다 — 확률 0.9면 엔트로피는 절반 이하로 떨어진다

0 0.5 1.0 앞면 확률 p 0 1 비트 H(p) p=0.5 → 1.00비트 p=0.9 → 0.47비트 p=0.99 → 0.08비트 H(0.9) 계산 −0.9·log₂0.9 − 0.1·log₂0.1 = 0.9×0.152 + 0.1×3.32 = 0.137 + 0.332 ≈ 0.47 비트/던지기 1,000번 결과를 470비트에 담는다
2부 · 엔트로피

Shannon의 정리 — 엔트로피는 넘을 수 없는 바닥이고, 닿을 수는 있다

하한: 평균 부호 길이 ≥ H
어떤 무손실 부호도 심볼당 평균 길이를 엔트로피 아래로 내릴 수 없다. 1부의 비둘기집이 "안 된다"를 말했다면, 이 정리는 "얼마까지는 된다"의 정확한 숫자를 준다.
달성 가능: H에 임의로 근접
심볼을 묶어서 부호화하면 평균 길이를 H + ε까지 줄일 수 있다. 그래서 엔트로피는 목표치다. 좋은 압축기란 이 바닥에 얼마나 붙느냐로 평가된다.
주의할 전제 하나. 이 정리는 심볼이 독립적으로, 같은 분포에서 나온다고 가정한다. 실제 데이터는 앞뒤가 연관돼 있어서(반복, 순서) 이 바닥보다 더 아래로 갈 수 있다. 4부에서 다시 만난다.
Shannon, 1948. 소스 부호화 정리(source coding theorem).
2부 · 실측

실측 — 테이블 컬럼의 엔트로피를 직접 계산해 봤다

컬럼 (20만 값)분포심볼 수엔트로피 (비트/값)균등이었다면이론 하한 (20만 값)
statusactive 70%, inactive 15%, pending 10%, deleted 5%41.322.0033.0 KB
category5개 값 균등52.322.3258.0 KB
price6개 값 균등62.582.5864.6 KB
status는 값이 4개니 균등이면 2비트인데, 70%가 한 값에 몰려 있어 1.32비트다. 편중이 0.68비트를 벌어 줬다. category와 price는 균등하게 만들었으니 log₂k 그대로다. 텍스트로 저장하면 status 컬럼은 1.49MB인데, 이론 하한은 33KB다. 45배의 여유가 편중에서 나온다.
직접 실측 · 합성 데이터 20만 행 · Python으로 빈도 세어 −Σp·log₂p 계산
3부

부호를 만드는 방법

Huffman에서 ANS까지 — 바닥에 어떻게 붙는가
3부 · 부호화

구분자 없이 해독하려면 어떤 부호도 다른 부호의 앞부분이면 안 된다

// 나쁜 부호: A=0, B=01, C=1
"01" 을 받았다
  → A 다음 C ?  (0 | 1)
  → B ?          (01)
해독 불가능 — 0이 01의 접두사

// 접두 부호: A=0, B=10, C=11
"0101110" 을 받았다
  → 0 | 10 | 11 | 10
  → A B C B   유일하게 해독
0 1 A 0 1 B C 심볼이 전부 잎(leaf)에 있으면 접두 부호다
3부 · 부호화

짧은 부호는 한정된 자원이다 — Kraft 부등식

Σ 2−ℓᵢ ≤ 1길이 ℓᵢ인 접두 부호들이 공존하려면 이 합이 1을 넘을 수 없다
직관
길이 1 부호 하나(0)를 쓰면 트리의 절반을 소비한다. 남은 절반에서 길이 2 부호는 최대 둘. 짧은 부호를 하나 쓸 때마다 다른 부호들이 쓸 자리가 준다.
그래서 배정은 곧 예산 문제
누구에게 짧은 부호를 줄 것인가. 답은 자명하다 — 자주 오는 심볼에게. 이 예산을 최적으로 배정하는 알고리즘이 다음 장이다.
3부 · 부호화

Huffman 1단계 — 가장 드문 둘을 합쳐 하나로 본다

심볼과 확률 A0.40 B0.30 C0.20 D0.10 가장 드문 둘: C(0.20)와 D(0.10) 병합 1 A0.40 B0.30 (CD)0.30 C D 탐욕 규칙 하나뿐이다: 확률이 가장 낮은 두 노드를 합쳐 새 노드(확률은 합)로 대체한다. 드문 것들이 먼저 합쳐지니 트리의 깊은 곳(긴 부호)으로 밀려나고, 자주 오는 것은 끝까지 살아남아 뿌리 가까이(짧은 부호)에 남는다.
David Huffman, 1952 — MIT 대학원 수업 과제로 고안했다.
3부 · 부호화

Huffman 2단계 — 트리가 완성되면 경로가 곧 부호다

1.0 0 1 A 0.40 0.6 0 1 B 0.30 0.3 0 1 C D
심볼확률부호길이기여
A0.40010.40
B0.301020.60
C0.2011030.60
D0.1011130.30
평균 길이 1.90비트. 엔트로피는 1.846비트. 고정 길이(2비트)보다 짧고, 바닥에서 0.05비트 위다.
3부 · 부호화

Huffman은 최적이지만 정수 비트의 벽이 있다

// 심볼 두 개: X 0.9, Y 0.1
이론 정보량
  X: −log₂0.9 = 0.152 비트
  Y: −log₂0.1 = 3.32 비트
  엔트로피 H = 0.47 비트/심볼

Huffman 부호
  X = 0   (1비트 — 0.152를 못 준다)
  Y = 1   (1비트)
  평균 = 1.00 비트/심볼

바닥의 2배 이상을 쓴다
Huffman은 심볼당 정수 길이 부호 중에서 최적이다. 하지만 정보량이 1비트 미만인 심볼에는 최소 1비트를 배정해야 한다.
편중이 심할수록 손해가 커진다. 확률 0.99면 이론은 0.014비트인데 여전히 1비트다. 바로 압축이 가장 잘 될 데이터에서 가장 못한다.
해결: 심볼 하나가 아니라 메시지 전체를 하나의 수로 부호화한다.
3부 · 부호화

산술 부호화 — 메시지 전체를 [0, 1) 안의 한 구간으로 좁혀 간다

심볼 X(0.9), Y(0.1). 메시지 "XXY"를 부호화한다. 시작 01 X 읽음 앞 90%를 취한다 → [0, 0.9) X 읽음 다시 앞 90% → [0, 0.81) Y 읽음 뒤 10% → [0.729, 0.81) 최종 구간 너비 = 0.9 × 0.9 × 0.1 = 0.081. 이 구간 안의 한 점을 지정하는 데 −log₂0.081 ≈ 3.6비트. Huffman은 3비트지만 메시지가 길어질수록 격차가 커진다.
구간 너비 = 확률의 곱 → 필요 비트 = 정보량의 합. 심볼당 분수 비트가 자연스럽게 달성된다.
3부 · 부호화

ANS — 산술 부호화의 압축률을 Huffman의 속도로, 그래서 zstd가 쓴다

Huffman
빠르다. 표 조회 한 번. 하지만 정수 비트의 벽.
산술 부호화
바닥에 붙는다. 하지만 심볼마다 곱셈과 나눗셈, 그리고 오래 특허에 묶여 있었다.
ANS (Duda, 2009 무렵)
상태를 정수 하나로 유지하며 표 조회로 갱신한다. 압축률은 산술에 가깝고 속도는 Huffman에 가깝다.
Asymmetric Numeral Systems. zstd의 FSE(Finite State Entropy)가 이 계열이고, 이후 여러 현대 압축기가 채택했다. "이론적 한계"와 "실용적 속도"가 60년 만에 한 자리에 모인 사례다.
4부

반복을 잡는다

통계만으로는 못 보는 것 — 사전 기반 압축
4부 · 사전

같은 문장이 100번 반복되는데, 글자 빈도만 보면 그걸 모른다

// 이런 로그 파일
2026-09-04 09:50:01 INFO sync ok
2026-09-04 09:50:02 INFO sync ok
2026-09-04 09:50:03 INFO sync ok
 … (100줄)

// 글자 빈도로 보면
'0': 많음, ' ': 많음, 'I': 100번 …
→ 심볼당 엔트로피는 그저 보통 텍스트 수준

// 하지만 사람 눈에는
"앞 줄과 초 단위만 다르다" → 거의 0비트
Shannon 정리의 전제가 여기서 깨진다. 심볼은 독립이 아니다. 앞에 나온 것이 뒤를 결정한다.
이 구조를 잡는 방법은 심볼 단위 부호화가 아니라 "앞에 나온 걸 가리키기"다. 사전(dictionary) 기반 압축의 아이디어다.
4부 · 사전

LZ77 — 이미 지나간 문자열을 (거리, 길이)로 가리킨다

입력 abra cad abra "abra" 처음 "abra" 다시 7글자 뒤로, 4글자 복사 출력 a b r a c a d (7, 4) 슬라이딩 윈도우 최근 몇 KB~몇 MB를 창으로 들고 있으면서 현재 위치에서 가장 길게 일치하는 과거를 찾는다. 찾으면 (거리, 길이) 한 쌍으로 대체한다. 못 찾으면 글자 그대로(literal) 내보낸다. 반복 100줄 로그는 (거리, 길이) 100개가 된다 Lempel과 Ziv, 1977. 압축 "레벨"을 올린다는 것은 대개 이 탐색을 더 오래, 더 멀리 한다는 뜻이다.
4부 · 사전

현대 압축기는 두 층이다 — 반복을 잡은 뒤, 남은 것의 편중을 잡는다

원본 바이트 반복 + 편중 1층 · 사전 (LZ77 계열) 반복을 (거리, 길이)로 치환 출력: literal + 매치 정보 2층 · 엔트로피 부호화 literal과 거리·길이 값의 편중을 Huffman / FSE로 짧게 Deflate (gzip, zip, PNG)= LZ77 + Huffman zstd= LZ77 계열 + FSE·Huffman + 사전 학습 LZMA (xz, 7z)= LZ77 계열 + 범위 부호화(산술 계열), 느리지만 강함
4부 · 사전

zstd가 기본값이 된 이유 — 압축률과 속도의 곡선을 통째로 옮겼다

레벨은 탐색 예산이다
레벨 1은 매치를 대충 빨리 찾고, 레벨 19는 오래 멀리 찾는다. 해제 속도는 레벨과 거의 무관하다. 쓸 때 한 번 고생하고 읽을 때는 항상 빠르다는 성질이 데이터 저장에 맞는다.
FSE가 2층을 바꿨다
Huffman 자리에 ANS 계열 FSE를 넣어 정수 비트의 벽을 넘었다. 편중이 심한 데이터(로그, 컬럼)에서 특히 이득이다.
사전 학습
작은 파일 수천 개를 압축할 때 각 파일 안에는 반복이 없어 LZ77이 무력하다. 샘플로 공용 사전을 미리 학습해 두면 첫 바이트부터 참조할 과거가 있다.
우리 환경
Spark 잡의 rdd, shuffle, spill 압축이 전부 zstd level 3다(지난 발표 실측). Parquet과 ORC도 zstd를 지원한다. 레벨 3은 "CPU를 거의 안 쓰면서 gzip보다 잘 줄이는" 지점으로 자리 잡았다.
4부 · 사전

손실 압축은 다른 게임이다 — 정보를 회수하는 게 아니라 버린다

무손실 (오늘의 주제)
원본을 비트 단위로 복원한다. 한계는 엔트로피(와 데이터의 구조). zstd, gzip, Parquet의 컬럼 인코딩이 전부 여기다.
손실 (JPEG, MP3, 영상)
사람이 못 느끼는 정보를 먼저 버리고, 남은 것을 무손실로 압축한다. 한계가 엔트로피가 아니라 지각 모델이라 수십 배가 가능하다.
데이터 파이프라인에서 손실 압축을 쓰는 곳은 없다고 생각하기 쉽지만, 근사 집계(HyperLogLog, 샘플링)는 개념적으로 같은 거래다. 정확도를 지불하고 크기를 산다.
5부

데이터를 어떻게 놓느냐가 압축률을 정한다

컬럼 저장, 인코딩, 그리고 실측
5부 · 배치

컬럼 저장이 압축에 유리한 이유는 엔트로피 한 줄로 설명된다

행 지향 — 서로 다른 타입이 번갈아 인접한다 1000000 1735689600 fleamarket active 5000 1000001 1735689607 jobs active 0 1000002 1735689614 realty pending 30000 … 열 지향 — 같은 타입, 비슷한 값이 이어진다 1000000 1000001 1000002 1000003 1000004 … 1735689600 1735689607 1735689614 … fleamarket jobs realty commerce community … active active pending active active … 국소 엔트로피가 다르다 행 지향: 압축기의 창 안에 id, 시각, 문자열, 숫자가 섞여 있다. 분포가 넓다. 열 지향: 창 안이 전부 status 값이다. 심볼 4개, 70%가 한 값. 분포가 좁다. 같은 바이트인데 배치만 바꿔 엔트로피를 낮췄다 Dremel(1주차)이 컬럼을 택한 이유의 절반이 이것이다
5부 · 실측

실측 — 같은 20만 행을 배치만 바꾸자 압축률이 9배에서 16배가 됐다

배치 (원본 7.97MB, 5컬럼 × 20만 행)zlib 결과zlib 배율lzma 결과lzma 배율
행 지향 (레코드 단위로 이어 붙임)1.38 MB5.77배0.86 MB9.31배
열 지향 (컬럼 값을 모아 붙임)1.22 MB6.54배0.49 MB16.14배
열 지향 + (category, status, price) 정렬1.27 MB6.26배0.61 MB13.11배
바이트는 한 개도 안 바뀌었다. 순서만 바꿨는데 lzma 기준 0.86MB가 0.49MB가 됐다. 창이 큰 압축기(lzma)가 컬럼 배치의 이득을 더 크게 받는다.
정렬은 양날이다. category·status·price 컬럼은 좋아졌지만, 그 대가로 순차적이던 id·ts 컬럼이 뒤섞여 전체는 오히려 나빠졌다. 다음 장에서 컬럼 하나만 떼어 본다.
직접 실측 · Python zlib level 6, lzma 기본 · 텍스트 직렬화 기준이라 절대값은 포맷마다 다르다
5부 · 배치

컬럼 포맷은 범용 압축 전에 값의 성질에 맞는 인코딩을 먼저 건다

인코딩노리는 성질동작잘 맞는 컬럼
딕셔너리서로 다른 값이 적다값마다 정수 id를 주고 id만 저장. 4개 값이면 2비트.status, category, 국가 코드
RLE (런 길이)같은 값이 연달아 나온다(값, 반복 횟수) 쌍으로 저장. 정렬돼 있으면 극적이다.정렬된 컬럼, 파티션 키, 불리언
델타이웃 값과 차이가 작다앞 값과의 차이만 저장. 큰 수가 작은 수로 바뀐다.타임스탬프, 자동 증가 id
비트 패킹값의 범위가 좁다64비트 정수에 값이 0~7만 있으면 3비트씩 채운다.델타나 딕셔너리 id의 결과
넷 다 "이 컬럼의 엔트로피는 실제로 낮다"는 것을 압축기에 미리 알려주는 장치다. 범용 압축기가 바이트 패턴에서 힘들게 발견해야 할 구조를 타입 정보로 직접 회수한다. Parquet, ORC, Capacitor가 전부 이 순서로 간다: 인코딩 → 그 다음 zstd 같은 범용 압축.
5부 · 실측

실측 — status 컬럼 하나가 1.49MB에서 56바이트까지 내려간다

텍스트 원본1,489,656 B zlib (원본 순서)69,270 B (21배) 딕셔너리 2비트/값50,000 B — 범용 압축보다 이미 낫다 엔트로피 하한 (iid)32,943 B — Shannon의 바닥 zlib (정렬 후)2,351 B — 바닥 아래로 내려갔다 RLE (정렬 후)56 B — active:140160 deleted:10077 inactive:29817 pending:19946 막대 길이는 원본 대비 비율. 아래 넷은 실제 비율로 그리면 보이지 않을 만큼 작다.
직접 실측 · 20만 값, active 70% / inactive 15% / pending 10% / deleted 5%
5부 · 실측

정렬이 Shannon의 바닥을 뚫은 것은 모순이 아니다 — 분포 모델이 바뀐 것이다

바닥 33KB의 전제
"값들이 서로 독립이고 같은 분포에서 나온다." 앞 값을 알아도 다음 값을 더 잘 맞히지 못한다는 뜻이다. 원본 순서의 status는 실제로 그렇다(무작위 생성).
정렬 뒤의 status
앞 값이 active면 다음도 거의 확실히 active다. 조건부 엔트로피가 0에 가깝다. 독립 가정이 깨졌고, 그래서 iid 바닥은 더 이상 바닥이 아니다.
정렬은 정보를 만든 게 아니라 "이 값들은 원래 4종류뿐이다"라는 구조를 순서에 드러낸 것이다. RLE 56바이트는 그 구조를 그대로 적은 결과다. 컬럼 포맷이 정렬과 행 재배치에 공을 들이는 이유(Capacitor의 row reordering, 1주차)가 이것이다.
5부 · 배치

압축률은 공짜가 아니다 — CPU와 I/O 중 어느 쪽이 병목인지가 레벨을 정한다

압축 레벨 → 압축률 (좋아지지만 체감) 압축 CPU 시간 (급증) zstd 3 근처 세게 누르면 CPU가 병목, 약하게 누르면 I/O와 저장 비용이 병목. 목표는 둘 다 병목이 아닌 지점. 읽기가 많은 데이터는 레벨을 올려도 된다(해제는 빠르니까).
곡선은 개념도. 실제 모양은 데이터와 압축기마다 다르며, 직접 재는 것이 답이다.
실측 코너

오늘 숫자는 전부 표준 라이브러리로 잰 것이다 — 30줄이면 재현된다

import zlib, lzma, math
from collections import Counter

# 행 지향 / 열 지향으로 직렬화
row = "\n".join("\t".join(str(r[k]) for k in cols) for r in rows).encode()
col = "\n".join("\t".join(str(r[k]) for r in rows) for k in cols).encode()

for name, b in (("행", row), ("열", col)):
    print(name, len(b), len(zlib.compress(b, 6)), len(lzma.compress(b)))

# 컬럼 하나의 엔트로피
vals = [r["status"] for r in rows]; n = len(vals)
H = -sum(c/n * math.log2(c/n) for c in Counter(vals).values())
print(f"{H:.3f} bit/값 → 하한 {H*n/8:,.0f} B")

# 정렬하고 다시 재 보기
srt = "\t".join(sorted(vals)).encode()
print(len(zlib.compress(srt, 6)))
실제 테이블로 하면 더 좋다. Parquet으로 저장할 때 compression과 컬럼 정렬 순서를 바꿔 파일 크기를 비교하면 오늘 이야기가 운영 숫자로 바뀐다.
한 가지 주의. 텍스트 직렬화는 숫자를 문자로 바꿔 부풀린 상태라 절대 배율은 과장돼 있다. 배치 간 상대 비교만 신뢰한다.
마무리

압축은 마법이 아니라
데이터에 이미 있는 편중을 회수하는 일이다

"비둘기집이 한계를 말하고, 엔트로피가 그 숫자를 말하고, 배치가 그 숫자를 바꾼다."
Huffman은 편중을, LZ77은 반복을, 컬럼 저장은 배치를 회수한다. 그래서 데이터를 어떻게 놓느냐가 압축률을 정한다 — 바이트를 한 개도 바꾸지 않고 9배를 16배로 만들 수 있었다.