데이터 구조 - 하프 만 인 코딩

하프 만 코드
       컴퓨터 세계 에서 모든 사물 은 2 진법 이다. 예 를 들 어 숫자, 문자, 색채, 소리 등 은 2 진법 으로 저장 되 고 물리 장치 에서 자극 이나 전극 으로 0 또는 1 을 표시 하 며 전류의 형식 으로 전송 되 며 전송 하 는 과정 에서 수 - 모 와 모 - 수의 전환 이 있다.0 과 1 두 가지 숫자 만 있 기 때문에 서로 다른 데 이 터 는 0 과 1 의 서로 다른 편성 으로 표시 되 는데 이런 편성 을 인 코딩 이 라 고 한다.인 코딩 은 컴퓨터 에서 매우 중요 한 개념 으로 인 코딩 이 없 으 면 컴퓨터 가 없 을 것 이다. 0 과 1 만 처리 할 수 있 기 때문에 현실 세계 에 아무런 의미 가 없 기 때문이다.현실 세계 로 서 는 인 코딩 이 없 었 다 면 문명 은 없 었 을 것 이다.소리 도 일종 의 인 코딩 이 라 고 할 수 있다. 서로 다른 소 리 는 서로 다른 의 미 를 나타 내 고 서로 다른 음 조 는 서로 다른 의 미 를 나 타 낼 수 있 으 며 문 자 는 더욱 인 코딩 성 을 가진다. 서로 다른 글자 의 조합 은 서로 다른 의 미 를 나 타 낼 수 있다. 자모의 배열 은 단 어 를 구성 하고 서로 다른 단 어 는 서로 다른 의 미 를 나 타 낼 수 있다.
      그러나 서로 다른 인 코딩 방식 을 사용 하면 사용 하 는 저장 공간 이 다르다.예 를 들 어 27 개의 자 모 는 0 - 26 으로 표시 할 수 있 고 0 - 26 은 5 자리 이상 의 이 진수 로 표시 할 수 있 으 며 서로 다른 자릿수 로 인 코딩 된 코드 의 길이 가 다 르 기 때문에 인 코딩 디 코딩 의 효율 도 다르다.따라서 더욱 좋 은 인 코딩 방식 을 선택 하면 코드 문 을 줄 이 고 인 코딩 과 디 코딩 속 도 를 증가 하 며 네트워크 전송 과정 에서 도 효율 을 높 일 수 있다.
       우 리 는 당연히 인 코딩 후의 코드 문 이 짧 을 수록 좋 기 를 바 랍 니 다. 코드 문 이 더 짧 으 려 면 가장 자주 사용 하 는 기호 에 대응 하 는 코드 를 가능 한 한 짧게 하고 원문 에서 x 기호 가 나타 나 는 횟수 를 f (x) 로 정의 해 야 합 니 다. x 에 대응 하 는 코드 의 길 이 는 g (x) 입 니 다. 그러면 원문의 모든 부호 가 x0 에서 x26 이면 코드 문의 길 이 는 f (x0) g (x0) +... f (x26) g (x26), f (x) 입 니 다. 우 리 는 바 꿀 수 없습니다.그러면 f (x) 가 클 수록 g (x) 를 작 게 설정 할 수록 전체 코드 의 길이 가 짧 아 지 는 것 을 볼 수 있 습 니 다.이것 은 가장 좋 은 문제 다.
       만약 에 이 진 트 리 로 표시 하면 모든 잎 노드 는 하나의 기 호 를 나타 낸다. 뿌리 노드 에서 이 잎 노드 까지 왼쪽으로 갈 때마다 0 을 표시 하고 오른쪽으로 가면 1 을 표시 한다. 뿌리 노드 에서 이 잎 노드 까지 의 경 로 는 0 과 1 의 서열 을 표시 할 수 있다.이 서열 은 왼쪽 에서 오른쪽으로 보면 이 잎 노드 가 표시 하 는 기호 로 인 코딩 될 수 있다.출현 횟수 가 비교적 많 거나 출현 확률 이 비교적 높 은 기 호 를 가능 한 한 이 진 트 리 의 상층 부 에 놓 고 반대로 출현 횟수 가 비교적 적 거나 출현 확률 이 비교적 적은 기 호 를 가능 한 한 이 진 트 리 의 하층부 에 놓 으 면 출현 횟수 가 비교적 많은 기호 가 대응 하 는 인 코딩 의 길이 가 비교적 짧 고 출현 횟수 가 비교적 적은 기호 가 대응 하 는 인 코딩 이 비교적 길다.또한 이 진 트 리 에서 뿌리 노드 부터 잎 노드 까지 모두 다 르 고 유일한 경로 가 있 기 때문에 모든 기호의 인 코딩 도 유일 할 수 있다.이것 은 디 코딩 의 정확성 을 보증 했다.그리고 이런 인 코딩 은 하나의 특성 이 있다. 즉, 모든 기호의 인 코딩 은 다른 기호 인 코딩 의 접두사 가 될 수 없다. 왜냐하면 모든 기호의 인 코딩 은 뿌리 노드 에서 특정한 잎 노드 까지 이기 때문이다.만약 에 x 기호의 인 코딩 이 y 기호 인 코딩 의 접두사 라면 뿌리 노드 에서 y 의 노드 는 반드시 x 의 노드 를 거 쳐 야 하지만 이것 은 이 진 트 리 에서 불가능 하고 잎 노드 는 경로 의 종점 이다.이렇게 하면 무슨 좋 은 점 이 있 습 니까?좋 은 점 은 디 코딩 할 때 접두사 가 있 는 경우, 예 를 들 어 110 으로 A 를 표시 하고 11 은 B 를 표시 하고 0 은 C 를 표시 하면 110 은 A 를 표시 해 야 합 니까? 아니면 BC 를 표시 해 야 합 니까?접두사 가 없 으 면 하나의 기 호 를 해석 할 때 이 기호의 인 코딩 에 뒤의 바 이 너 리 수 를 더 하면 다른 기호의 인 코딩 을 만 들 수 없습니다.이렇게 하면 인 코딩 디 코딩 의 정확성 을 확보 할 수 있다.
       각 잎 노드 에 수치 w (i) 를 설정 하고 뿌리 노드 에서 이 잎 노드 까지 의 경로 길이 가 l (i) 이면 전체 나무의 W =  w (0) l (0) + w (1) l (1) +.만약 에 w (i) 를 기호 가 나타 나 는 횟수 나 빈도 로 설정 하면 경 로 는 이 기호 에 대응 하 는 코드 이 고 l (i) 은 코드 의 길이 이 며 W 는 코드 의 길이 이기 때문에 하프 만 트 리 가 구 조 된 인 코딩 의 최종 코드 의 길이 가 가장 짧 을 것 이다. 이런 가장 좋 은 인 코딩 은 하프 만 인 코딩 이 라 고도 부른다.
       허 면 하프 만 인 코딩 을 어떻게 구성 하 는 지 하 는 임 무 는 하프 만 나 무 를 어떻게 구성 하 는 지 로 바 뀌 었 다.이 진 트 리 의 구 조 는 일반적으로 뿌리 에서 자 랄 수 있 고 잎 노드 부터 합성 하 는 두 가지 방식 으로 나 뉘 는데 하 프 만 나무의 구 조 는 잎 노드 부터 합성 하 는 방식 으로 구 조 를 선택해 야 한다.처음에 모든 기호 에 의 해 일련의 잎 노드 를 생 성 했다. 노드 에 이 기호의 출현 횟수 나 빈도 가 저장 되 어 있다. 이 를 이 노드 의 가중치 w 로 설정 하고 ch 로 이 기 호 를 표시 한다. 그러면 이 잎 노드 를 가중치 가 가장 작은 두 개의 잎 노드 를 선택 하고 다른 노드 를 생 성 한다.이 두 잎 노드 를 각각 새로 생 성 된 노드 의 좌우 부분 노드 로 하고 새로 생 성 된 이 노드 의 이 가중치 를 두 개의 노드 의 가중치 의 합 으로 설정 하면 한 그루 의 나 무 를 생 성 하고 이 나 무 를 하나의 잎 노드 로 삼 아 뿌리 노드 의 권 치 를 그의 가중치 로 간주한다.이 를 남 은 잎 노드 의 집합 에 넣 고 이 노드 에서 가중치 가 가장 작은 두 노드 를 선택 하여 위의 과정 을 반복 한다. 마지막 으로 집합 에서 한 노드 만 남 았 다. 이 노드 는 바로 구조의 하 프 만 나무의 뿌리 노드 이다. 그러면 하 프 만 나 무 는 성공 적 으로 만 들 었 다.
      어떻게 하프 만 트 리 에 따라 인 코딩 표를 생 성 합 니까?원리 도 간단 합 니 다. 이 진 트 리 옮 겨 다 니 기 알고리즘 을 마음대로 사용 하고 하나의 변수 로 루트 노드 가 현재 방문 노드 의 경 로 를 기록 합 니 다. 만약 에 현재 노드 가 하나의 잎 노드 라면 기록 변수의 값 을 코드 로 인 코딩 표 에 추가 합 니 다. 잎 노드 의 ch 는 해당 하 는 기호 입 니 다.
