웹에 사용되는 압축 알고리즘의 원리

subtitle

알고보면 압축되어있는 웹

압축이란 무엇일까?

압축은 같은 정보를 더 적은 데이터로 표현하는 기술이다.

예를 들어 다음과 같은 문자열이 있다고 가정해보자.

Plain Text
복사

이를 그대로 저장하면 10개의 문자가 필요하다.

하지만 이렇게 표현할 수도 있다.

Plain Text
복사

"A가 10번 반복된다"는 의미만 저장한 것이다.

정보는 동일하지만 저장해야 할 데이터는 줄어들었다.

사실 대부분의 압축 알고리즘은 이런 아이디어에서 출발한다.

"중복되는 정보를 더 효율적으로 저장할 수 없을까?"

압축에는 두 종류가 있다

압축은 크게 무손실 압축과 손실 압축으로 나뉜다.

무손실 압축

압축을 해제했을 때 원본 데이터가 100% 복원된다.

대표적인 예시는 다음과 같다.

•

ZIP

•

GZIP

•

PNG

예를 들어

AAAAABBBBBCCCC
Plain Text
복사

를

Plain Text
복사

로 저장하는 방식이다.

이를 RLE(Run Length Encoding)라고 한다.

하지만 실제 압축 알고리즘은 좀 더 복잡하다

RLE은 압축의 기본 아이디어이지, 전부가 아니었다..

실제 gzip, Brotli, PNG 같은 압축 포맷은 여러 알고리즘을 조합한다.

대표적인 예가 허프만 코딩(Huffman Coding)이다.

허프만 코딩은 자주 등장하는 데이터에는 짧은 비트를 할당하고, 드물게 등장하는 데이터에는 긴 비트를 할당한다.

예를 들어 A = 0, B = 10, C = 11 처럼 표현해서 전체 데이터 크기를 줄인다.

허프만 코딩은 어떻게 데이터를 줄일까?

처음 허프만 코딩을 봤을 때는 잘 이해가 되지 않았다.

"비트를 다르게 할당한다고 정말 용량이 줄어드나?"

좀 더 이해하기 쉽게 예시를 들어보자.

다음 문자열이 있다고 가정해보자.

Plain Text
복사

문자의 등장 횟수를 세어보면 다음과 같다.

A: 6번
B: 2번
C: 1번
Plain Text
복사

가장 많이 등장하는 문자는 A다.

그런데 만약 모든 문자를 동일한 길이로 저장한다면 어떨까?

A = 00
B = 01
C = 10
Plain Text
복사

각 문자를 2비트로 표현한다고 가정하면,

Plain Text
복사

는

Plain Text
복사

이 된다.

AAAAAABBC를 표현하기 위해서는 총 18비트가 필요하다.

그런데 가만히 생각해보면 A는 전체 데이터의 대부분을 차지한다.

그렇다면 가장 많이 등장하는 A를 더 짧게 표현하면 어떨까?

A = 0
B = 10
C = 11
Plain Text
복사

이제 같은 문자열을 다시 저장해보자.

Plain Text
복사

↓

Plain Text
복사

총 비트 수를 세어보면

A: 1비트 × 6 = 6비트
B: 2비트 × 2 = 4비트
C: 2비트 × 1 = 2비트

총 12비트
Plain Text
복사

기존 18비트에서 12비트로 약 33% 줄어들었다.

우리가 데이터를 압축할 때 쓰는 gzip 역시 허프만 코딩을 사용한다.

다만 허프만 코딩만 사용하는 것은 아니다.

먼저 LZ77 알고리즘으로 중복 문자열을 찾아 제거하고, 그 결과를 허프만 코딩으로 다시 압축한다.

우리가 API 응답을 gzip으로 압축했을 때 크기가 크게 줄어드는 이유도 바로 여기에 있었다.

손실 압축

손실 압축은 압축 과정에서 일부 데이터를 제거한다.

대표적인 예시는 다음과 같다.

•

JPG

•

WebP

•

MP3

•

MP4

예를 들어 아래 두 색상은 사람의 눈으로 거의 구분하기 어렵다.

