Hoffman 알고리즘의 방식이 최적의 나무로 시작하는 방식은 무엇입니까?

Question

이 백서 x 및 y 이 가장 작은 확률이고 이 두 문자가 최대 깊이에서 형제 자매 인 최적의 코드 트리가있다....에그 주장에 대한 증거에서, 저자는 트리의 최대 깊이에 b 및 c 을 갖는 t 로 시작한다.나는 x 및 y 이 가장 작은 확률을 가지고 있기 때문에 트리 t 이 최적이라고하는 이유를 이해할 수는 없습니다.알고리즘은 이러한 나무를 만드는 것입니다.나는 최적의 나무가 무엇을 의미하는지 이해하는 것과 관련이 있다고 생각합니다.

누군가가 CSLR에서 오는 경우 이것은 보조 정리 16.2에 관한 것입니다.

Answer 1

평균 코드 워드 길이가 최소 인 경우 코드 트리가 최적의 입니다. 이것은 허프만의 알고리즘과 아무 관련이 없습니다. Huffman의 알고리즘은 최적의 코드 트리를 생성 할 수 있지만 다른 코드 트리가있을 수 있습니다. 실제로 Huffman의 알고리즘은 서로 다른 넥타이 브레이킹 규칙을 사용하여 다른 코드 트리를 생성 할 수 있습니다. 또한 임의의 타이 브레이킹 규칙을 사용하여 허프만의 알고리즘을 사용하여 최적의 코드 트리를 생산할 수있는 것은 아닙니다.

여기에 최적의 코드 트리의 공식적인 정의입니다. $ \ pi $ 배포가되도록하십시오. 코드 트리의 $ \ pi $ -cost 은 코드 워드의 예상 길이이며 $ \ pi $ . 코드 트리는 $ \ pi $ 에 최적입니다 $ \ pi $ -cost는 최소 $ \ pi $ - 모든 코드 트리의 코스트와 같습니다.