허프만 코딩에는 어떤 데이터 구조가 사용됩니까?

허프만 코딩에 사용되는 데이터 구조는 "트리 구조"입니다. 허프만 알고리즘의 지원으로 최적의 이진 트리가 구성되며, 이러한 유형의 트리를 허프만 트리라고 명명합니다. 따라서 엄밀히 말하면 허프만 코딩은 허프만 트리를 기반으로 구성된 코딩 형태이다.

이 튜토리얼의 운영 환경: Windows 7 시스템, Dell G3 컴퓨터.

허프만 코딩에 사용되는 데이터 구조는 "트리 구조"입니다.

허프만 코딩이라고도 알려진 허프만 코딩은 VLC(가변 길이 코딩)의 한 유형입니다. 허프만은 1952년에 코딩 방법을 제안했습니다. 이 방법은 전적으로 문자 발생 확률에 기초하여 서로 다른 접두어의 평균 길이가 가장 짧은 코드워드를 구성하는 방법으로, 때로는 최고의 인코딩이라고도 불리며, 일반적으로 허프만 코딩(Huffman Coding)이라고도 합니다. 허프 코딩).

허프만 코딩은 데이터 구조의 트리 구조를 사용하여 허프만 알고리즘을 지원하여 최적의 이진 트리를 구성합니다. 이러한 유형의 트리를 허프만 트리라고 합니다. 따라서 엄밀히 말하면 허프만 코딩은 허프만 트리를 기반으로 구축된 코딩 형태이며 활용 범위가 매우 넓다.

Huffman Tree

N개의 리프 노드에 N개의 가중치를 부여하여 트리의 가중 경로 길이가 최소값에 도달하면 이러한 이진 트리를 최적 이진 트리라고 하며 허프만 트리라고도 합니다. 나무. 허프만 트리는 가중치가 적용된 경로 길이가 가장 짧은 트리이며, 가중치가 큰 노드는 루트에 더 가깝습니다.

트리의 소위 가중치 경로 길이는 트리에 있는 모든 리프 노드의 가중치에 루트 노드까지의 경로 길이를 곱한 것입니다(루트 노드가 레벨 0인 경우 리프 노드에서 루트까지의 경로 길이 node는 리프 노드의 레이어 수입니다. 트리의 경로 길이는 트리 루트에서 각 노드까지의 경로 길이의 합이며, WPL = (W1*L1+W2*L2+W3*L3+...+Wn*Ln), N 가중치 Wi( i=1,2,...n)은 N개의 리프 노드로 구성된 이진 트리를 구성하고 해당 리프 노드의 경로 길이는 Li(i=1,2,...n)입니다. 허프만 트리의 WPL이 가장 작다는 것을 증명할 수 있습니다.

더 많은 관련 기사를 보려면 PHP 중국어 웹사이트를 방문하세요! !

위 내용은 허프만 코딩에는 어떤 데이터 구조가 사용됩니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!