Plain Text
복사

그렇다면 굳이 두 값을 모두 저장할 필요가 있을까?

손실 압축은 인간이 거의 인식하지 못하는 정보를 제거하여 더 작은 파일을 만든다.

WebP는 왜 JPG보다 작을까?

WebP는 단순히 "더 가벼운 JPG"가 아니다.

실제로는 여러 압축 기법을 조합하여 사용한다.

그중 핵심은 예측(Prediction)이다.

이미지는 픽셀들의 집합이다.

예를 들어 아래와 같은 픽셀 값이 있다고 가정해보자.

Plain Text
복사

이를 그대로 저장할 수도 있지만,

100
+1
+1
+1
Plain Text
복사

처럼 저장할 수도 있다.

이미지에서는 주변 픽셀끼리 색상이 비슷한 경우가 매우 많다.

하늘 사진을 생각해보면 이해하기 쉽다.

하늘의 파란색은 대부분 비슷한 값을 가지므로 매 픽셀을 저장하기보다 "이전 픽셀과 거의 같다"는 정보만 저장하는 것이 훨씬 효율적이다.

즉, 이렇게 해서 WebP는 실제 색상값보다 "차이"를 저장함으로써 데이터를 압축할 수 있다.

Draco는 왜 그렇게 많이 줄어들까?

내가 포폴 사이트를 만들 때 썼던 draco 압축의 원리도 궁금했다. GLB 모델은 기본 몇 MB인데, “draco는 어떻게 압축할 수 있는 걸까” 궁금했다.

Draco는 이미지가 아니라 3D 모델을 압축한다.

3D 모델은 사실상 숫자들의 집합이다.

•

vertex (각 메쉬의 꼭짓점)

•

normal (vertex나 face가 바라보는 방향. 면에서 수직인 방향.)

•

uv (3d 모델을 평평하게 펼쳐서 2d 평면으로 표현한 것이라고 생각하면 된다.)

•

face (메쉬의 면. vertex 3개가 모이면 면이 된다.)

이런 데이터들이 수천 개, 수만 개 저장되어 있다.

예를 들어 정점 데이터는 다음과 같이 저장될 수 있다.

(1.1234567, 2.3456789, 3.9876543)
Plain Text
복사

하지만 대부분의 경우 화면에 렌더링할 때 소수점 7자리까지는 필요하지 않다.

그래서 Draco는 이를 다음과 같이 줄인다.

(1.12, 2.35, 3.99)
Plain Text
복사

이 과정을 Quantization이라고 한다.

쉽게 말해 필요한 만큼만 정밀도를 유지하는 것이다.

데이터만 봤을 때는, 이렇게 해도 될까? 라는 생각이 들지만 실제 예시를 들어보면 납득이 된다.

키 170cm인 사람을 모델링한다고 해보자.

170.1234567cm인 사람을 170.12cm으로 압축한다고 하면, 0.0034567cm의 차이가 난다.

사람이 0.03mm의 차이를 실제 3차원 공간이 아닌 작은 모니터 화면에서 본다면

그 차이를 구분해내는 게 사실상 어렵다.

사실 Draco 내부에서는 더 극단적으로 압축한다.

예를 들어 모델 좌표가 0 ~ 100 범위라면 원래 float32로 저장하던 것을 16bit integer로 바꿔버린다.

ex) 1.1234567 → 735.

전혀 다른 숫자가 된 것 같지만, 735라는 숫자를 1.12로 역변환해서 1.12라는 숫자로 복원한다.

이게 왜 용량 절약이 되냐면, 원래는 float32로 저장할 때 정점(vertex)이 100만 개면 100만 × 3축 × 4바이트 = 12MB가 된다.

하지만 uint16 로 저장하면 100만 × 3축 × 2바이트 = 6MB가 된다.

차이만 저장하기

Draco는 또 하나의 중요한 기법을 사용한다.

바로 Delta Encoding이다.

다음 숫자들을 보자.

Plain Text
복사

보통은 모두 저장해야 한다.

하지만 Draco는 이렇게 생각한다.

