3.1 정보 이론 — 데이터는 어디까지 줄어드는가

압축률은 파일 확장자가 아니라 입력을 예측하는 모델이 정한다. 엔트로피는 그 모델 아래에서 가능한 평균 부호 길이의 하한이다.

학습 목표

• 사건의 정보량과 확률 분포의 엔트로피를 비트 단위로 계산한다.
• 가변 길이 부호가 유일하게 복호되기 위한 조건과 prefix code의 구조를 설명한다.
• 허프만 부호의 평균 길이를 엔트로피와 비교하고 차이의 원인을 판단한다.
• 해밍 거리로 오류 감지·정정 능력을 계산하고 CRC·ECC·MAC의 목적을 구분한다.
• 입력 모델과 헤더 비용을 통제해 압축 실험을 설계한다.

배경: 파일 크기와 정보량은 다르다

길이가 같은 두 메시지를 생각하자.

AAAAAAAAAAAAAAAA
7c 91 0a e3 54 b8 2f d1 6e 40 99 25 a7 13 cc 08

첫 메시지는 "A가 16번"이라는 짧은 규칙으로 표현할 수 있다. 두 번째가 균등 난수에서 나왔다면 특정 값을 미리 맞힐 확률은 2^-128이다. 둘 다 128비트의 저장 공간을 차지하지만, 확률 모델이 부여하는 놀라움은 다르다. 정보 이론은 의미가 아니라 가능한 사건 중 어느 것이 일어났는가를 구분하는 비용을 다룬다.

압축기는 이 차이를 이용한다. 자주 나오거나 앞 문맥에서 예측 가능한 패턴에는 짧은 표현을, 드문 패턴에는 긴 표현을 준다. 모든 입력을 동시에 짧게 만들 수는 없다. 압축 함수가 서로 다른 두 입력을 같은 짧은 출력에 매핑하면 복호기가 원본을 구분할 수 없기 때문이다.

핵심 개념

정보량은 놀라움을 로그로 잰다

확률 p(x)인 사건 x의 자기 정보량(self-information)은 다음과 같다.

I(x) = -log₂ p(x)

확률이 1/2인 사건은 1비트, 1/8인 사건은 3비트의 정보를 준다. 로그를 쓰면 독립 사건의 확률 곱이 정보량의 합이 된다.

I(x, y) = -log₂(p(x)p(y)) = I(x) + I(y)

확실한 사건 p=1의 정보량은 0이다. "A만 나오는 소스"에서 다음 A는 새 선택을 알려 주지 않는다. 정보량은 문자열의 인간적 중요도나 보안 등급이 아니다. 선택지를 구분하는 데 필요한 비트 수다.

엔트로피는 평균 정보량이다

확률 변수 X의 엔트로피(entropy)는 가능한 사건의 정보량을 확률로 가중한 평균이다.

H(X) = Σ p(x) I(x) = -Σ p(x) log₂ p(x)

A가 1/2, B가 1/4, C와 D가 각각 1/8이면 정보량은 각각 1, 2, 3, 3비트이고 엔트로피는 1.75비트/심볼이다. 네 심볼이 균등하면 모두 2비트이고 엔트로피도 2다. 선택지가 고정된 상태에서는 균등 분포가 가장 예측하기 어려워 엔트로피가 최대다.

경계가 중요하다. "이 파일의 엔트로피"라는 말에는 심볼과 확률 모델이 생략돼 있다. 바이트별 독립 분포를 쓰면 TH처럼 심볼 사이 상관관계를 보지 못한다. 단어·n-gram·문맥 모델을 쓰면 더 잘 예측할 수 있지만 모델 자체와 상태를 전달하는 비용이 든다.

고정 길이와 가변 길이 부호

네 심볼의 고정 길이 부호는 각각 2비트다. 빈도가 치우치면 자주 나오는 심볼을 더 짧게 만들어 평균을 줄일 수 있다.

심볼	확률	부호	길이
A	1/2	0	1
B	1/4	10	2
C	1/8	110	3
D	1/8	111	3

이 부호는 구분자를 넣지 않고도 왼쪽부터 하나씩 복호할 수 있다. 어느 부호도 다른 부호의 접두사(prefix)가 아니기 때문이다. 이런 prefix code는 이진 트리의 잎과 정확히 대응한다. 왼쪽 간선을 0, 오른쪽을 1로 읽으면 잎에 도착하는 순간 심볼 하나가 끝난다.

