가상 저장기의 원본 기록은 0과 1로 이루어진 네 비트예요. 예를 들어 0000과 0001도 다른 기록이에요. 고정된 하나의 압축·복원 규칙으로 모든 원본을 세 비트 이하로 줄이려 해요. 파일 이름이나 별도 표에 원본 정보를 숨기지 않고 저장한 비트열만으로 정확히 복원해야 해요.
원본 종류는 각 자리에 두 선택지가 있으므로 2⁴=16개예요. 압축 기록에는 0, 1, 2, 3비트 길이를 모두 허용하며 길이도 구별한다고 해 볼까요? 가장 유리하게 길이가 0인 빈 기록까지 하나로 세어요.
길이별 기록 수를 다 합해도 15개뿐이에요. 서로 다른 원본 두 개가 같은 압축 기록을 받으면 복원기는 그 기록을 보고 어느 원본이었는지 알 수 없어요. 따라서 정확한 복원에는 서로 다른 원본이 서로 다른 기록으로 가는 일대일 대응이 필요해요.
16개 원본을 15개 기록에 충돌 없이 배정할 수 없으므로 모든 네 비트 파일을 짧게 만드는 규칙은 없어요. 어떤 원본은 적어도 네 비트 이상을 써야 해요. 이것은 반복이 많은 특정 파일이 잘 압축될 수 없다는 뜻이 아니에요. 유리한 파일에서 길이를 줄이는 것과 가능한 모든 파일에 단축을 보장하는 것은 서로 다른 요구예요.
참고한 수학 개념: AMS · Alan Turing and the Countability of Computable Numbers.
이 글의 생활 상황과 계산 예시는 수학 이야기에서 새로 구성했습니다.