최우수 두 갈래 나무 & 하프만 인코딩

트리 경로 길이

트리의 경로 길이는 트리 루트에서 트리의 각 결점까지의 경로 길이의 합입니다.결점 수가 같은 두 갈래 나무 중에서 완전 두 갈래 나무의 경로 길이가 가장 짧다.

트리의 권한 경로 길이(weighted path length of tree, wpl)

결점의 권한 값: 일부 응용 프로그램에서 트리의 결점에 어떤 의미를 부여하는 실수,
결점의 권한 있는 경로 길이: 결점에서 나무 뿌리 사이의 경로 길이와 이 결점의 권한 곱하기
트리의 권한 있는 경로 길이 (wpl): 트리의 모든 결점의 권한 있는 경로 길이의 합으로 정의됨

최우수 두 갈래 나무

재권은 w1, w2,...,n개
잎결점으로 구성된 모든 두 갈래 나무 중 대권 경로의 길이가 가장 작은 두 갈래 나무가 가장 좋은 두 갈래 나무가 된다.
참고:

잎의 권치가 모두 같고 완전 두 갈래 나무는 반드시 최우선 두 갈래 나무일 것이다. 그렇지 않으면 완전 두 갈래 나무가 반드시 최우선 두 갈래 나무가 아닐 것이다

가장 좋은 두 갈래 나무 중 권치가 큰 잎사귀의 결점은 뿌리와 가깝다

가장 좋은 두 갈래 나무의 형태는 유일하지 않고 wpl이 가장 작다

구조가 가장 좋은 두 갈래 나무

하프만 알고리즘

주어진 n개의 권한에 따라 w1, w2,...,n은 n그루의 두 갈래 나무를 구성하는 숲 F={T1, T2,..., Tn}을 구성하는데 그 중에서 두 갈래 나무 Ti 중 하나의 권한이 wi인 뿌리 노드만 있고 좌우 나무는 모두 비어 있다

삼림 F에서 두 그루의 뿌리가 가장 작은 나무(이런 나무가 두 그루에 그치지 않을 때 그 중에서 두 그루를 선택할 수 있음)를 선택하여 이 두 그루의 나무와 한 그루의 새 나무라고 부른다. 새 나무가 여전히 두 갈래 나무임을 확보하기 위해서는 새 나무의 뿌리로 새 뿌리를 추가하고 선택한 두 그루의 뿌리를 각각 새 나무의 좌우 아이로 하여 이 두 아이의 가치와 새 뿌리의 가치로 삼아야 한다

새로운 숲 F에 대해 2를 반복하고 숲 F에 나무 한 그루만 남을 때까지..

주의하다

초기 삼림 중의 n그루의 두 갈래 나무는 나무마다 고립된 결점이 있는데 뿌리이자 잎이다

n개의 잎결점을 가진 하프만 나무는 n-1회 합병을 거쳐 n-1개의 새로운 결점을 만들어야 한다.최종적으로 구한 하프만 나무는 모두 2n-1개의 결점이 있다

하프만 나무는 엄격한 두 갈래 나무로 도수가 1인 분지 결점이 없다

하프만 나무 저장 구조

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 100
#define MIN_NUM 1000000

struct hfmcode
{
	int weight;
	int lchild;
	int rchild;
	int parent;
};

참고:

따라서 수조 하계는 0이기 때문에 -1로 빈 바늘을 표시한다.나무의 어떤 결점인lchild,rchild,parent는 -1과 같지 않을 때, 그것들은 각각 이 결점의 왼쪽, 오른쪽 아이와 양친 결점이 벡터 중의 하표이다

parent역의 역할: 첫째, 양친 결점을 찾는 것이 더욱 간단하다.둘째,parent값이 -1인지 아닌지를 판정하여 뿌리와 비뿌리 결점을 구분할 수 있다..

구현 코드

(1) 초기화하여 T[0.m-1]의 2n-1 결점에 있는 세 개의 바늘을 모두 비우고(=-1), 값을 0으로 설정합니다.

void initHuffmantree(struct hfmcode *tree, int len)
{
	int i;

	for(i = 0; i < len; i ++)
	{
		tree[i].weight = 0;
		tree[i].lchild = -1;
		tree[i].rchild = -1;
		tree[i].parent = -1;
	}
}

(2) 입력, n개의 잎을 읽는 권한은 벡터의 앞 n개의 분량 (즉 T[0.n-1]) 에 저장됩니다.