1
+1
+1
+1
+1
+1
+1
Plain Text
복사

변화량만 저장하면 훨씬 적은 공간으로 표현할 수 있다.

3D 모델의 정점 데이터는 위치가 연속적으로 변하는 경우가 많기 때문에 이 방식이 매우 효과적이다.

엔트로피 코딩 알고리즘

이제 끝인가?! 생각할 수 있지만 사실 더 압축할 수 있다.

왜냐하면 실제 3D 모델 데이터는 특정 숫자가 엄청 자주 등장하기 때문이다.

예를 들어 Delta Encoding 이후 다음과 같은 데이터가 만들어졌다고 가정해보자.

Plain Text
복사

눈으로만 봐도 0이 압도적으로 많이 등장한다.

엔트로피 코딩 알고리즘은 위와 같은 데이터에 대해 이런 방식으로 압축한다.

•

자주 등장하는 데이터 → 적은 비트 사용

•

드물게 등장하는 데이터 → 많은 비트 사용

예를 들어 문자 빈도가 다음과 같다고 해보자.

A: 90%
B: 9%
C: 1%
Plain Text
복사

그렇다면 A를 표현하는 데 많은 비트를 사용하는 것은 낭비다.

오히려 가장 자주 등장하는 A를 최대한 짧게 표현하는 것이 효율적이다.

앞에서 살펴본 허프만 코딩(Huffman Coding)도 같은 아이디어를 사용한다.

다만 draco는 허프만 코딩을 사용하지 않고 rANS를 사용한다.

허프만 코딩보다 더 높은 압축률을 제공하면서도 처리 속도가 빠르다기 때문이다.

근데 여기서 또 궁금증이 생겼다.

‘왜 허프만 코딩을 사용하지 않을까?’

허프만 코딩의 한계

데이터의 등장 확률이 다음과 같다고 가정해보자.

0 = 90%
1 = 9%
2 = 1%
Plain Text
복사

그렇다면 가장 자주 등장하는 0은 짧게, 드물게 등장하는 2는 길게 표현하는 것이 효율적이다.

허프만 코딩은 이를 다음과 같이 표현할 수 있다.

Plain Text
복사

하지만 한 가지 한계가 있다.

허프만 코딩은 항상 정수 비트 단위로만 표현할 수 있다.

0 = 1비트
1 = 2비트
2 = 2비트
Plain Text
복사

이게 왜 비효율적인지 잘 납득이 가지 않는다…

왜냐하면 확률과 정보량에 대해 알아야하기 때문이다.

예를 들어 데이터가 있다고 해보자.

0 = 90%
1 = 9%
2 = 1%
Plain Text
복사

즉 100개 중 0이 대부분이고, 2는 거의 안나온다.

상식적으로 생각해보자. 90% 확률로 0이 나온다.

그럼 사실 0이 나오는 것은 놀랍지 않은 정보다. 확률이 높기 때문이다.

반대로 2가 나오면 ‘1%인데 등장했네?’라는 생각이 든다.

예상하기 어려운 사건이다.

정보이론에서는 예상하기 어려울수록 더 많은 정보량을 가진다라고 본다.

우리는 지금 압축에 대해서 배우고 있기 때문에 ‘정보량’에 대한 개념이 좀 헷갈릴 수 있다.

압축에서의 정보량은 ‘표현하기 위한 정보의 양’이지만, 정보 이론에서 정보량은 ‘사람이 느끼는 정보의 양’에 가깝다.

그래서 ‘예상하기 어려운 사건, 놀라운 사건’은 정보량이 많다고 하는 것이다.

하지만 정보이론의 창시자인 Claude Shannon은 이걸 심리학으로 정의하지 않았다.

왜냐하면 사람마다 놀라움이 다르기 때문이다.

예를 들어 오늘 비가 온다는 사실은 장마가 있는 나라에서는 놀랍지 않고, 사막에서는 놀라울 수 있다.

즉, 사람 기준으로는 정의가 흔들릴 수 있기 때문에 Shannon은 "사건이 발생할 확률만 알면 정보량을 정의할 수 있지 않을까?"라고 생각했다.

