한 걸음 한 걸음 알고리즘 (하 프 만 트 리 에)

【 성명: 판권 소유, 전재 환영, 상업 용도 로 사용 하지 마 십시오. 연락처: feixiaoxixing @ 163. com] 
     데이터 전송 과정 에서 우 리 는 가능 한 한 적은 대역 폭 으로 더 많은 데 이 터 를 전송 하 기 를 원한 다. 하 프 만 은 그 중의 비교적 적은 대역 폭 전송 방법 이다.하 프 만 의 기본 사상 은 복잡 하지 않다. 그것 은 바로 빈도 가 높 은 데 이 터 를 짧 은 바이트 로 표시 하고 빈도 가 비교적 낮은 데 이 터 를 긴 바이트 로 표시 하 는 것 이다.
    예 를 들 어 현재 4 개의 데 이 터 를 전송 해 야 하 는데 각각 A, B, C, D 이기 때문에 일반적으로 이때 네 개의 데이터 가 나타 날 확률 을 고려 하지 않 으 면 우 리 는 이렇게 분배 할 수 있다. 평균 길 이 는 2 이다.

/*
*  A - 00         B - 01
*  C - 10         D - 11
*/

    그러나 현재 조건 이 바 뀌 었 고 네 개의 데이터 가 나타 나 는 빈 도 는 각각 0.1 / 0.2 / 0.3 / 0.4 이다.그렇다면 이 럴 때 길 이 를 어떻게 나 눠 야 할 지 는 간단 하 다.우 리 는 모든 데 이 터 를 주파수 에 따라 낮은 것 에서 높 은 것 으로 배열 하고 매번 앞의 두 자 리 를 취하 여 새로운 노드 로 합 친 다음 에 이 새 노드 를 대열 에 넣 고 다시 정렬 하면 된다.새 노드 의 왼쪽 노드 는 기본적으로 1 로 설정 하고 오른쪽 노드 는 기본적으로 0 으로 설정 합 니 다.그리고 위의 과정 을 반복 해서 모든 노드 가 하나의 노드 로 합 쳐 질 때 까지 합 니 다.실제 예제 에 적용 된다 면 합병 과정 은 이 렇 을 것 이다.
    첫 번 째 단 계 는 A 와 B 를 먼저 합병 하 는 것 이다. 왜냐하면 A 와 B 는 확률 이 가장 낮 기 때문이다.

/*
*  
*           total_1(0.3)           C (0.3)   D(0.4)
*          /         \
*        A(0.1)      B(0.2)
*/

    두 번 째 단계, 이어서 total 합병1 과 C,

/*
*                 total_2 (0.6)
*               /          \     
*           total_1(0.3)    C (0.3)    D(0.4)
*          /         \
*        A(0.1)      B(0.2)
*/

    마지막 단계, 토 탈 합병2 와 D,

/*
*            final (1.0)
*          /       \          
*       D (0.4)    total_2 (0.6)    
*                /          \     
*           total_1(0.3)    C (0.3)   
*          /         \
*        A(0.1)      B(0.2)
*/

    그래서 위의 생 성 트 리 에 따라 데이터 의 번 호 는 이렇게 배정 해 야 합 니 다.

/*
*   A - 011       B - 010
*   C - 00        D - 1
*/

    A 와 B 의 길이 가 더 늘 어 난 것 처럼 보이 지만 D 의 길 이 는 줄 어 들 었 다.그렇다면 전체 데이터 의 평균 길 이 는 줄 어 들 었 을 까?우 리 는 계산 해 볼 수 있다.3 * 0.1 + 3 * 0.2 + 2 * 0.3 + 0.4 = 1.9 < 2。우 리 는 조 정 된 데이터 의 평균 길이 가 원래 보다 근 (2 - 1.9) / 2 * 100% = 10% 감소 한 것 을 발견 했다. 이것 은 매우 큰 발견 이다.
    하프 만 트 리 전 체 를 만 들 기 위해 서 는 데이터 구 조 를 정의 해 야 합 니 다.

typedef struct _HUFFMAN_NODE
{
	char str;
	double frequence;
	int symbol;
	struct _HUFFMAN_NODE* left;
	struct _HUFFMAN_NODE* right;
	struct _HUFFMAN_NODE* parent;

}HUFFMAN_NODE;

    그 중에서 str 기록 문자, frequency 기록 문자 가 나타 나 는 빈 도 를 기록 하고 symbol 은 분 배 된 데 이 터 를 기록 합 니 다. 왼쪽 트 리 는 1 이 고 오른쪽 트 리 는 0 이 며 left 는 왼쪽 트 리 이 고 right 는 오른쪽 트 리 이 며 parent 는 부모 노드 입 니 다.다음은 허 프 맨 노드 를 만 드 는 것 부터 시작 합 니 다.

HUFFMAN_NODE* create_new_node(char str, double frq)
{
	HUFFMAN_NODE* pNode = (HUFFMAN_NODE*)malloc(sizeof(HUFFMAN_NODE));
	assert(NULL != pNode);

	pNode->str = str;
	pNode->frequence = frq;
	pNode->symbol = -1;
	pNode->left = NULL;
	pNode->right = NULL;
	pNode->parent = NULL;
	return pNode;
}

[미 완성, 계속!]