A, B, C를 각각 0, 01, 11로 바꾸고 구분표 없이 이어 붙여요. 메시지는 유한하고 끝 위치는 알지만 원래 기호 수는 몰라요. 0이 01의 앞부분이므로 원문이 반드시 모호한가? 어떤 유한 메시지에서도 원문을 하나로 복원할 수 있는지 설명해 볼까요? 부호어 길이의 구성이 같은 0, 01, 10 부호와도 비교해요.
메시지 맨 앞에서 0이 나오기 전의 연속 1은 11 부호들이므로 반드시 짝수 개이고 C들로 유일하게 나뉘어요. 그 뒤 각 0은 A 또는 B의 시작이에요. 그 0 다음부터 다음 0 또는 끝까지의 연속 1 개수를 k라 해 볼까요? k가 짝수이면 A 다음 C가 k/2개, 홀수이면 B 다음 C가 (k−1)/2개예요. 따라서 모든 0 구간이 유일하게 분해된다.
어떤 기호의 부호어도 다른 부호어의 앞부분이 아닌 성질을 prefix 조건이라 불러요. 현재는 그 조건을 갖추지 않았지만 완전한 메시지는 유일하게 복원돼요. 다만 0 직후에는 A인지 B인지 바로 결정하지 못할 수 있어요. 반면 C를 10으로 바꾸면 010이 AC와 BA 두 원문에서 나와 모호해요. 두 부호는 길이 1, 2, 2가 같고 길이 합 검사 1/2+1/4+1/4=1도 같지만 실제 복원 구조는 달라요.
Stanford 강의는 prefix 조건과 모든 기호열의 유일 복원을 구별해요. 이 글의 세 부호와 홀짝 분해는 원문 네 기호 연습 문항을 옮긴 것이 아니에요. Kraft 조건의 역이 말하는 것도 그 길이의 어떤 부호가 존재한다는 뜻이며 주어진 임의 부호가 항상 복원된다는 뜻은 아니에요.
한 부호어를 발견하자마자 읽을 수 있는 조건과 끝까지 읽은 뒤 유일해지는 조건을 나누어 봐요. 몇 개의 성공 메시지를 확인하는 대신 모든 연속 1 구간을 분해하는 규칙을 답안에 남겨요.
착안 원문: Stanford EE376A, Lecture5: Variable Length Lossless Compression (23 January2018). 세 기호의 두 부호표와 유한 메시지의 홀짝 분해·유일 복원 증명은 자체 작성했으며, 원문의 prefix 정의와 구별해 사용했어요.