반대로 A=0, B=01이면 01을 A 뒤의 무언가로 읽을지 B로 읽을지 즉시 결정할 수 없다. 모든 유일 복호 가능 부호가 prefix code인 것은 아니지만 prefix code는 스트리밍 복호가 단순하고 안전한 충분조건이다.

Kraft 부등식은 부호 길이의 예산이다

이진 prefix code의 길이를 l₁...lₙ이라 하면 다음을 만족해야 한다.

Σ 2^(-lᵢ) ≤ 1

깊이 l인 잎 하나는 완전 이진 트리의 전체 경로 공간 중 2^-l을 차지한다. 짧은 부호를 하나 주면 많은 접두사 공간을 소비하므로 다른 심볼은 더 깊이 내려가야 한다. Kraft 부등식은 "모두에게 짧은 부호"를 줄 수 없다는 트리 예산을 수식으로 표현한다.

허프만은 가장 드문 두 심볼을 묶는다

허프만 부호화(Huffman coding)는 빈도가 가장 낮은 두 노드를 반복해서 합친다.

빈도: A:8 B:4 C:2 D:2

1. C:2 + D:2 -> CD:4
2. B:4 + CD:4 -> BCD:8
3. A:8 + BCD:8 -> root:16

결과 길이는 앞 표처럼 1, 2, 3, 3이 된다. 매 단계에서 최소 두 노드를 고르는 우선순위 큐 구현과 그리디 선택의 정당성은 알고리즘 설계 패러다임에 위임한다. 여기서 중요한 계약은 주어진 심볼 빈도에 대한 이진 prefix code 중 가중 평균 길이가 최소라는 점이다.

허프만이 모든 압축에서 최적인 것은 아니다.

• 심볼마다 정수 비트 길이를 주므로 -log₂p가 분수면 보통 H ≤ L < H+1의 틈이 남는다.
• 독립 심볼 빈도만 보면 순서와 문맥의 중복을 놓친다.
• 부호 트리 또는 길이표를 파일에 저장해야 하므로 작은 입력에서는 헤더가 절약분보다 크다.
• 입력 분포가 바뀌면 정적 부호표의 예측이 틀린다.

gzip·zstd·Brotli 같은 실용 압축기는 반복 문자열을 거리·길이 쌍으로 바꾸는 모델링과 엔트로피 부호화를 조합한다. gzip이 단일 바이트 허프만보다 잘 줄었다면 "엔트로피 한계를 깼다"가 아니라 더 나은 심볼 모델로 다른 엔트로피를 측정한 것이다.

Shannon 한계는 모델 아래의 평균 하한이다

Shannon의 source coding 정리는 충분히 긴 독립 표본을 적절히 묶어 부호화하면 평균 길이를 엔트로피에 임의로 가깝게 만들 수 있지만, 무손실 부호의 평균은 엔트로피보다 아래로 지속적으로 내려갈 수 없음을 말한다. 한 특정 파일이 우연히 더 짧아지는 것과 분포 전체의 기대 길이를 낮추는 것을 구분해야 한다.

이미 압축된 파일이나 암호문은 바이트 분포가 거의 균등하고 국소 중복도 적다. 다시 압축하면 보통 헤더만 늘어난다. 어떤 압축기도 모든 입력을 줄일 수 없다는 것은 비둘기집 원리로도 볼 수 있다. 길이 n 이하의 출력 수는 모든 n비트 입력 수보다 적으므로, 일부 입력이 줄면 다른 일부는 같거나 늘어야 역함수가 존재한다.

오류 정정은 중복을 의도적으로 되돌려 넣는다

압축이 가능한 메시지 집합을 촘촘하게 표현한다면 오류 정정 부호(error-correcting code)는 유효한 코드워드 사이를 멀리 벌린다. 해밍 거리(Hamming distance)는 같은 길이 두 비트열에서 값이 다른 위치의 수다.

최소 거리 d_min인 코드는 검출만을 목표로 할 때와 가장 가까운 코드워드로 정정할 때 각각 다음 한계를 갖는다.

감지 가능한 비트 오류 수: d_min - 1
정정 가능한 비트 오류 수: floor((d_min - 1) / 2)

