압축 프로토콜과 정확한 복원

압축은 복호 규칙까지 포함한다

압축된 배열이 짧아 보이는 것만으로 무손실 부호가 되지는 않습니다. 수신자가 비트열을 원본으로 유일하게 되돌릴 규칙이 있어야 합니다. 여기서는 N=8 또는 16이 외부에서 공유되었다고 가정하고 길이 N의 이진 문자열을 부호화합니다. 원본 길이가 알려지지 않으면 그 길이를 보내는 비용도 추가해야 합니다.

실습의 mask는 정수이며 낮은 N비트만 사용합니다. 화면의 문자열은 보통의 높은 자리부터 읽습니다. 외부 길이, 비트 순서, 방식 헤더도 프로토콜의 일부입니다.

두 방식의 정확한 문법

Raw 방식은 헤더 0 뒤에 N비트를 그대로 붙입니다. RLE는 헤더 1 뒤에 첫 비트 한 개와 각 run의 길이−1을 붙입니다. N이 2의 거듭제곱이므로 각 길이는 w=log₂N비트로 표현할 수 있습니다. run 사이의 비트는 항상 반전되므로 따로 보내지 않습니다.

N=16의 0000000000000000은 1 · 0 · 1111입니다. 마지막 1111은 정수 15에 1을 더한 길이 16입니다. 전체는 6비트이며 원본을 정확히 복원합니다. N=16의 0000000011111111은 1 · 0 · 0111 · 0111로 10비트입니다.

복호가 실제로 수행하는 일

수신자는 헤더로 방식을 선택하고, RLE이면 첫 비트를 각 길이만큼 반복한 뒤 반전합니다. 길이의 합이 정확히 N이어야 합니다. 부족한 토큰·N 초과·잘못된 문자는 오류로 거부합니다. Raw 헤더이면 나머지가 정확히 N비트인지 검사합니다.

화면은 실제 전송 stream과 실제 복호 결과를 표시합니다. RLE가 더 길면 raw를 선택하며 동점도 raw로 처리합니다. 선택 규칙을 알고 있어도 어느 방식이 선택되었는지 전달할 헤더는 여전히 필요합니다.

모든 입력을 압축할 수 없는 이유

교대열 0101…은 run이 16개라 RLE 비용이 66비트입니다. 최종 인코더는 raw의 17비트를 택합니다. 원본 16비트보다 한 비트 길지만 공유 문법 아래에서 유일 복원됩니다. N비트 문자열은 2ᴺ개인데 길이가 N 미만인 모든 문자열은 2ᴺ−1개뿐입니다. 비둘기집 원리 때문에 모든 입력을 동시에 짧게 하는 단사 압축은 불가능합니다.

AI 체크포인트의 압축률도 가중치 본체뿐 아니라 코드북·스케일·인덱스·모형 버전을 포함해야 합니다. 손실 양자화는 정확한 원본 복원이라는 현재 조건을 바꿉니다. 전송 중 오류를 고치는 것은 별도의 오류정정부호 문제입니다.

확인 문제와 해설

1. N=8에서 상수열 길이는? 5비트입니다. 헤더 1, 첫 비트 1, 길이 3비트입니다.
2. 헤더를 빼고 압축률을 비교해도 되나요? 아니요. 복호기가 방식을 모르면 실제 독립 프로토콜이 아닙니다. 공유한 경우에는 그 공유 조건을 명시해야 합니다.
3. 압축된 stream 한 비트가 변하면 자동 복구되나요? 보장하지 않습니다. 유효한 다른 길이나 다른 문자열이 될 수 있습니다.

실습의 문법과 복호기는 이 단원의 명세입니다. 추가 배경: MIT 6.441, Source Coding and Channel Coding.