2013-01-21 1 views
2

나는 이벤트 발생 확률을 보여주는 테이블을 가지고있다. 1 부에는 문제가 없지만 2 부는 나와 함께 클릭하지 않습니다. 내가 어떻게 주위에 내 머리를 얻으려고 노력하고있다 이진수는 2 부에서 파생됩니까?이 허프만 테이블은 어떻게 생성됩니까?

나는 가장 큰 확률에 0이 할당되어 있다는 것을 알고 있으며 그곳에서부터 작업하지만, 다음 이진수 집합은 어떻게 될까요? 숫자 주위의 동그라미는 회색의 회색 음영 2 개를 차별화합니까?

그냥 클릭하지 않는 것입니다. 어쩌면 누군가 나를 이해할 수있는 방식으로 설명 할 수 있을까요? Diagram 2

답변

4

Diagram 1

는 허프만 코드를 구축하는 하나 개의 방식은 주파수에 따라 정렬 데이터 코드가 삽입되어 할당되도록하는 우선 순위 큐를 이용하여, 이진 트리를 구축한다.

시작하려면 각 데이터를 나타내는 리프 노드 만있는 큐가 있어야합니다.

각 단계에서 대기열에서 두 개의 우선 순위가 가장 낮은 노드를 가져오고 두 개의 제거 된 노드의 합계와 동일한 빈도로 새 노드를 만든 다음이 두 노드를 왼쪽 및 오른쪽 하위 노드로 연결하십시오. 이 새 노드는 빈도에 따라 대기열에 다시 삽입됩니다.

대기열에 하나의 노드 만있을 때까지이 작업을 반복하십시오.

이제 루트에서 모든 리프 노드로 트리를 탐색 할 수 있으며 각 레벨에서 (왼쪽 또는 오른쪽으로 이동하든) 걸리는 경로는 0 또는 1과 경로 길이 노드가 얼마나 멀리 트리에 있는지)는 코드 길이를 제공합니다.

실제적으로 트리를 빌드 할 때이 코드를 빌드 할 수 있지만 포함 된 하위 트리가 왼쪽 또는 오른쪽에 추가되는지 여부에 따라 각 노드의 코드에 0 또는 1을 추가하십시오 새로운 부모의

다이어그램에서 원 안에있는 숫자는 트리를 만드는 각 단계에서 결합 된 두 노드의 빈도의 합계를 나타냅니다.

또한 결합되는 두 개의 비트가 서로 다른 비트 (하나는 0, 다른 하나는 1)로 지정되어야합니다.

다이어그램이 도움이 될 수 있습니다. 내 손으로 쓰는 것에 대한 사과 :

enter image description here