반복 속에 숨어 있는 빈 공간

세 입력은 모두 65,536바이트인데 압축 결과는 85, 162, 65,562바이트다.

첫 입력은 A를 반복하고 둘째는 ASTERXOR| 패턴을 같은 총길이까지 반복한다. 셋째는 고정 시드 의사난수 바이트다. zlib 레벨 6으로 모두 압축하고 다시 풀었다. 같은 출발 길이에서 아주 다른 출력이 나왔지만 복구된 모든 바이트는 원본과 같았다.

기회는 데이터 양뿐 아니라 패턴에 있다.

SAY IT SHORTER

반복 구절을 다시 쓰지 않기

문장이 여러 번 반복된다면 앞의 위치를 가리키고 얼마를 재사용할지 적어 짧게 설명할 수 있다. 이 zlib 스트림 내부의 DEFLATE는 반복 바이트 수열에 대한 참조와 효율적인 비트 패턴의 기호 부호화를 결합한다. 복호기는 설명을 따라 원본을 재구성한다.

무손실 거래다. 비슷하게 보이는지만 판단하지 않고 전체 해제 바이트 문자열의 동일성을 검사한다. 이미지 품질 설정, 시각 허용 오차, 버리는 세부는 없다. 더 짧은 표현은 같은 입력을 정확히 되돌릴 때만 성공이다.

THE THREE INPUTS

레벨 6에서 반복 A는 85바이트, 아홉 바이트 반복 패턴은 162바이트가 된다. 의사난수는 원본 65,536보다 조금 큰 65,562바이트다. 가상 압축 내용만이 아니라 형식 비용을 포함한 전체 zlib 출력의 실측 길이다.

두 규칙적 입력 사이 차이도 중요하다. 압축은 서로 다른 바이트 종류만 세지 않는다. 반복 수열의 배치와 길이, 부호화 선택, 스트림 형식이 모두 기여한다. 둘 다 예측 가능하지만 이 인코더에서 같은 길이의 설명을 요구하지는 않는다.

WHEN THERE IS LITTLE TO REUSE

독립적으로 보이는 바이트에는 범용 압축기가 활용할 반복이 적다. 그래도 유효한 스트림의 틀과 무결성 정보가 필요하다. 이 예에서는 26바이트 커졌다. 입력을 망가뜨리거나 왕복에 실패한 것이 아니라 절약이 형식 비용을 넘지 못한 것이다.

한 예가 생성기의 진정한 무작위성을 증명하지 않으며 모든 난수 같은 문자열이 같은 양만큼 커지는 것도 아니다. 압축기는 만능 무작위 검사도 아니다. 어떤 구조를 설명할 줄 아는지와 데이터 양에 따라 성공이 달라진다.

TURN THE DIAL

레벨 1, 6, 9도 시험했다. 반복 A는 308, 85, 85바이트, 패턴은 355, 162, 162바이트다. 의사난수는 항상 65,562바이트였다. 이 세 예에서는 6에서 9로 바꿔도 길이가 달라지지 않았다.

레벨은 인코더의 절충을 안내할 뿐 보존 정보의 백분율이 아니다. 모두 무손실이다. CPU 시간이나 메모리는 측정하지 않아 실제 작업에서 가장 빠르거나 싼 설정을 말할 수 없다. 다이얼은 입력이 거의 주지 않는 기회를 더 열심히 찾을 수는 있다.

THE IMPOSSIBLE PROMISE

가능한 모든 고정 길이 이진 입력에 각각 유일한 더 짧은 설명을 줄 수 없다. 짧은 설명의 수가 부족하기 때문이다. 모두 복원하려면 일부 입력은 그대로이거나 커져야 한다. 현실 형식의 실용 구조도 비용을 보탠다.

이 셈법이 특정 문서의 압축률을 알려 주지는 않는다. 하지만 “모든 파일을 내용 그대로 작게”라는 보편 약속은 불가능함을 설명한다. 실제 자료를 시험하고 필요하면 원본을 보존하며 전체 크기를 비교하자. 예측 가능성이 기회를 만들고 형식은 얼마나 이용할지 정한다.

공식 문서와 함께 읽으면 좋은 자료입니다.