다음은 하프 만 트 리 를 구성 하 는 알고리즘 코드 입 니 다.
테스트 코드

#pragma once
#ifndef HUFFMAN_H
#define HUFFMAN_H
namespace dataStructure
{
	template
	struct HuffmanNode
	{
		T ch;
		int w;
		HuffmanNode *lc;
		HuffmanNode *rc;
	};
	template
	struct HuffmanSetNode
	{
		HuffmanNode* data = NULL;
		HuffmanSetNode *next = NULL;
		HuffmanSetNode *pre = NULL;
	};
	template
	class HuffmanSet
	{
	public:
		HuffmanSet(HuffmanNode** nodes, const int size);
		HuffmanNode* RemoveMin();
		void Add(HuffmanNode* ndoe);
		int Size()const;
	private:
		HuffmanSetNode* header;
		int size;
	};
	template
	HuffmanSet::HuffmanSet(HuffmanNode** nodes,const int size)
	{
		header = new HuffmanSetNode;
		HuffmanSetNode* node = header;
		this->size = size;
		for (int i = 0;i < size;i++) 
		{
			HuffmanNode *hum = nodes[i];
			HuffmanSetNode* newNode = new HuffmanSetNode;
			newNode->data = hum;
			node->next = newNode;
			newNode->pre = node;
			node = newNode;
		}
	}

