데이터 압축: 무손실과 손실

압축이란

압축(compression)은 같은 정보를 원래보다 적은 비트로 표현하는 일이다. 저장 공간을 아끼고, 같은 대역폭으로 더 빨리 보내기 위해 쓴다. 압축이 가능한 이유는 대부분의 데이터에 중복(redundancy) 이 있거나, 사람에게 필요 없는 정보가 섞여 있기 때문이다.

갈래	무엇을 줄이나	복원 결과	쓰는 곳
무손실(lossless)	중복	원본과 비트 단위로 같다	문서, 코드, 실행 파일, ZIP·gzip, PNG·GIF, FLAC
손실(lossy)	사람이 알아채기 어려운 정보	원본과 다르지만 느끼기에 비슷하다	JPEG·WebP·AVIF, MP3·AAC·Opus, 동영상 코덱

글자 하나가 바뀌면 뜻이 달라지는 문서·프로그램은 반드시 무손실로 압축한다. 사진·소리·영상은 손실 압축으로 훨씬 작게 만든다.

무손실 압축

무손실 기법은 크게 반복을 줄이는 것과 더 짧은 표현으로 바꾸는 것 두 가지이고, 실제 형식은 둘을 겹쳐 쓴다.

런 렝스 부호화

런 렝스 부호화(run-length encoding, RLE) 는 같은 값이 연달아 나오는 구간(run)을 「값 + 반복 횟수」로 바꾼다.

원본:  W W W W W W W B B B W        (11개)
RLE:   7W 3B 1W                     (쌍 3개 = 값 6개)

어느 바이트가 횟수이고 어느 바이트가 값인지 헷갈리지 않도록 모든 값 앞에 횟수를 붙이는 식으로 규칙을 일관되게 지킨다.
반복이 없는 데이터에서는 값마다 횟수가 하나씩 붙어 오히려 커진다. 단색 면이 넓은 그림, 흑백 팩스 문서처럼 런이 긴 데이터에 맞는다.

사전 방식: 반복 구간을 짧은 참조로

자주 나오는 덩어리를 짧은 부호로 바꾸고, 부호와 원래 덩어리의 대응표(사전)를 함께 둔다. 긴 문구를 약어로 줄이는 것과 같다.

방식	원리	쓰이는 곳
LZ77	앞에서 이미 나온 구간이 다시 나오면 「몇 바이트 앞에서, 몇 바이트 길이」라는 참조로 바꾼다. 사전을 따로 두지 않고 지나온 데이터가 곧 사전이다	DEFLATE의 앞 단계
LZW	데이터를 읽으며 새로 본 문자열을 사전에 차례로 등록하고 번호로 내보낸다. 복원하는 쪽도 같은 규칙으로 사전을 다시 만들어 사전을 보낼 필요가 없다	GIF
DEFLATE	LZ77로 반복을 참조로 바꾼 뒤 결과를 허프만 부호화한다	ZIP, gzip, PNG

웹 전송에 쓰는 Brotli·Zstandard도 LZ 계열 참조와 엔트로피 부호화를 겹친 같은 구조다.

허프만 부호화

고정 길이 부호는 모든 기호에 같은 비트 수를 준다. 허프만 부호화(Huffman coding) 는 기호의 출현 빈도를 보고 자주 나오는 기호에 짧은 부호, 드문 기호에 긴 부호를 준다.

만드는 법은 빈도표에서 출발해 트리를 아래에서 위로 쌓는 것이다.

모든 기호를 빈도와 함께 늘어놓는다.
빈도가 가장 낮은 둘을 골라 한 노드 아래로 묶고, 그 노드의 빈도는 둘의 합으로 한다.
노드가 하나 남을 때까지 2를 되풀이한다. 가장 작은 둘을 매번 꺼내야 하므로 힙(우선순위 큐)으로 구현한다.
각 가지에 왼쪽 0, 오른쪽 1을 붙인다. 루트에서 기호까지의 경로가 그 기호의 부호다.

문자열 AAAABBCD, 빈도: A 4, B 2, C 1, D 1

flowchart BT
    C["C(1)"] -->|"1단계"| n2["(2)"]
    D["D(1)"] -->|"1단계"| n2
    B["B(2)"] -->|"2단계"| n4["(4)"]
    n2 -->|"2단계"| n4
    A["A(4)"] -->|"3단계"| n8["(8) 루트"]
    n4 -->|"3단계"| n8

flowchart TB
  n8["(8)"] -->|"0"| a["A"]
  n8 -->|"1"| n4["(4)"]
  n4 -->|"0"| b["B"]
  n4 -->|"1"| n2["(2)"]
  n2 -->|"0"| c["C"]
  n2 -->|"1"| d["D"]

부호: A=0  B=10  C=110  D=111
고정 2비트: 8글자 × 2 = 16비트
허프만:    4×1 + 2×2 + 1×3 + 1×3 = 14비트

트리의 잎에만 기호가 있으므로 어떤 부호도 다른 부호의 앞부분이 되지 않는다. 이를 접두 부호(prefix-free code) 라 한다. 구분자 없이 비트를 이어 붙여도 처음부터 읽으면 한 가지로만 풀린다.
허프만 부호는 기호별 빈도가 주어졌을 때 기호마다 정수 비트를 쓰는 부호 중 평균 길이가 가장 짧다.
풀려면 부호표가 필요하다. 부호표(또는 빈도표)를 압축 결과 앞에 함께 저장해야 하므로, 아주 작은 데이터는 표 때문에 이득이 줄거나 사라진다.

