허프만 코드를위한 완전한 이진 트리의 이점은 무엇입니까?

나는 하프 맨 코드를 사용하여 문자 스트림을 인코딩하고 최적의 코드는 각기 다른 문자가 리프로 표현되고 모든 내부 노드는 정확히 두 개의 자식을 포함하는 전체 이진 트리로 표현된다는 것을 읽었다.허프만 코드를위한 완전한 이진 트리의 이점은 무엇입니까?

여기 왜 전체 이진 트리가 최적의 선택인지 알고 싶습니까? 즉, 여기서 전체 이진 트리의 이점은 무엇입니까?

출처

2012-09-17 Geek

[* this *] (http://xlinux.nist.gov/dads/HTML/optimalMerge.html) – alfasin

어디서 읽었습니까? – Deestan

@deestan [알고리즘 소개]의 욕심 많은 알고리즘 장 (http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall) -2005 /) – Geek

이것은 선택 사항이 아니라 동등한 것입니다.

최적 허프만 코드는

각각의 상태는 정확히 두 개의 출구가있는, 유한 상태 머신에 의해 디코딩된다 (인 다음 비트를 0 또는 1)

각 상태는 정확히 하나를 가지고 엔트리

출력 심볼을 포함하는 모든 상태는 정지 상태, 및

모든 정지 상태에는 출력 심볼이 포함됩니다.

이

모든 내부 노드가 정확히 두 아이

모든 노드가 정확히 하나의 부모가 출력 심볼을 포함

모든 노드가 잎 노드, 및 검색 트리에 해당

모든 리프 노드에는 출력 기호가 포함됩니다.

출력 심볼을 포함하지 않는 정지 상태/리프 노드가있는 최적화되지 않은 허프만 코드도 있습니다. 이러한 이진 트리는 이 아니며이 아닙니다.

출처

2012-09-17 08:12:01

"각 주에는 정확히 하나의 항목이 있습니다. "이 무슨 뜻입니까? 또한 전체 이진 트리가 만족하는 허프만 코드 디코딩의 네 가지 요구 사항을 모두 보여주는 그림을 제공 할 수 있습니다. – Geek

각 노드 (시작을 제외하고)에는 하나의 에지 만이 존재합니다 (즉, 동일한 상태를 유도하는 두 개의 입력 심볼 시퀀스가 없음). –

바이너리 트리는 항상 처음 두 개 (내부 노드 당 두 개의 자식 인 "binary"-> "tree"-> cycle free)를 수행합니다. –

허프만 코드를위한 완전한 이진 트리의 이점은 무엇입니까?

답변

관련 문제