그래서 정보량 공식 -log₂(p) 을 만들었다.

정보량 함수는 아래와 같은 조건을 만족시켜야 한다.

•

확률이 작을수록 결과값이 커져야 함 

•

독립 사건은 더해져야 함 → 예를 들어, 앞면(50%) + 앞면(50%)이면 25% 확률

정보량도 1bit + 1bit = 2bit가 되어야 한다.

이 조건을 만족하는 함수가 -log₂(p)밖에 없다고 한다.

수학적으로는 정보량 = -log₂(확률) 이다.

이제 다시 허프만 코딩으로 돌아와보자. 0이 등장할 확률이 90%면 0의 정보량은 -log₂(0.9) ≈ 0.15 비트 이다.

반면 2가 등장할 확률은 1%이다. 그러면 -log₂(0.01) ≈ 6.64 비트 가 된다.

즉 이론적으로는 0을 표현하는데 0.15비트만 있으면 충분하지만, 허프만 코딩은 0을 표현하는데 정수로만 표현가능하기 때문에 최소 1비트는 써야한다.

0.15비트로 저장할 방법이 없다.

Arithmetic Coding의 등장

그래서 나온 것이 Arithmetic Coding이다.

Arithmetic Coding은 문자 하나하나를 비트로 표현하는 대신 문자열 전체를 하나의 숫자로 표현한다.

예를 들어 AAAB라는 문자열을 0.123456789...같은 하나의 숫자로 표현할 수 있어 압축률이 매우 뛰어나다.

하지만 이런 단점도 있다.

•

계산이 복잡함

•

CPU 사용량이 높음

•

병렬 처리가 어려움

문자열 패턴을 하나의 숫자로 바꾸면 되니까 병렬처리하기 쉬울 것 같지만,

Arithmetic Coding은 문자열 전체를 하나의 구간으로 압축하기 때문에

세 번째 문자의 범위를 계산하려면 두 번째 문자 결과를 알아야해서 병렬 처리가 어렵다.

그래서 Draco는 rANS를 사용한다

rANS는 Arithmetic Coding 수준의 압축률과 허프만 코딩 수준의 속도를 동시에 얻기 위해 만들어진 알고리즘이다.

쉽게 말해 Arithmetic Coding의 압축률 + Huffman Coding의 속도를 목표로 한다.

허프만은

A → 0
B → 10
C → 11
Plain Text
복사

처럼 문자 하나를 바로 비트열로 바꾼다.

반면 rANS는 현재 상태 + 새 심볼 = 새 상태 를 반복하며, 정수를 통해 상태를 누적한다.

예를 들어, 초기 상태가 100이면,

•

A 입력 → 531

•

A 입력 → 2782

•

B 입력 → 14592

이렇게 초기 값에 상태를 계속 누적한다.

그럼 여기서 ‘그럼 정수가 무한히 커질 수 있는 건가?’라는 생각이 들었다.

상태가 무한히 커지면 압축의 의미가 없어지기 때문에 rANS는 중간중간 14592같이 너무 커진 상태를 보고 일부 비트를 출력한다.

이를 보통 renormalization이라고 한다.

일반 숫자라면 14592 전체를 저장하지만, rANS에서는 14592를 하위 8비트 00000000을 출력해서 상태를 52로 축소한다.

즉, 정수(=상태)는 계산용이고, 실제 파일에는 조금씩 뽑아낸 비트들이 저장된다.

내부에서는 정수 하나로 상태를 관리하지만, 결과는 압축된 비트 스트림이다.

허프만은 확률 90%에 정보량 0.15만 써도 되는데 무조건 1비트씩 사용하기 때문에 낭비가 컸다.

하지만 rANS는 AAAA를 한 번에 상태에 반영해서 평균 0.15 * 4 = 0.6 비트 수준의 정보량에 가깝게 표현한다.

이걸 이해하면 "왜 rANS가 빠른데도 압축률이 높은가?"라는 질문에 대한 답이 꽤 명확해진다.

