8 비트 시퀀스에서 호프만 코딩이 입증되었습니다.

Question

데이터 파일에는 8 비트 문자 시퀀스가 ​​포함되어있어 모든 256 문자가 공통으로 사용됩니다. 최대 문자 빈도는 최소 문자 빈도의 두 배 미만입니다. 이 경우 허프만 코딩이 일반적인 8 비트 고정 길이 코드를 사용하는 것보다 효율적이지 않다는 것을 증명하십시오.

Answer 1

증명은 직접적입니다. 가정합니다. 문자는 주파수의 오름차순으로 정렬됩니다. 우리는 f (1)과 f (2)가 먼저 f '(1)에 결합되고 f (2)> = f (1) 및 2 * f (1)> f f (256)가 무언가와 결합 될 때까지 결합되지 않습니다. 같은 토큰으로, f (3)와 f (4)는 f '(2)> = f'(1)> f (256)로 f '(2)에 결합됩니다. 계속해서 f (253)와 f (254)를 f '(127)> =>> = f'(1)> f (256)에 합치면된다. 마지막으로, f (255)와 f (256)은 f '(128)> = f'(127)> =>> = f '(1)로 결합된다. 이제 f (256) <2 * f (1) < = f '(1) 및 f'(128) < = 2 * f (256), f '(128) < = 2 * f) <4 * f (1) < = 2 * f '(1). Ergo, f '(128) < 2 * f'(1), 허프만 알고리즘의 첫 번째 라운드에서 유지했던 것과 동일한 조건.

조건이이 라운드에서 유지되므로, 모든 라운드에서 유사하게 유지 될 것이라고 주장하는 것이 간단합니다. 허프만은 모든 노드가 루트 (128, 64, 32, 16, 8, 4, 2, 1)에 연결될 때까지 8 라운드를 수행하며, 알고리즘이 종료됩니다. 각 단계에서 각 노드가 허프만 알고리즘에 의해 동일한 처리를받은 다른 노드에 연결되기 때문에 트리의 각 분기는 동일한 길이를 갖습니다 : 8.

이것은 다소 비공식적입니다 증명보다 스케치가 필요하지만, 좀 더 공식적인 것을 쓰는 것 이상으로 충분해야합니다.