표찰 A<B<C<D가 열 번의 기록에 각각 1·4·3·2번 나와요. 빈 문자열이 아닌 유한한 0·1 부호어를 표찰에 하나씩 정하는 함수예요. 이어 붙인 기록을 구분선 없이 읽도록 어느 부호어도 다른 부호어의 앞부분이면 안 돼요. 부호어 사전순은 처음 다른 비트에서 0이 1보다 앞서는 순서예요. 이 순서도 A<B<C<D와 같아야 해요. 길이 ℓA, ℓB, ℓC, ℓD로 기록의 최소 비트 수와 모든 최소 부호를 구해 볼까요? 머리말·바이트 채움은 세지 않아요.
부호를 나무의 잎으로 놓아요. 자식이 하나인 마디를 줄이면 잎의 순서와 앞부분 조건을 유지하면서 그 아래 모든 부호가 짧아져요. 따라서 최소에서는 각 안쪽 마디의 자식이 둘이에요. 잎 네 개의 왼쪽·오른쪽 분할은 1+3, 2+2, 3+1이며 양끝 분할마다 두 모양이에요. A부터의 길이 배열은 (1,2,3,3), (1,3,3,2), (2,2,2,2), (2,3,3,1), (3,3,2,1) 전부예요. 비용은 차례로 24·26·20·25·23이므로 답은 하나예요.
A=110, B=0, C=10, D=111은 앞부분 조건을 지키며 19비트지만 A보다 B가 앞서므로 제외해요. B에 0 하나를 주면 맨 앞, 1 하나를 주면 맨 뒤가 되어 가운데 순서를 지킬 수 없어요. 자체 기록 모형이며 실제 파일 크기·처리 속도를 예측하지 않아요.
출처: NIST DADS의 부호나무·순서보존 부호 설명. 다섯 나무와 최적값은 자체 계산이다.
출처·착안: Coding tree