데이터 압축 해설
여러분이 불러오는 모든 웹 페이지, 모든 ZIP 파일, 모든 PNG 이미지는 압축되어 있습니다. 비트 하나 잃지 않고 작아졌다가 도착하면 다시 풀리는 것입니다. 그 뒤에 있는 방법은 놀라울 만큼 단순합니다. 반복되는 것을 찾아서, 다시 말하는 대신 “앞과 같음”이라고 말합니다. 이 아이디어가 어디까지 통하고 어디서 멈추는지는 컴퓨터 과학에서 가장 멋진 이야기 중 하나입니다.
무손실과 손실
압축에는 두 종류가 있습니다. 무손실 압축은 원본을 정확히 되돌려 주며, 텍스트, 프로그램, 스프레드시트처럼 비트 하나만 틀려도 문제가 되는 모든 것에 꼭 필요합니다. 사진, 음악, 동영상에 쓰이는 손실 압축은 사람이 거의 지각하지 못하는 세부를 버려 훨씬 작은 크기에 이르지만, 원본은 영영 사라집니다. 이 페이지와 데모가 다루는 것은 무손실 압축입니다. 무손실 압축은 중복성, 즉 데이터에서 예측할 수 있었던 부분을 찾아 없애는 방식으로 작동합니다.
런 렝스 부호화
가장 단순한 방법은 같은 기호가 이어지는 런을 개수와 그 기호로 바꾸는 것입니다. 흰색 픽셀 12개는 12W가 됩니다. 팩스, 초기 비트맵 형식, PCX 이미지 형식이 이 방법을 썼습니다. 스캔한 페이지와 단순한 그림에는 긴 런이 가득하기 때문입니다. 평범한 텍스트에서는 쓸모가 없고 오히려 해롭습니다. 런이 드물어서 글자 하나하나마다 개수를 쓰면 크기가 두 배가 되기 때문입니다. 그래도 런 렝스 부호화는 첫 번째 변환 뒤에 남는 0의 런을 처리하는 데 쓰이며, 다른 방법 안에서 지금도 살아 있습니다.
LZ77: 앞을 가리키기
1977년 이스라엘 테크니온 공과대학의 두 연구자 아브라함 렘펠과 야코브 지브가 이 분야를 바꾼 방법을 발표했습니다. 부호기는 방금 처리한 텍스트의 윈도우를 유지합니다. 다음 문자들이 이미 윈도우에 나왔다면, 앞선 사본이 얼마나 앞에서 시작하는지와 그 길이가 얼마인지를 한 쌍으로 씁니다. 그렇지 않으면 문자 자체를 씁니다. 복호기는 사전이 전혀 필요 없고, 이미 다시 만든 텍스트만 있으면 됩니다. 참조는 자신이 만들어 내는 텍스트와 겹칠 수도 있어서, 같은 글자 100개가 이어지는 런은 글자 하나와 참조 하나가 됩니다.
LZW: 사전 배우기
렘펠과 지브의 두 번째 방법인 LZ78은 윈도우를 되돌아보는 대신 사전을 만듭니다. 테리 웰치가 1984년에 다듬은 LZW는 256가지 바이트 값 모두로 시작해, 단계마다 이미 아는 가장 긴 문자열의 번호를 보내고, 그 문자열에 다음 문자를 더한 것을 새 항목으로 추가합니다. 복호기는 번호만으로 같은 사전을 다시 만듭니다. LZW는 빠르고 단순해서 Unix의 compress 명령, GIF 이미지 형식, TIFF 파일에 쓰였지만, 1990년대에는 그 특허를 둘러싸고 오랜 분쟁이 벌어졌습니다.
deflate, ZIP, 그리고 그 너머
필 카츠가 1993년 PKZIP 2와 함께 내놓은 deflate 방식은 LZ77과 허프만 부호화를 결합합니다. 반복을 찾은 뒤, 가장 흔한 리터럴, 길이, 거리에 가장 짧은 비트 부호를 줍니다. deflate는 ZIP, gzip, PNG 이미지, 웹 페이지 압축에 쓰이며, 이 데모가 브라우저 자체의 압축기로 측정하는 방식이기도 합니다. Zstandard, Brotli, xz 같은 새로운 방식은 더 큰 윈도우, 더 똑똑한 일치 탐색, 더 정밀한 엔트로피 부호화를 써서 일반적인 파일을 10~30% 더 줄입니다.
모든 것을 줄일 수 없는 이유
어떤 방법도 모든 파일을 더 작게 만들 수는 없습니다. n비트 파일은 2ⁿ개이지만 그보다 짧은 파일은 2ⁿ − 1개뿐이므로, 어떤 방법이 그 모두를 줄인다면 두 파일이 같은 결과가 되어 둘 다 복원할 수는 없게 됩니다. 이것이 비둘기집 원리입니다. 그래서 모든 압축기는 일부 입력을 더 크게 만들며, 보통 암호화된 파일, 이미 압축된 파일, 잡음처럼 무작위로 보이는 데이터가 그렇습니다. 이것은 무작위성의 검사이기도 합니다. 어떤 압축기로도 줄일 수 없는 데이터는 무작위로 보입니다.
엔트로피 한계
클로드 섀넌은 1948년, 정보원의 엔트로피가 어떤 무손실 부호든 기호당 평균 비트 수로 가능한 최솟값이라는 것을 보였습니다. 글자 하나씩 세면 영어 텍스트의 엔트로피는 글자당 약 4비트로, 저장에 쓰는 8비트의 절반입니다. LZ77처럼 문맥을 이용하는 방법은 참조 하나가 한 구간 전체를 한꺼번에 나타내므로, 반복이 많은 텍스트에서 이 글자 단위 수치보다 낮아집니다. 앞에 나온 모든 것으로부터 각 글자를 예측하는 최고의 현대 압축기는 영어를 글자당 2비트 미만까지 줄입니다.
직접 탐구하기
압축 데모를 열어 문단, 후렴이 있는 노래, 픽셀 한 줄, 데이터 표, 무작위 글자, DNA, 또는 직접 입력한 텍스트에 LZ77, LZW, 런 렝스 부호화를 실행해 보세요. LZ77 참조를 클릭해 무엇을 복사하는지 보고, LZW 사전이 자라는 모습을 지켜보며, 모든 방법을 ZIP 및 엔트로피 한계와 비교해 보세요.
자주 묻는 질문
압축비 3 : 1은 무슨 뜻인가요?
원본이 압축된 버전보다 세 배 크다는 뜻입니다. 따라서 압축된 파일은 공간의 3분의 1만 차지하고 3분의 2를 절약합니다. 텍스트는 ZIP으로 보통 2 : 1에서 4 : 1에 이르며, 로그 파일처럼 반복이 많은 데이터는 흔히 그보다 훨씬 높습니다.
ZIP 파일을 다시 압축해도 소용없는 이유는 무엇인가요?
첫 번째 압축에서 이미 반복이 제거되어 출력이 거의 무작위처럼 보입니다. 두 번째 압축은 가리킬 것을 하나도 찾지 못하고 자체 오버헤드만 더하므로, 파일 크기는 그대로이거나 조금 커집니다.
LZ77 윈도우는 왜 클수록 좋은가요?
윈도우가 크면 부호기가 여러 절이 지난 뒤 다시 나오는 후렴처럼 더 멀리 앞에 있는 반복도 찾을 수 있습니다. 대신 거리마다 쓰는 데 더 많은 비트가 들고 탐색 시간도 길어집니다. 그래서 deflate는 32 KB에서 멈추고, 새로운 방식은 메가바이트 단위를 허용합니다.
압축은 암호화와 같은 것인가요?
아니요. 압축은 데이터를 작게 만들며 누구나 되돌릴 수 있습니다. 암호화는 키 없이는 데이터를 읽을 수 없게 만듭니다. 둘은 자주 함께 쓰이는데, 그때는 반드시 먼저 압축해야 합니다. 암호화된 데이터는 무작위로 보여서 더는 압축할 수 없기 때문입니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
압축 데모 열기