정정은 수신 단어를 가장 가까운 코드워드로 골라야 하므로 반지름 t인 오류 구가 겹치지 않아야 한다. 단순 짝수 패리티는 모든 유효 코드워드의 1 개수 parity를 같게 만들어 d_min=2다. 1비트 오류는 감지하지만 어느 비트가 틀렸는지 알 수 없어 정정하지 못한다.

해밍 코드는 데이터 위치 사이에 패리티 비트를 배치하고 각 패리티가 서로 다른 위치 집합을 검사하게 한다. 검사 실패 패턴인 syndrome을 이진 위치 번호로 해석하면 잘못된 한 비트를 찾을 수 있다. 표준적인 Hamming(7,4)은 4 데이터 비트를 7비트 코드워드로 보내며 최소 거리가 3이다. 따라서 검출만 하면 2비트까지 찾거나, 가장 가까운 codeword로 1비트를 정정할 수 있다. 1비트 정정과 2비트 오류 감지를 함께 보장하려면 전체 parity를 더해 최소 거리를 4로 만든 SECDED 같은 설계가 필요하다.

실무 관점: 오류 모델에 맞는 중복을 고른다

도구	주 오류·공격 모델	보장과 경계
checksum	우연한 손상	빠르지만 충돌을 의도적으로 만들기 쉽다
CRC	burst 전송 오류	선택한 생성다항식 범위의 오류를 강하게 감지하지만 공격자 변조 방지는 아니다
ECC memory	메모리 셀 bit flip	보통 단일 비트 정정·다중 비트 감지, 장치 구성에 의존한다
Reed–Solomon	심볼 단위 손실·오염	QR, 저장장치, RAID 등에 쓰이며 유한체 세부는 이 장 범위 밖이다
MAC/AEAD tag	키를 모르는 공격자의 능동 변조	비밀 키와 올바른 nonce·검증 절차가 필요하다

CRC가 통과했다고 메시지가 진짜인 것은 아니다. 공격자는 데이터와 CRC를 함께 다시 계산할 수 있다. 우연한 잡음과 의도적 공격자는 다른 모델이며, 후자는 MAC과 AEAD가 맡는다.

손실 압축과 무손실 압축도 구분해야 한다. PNG는 픽셀을 정확히 복원하는 무손실 형식이다. JPEG·MP3는 인간 지각 모델에서 덜 중요한 정보를 버린 뒤 남은 신호를 부호화한다. 작은 파일은 "더 좋은 무손실 부호" 때문만이 아니라 허용 오차를 계약에 추가했기 때문에 가능하다.

미니 실험: 엔트로피로 gzip 결과를 예측한다

다음 코드를 entropy.mjs로 저장하고 Node.js 24에서 실행한다. 바이트 독립 모델의 엔트로피 하한과 gzip 결과를 비교한다.

import { gzipSync } from "node:zlib";
import { randomBytes } from "node:crypto";

function entropy(buffer) {
  const counts = new Uint32Array(256);
  for (const byte of buffer) counts[byte]++;
  let bitsPerByte = 0;
  for (const count of counts) {
    if (count === 0) continue;
    const p = count / buffer.length;
    bitsPerByte -= p * Math.log2(p);
  }
  return bitsPerByte;
}

const text = Buffer.from("ABRACADABRA ".repeat(8_000));
const random = randomBytes(text.length);
const compressed = gzipSync(random);

for (const [name, input] of [
  ["text", text],
  ["random", random],
  ["already-gzipped", compressed],
]) {
  const output = gzipSync(input);
  console.log({
    name,
    bytes: input.length,
    byteEntropy: entropy(input).toFixed(3),
    gzipRatio: (output.length / input.length).toFixed(3),
  });
}

관찰할 것은 정확한 수치보다 순서다. 반복 텍스트는 바이트 엔트로피도 낮지만 gzip은 반복 구문까지 모델링해 훨씬 작아진다. 난수와 난수를 이미 gzip한 데이터는 8비트/바이트에 가까우며 gzip header 때문에 비율이 1보다 커질 수 있다. 샘플 크기와 난수 때문에 수치는 실행마다 달라진다. 매우 작거나 특수한 입력은 gzip container 내부에도 다시 포착할 구조가 남을 수 있으므로 "압축 결과는 절대 재압축되지 않는다"고 일반화하지 않는다.

