목차
압축을 처음 배우면 한 번쯤 품는 의문이 있다. 압축한 걸 또 압축하면 더 줄지 않나.
무엇이든 줄이는 프로그램은 있을 수 없다
먼저 결론부터 놓는다. 모든 입력을 한 비트라도 줄여 주는 무손실 압축기는 존재하지 않는다. 아직 안 나온 게 아니라 있을 수 없다는 것이 증명되어 있다.
이건 압축 기술이 덜 발달해서가 아니고, 앞으로 아무리 좋은 알고리즘이 나와도 바뀌지 않는다. 이유는 알고리즘과 상관없이 개수를 세기만 하면 나오기 때문이다.
짧은 이름의 개수가 모자란다
3비트짜리 파일을 전부 모아 보자. 000부터 111까지 딱 여덟 개다. 이제 압축기가 이 여덟 개를 전부 3비트보다 짧게 만들었다고 해 보자.
3비트보다 짧은 비트열은 몇 개나 있을까. 0비트짜리가 하나(아무것도 없는 것), 1비트짜리가 둘, 2비트짜리가 넷이다. 전부 합쳐 일곱 개다.
여덟 개를 일곱 칸에 넣으면 마지막 칸에 둘이 몰린다. 그 칸을 받아 든 쪽은 어느 것으로 되돌릴지 알 수 없다.
여덟 개를 일곱 개의 이름에 나눠 담아야 한다. 그러면 적어도 두 입력이 같은 이름을 받는다. 그 이름을 받아 든 압축 해제기는 둘 중 어느 것으로 되돌려야 할지 알 수 없다.
무손실이라는 약속이 여기서 깨진다. 원본을 정확히 되돌리려면 서로 다른 입력은 반드시 서로 다른 결과가 되어야 하는데, 담을 그릇보다 담을 것이 많으면 그게 불가능하다.
3비트에서만 그런 게 아니다. 어떤 길이를 잡아도 그보다 짧은 것의 개수는 항상 하나가 모자란다. 같은 셈이 해시 테이블에서 충돌이 반드시 일어나는 이유와 똑같다는 걸 눈치챘다면 정확하다. 넣을 것보다 칸이 적으면 겹친다는 한 문장이다.
그래서 어떤 파일은 반드시 커진다
여기서 따라 나오는 결론이 압축의 성격을 정한다. 어떤 입력을 줄였다면 다른 어떤 입력은 늘어난다.
압축은 공짜로 작아지는 마법이 아니라 자리를 옮기는 거래다. 자주 나올 법한 데이터에 짧은 이름을 몰아주는 대신, 거의 안 나올 법한 데이터에 긴 이름이 돌아간다.
그러면 왜 실무에서는 압축이 늘 이득처럼 보이는가. 우리가 다루는 데이터가 전체 가능성 중 아주 작은 구석에만 몰려 있기 때문이다. 로그, JSON, HTML, 소스 코드는 전부 반복과 치우침이 심한 데이터고, 압축기는 정확히 그 구석에 짧은 이름을 몰아 준 것이다.
실제 압축 형식이 부풀지 않는 것처럼 보이는 것도 요령 덕이다. 앞 글에서 본 대로 줄여 봐야 손해인 구간은 “원본 그대로”라고 표시하고 손대지 않는다. 그래도 그 표시를 적는 자리만큼은 커진다. 늘어나는 폭을 아주 작게 묶어 둘 뿐 늘지 않게 할 수는 없다.
줄여 적은 노트는 더 못 줄인다
이제 처음의 의문으로 돌아간다. 압축한 파일을 다시 압축하면 어떻게 되나.
노트로 생각하면 답이 그냥 보인다. 이미 기호로 줄여 적고 반복은 “위 세 줄”로 가리켜 둔 노트를 놓고 또 줄이려고 하면 줄일 게 없다. 같은 말이 이어지는 자리도 없고 유난히 자주 나오는 낱말도 없다. 압축기가 찾는 두 가지 연료가 첫 번째 압축이 이미 다 태워 버렸기 때문이다.
실제로 해 보면 결과가 아주 조금 커진다. 형식마다 붙는 머리말과 검사값 자리만큼 늘고 줄일 것은 없어서다.
이건 압축 형식이 잘 만들어졌다는 증거다. 압축한 결과가 다시 압축된다면 첫 번째 압축이 일을 덜 한 것이다. 잘 압축된 데이터는 반복도 치우침도 남아 있지 않아 무작위와 구별하기 어렵게 생겼다.
바닥이 있다
여기까지 오면 자연스러운 질문이 남는다. 어떤 데이터를 가장 짧게 적으면 얼마나 짧아지나.
이 바닥에는 이름이 있다. 허프만 편에서 잠깐 나온 엔트로피다. “이 데이터의 글자 하나를 적는 데 평균 몇 비트가 꼭 필요한가”를 말해 주는 값이고, 어떤 압축기도 이 아래로는 못 내려간다.
감을 잡는 데는 동전 던지기가 좋다.
- 양면이 같은 동전 - 결과가 늘 앞면이니 적을 게 없다. 백 번 던진 기록도 “앞면 백 번”이면 끝난다
- 공정한 동전 - 앞뒤가 반반이라 다음이 무엇일지 전혀 짐작이 안 된다. 백 번 던진 기록은 백 비트가 꼭 필요하고 한 비트도 못 깎는다
- 한쪽으로 기운 동전 - 열에 아홉이 앞면이라면 짐작이 되니 그만큼 줄일 수 있다
짐작이 될수록 줄고, 안 될수록 안 준다. 압축률이 좋다는 말은 사실 “이 데이터가 짐작하기 쉬웠다”는 말이다.
더 근본적인 물음도 있다. “이 데이터를 만들어 내는 가장 짧은 프로그램의 길이”를 그 데이터의 복잡도로 보는 관점인데, 이 값은 계산해서 구할 수가 없다는 것이 증명되어 있다. 그래서 실제 압축기는 이 바닥을 겨냥하지 않고 반복과 치우침이라는 눈에 보이는 두 낭비만 걷어낸다. 이 시리즈가 원리를 둘로만 설명한 데에는 이런 배경이 있다.
짐작이 안 되면 안 줄어든다
바닥이라는 개념을 손에 쥐면 왜 안 줄어드는지를 하나하나 설명할 필요가 없어진다. 전부 한 문장으로 끝난다.
| 안 줄어드는 것 | 왜 |
|---|---|
| 난수 | 다음 값이 앞의 값과 아무 관계가 없다. 짐작할 근거가 없다 |
| 이미 압축된 파일 | 짐작할 수 있는 부분을 첫 압축이 이미 다 걷어냈다 |
| 암호화된 데이터 | 짐작이 되면 그 암호가 실패한 것이다 |
| JPEG·MP3·MP4 | 손실 단계를 거친 뒤 무손실 압축까지 이미 걸려 있다 |
| 해시값·토큰·UUID | 짧고 무작위에 가깝게 설계된 값이다 |
암호가 특히 분명하다. 같은 블록이 같게 나오면 정보가 샌다는 것이 암호 설계의 기본이라, 잘 만든 암호문에는 반복과 치우침이 남아 있으면 안 된다. 그런데 그 둘이 정확히 압축의 연료다. 좋은 암호문은 정의상 압축이 안 되는 데이터인 셈이다.
압축과 암호화에는 순서가 있다
앞의 사실에서 실무 규칙 하나가 곧장 나온다. 두 가지를 다 하려면 압축을 먼저 하고 암호화를 나중에 해야 한다.
거꾸로 하면 압축 단계가 할 일이 없다. 암호문에는 걷어낼 낭비가 없으니 CPU만 태우고 크기는 그대로거나 조금 늘어난다.
다만 “압축 먼저”가 언제나 안전한 것은 아니다. 압축한 결과의 크기 자체가 내용에 대한 힌트를 흘리기 때문이다. 비밀 값과 공격자가 넣은 값이 한 덩어리에 섞여 압축되면, 공격자는 넣은 값을 바꿔 가며 결과 크기를 재는 것만으로 비밀에 다가갈 수 있다. 넣은 값이 비밀과 겹칠수록 더 잘 줄어들기 때문이다. 실제로 이 방식의 공격이 알려져 있어서 비밀이 실린 응답에는 압축을 끄는 것이 권고된다. 압축은 크기를 줄이지만, 그 크기가 새로운 정보가 된다.
실무에서: 안 줄어드는 것에 CPU를 태우지 않는다
이 편의 내용은 전부 하나의 실무 판단으로 모인다. 압축을 걸기 전에 이 데이터에 줄일 것이 있는지부터 본다.
가장 흔한 낭비 셋이다.
- 이미 압축된 응답을 다시 압축한다. 이미지, 동영상, 내려받게 하는 zip 파일에 압축을 거는 설정이 그렇다. 대부분의 웹 서버는 압축을 걸 대상 타입을 정할 수 있고, 텍스트 계열만 켜는 것이 기본형이다
- 아주 작은 응답까지 압축한다. 형식마다 붙는 머리말과 이름표가 있어서 몇백 바이트짜리는 오히려 커진다. 그래서 최소 크기 기준을 두는 설정이 대부분의 서버에 있다
- 압축된 상태로 저장한 것을 검색하려고 매번 푼다. 압축은 공간을 아끼는 대신 읽을 때마다 푸는 비용을 물린다. 자주 읽는 데이터라면 저장 공간보다 그쪽이 비쌀 수 있다
여기서 판단의 근거가 하나 더 생긴다. 압축률을 미리 재 보는 것이 가장 확실하다. 대표 샘플 몇 개를 실제로 압축해서 얼마나 주는지 보면, 이 편의 모든 이론보다 그 숫자가 낫다. 20%도 안 줄어드는 데이터라면 CPU를 쓸 값이 없다는 뜻이다.
정리
- 모든 입력을 줄여 주는 무손실 압축기는 있을 수 없다. 알고리즘 문제가 아니라 개수를 세면 나오는 결론이다.
- 짧은 이름의 개수가 입력의 개수보다 항상 모자라기 때문이다. 해시 충돌이 필연인 이유와 같은 셈이다.
- 따라서 어떤 것을 줄이면 다른 어떤 것은 늘어난다. 압축은 자주 나올 데이터에 짧은 이름을 몰아주는 거래다.
- 압축한 것을 다시 압축하면 오히려 조금 커진다. 첫 압축이 연료를 다 태웠기 때문이고, 그게 잘 압축됐다는 증거다.
- 바닥이 있고 그 이름이 엔트로피다. 짐작이 될수록 줄고 안 될수록 안 준다.
- 난수·암호문·이미 압축된 파일이 안 주는 이유는 전부 이 한 문장이다.
- 그래서 압축을 먼저, 암호화를 나중에 한다. 다만 비밀이 실린 응답에서는 압축한 크기가 힌트를 흘린다.
마지막 글은 지금까지의 원리를 켤 자리와 끌 자리를 고르는 한 장의 표로 접는다.