	template
	HuffmanNode* HuffmanSet::RemoveMin()
	{
		HuffmanSetNode *node = header->next;
		HuffmanSetNode *minNode = node;
		node = node->next;
		while(node)
		{
			if(minNode->data->w > node->data->w)
			{
				minNode = node;
			}
			node = node->next;
		}
		minNode->pre->next = minNode->next;
		if (minNode->next)
		{
			minNode->next->pre = minNode->pre;
		}
		size--;
		return minNode->data;
	}

	template
	void HuffmanSet::Add(HuffmanNode *node)
	{
		HuffmanSetNode *newNode = new HuffmanSetNode;
		newNode->data = node;
		newNode->pre = header;
		newNode->next = header->next;
		if (header->next)
		{
			header->next->pre = newNode;
		}
			header->next = newNode;
		++size;
	}

	template
	int HuffmanSet::Size()const
	{
		return size;
	}

	template
	HuffmanNode *createHuffmanTree(HuffmanNode **nodes,const int size)
	{
		HuffmanSet *set = new HuffmanSet(nodes, size);
		HuffmanNode *min1, *min2;
		while(set->Size()>1)
		{
			min1 = set->RemoveMin();
			min2 = set->RemoveMin();
			HuffmanNode* newNode = new HuffmanNode;
			newNode->w = min1->w + min2->w;
			newNode->lc = min1;
			newNode->rc = min2;
			set->Add(newNode);
		}
		return set->RemoveMin();
	}
}