이 실험은 엔트로피 추정기의 한계도 보여 준다. ABRACADABRA의 바이트 빈도만 섞어도 계산된 1차 엔트로피는 같지만, 순서를 무작위화하면 gzip의 반복 문자열 모델이 덜 맞아 압축률이 달라진다. 엔트로피 값에는 항상 "어떤 심볼과 조건부 모델인가"를 붙인다.

더 깊이: 압축률 리포트를 잘못 읽는 방식

• 원본 크기만 비교하고 부호표·컨테이너 헤더를 제외하면 실제 저장 비용을 과소평가한다.
• 서로 다른 문자 인코딩을 바이트 입력으로 비교하면 모델이 아니라 입력 표현 차이를 재는 셈이다.
• 학습한 corpus와 평가 corpus가 같으면 적응형 모델의 일반화 비용을 숨길 수 있다.
• 한 파일의 결과를 전체 workload로 일반화하면 파일 크기와 분포의 혼합 효과를 놓친다.
• 압축 뒤 암호화한 결과의 길이를 공개하면 입력 길이와 압축률이 메타데이터로 남는다.

실험에서는 원본 바이트 수, 모델만의 이론 하한, payload 비트 수, 헤더 포함 파일 크기를 각각 기록한다. 이 네 값이 있어야 알고리즘, 모델, 포맷 오버헤드를 분리할 수 있다.

정리

• 정보량 -log₂p는 사건의 놀라움을, 엔트로피는 그 평균을 비트로 잰다.
• prefix code는 부호 트리의 잎이며 Kraft 부등식은 짧은 부호의 공간 예산을 나타낸다.
• 허프만은 주어진 심볼 빈도에서 최적 이진 prefix code를 만들지만 문맥과 헤더 비용은 별도다.
• 엔트로피는 선택한 모델 아래의 평균 하한이다. 이미 압축되거나 암호화된 데이터는 다시 줄기 어렵다.
• 오류 정정은 코드워드 사이의 해밍 거리를 확보하려고 중복을 넣는다. 우연한 오류 감지와 공격자 변조 검증은 다른 계약이다.

확인 문제

1. 바이트 빈도 엔트로피가 같은 두 파일의 gzip 압축률이 크게 달랐다. 가능한 원인과 이를 검증할 대조 실험을 설명하라.

정답과 해설

1차 바이트 분포는 같아도 심볼 순서와 반복 문자열의 분포가 다를 수 있다. 한 파일의 바이트를 무작위로 섞어 빈도는 보존하고 순서 상관관계만 없앤 뒤 gzip 크기를 비교한다. 차이가 커지면 gzip의 사전 모델이 포착한 문맥 중복이 원인이다.

2. Hamming distance가 4인 코드가 보장하는 감지·정정 범위를 구하고, 2비트 오류를 항상 정정할 수 없는 이유를 설명하라.

정답과 해설

최대 3비트 오류를 감지하고 floor((4-1)/2)=1비트 오류를 정정한다. 2비트만큼 이동한 수신 단어는 다른 코드워드에서도 2비트 떨어질 수 있어 가장 가까운 원본을 유일하게 정할 수 없다.

3. 200바이트 파일에서 허프만 payload가 20바이트 줄었지만 결과 파일은 15바이트 커졌다. 구현 실패라고 단정할 수 없는 이유는 무엇인가?

정답과 해설

복호에 필요한 부호 길이표, 원본 길이, padding 정보와 컨테이너 헤더가 35바이트보다 클 수 있다. payload와 헤더 포함 크기를 분리하고 더 큰 동일 분포 입력에서 고정 오버헤드가 상쇄되는지 확인한다.

참고 자료

• Shannon, A Mathematical Theory of Communication: 정보량, 엔트로피와 source coding의 원래 문제 설정을 제시한다.
• Huffman, A Method for the Construction of Minimum-Redundancy Codes: 최소 중복 부호의 구성 원리를 다룬다.
• Hamming, Error Detecting and Error Correcting Codes: 거리 기반 오류 감지·정정의 기초 논문이다.
• RFC 1952 — GZIP file format: gzip 컨테이너의 헤더·트레일러와 무결성 필드를 확인할 수 있다.
• Node.js zlib 문서: 미니 실험의 gzipSync API와 런타임 동작 기준이다.