int main()
{
	int n, m, i;
	struct hfmcode hfmtree[MAX_SIZE];

	while(scanf("%d", &n) != EOF)
	{
		/* */
		m = 2 * n - 1;

		/* */
		initHuffmantree(hfmtree, m);

		/* */
		for(i = 0; i < n; i ++)
		{
			scanf("%d", &hfmtree[i].weight);
		}

		/* */
		createHuffmantree(hfmtree, n, m);

		printf("%d
", hfmtree[m - 1].weight);
	}

	return 0;
}

(3) 합병, 삼림 속의 나무에 대해 모두 n-1회 합병, 발생하는 새로운 결점은 차례로 벡터 T의 i번째 분량에 넣는다(n<=i<=m-1).병합할 때마다 두 단계로 나뉩니다.

현재 삼림 T[0.i-1]의 모든 결점에서 선택권이 가장 작고 다음이 작은 두 개의 뿌리 노드 T[p1]와 T[p2]를 합병 대상으로 한다. 여기에 0<=p1, p2<=i-1

뿌리가 T[p1]와 T[p2]인 두 그루의 나무를 좌우자 나무로 합쳐 새로운 나무로 만들고 새로운 뿌리는 새로운 노드 T[i]이다.구체적인 조작은 T[p1]와 T[p2]의parent를 i로 하고, T[i]의lchild와 rchild를 각각 p1과 p2로 하는 것이다.새 결점 T[i]의 값은 T[p1]와 T[p2]의 값의 합으로 설정됩니다

합병 후, T[p1]와 T[p2]는 현재 숲에서 더 이상 뿌리가 아니다. 그들의 양친 지침은 모두 T[i]를 가리키기 때문에 다음 합병 시 합병 대상으로 선택되지 않는다

void createHuffmantree(struct hfmcode *tree, int n, int m)
{
	int m1, m2, i, loc1, loc2, k;

	for(i = n; i < m; i ++)
	{
		/* 、 */
		m1 = m2 = MIN_NUM;
		loc1 = loc2 = -1;
		/* */
		for(k = 0; k < i; k ++)
		{
			if(tree[k].parent == -1)
			{
				if(tree[k].weight < m1)
				{
					m2 = m1;
					loc2 = loc1;
					m1 = tree[k].weight;
					loc1 = k;
				}else if(tree[k].weight < m2)
				{
					m2 = tree[k].weight;
					loc2 = k;
				}
			}
		}

		/* 2 */
		tree[loc1].parent = i;
		tree[loc2].parent = i;

		/* parent */
		tree[i].weight = tree[loc1].weight + tree[loc2].weight;

		/* parent */
		tree[i].lchild = loc1;
		tree[i].rchild = loc2;
	}
}

하프만 코드

인코딩 및 디코딩

데이터가 압축되는 과정은 인코딩이 된다.파일의 모든 문자를 유일한 바이너리 문자열로 변환합니다
데이터 압축 해제 과정이 디코딩이 되다.바이너리 직렬 변환에 대응하는 문자

접두사 & & 최우수 접두사

문자 집합을 인코딩할 때, 문자 집합을 요구하는 모든 문자의 인코딩은 다른 문자의 인코딩 접두사가 아니다. 이런 인코딩은 접두사 인코딩이 된다
평균 부호 길이나 파일 길이가 가장 작은 접두사 인코딩이 가장 좋은 접두사 인코딩이 되고, 가장 좋은 접두사 인코딩은 파일의 압축 효과도 가장 좋다.

하프만 인코딩 최우선 접두사 인코딩

모든 잎 문자ci의 코드 길이는 뿌리에서 이 잎까지의 경로 길이인 li이고, 평균 코드 길이(또는 파일 길이)는 두 갈래 나무의 권한 있는 경로 길이인 WPL이다.하프만 나무는 WPL에서 가장 작은 두 갈래 나무이기 때문에 인코딩의 평균 부호 길이도 가장 작다

나무에 잎이 하나도 없는 것은 다른 잎의 조상이다. 잎마다 대응하는 인코딩은 다른 잎 인코딩의 접두사가 될 수 없다

하프만 인코딩 알고리즘

알고리즘 사상

주어진 문자 집합의 하프만 트리를 생성한 후 하프만 인코딩을 구하는 구체적인 실현 과정은 다음과 같다. 순서대로 잎 T[i](0<=i참고:

인코딩과 요구된 인코딩 반순으로 인코딩되었습니다

알고리즘 코드

/* */
struct hfmd
{
	char code[MAX_SIZE];
};

void createHuffmancode(struct hfmcode *htree, struct hfmd *hcode, int n)
{
	/*c p T */
	int p, i, c;
	/* */
	char cd[n];
	/* cd */
	int start;
	
	/* T[i] */
	for(i = 0; i < n; i ++)
	{
		c = i;
		start = n;
		memset(cd, 0, sizeof(cd));
		p = htree[c].parent;
		while(p != -1)
		{
			cd[-- start] = (htree[p].lchild == c)? '0' : '1';
			c = p;
			p = htree[p].parent;
		}
		strcpy(hcode[i].code, cd + start);		
	}
}

체인 시계는 하프만 나무를 실현한다

주의하다

체인 시계로 하프만 나무를 실현하는 학우들은 바늘 변수와 노드 변수의 차이에 주의하는 것이 가장 좋다!

하프만 나무 저장 구조 정의

// 
struct huffmancode
{
	int power;
	struct huffmancode *lchild;
	struct huffmancode *rchild;
	struct huffmancode *next;
};

하프만 나무 만들기

여기에 기교가 하나 있습니다. 체인 테이블을 구축할 때 체인 테이블의 질서를 확보합니다. 이렇게 매번 가장 작은 두 개의 노드를 취할 때마다 처음부터 헤드에서pl=head->next,pr=head->next->next를 찾으면 됩니다. 정렬 시간을 절약할 수 있습니다!

/**
 * Description: 
 */
struct huffmancode* createHuffmanTree(int n, int *weight)
{
	int i;
	struct huffmancode *head, *pl, *pr, *proot;
	head = (struct huffmancode *)malloc(sizeof(struct huffmancode));
	head->next = NULL;

	// 
	for(i = 0; i < n; i ++)
	{	
		struct huffmancode *pnode = (struct huffmancode *)malloc(sizeof(struct huffmancode));
		pnode->power = *(weight + i);
		pnode->lchild = pnode->rchild = pnode->next = NULL;
		addNode(head, pnode);
	}

	// 
	while(head->next->next)
	{
		// 
		if(!head->next->next)
		{
			break;
		}

		// 
		pl = head->next;
		pr = pl->next;

		// pl、pr ， 
		head->next = pr->next;
		proot = (struct huffmancode *)malloc(sizeof(struct huffmancode));
		proot->power = pl->power + pr->power;
		proot->lchild = pl;
		proot->rchild = pr;
		addNode(head, proot);
	}		

	return head->next;
}

/**
 * Description: 
 */
void addNode(struct huffmancode *head, struct huffmancode *pnode)
{
	struct huffmancode *t = head;

	// ，t 
	while(t->next && t->next->power < pnode->power)
	{
		t = t->next;
	}
	pnode->next = t->next;
	t->next = pnode;
}

WPL 가져오기

/**
 * Description: 
 */
int getWPL(struct huffmancode *root, int level)
{
	if(!root)
	{
		return 0;
	}
	if(!root->lchild && !root->rchild)
	{
		return root->power * level;
	}
	
	return getWPL(root->lchild, level + 1) + getWPL(root->rchild, level + 1);
}

하프만 나무 비우기

/**
 * Description: 
 */
void freeHuffmantree(struct huffmancode *root)
{
	if(!root)
	{
		return;
	}
	freeHuffmantree(root->lchild);
	freeHuffmantree(root->rchild);
	free(root);
}

후기

하프만 나무와 하프만 인코딩이 가장 좋은 기초입니다. 제가 아래에 9도 acm문제를 붙여서 하프만 나무를 실전해 보겠습니다. 괜찮은 것 같으면 댓글을 달아도 돼요. 친구, 의문이 있으면 토론해도 돼요, 친구!

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

java 데이터 구조 2차원 트리의 실현 코드

일.두 갈래 트리 인터페이스 2 노드 클래스 3. 두 갈래 나무 구현 이 글을 통해 여러분께 도움이 되었으면 좋겠습니다. 본 사이트에 대한 지지에 감사드립니다!...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

최우수 두 갈래 나무 & 하프만 인코딩

트리 경로 길이

트리의 권한 경로 길이(weighted path length of tree, wpl)

최우수 두 갈래 나무

구조가 가장 좋은 두 갈래 나무

하프만 알고리즘

하프만 나무 저장 구조

구현 코드

하프만 코드

인코딩 및 디코딩

접두사 & & 최우수 접두사

하프만 인코딩 최우선 접두사 인코딩

하프만 인코딩 알고리즘

알고리즘 사상

알고리즘 코드

체인 시계는 하프만 나무를 실현한다

주의하다

하프만 나무 저장 구조 정의

하프만 나무 만들기

WPL 가져오기

하프만 나무 비우기

후기

좋은 웹페이지 즐겨찾기