실수 구간(Arithmetic Coding)을 정수 상태 머신으로 바꿔버렸기 때문에

CPU가 좋아하면서도 정보량 손실이 거의 없다.

즉, draco는

•

정밀도를 줄이고

•

변화량만 저장하고

•

마지막으로 엔트로피 코딩까지 적용해 압축의 한계를 최대한 극복하는

정교한 압축 파이프라인이다.

서버 데이터도 압축된다

압축은 이미지나 3D 모델에만 적용되는 기술이 아니다.

우리가 매일 호출하는 API 응답도 대부분 압축되어 전송된다.

브라우저는 서버에 요청을 보낼 때 다음과 같은 헤더를 함께 보낸다.

Accept-Encoding: gzip, br
Plain Text
복사

이는 "나는 gzip과 Brotli 압축을 해제할 수 있다"는 의미다.

그러면 서버는 응답 데이터를 압축한 뒤 다음과 같은 헤더와 함께 전달한다.

Content-Encoding: br
Plain Text
복사

예를 들어 아래와 같은 JSON 응답을 생각해보자.

{
  "users": [
    {
      "id": 1,
      "name": "김철수",
      "email": "kim@example.com"
    },
    {
      "id": 2,
      "name": "이영희",
      "email": "lee@example.com"
    }
  ]
}
JSON
복사

JSON에는 "id", "name", "email" 같은 문자열이 반복적으로 등장한다.

압축 알고리즘 입장에서는 이런 데이터가 매우 반갑다.

반복되는 패턴을 발견할수록 더 적은 데이터로 표현할 수 있기 때문이다.

실제로 수십 KB에서 수백 KB 크기의 JSON 응답은 gzip이나 Brotli 압축 후 훨씬 작은 크기로 전송되는 경우가 많다.

즉 서버 데이터 압축도 결국 같은 원리를 사용한다.

반복을 찾고, 중복을 제거하고, 더 효율적인 형태로 저장하는 것이다.

결국 모든 압축은 비슷한 철학을 가진다

압축 알고리즘마다 구현 방식은 다르다.

하지만 대부분은 아래 네 가지 아이디어 중 하나를 사용한다.

1. 반복 찾기

Plain Text
복사

↓

Plain Text
복사

2. 예측하기

Plain Text
복사

↓

Plain Text
복사

3. 차이만 저장하기

원본 대신 변화량만 저장한다.

4. 사람이 못 느끼는 정보 버리기

시각적 차이가 거의 없는 데이터를 제거한다.

프론트엔드 개발자에게 왜 중요할까?

압축 알고리즘을 직접 구현할 일은 거의 없다.

하지만 원리를 이해하면 최적화 전략을 세울 때 훨씬 도움이 된다.

예를 들어

<img src="/hero.jpg" />
HTML
복사

를

<img src="/hero.webp" />
HTML
복사

로 바꾸는 이유를 설명할 수 있게 된다.

또한 Three.js 프로젝트에서

useGLTF('/robot.glb')
TypeScript
복사

보다

useGLTF('/robot-draco.glb')
TypeScript
복사

를 사용하는 이유도 이해할 수 있다.

뿐만 아니라 API 응답이 느릴 때 단순히 서버 성능만 의심하는 것이 아니라 gzip이나 Brotli 압축이 제대로 적용되어 있는지도 확인할 수 있다.

압축은 단순히 파일 크기를 줄이는 기술이 아니다.

네트워크 비용을 줄이고, 로딩 속도를 개선하고, 사용자 경험을 향상시키는 기술이다.

이미지는 WebP로 압축된다.

3D 모델은 Draco로 압축된다.

서버 응답은 gzip이나 Brotli로 압축된다.

결국 웹 성능 최적화의 상당 부분은 더 적은 데이터를 전송하기 위한 노력이라고 볼 수 있다.

그리고 그 시작은 생각보다 단순했다.

"반복되는 정보를 더 똑똑하게 저장할 수 없을까?"

우리가 매일 사용하는 WebP, Draco, gzip, Brotli도 결국 그 질문에서 출발한 결과물이었다.