압축 파일이 크기를 줄이는 방법, 반복을 찾아 짧게 적는 부호

압축 파일이 작아지는 이유는 데이터 안에 되풀이되는 부분과 자주 나오는 기호가 있기 때문이다. 압축 프로그램은 이미 나온 내용을 다시 적는 대신 "앞에서 나온 것을 다시 쓰라"는 짧은 지시로 바꾸고, 자주 나오는 기호에는 짧은 부호를, 드물게 나오는 기호에는 긴 부호를 붙인다. 반대로 반복도 치우침도 없는 데이터는 어떤 방법으로도 줄일 수 없다.

같은 것을 두 번 적지 않는다

가장 단순한 방법은 연속된 반복을 세는 것이다. "ㅋㅋㅋㅋㅋㅋㅋㅋ"를 여덟 글자 그대로 저장하는 대신 "ㅋ을 8번"이라고 적으면 훨씬 짧다. 이를 연속 길이 부호화라고 하며, 같은 색이 넓게 이어지는 단순한 그림에서 효과가 크다.

실제 문서에서는 똑같은 글자가 연달아 나오는 일보다 같은 낱말이나 구절이 떨어진 곳에서 다시 나오는 일이 훨씬 많다. 1977년에 발표된 LZ77 방식은 이 점을 노린다. 압축기는 방금 지나온 데이터를 기억해 두었다가, 지금 읽는 부분이 앞에서 나온 적이 있으면 "몇 글자 뒤로 가서 몇 글자를 복사하라"는 두 숫자만 남긴다. 법률 문서처럼 같은 표현이 자주 나오는 글일수록 이 두 숫자가 긴 문장을 대신하게 된다.

자주 나오는 것에 짧은 이름을 준다

두 번째 방법은 기호마다 길이가 다른 부호를 주는 것이다. 영어 문장에서 e는 자주 나오고 z는 드물게 나온다. 모든 글자에 똑같이 8비트를 쓰는 대신 e에는 3비트, z에는 9비트를 주면 전체 길이가 줄어든다. 모스 부호가 가장 흔한 글자인 E에 점 하나만 준 것도 같은 생각이다.

1952년 데이비드 허프먼이 만든 허프먼 부호는 이 길이를 가장 알맞게 정하는 방법이다. 가장 드문 두 기호를 묶어 하나로 보고, 다시 가장 드문 두 묶음을 합치는 일을 되풀이하면 나무 모양의 표가 만들어진다. 나무의 뿌리에서 각 기호까지 내려가는 길이 그 기호의 부호가 된다. 이렇게 만든 부호는 어떤 부호도 다른 부호의 앞부분이 되지 않아서, 구분 기호 없이 이어 붙여도 오해 없이 읽어 낼 수 있다.

흔히 쓰는 ZIP 파일은 이 두 생각을 이어 쓴다. 먼저 LZ77 계열 방식으로 반복을 짧은 지시로 바꾸고, 그 결과를 다시 허프먼 부호로 적는다. 반복을 줄이는 일과 기호를 짧게 적는 일은 서로 다른 낭비를 잡기 때문에 함께 쓸 때 효과가 커진다.

되살릴 수 있는 압축과 버리는 압축

구분	무손실 압축	손실 압축
되살린 결과	원본과 한 비트도 다르지 않음	원본과 비슷하지만 같지는 않음
쓰는 곳	문서, 프로그램, 압축 파일	사진, 음악, 동영상
줄이는 정도	데이터에 따라 몇 분의 일	수십 분의 일까지 가능

프로그램 파일이나 계좌 기록에서 한 글자라도 바뀌면 쓸모가 없어지므로 무손실 압축만 쓴다. 사진과 음악은 사정이 다르다. 사람의 눈은 밝기 변화에는 예민하지만 색의 미세한 차이에는 둔하고, 귀는 큰 소리 바로 옆의 작은 소리를 잘 듣지 못한다. 손실 압축은 사람이 알아채기 어려운 정보를 먼저 버린 뒤 남은 것을 무손실 방식으로 한 번 더 줄인다. 같은 사진을 여러 번 고쳐 저장하면 화질이 조금씩 나빠지는 것은 저장할 때마다 버리는 과정이 되풀이되기 때문이다.

아무리 해도 줄지 않는 데이터

모든 파일을 반드시 줄이는 압축 방법은 존재할 수 없다. 이는 비둘기집 원리로 간단히 보일 수 있다. 길이가 100비트인 파일은 2의 100제곱 가지가 있지만, 그보다 짧은 파일을 모두 합쳐도 그 수에 하나가 모자란다. 모든 100비트 파일을 더 짧게 바꾸려면 서로 다른 두 파일이 같은 결과로 바뀌는 경우가 반드시 생기고, 그러면 원래대로 되돌릴 수 없다.

그래서 동전을 던져 만든 것처럼 무작위인 데이터는 압축되지 않는다. 이미 압축한 파일을 다시 압축해도 거의 줄지 않는 것도 같은 이유다. 첫 번째 압축이 반복과 치우침을 대부분 걷어 냈기 때문에, 결과물은 무작위 데이터와 비슷한 모습이 된다. 압축이 잘 된다는 것은 곧 그 데이터에 아직 예측할 수 있는 규칙이 남아 있다는 뜻이다.

압축률은 파일의 종류에 따라 크게 달라진다. 같은 낱말이 자주 나오는 글이나 빈칸이 많은 표는 몇 분의 일로 줄지만, 이미 손실 압축을 거친 사진이나 동영상은 ZIP으로 묶어도 거의 그대로다. 그래서 사진을 압축 파일로 보내는 것은 크기를 줄이기보다 여러 파일을 하나로 묶는 데 더 쓸모가 있다.

남은 질문

어떤 데이터를 얼마나 줄일 수 있는지의 이론적 한계는 정보량으로 계산할 수 있지만, 그 한계에 얼마나 빨리 다가갈 수 있는지는 여전히 열린 문제다. 압축을 많이 할수록 계산 시간과 기억 공간이 더 들기 때문에, 실제 프로그램은 늘 압축률과 속도 사이에서 타협한다. 최근에는 기계 학습 모델로 다음에 올 기호를 예측해 압축률을 높이려는 시도가 이어지고 있다. 예측을 잘하는 것과 압축을 잘하는 것이 같은 문제라는 사실은, 압축이 단순한 저장 기술을 넘어 데이터를 이해하는 일과 맞닿아 있음을 보여 준다.