압축할 수 없는 데이터

무손실 압축이 모든 데이터를 줄일 수는 없다. n비트 데이터 2ⁿ가지를 모두 더 짧은 비트열에 일대일로 대응시킬 수는 없기 때문이다(비둘기집 원리). 줄어드는 한계는 데이터의 정보량, 즉 엔트로피(entropy) 다.

무작위 데이터, 이미 압축된 파일(JPEG, MP4, ZIP), 암호문은 중복이 거의 없어 다시 압축해도 줄지 않는다.
그래서 압축과 암호화를 함께 할 때는 압축을 먼저 한다. 암호화한 뒤에는 무작위처럼 보여 압축이 안 된다.

손실 압축: 지각 부호화

손실 압축은 사람의 감각이 잘 알아채지 못하는 정보를 줄이거나 버린다. 사람의 지각 모델에 맞춰 정밀도를 다르게 주는 방식을 지각 부호화(perceptual coding) 라 하고, 그 지각 모델은 자극과 감각의 관계를 다루는 정신물리학(psychophysics)에서 나온다.

대상	사람이 둔한 것	버리는 방식
소리	가청 범위 밖(초음파), 덜 민감한 대역(아주 낮은 저음), 큰 소리에 가려진 작은 소리(마스킹)	주파수 대역을 나눠 대역마다 다른 정밀도로 저장한다. 목소리가 있는 중간 대역은 정밀하게, 나머지는 거칠게
이미지	미세한 색 변화, 잘게 변하는 고주파 디테일. 반대로 경계(명암 대비)에는 민감하다	8×8 같은 블록을 주파수 성분으로 바꾼 뒤 고주파를 거칠게 반올림(양자화)한다. 형식별 세부는 이미지 압축과 인코딩 자동화
영상	위 이미지의 성질 + 프레임 사이에 거의 변하지 않는 부분	아래 「동영상: 프레임 사이의 중복」

비압축 PCM 음원인 CD 음질(44.1kHz·16비트·스테레오)은 초당 약 1,411kbps이고, 128kbps MP3는 그 약 1/11이다. 표본화·양자화로 소리를 숫자로 만드는 과정은 디지털 오디오 기초에, 전화망의 음성 부호화는 VoIP 전화망에 있다.
통화 코덱은 대역폭이 나빠지면 비트레이트를 낮춰 더 많은 정보를 버린다. 화상 통화 소리가 기계음처럼 뭉개지는 이유다.
손실 압축은 품질을 고르는 일이다. 강하게 압축할수록 작아지지만 블록 경계·번짐 같은 아티팩트가 드러난다. 손실 압축을 여러 번 되풀이하면 손실이 쌓이므로 원본은 무손실로 보관한다.

동영상: 프레임 사이의 중복

동영상은 이미지의 연속이라 프레임 하나하나를 이미지처럼 압축할 수 있다. 여기에 더해 이웃한 프레임은 대부분 같다는 시간적 중복(temporal redundancy)을 없앤다.

프레임	담는 것
I 프레임(intra)	다른 프레임을 참조하지 않는 완전한 그림. 탐색(seek)의 시작점이 된다
P 프레임(predicted)	앞 프레임에서 바뀐 부분만
B 프레임(bidirectional)	앞뒤 프레임을 모두 참조해 차이만

배경이 그대로인 장면     → 앞 프레임의 블록을 그대로 복사
값만 조금 바뀐 블록      → 차이(잔차, residual)만 저장
손이 옆으로 움직인 장면  → "이 블록을 (dx, dy)만큼 옮겨라"는 움직임 벡터 + 잔차

앞 프레임의 블록을 옮겨 현재 프레임을 예측하는 것을 움직임 보상(motion compensation) 이라 한다. 고급 코덱은 이동 외에 밝기 변화 같은 보정도 예측에 넣는다. 압축을 너무 세게 하거나 참조할 프레임이 깨지면, 플레이어는 잘못된 블록 내용에 움직임 벡터만 계속 적용한다. 다음 I 프레임이 올 때까지 화면이 녹아내리듯 번지는 현상이 이것이다. H.264·HEVC·AV1 같은 코덱과 웹에서 동영상을 다루는 법은 동영상 성능에 있다.

정리

무손실 압축은 중복을 줄인다. 반복 구간은 RLE나 LZ 계열 참조로, 기호 빈도의 치우침은 허프만 같은 엔트로피 부호화로 줄이고, 실제 형식(DEFLATE)은 둘을 겹친다.
허프만 부호는 빈도가 낮은 둘을 반복해 묶은 트리에서 나오고, 접두 부호라 구분자 없이 풀린다. 부호표도 함께 저장해야 한다.
무작위 데이터와 이미 압축된 데이터는 더 줄지 않는다. 압축은 암호화보다 먼저 한다.
손실 압축은 사람의 지각이 둔한 정보를 버리는 지각 부호화이고, 동영상은 움직임 보상으로 프레임 사이의 중복까지 없앤다.
문서·코드는 무손실, 사진·소리·영상은 손실 압축이 기본이다.

버그 제보