Kodowanie Huffmana to bezstratny algorytm kompresji danych. Pomysł polega na tym, aby do wprowadzanych znaków przypisywać kody o zmiennej długości, długości przypisywanych kodów opierają się na częstotliwości występowania odpowiednich znaków.
Kody o zmiennej długości przypisane do znaków wejściowych to Kody prefiksów , oznacza, że ​​kody (sekwencje bitów) są przypisane w taki sposób, że kod przypisany do jednego znaku nie jest przedrostkiem kodu przypisanego do innego znaku. W ten sposób Huffman Coding gwarantuje, że podczas dekodowania wygenerowanego strumienia bitów nie będzie żadnych dwuznaczności.
Przyjrzyjmy się kodom prefiksów na przykładzie licznika. Niech będą cztery znaki a, b, c i d, a odpowiadające im kody o zmiennej długości będą wynosić 00, 01, 0 i 1. To kodowanie prowadzi do niejednoznaczności, ponieważ kod przypisany do c jest przedrostkiem kodów przypisanych do a i b. Jeżeli skompresowany strumień bitów ma wartość 0001, zdekompresowany wynik może mieć postać cccd, ccb, ​​acd lub ab.
Widzieć Ten do zastosowań kodowania Huffmana.
Kodowanie Huffmana składa się głównie z dwóch głównych części

1. Zbuduj drzewo Huffmana na podstawie wprowadzonych znaków.
2. Przemierzaj Drzewo Huffmana i przypisuj kody postaciom.

Algorytm:

Metoda, która służy do konstruowania optymalnego kodu przedrostkowego, nazywa się Kodowanie Huffmana .

Algorytm ten buduje drzewo w sposób oddolny. Możemy oznaczyć to drzewo przez T

Niech, |c| być liczbą liści

|c| -1 to liczba operacji wymaganych do połączenia węzłów. Q będzie kolejką priorytetową, której można użyć podczas konstruowania sterty binarnej.

Algorithm Huffman (c) { n= |c| Q = c for i <-1 to n-1 do { temp  <- get node () left (temp] Get_min (Q) right [temp] Get Min (Q) a = left [templ b = right [temp] F [temp] <- f[a] + [b] insert (Q, temp) } return Get_min (0) } 

Kroki do zbudowania drzewa Huffmana
Dane wejściowe to tablica unikalnych znaków wraz z częstotliwością ich występowania, a dane wyjściowe to Drzewo Huffmana.

1. Utwórz węzeł-liść dla każdego unikalnego znaku i zbuduj minimalną stertę wszystkich węzłów-liście (Min Heap jest używana jako kolejka priorytetowa. Wartość pola częstotliwości służy do porównywania dwóch węzłów w min stercie. Początkowo najrzadziej występujący znak znajduje się na źródło)
2. Wyodrębnij dwa węzły z minimalną częstotliwością ze sterty min.
   
3. Utwórz nowy węzeł wewnętrzny o częstotliwości równej sumie częstotliwości dwóch węzłów. Ustaw pierwszy wyodrębniony węzeł jako lewy element podrzędny, a drugi wyodrębniony węzeł jako prawy element podrzędny. Dodaj ten węzeł do sterty min.
4. Powtarzaj kroki nr 2 i 3, aż sterta będzie zawierać tylko jeden węzeł. Pozostały węzeł jest węzłem głównym i drzewo jest gotowe.
   Zrozumiemy algorytm na przykładzie:

character Frequency a 5 b 9 c 12 d 13 e 16 f 45 

Krok 1. Zbuduj minimalną stertę zawierającą 6 węzłów, gdzie każdy węzeł reprezentuje korzeń drzewa z pojedynczym węzłem.
Krok 2 Wyodrębnij dwa węzły częstotliwości minimalnej ze sterty min. Dodaj nowy węzeł wewnętrzny z częstotliwością 5 + 9 = 14.

Ilustracja kroku 2

Teraz minimalna sterta zawiera 5 węzłów, gdzie 4 węzły to korzenie drzew z jednym elementem każdy, a jeden węzeł sterty jest korzeniem drzewa z 3 elementami

character Frequency c 12 d 13 Internal Node 14 e 16 f 45 

Krok 3: Wyodrębnij dwa węzły częstotliwości minimalnej ze sterty. Dodaj nowy węzeł wewnętrzny o częstotliwości 12 + 13 = 25

Ilustracja kroku 3

Teraz minimalna sterta zawiera 4 węzły, gdzie 2 węzły są korzeniami drzew z jednym elementem każdy, a dwa węzły sterty są korzeniami drzewa z więcej niż jednym węzłem

character Frequency Internal Node 14 e 16 Internal Node 25 f 45 

Krok 4: Wyodrębnij dwa węzły częstotliwości minimalnej. Dodaj nowy węzeł wewnętrzny o częstotliwości 14 + 16 = 30

Ilustracja kroku 4

Teraz min sterta zawiera 3 węzły.

character Frequency Internal Node 25 Internal Node 30 f 45 

Krok 5: Wyodrębnij dwa węzły częstotliwości minimalnej. Dodaj nowy węzeł wewnętrzny o częstotliwości 25 + 30 = 55

Ilustracja kroku 5

Teraz minimalna sterta zawiera 2 węzły.

character Frequency f 45 Internal Node 55 

Krok 6: Wyodrębnij dwa węzły częstotliwości minimalnej. Dodaj nowy węzeł wewnętrzny o częstotliwości 45 + 55 = 100

Ilustracja kroku 6

Teraz min sterta zawiera tylko jeden węzeł.

character Frequency Internal Node 100 

Ponieważ sterta zawiera tylko jeden węzeł, algorytm zatrzymuje się w tym miejscu.

Kroki drukowania kodów z Huffman Tree:
Przemierzaj utworzone drzewo zaczynając od korzenia. Utrzymuj tablicę pomocniczą. Przechodząc do lewego dziecka, wpisz 0 do tablicy. Przechodząc do prawego dziecka, wpisz 1 do tablicy. Wydrukuj tablicę po napotkaniu węzła liścia.

Kroki drukowania kodu z HuffmanTree

Kody są następujące:

character code-word f 0 c 100 d 101 a 1100 b 1101 e 111 

Zalecana praktyka Kodowanie Huffmana Wypróbuj!

Poniżej znajduje się implementacja powyższego podejścia:

C

// C program for Huffman Coding> #include> #include> > // This constant can be avoided by explicitly> // calculating height of Huffman Tree> #define MAX_TREE_HT 100> > // A Huffman tree node> struct> MinHeapNode {> > > // One of the input characters> > char> data;> > > // Frequency of the character> > unsigned freq;> > > // Left and right child of this node> > struct> MinHeapNode *left, *right;> };> > // A Min Heap: Collection of> // min-heap (or Huffman tree) nodes> struct> MinHeap {> > > // Current size of min heap> > unsigned size;> > > // capacity of min heap> > unsigned capacity;> > > // Array of minheap node pointers> > struct> MinHeapNode** array;> };> > // A utility function allocate a new> // min heap node with given character> // and frequency of the character> struct> MinHeapNode* newNode(> char> data, unsigned freq)> {> > struct> MinHeapNode* temp = (> struct> MinHeapNode*)> malloc> (> > sizeof> (> struct> MinHeapNode));> > > temp->lewy = temp->prawy = NULL;> > temp->dane = dane;> > temp->częstotliwość = częstotliwość;> > > return> temp;> }> > // A utility function to create> // a min heap of given capacity> struct> MinHeap* createMinHeap(unsigned capacity)> > {> > > struct> MinHeap* minHeap> > = (> struct> MinHeap*)> malloc> (> sizeof> (> struct> MinHeap));> > > // current size is 0> > minHeap->rozmiar = 0;> > > minHeap->pojemność = pojemność;> > > minHeap->tablica = (> struct> MinHeapNode**)> malloc> (> > minHeap->pojemność *> sizeof> (> struct> MinHeapNode*));> > return> minHeap;> }> > // A utility function to> // swap two min heap nodes> void> swapMinHeapNode(> struct> MinHeapNode** a,> > struct> MinHeapNode** b)> > {> > > struct> MinHeapNode* t = *a;> > *a = *b;> > *b = t;> }> > // The standard minHeapify function.> void> minHeapify(> struct> MinHeap* minHeap,> int> idx)> > {> > > int> smallest = idx;> > int> left = 2 * idx + 1;> > int> right = 2 * idx + 2;> > > if> (left size> > && minHeap->tablica[po lewej]->częstotliwość> > array[smallest]->częstotliwość)> > smallest = left;> > > if> (right size> > && minHeap->tablica[po prawej]->częstotliwość> > array[smallest]->częstotliwość)> > smallest = right;> > > if> (smallest != idx) {> > swapMinHeapNode(&minHeap->tablica[najmniejsza],> > &minHeap->tablica[idx]);> > minHeapify(minHeap, smallest);> > }> }> > // A utility function to check> // if size of heap is 1 or not> int> isSizeOne(> struct> MinHeap* minHeap)> {> > > return> (minHeap->rozmiar == 1);> }> > // A standard function to extract> // minimum value node from heap> struct> MinHeapNode* extractMin(> struct> MinHeap* minHeap)> > {> > > struct> MinHeapNode* temp = minHeap->tablica[0];> > minHeap->tablica[0] = minHeap->tablica[minHeap->rozmiar - 1];> > > --minHeap->rozmiar;> > minHeapify(minHeap, 0);> > > return> temp;> }> > // A utility function to insert> // a new node to Min Heap> void> insertMinHeap(> struct> MinHeap* minHeap,> > struct> MinHeapNode* minHeapNode)> > {> > > ++minHeap->rozmiar;> > int> i = minHeap->rozmiar - 1;> > > while> (i> > && minHeapNode->częstotliwość> > array[(i - 1) / 2]->częstotliwość) {> > > minHeap->tablica[i] = minHeap->tablica[(i - 1) / 2];> > i = (i - 1) / 2;> > }> > > minHeap->tablica[i] = minHeapNode;> }> > // A standard function to build min heap> void> buildMinHeap(> struct> MinHeap* minHeap)> > {> > > int> n = minHeap->rozmiar - 1;> > int> i;> > > for> (i = (n - 1) / 2; i>= 0; --i)> > minHeapify(minHeap, i);> }> > // A utility function to print an array of size n> void> printArr(> int> arr[],> int> n)> {> > int> i;> > for> (i = 0; i printf('%d', arr[i]); printf(' '); } // Utility function to check if this node is leaf int isLeaf(struct MinHeapNode* root) { return !(root->po lewej) && !(root->prawy); } // Tworzy minimalną stertę // o pojemności równej wielkości i wstawia wszystkie znaki // data[] do minimalnej sterty. Początkowo rozmiar // min sterty jest równy pojemności struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap = createMinHeap(size); for (int i = 0; i minHeap->array[i] = newNode(data[i], freq[i]); minHeap->size = size; buildMinHeap(minHeap); return minHeap; } // Główna funkcja budujące drzewo Huffmana struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Krok 1: Utwórz minimalną stertę o pojemności // równej wielkości Początkowo istnieją // tryby równe rozmiarowi struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size); // Wykonuj iterację, gdy rozmiar sterty nie wynosi 1 while (!isSizeOne(minHeap)) { // Krok 2: Wyodrębnij dwa minimalne elementy // freq ze sterty min. left = wyodrębnijMin(minHeap); prawo = wyodrębnijMin(minHeap); // Krok 3: Utwórz nowy wewnętrzny // węzeł z częstotliwością równą // sumie częstotliwości dwóch węzłów. // Utwórz dwa wyodrębnione węzły jako // lewe i prawe dziecko tego nowego węzła. // Dodaj ten węzeł do sterty min. // '$' to specjalna wartość dla węzłów wewnętrznych, a nie // użyte top = newNode('$', lewo->częstotliwość + prawo->częstotliwość); góra->lewo = lewo; góra->prawo = prawo; wstawMinHeap(minHeap, góra); } // Krok 4: Pozostały węzeł jest // węzłem głównym i drzewo jest gotowe. zwróć ekstraktMin(minHeap); } // Drukuje kody Huffmana z korzenia Drzewa Huffmana. // Używa arr[] do przechowywania kodów void printCodes(struct MinHeapNode* root, int arr[], int top) { // Przypisz 0 do lewej krawędzi i powtórz if (root->left) { arr[top] = 0 ; printCodes(root->lewo, tablica, góra + 1); } // Przypisz 1 do prawej krawędzi i powtórz if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // Jeśli jest to węzeł-liść, to // zawiera jeden z // znaków wejściowych, wypisz znak // i jego kod z arr[] if (isLeaf(root)) { printf('%c: ', root->dane); printArr(arr, góra); } } // Główna funkcja budująca // Drzewo Huffmana i drukująca kody poprzez // zbudowane Drzewo Huffmana void HuffmanCodes(char data[], int freq[], int size) { // Konstruuje strukturę drzewa Huffmana struct MinHeapNode* root = buildHuffmanTree(dane, częstotliwość, rozmiar); // Wydrukuj kody Huffmana przy użyciu // drzewa Huffmana zbudowanego powyżej int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Kod sterownika int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f ' }; int częstotliwość [] = { 5, 9, 12, 13, 16, 45 }; int rozmiar = rozmiar(tablica) / rozmiar(tablica[0]); HuffmanCodes(arr, częstotliwość, rozmiar); zwróć 0; }>

C++

// C++ program for Huffman Coding> #include> #include> using> namespace> std;> > // This constant can be avoided by explicitly> // calculating height of Huffman Tree> #define MAX_TREE_HT 100> > // A Huffman tree node> struct> MinHeapNode {> > > // One of the input characters> > char> data;> > > // Frequency of the character> > unsigned freq;> > > // Left and right child of this node> > struct> MinHeapNode *left, *right;> };> > // A Min Heap: Collection of> // min-heap (or Huffman tree) nodes> struct> MinHeap {> > > // Current size of min heap> > unsigned size;> > > // capacity of min heap> > unsigned capacity;> > > // Array of minheap node pointers> > struct> MinHeapNode** array;> };> > // A utility function allocate a new> // min heap node with given character> // and frequency of the character> struct> MinHeapNode* newNode(> char> data, unsigned freq)> {> > struct> MinHeapNode* temp = (> struct> MinHeapNode*)> malloc> (> > sizeof> (> struct> MinHeapNode));> > > temp->lewy = temp->prawy = NULL;> > temp->dane = dane;> > temp->częstotliwość = częstotliwość;> > > return> temp;> }> > // A utility function to create> // a min heap of given capacity> struct> MinHeap* createMinHeap(unsigned capacity)> > {> > > struct> MinHeap* minHeap> > = (> struct> MinHeap*)> malloc> (> sizeof> (> struct> MinHeap));> > > // current size is 0> > minHeap->rozmiar = 0;> > > minHeap->pojemność = pojemność;> > > minHeap->tablica = (> struct> MinHeapNode**)> malloc> (> > minHeap->pojemność *> sizeof> (> struct> MinHeapNode*));> > return> minHeap;> }> > // A utility function to> // swap two min heap nodes> void> swapMinHeapNode(> struct> MinHeapNode** a,> > struct> MinHeapNode** b)> > {> > > struct> MinHeapNode* t = *a;> > *a = *b;> > *b = t;> }> > // The standard minHeapify function.> void> minHeapify(> struct> MinHeap* minHeap,> int> idx)> > {> > > int> smallest = idx;> > int> left = 2 * idx + 1;> > int> right = 2 * idx + 2;> > > if> (left size> > && minHeap->tablica[po lewej]->częstotliwość> > array[smallest]->częstotliwość)> > smallest = left;> > > if> (right size> > && minHeap->tablica[po prawej]->częstotliwość> > array[smallest]->częstotliwość)> > smallest = right;> > > if> (smallest != idx) {> > swapMinHeapNode(&minHeap->tablica[najmniejsza],> > &minHeap->tablica[idx]);> > minHeapify(minHeap, smallest);> > }> }> > // A utility function to check> // if size of heap is 1 or not> int> isSizeOne(> struct> MinHeap* minHeap)> {> > > return> (minHeap->rozmiar == 1);> }> > // A standard function to extract> // minimum value node from heap> struct> MinHeapNode* extractMin(> struct> MinHeap* minHeap)> > {> > > struct> MinHeapNode* temp = minHeap->tablica[0];> > minHeap->tablica[0] = minHeap->tablica[minHeap->rozmiar - 1];> > > --minHeap->rozmiar;> > minHeapify(minHeap, 0);> > > return> temp;> }> > // A utility function to insert> // a new node to Min Heap> void> insertMinHeap(> struct> MinHeap* minHeap,> > struct> MinHeapNode* minHeapNode)> > {> > > ++minHeap->rozmiar;> > int> i = minHeap->rozmiar - 1;> > > while> (i> > && minHeapNode->częstotliwość> > array[(i - 1) / 2]->częstotliwość) {> > > minHeap->tablica[i] = minHeap->tablica[(i - 1) / 2];> > i = (i - 1) / 2;> > }> > > minHeap->tablica[i] = minHeapNode;> }> > // A standard function to build min heap> void> buildMinHeap(> struct> MinHeap* minHeap)> > {> > > int> n = minHeap->rozmiar - 1;> > int> i;> > > for> (i = (n - 1) / 2; i>= 0; --i)> > minHeapify(minHeap, i);> }> > // A utility function to print an array of size n> void> printArr(> int> arr[],> int> n)> {> > int> i;> > for> (i = 0; i cout < < arr[i]; cout < < ' '; } // Utility function to check if this node is leaf int isLeaf(struct MinHeapNode* root) { return !(root->po lewej) && !(root->prawy); } // Tworzy minimalną stertę o pojemności // równej wielkości i wstawia wszystkie znaki // data[] do minimalnej sterty. Początkowo rozmiar // min sterty jest równy pojemności struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap = createMinHeap(size); for (int i = 0; i minHeap->array[i] = newNode(data[i], freq[i]); minHeap->size = size; buildMinHeap(minHeap); return minHeap; } // Główna funkcja budujące drzewo Huffmana struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Krok 1: Utwórz minimalną stertę o pojemności // równej wielkości Początkowo istnieją // tryby równe rozmiarowi struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size); // Wykonuj iterację, gdy rozmiar sterty nie wynosi 1 while (!isSizeOne(minHeap)) { // Krok 2: Wyodrębnij dwa minimalne elementy // freq ze sterty min. left = wyodrębnijMin(minHeap); prawo = wyodrębnijMin(minHeap); // Krok 3: Utwórz nowy wewnętrzny // węzeł z częstotliwością równą // sumie częstotliwości dwóch węzłów. // Utwórz dwa wyodrębnione węzły jako // lewe i prawe dziecko tego nowego węzła. // Dodaj ten węzeł do sterty min. // '$' to specjalna wartość dla węzłów wewnętrznych, a nie // użyte top = newNode('$', lewo->częstotliwość + prawo->częstotliwość); góra->lewo = lewo; góra->prawo = prawo; wstawMinHeap(minHeap, góra); } // Krok 4: Pozostały węzeł jest // węzłem głównym i drzewo jest gotowe. zwróć ekstraktMin(minHeap); } // Drukuje kody Huffmana z korzenia Drzewa Huffmana. // Używa arr[] do przechowywania kodów void printCodes(struct MinHeapNode* root, int arr[], int top) { // Przypisz 0 do lewej krawędzi i powtórz if (root->left) { arr[top] = 0 ; printCodes(root->lewo, tablica, góra + 1); } // Przypisz 1 do prawej krawędzi i powtórz if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // Jeśli jest to węzeł-liść, to // zawiera jeden ze // znaków wejściowych, wypisz znak // i jego kod z arr[] if (isLeaf(root)) { cout ': '; printArr(arr, góra); } } // Główna funkcja budująca // Drzewo Huffmana i drukująca kody poprzez // zbudowane Drzewo Huffmana void HuffmanCodes(char data[], int freq[], int size) { // Konstruuje strukturę drzewa Huffmana struct MinHeapNode* root = buildHuffmanTree(dane, częstotliwość, rozmiar); // Wydrukuj kody Huffmana przy użyciu // drzewa Huffmana zbudowanego powyżej int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Kod sterownika int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f ' }; int częstotliwość [] = { 5, 9, 12, 13, 16, 45 }; int rozmiar = rozmiar(tablica) / rozmiar(tablica[0]); HuffmanCodes(arr, częstotliwość, rozmiar); zwróć 0; }>

C++

// C++(STL) program for Huffman Coding with STL> #include> using> namespace> std;> > // A Huffman tree node> struct> MinHeapNode {> > > // One of the input characters> > char> data;> > > // Frequency of the character> > unsigned freq;> > > // Left and right child> > MinHeapNode *left, *right;> > > MinHeapNode(> char> data, unsigned freq)> > > {> > > left = right = NULL;> > this> ->dane = dane;> > this> ->częstotliwość = częstotliwość;> > }> };> > // For comparison of> // two heap nodes (needed in min heap)> struct> compare {> > > bool> operator()(MinHeapNode* l, MinHeapNode* r)> > > {> > return> (l->częstotliwość> r->częstotliwość);> > }> };> > // Prints huffman codes from> // the root of Huffman Tree.> void> printCodes(> struct> MinHeapNode* root, string str)> {> > > if> (!root)> > return> ;> > > if> (root->dane !=> '$'> )> > cout ': ' < < str < < ' '; printCodes(root->lewo, str + '0'); printCodes(root->right, str + '1'); } // Główna funkcja budująca drzewo Huffmana i // drukująca kody przechodzące przez zbudowane drzewo Huffmana void HuffmanCodes(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Utwórz minimalną stertę i wstaw wszystkie znaki data[] priorytet_kolejka porównaj> minHeap; for (int i = 0; i minHeap.push(new MinHeapNode(data[i], freq[i])); // Iteruj, dopóki rozmiar sterty nie osiągnie 1 while (minHeap.size() != 1 ) { // Wyodrębnij dwa minimalne // częste elementy ze sterty min. left = minHeap.top(); minHeap.pop();right = minHeap.top(); minHeap.pop(); // Utwórz nowy węzeł wewnętrzny z // częstotliwością równą sumie // częstotliwości dwóch węzłów. Uczyń // dwa wyodrębnione węzły jako lewe i prawe dziecko // tego nowego węzła. Dodaj ten węzeł // do minimalnej sterty '$' specjalna wartość // dla węzłów wewnętrznych, nieużywana top = new MinHeapNode('$', lewy->częstotliwość + prawy->częstotliwość); (top); } // Wydrukuj kody Huffmana przy użyciu // drzewa Huffmana zbudowanego powyżej printCodes(minHeap.top(), ''); } // Kod sterownika int main() { char arr[] = { ' a', 'b', 'c', 'd', 'e', 'f' }; int freq[] = { 5, 9, 12, 13, 16 , 45 }; int rozmiar = rozmiar(tablica) / rozmiar(tablica[0]); zwróć 0; } // Ten kod został stworzony przez Adityę Goel>

Jawa

import> java.util.Comparator;> import> java.util.PriorityQueue;> import> java.util.Scanner;> > class> Huffman {> > > // recursive function to print the> > // huffman-code through the tree traversal.> > // Here s is the huffman - code generated.> > public> static> void> printCode(HuffmanNode root, String s)> > {> > > // base case; if the left and right are null> > // then its a leaf node and we print> > // the code s generated by traversing the tree.> > if> (root.left ==> null> && root.right ==> null> > && Character.isLetter(root.c)) {> > > // c is the character in the node> > System.out.println(root.c +> ':'> + s);> > > return> ;> > }> > > // if we go to left then add '0' to the code.> > // if we go to the right add'1' to the code.> > > // recursive calls for left and> > // right sub-tree of the generated tree.> > printCode(root.left, s +> '0'> );> > printCode(root.right, s +> '1'> );> > }> > > // main function> > public> static> void> main(String[] args)> > {> > > Scanner s => new> Scanner(System.in);> > > // number of characters.> > int> n => 6> ;> > char> [] charArray = {> 'a'> ,> 'b'> ,> 'c'> ,> 'd'> ,> 'e'> ,> 'f'> };> > int> [] charfreq = {> 5> ,> 9> ,> 12> ,> 13> ,> 16> ,> 45> };> > > // creating a priority queue q.> > // makes a min-priority queue(min-heap).> > PriorityQueue q> > => new> PriorityQueue(> > n,> new> MyComparator());> > > for> (> int> i => 0> ; i // creating a Huffman node object // and add it to the priority queue. HuffmanNode hn = new HuffmanNode(); hn.c = charArray[i]; hn.data = charfreq[i]; hn.left = null; hn.right = null; // add functions adds // the huffman node to the queue. q.add(hn); } // create a root node HuffmanNode root = null; // Here we will extract the two minimum value // from the heap each time until // its size reduces to 1, extract until // all the nodes are extracted. while (q.size()>1) { // ekstrakt z pierwszej minuty. Węzeł Huffmana x = q.peek(); q.ankieta(); // ekstrakt z drugiej minuty. Węzeł Huffmana y = q.peek(); q.ankieta(); // nowy węzeł f równy HuffmanNode f = new HuffmanNode(); // do sumy częstotliwości dwóch węzłów // przypisując wartości do węzła f. f.dane = x.dane + y.dane; f.c = '-'; // pierwszy wyodrębniony węzeł jako lewy element podrzędny. f.lewy = x; // drugi wyodrębniony węzeł jako prawy element podrzędny. f.prawo = y; // oznaczenie węzła f jako węzła głównego. pierwiastek = f; // dodaj ten węzeł do kolejki priorytetowej. q.add(f); } // wydrukuj kody, przechodząc przez drzewo printCode(root, ''); } } // klasa węzła jest podstawową strukturą // każdego węzła występującego w drzewie Huffmana. klasa HuffmanNode { int dane; znak c; HuffmanWęzeł został pozostawiony; HuffmanWęzeł po prawej; } // klasa komparatora pomaga porównać węzeł // na podstawie jednego z jego atrybutów. // Tutaj będziemy porównywani // na podstawie wartości danych węzłów. class MyComparator implements Comparator {public int Compare(HuffmanNode x, HuffmanNode y) { return x.data - y.data; } } // Autorem tego kodu jest Kunwar Desh Deepak Singh>

Python3

# A Huffman Tree Node> import> heapq> > > class> node:> > def> __init__(> self> , freq, symbol, left> => None> , right> => None> ):> > # frequency of symbol> > self> .freq> => freq> > > # symbol name (character)> > self> .symbol> => symbol> > > # node left of current node> > self> .left> => left> > > # node right of current node> > self> .right> => right> > > # tree direction (0/1)> > self> .huff> => ''> > > def> __lt__(> self> , nxt):> > return> self> .freq # utility function to print huffman # codes for all symbols in the newly # created Huffman tree def printNodes(node, val=''): # huffman code for current node newVal = val + str(node.huff) # if node is not an edge node # then traverse inside it if(node.left): printNodes(node.left, newVal) if(node.right): printNodes(node.right, newVal) # if node is edge node then # display its huffman code if(not node.left and not node.right): print(f'{node.symbol} ->{newVal}') # znaków dla znaków drzewa Huffmana = ['a', 'b', 'c', 'd', 'e', 'f'] # częstotliwość znaków freq = [5, 9, 12, 13, 16, 45] # lista zawierająca nieużywane węzły nodes = [] # konwersja znaków i częstotliwości # na węzły drzewa Huffmana dla x w zakresie(len(chars)): heapq .heappush(nodes, node(freq[x], chars[x])) while len(nodes)> 1: # sortuj wszystkie węzły w kolejności rosnącej # na podstawie ich częstotliwości left = heapq.heappop(nodes) Right = heapq .heappop(nodes) # przypisz wartość kierunkową do tych węzłów left.huff = 0right.huff = 1 # połącz 2 najmniejsze węzły, aby utworzyć # nowy węzeł jako ich rodzic newNode = node(left.freq+right.freq, left. symbol+right.symbol, lewy, prawy) heapq.heappush(nodes, newNode) # Drzewo Huffmana jest gotowe! printNodes(nodes[0])>

JavaScript

> > // node class is the basic structure> // of each node present in the Huffman - tree.> class HuffmanNode> {> > constructor()> > {> > this> .data = 0;> > this> .c => ''> ;> > this> .left => this> .right => null> ;> > }> }> > // recursive function to print the> > // huffman-code through the tree traversal.> > // Here s is the huffman - code generated.> > function> printCode(root,s)> > {> > // base case; if the left and right are null> > // then its a leaf node and we print> > // the code s generated by traversing the tree.> > if> (root.left ==> null> > && root.right ==> null> > && (root.c).toLowerCase() != (root.c).toUpperCase()) {> > > // c is the character in the node> > document.write(root.c +> ':'> + s+> ' '> );> > > return> ;> > }> > > // if we go to left then add '0' to the code.> > // if we go to the right add'1' to the code.> > > // recursive calls for left and> > // right sub-tree of the generated tree.> > printCode(root.left, s +> '0'> );> > printCode(root.right, s +> '1'> );> > }> > > // main function> // number of characters.> > let n = 6;> > let charArray = [> 'a'> ,> 'b'> ,> 'c'> ,> 'd'> ,> 'e'> ,> 'f'> ];> > let charfreq = [ 5, 9, 12, 13, 16, 45 ];> > > // creating a priority queue q.> > // makes a min-priority queue(min-heap).> > let q = [];> > > for> (let i = 0; i // creating a Huffman node object // and add it to the priority queue. let hn = new HuffmanNode(); hn.c = charArray[i]; hn.data = charfreq[i]; hn.left = null; hn.right = null; // add functions adds // the huffman node to the queue. q.push(hn); } // create a root node let root = null; q.sort(function(a,b){return a.data-b.data;}); // Here we will extract the two minimum value // from the heap each time until // its size reduces to 1, extract until // all the nodes are extracted. while (q.length>1) { // ekstrakt z pierwszej minuty. niech x = q[0]; q.shift(); // ekstrakt z drugiej minuty. niech y = q[0]; q.shift(); // nowy węzeł f równy let f = new HuffmanNode(); // do sumy częstotliwości dwóch węzłów // przypisując wartości do węzła f. f.dane = x.dane + y.dane; f.c = '-'; // pierwszy wyodrębniony węzeł jako lewy element podrzędny. f.lewy = x; // drugi wyodrębniony węzeł jako prawy element podrzędny. f.prawo = y; // oznaczenie węzła f jako węzła głównego. pierwiastek = f; // dodaj ten węzeł do kolejki priorytetowej. q.push(f); q.sort(funkcja(a,b){zwróć a.data-b.data;}); } // wydrukuj kody, przechodząc przez drzewo printCode(root, ''); // Ten kod został napisany przez avanitrachhadiya2155>

C#

// C# program for the above approach> > using> System;> using> System.Collections.Generic;> > // A Huffman tree node> public> class> MinHeapNode> {> > // One of the input characters> > public> char> data;> > > // Frequency of the character> > public> uint> freq;> > > // Left and right child> > public> MinHeapNode left, right;> > > public> MinHeapNode(> char> data,> uint> freq)> > {> > left = right => null> ;> > this> .data = data;> > this> .freq = freq;> > }> }> > // For comparison of two heap nodes (needed in min heap)> public> class> CompareMinHeapNode : IComparer> {> > public> int> Compare(MinHeapNode x, MinHeapNode y)> > {> > return> x.freq.CompareTo(y.freq);> > }> }> > class> Program> {> > // Prints huffman codes from the root of Huffman Tree.> > static> void> printCodes(MinHeapNode root,> string> str)> > {> > if> (root ==> null> )> > return> ;> > > if> (root.data !=> '$'> )> > Console.WriteLine(root.data +> ': '> + str);> > > printCodes(root.left, str +> '0'> );> > printCodes(root.right, str +> '1'> );> > }> > > // The main function that builds a Huffman Tree and> > // print codes by traversing the built Huffman Tree> > static> void> HuffmanCodes(> char> [] data,> uint> [] freq,> int> size)> > {> > MinHeapNode left, right, top;> > > // Create a min heap & inserts all characters of data[]> > var> minHeap => new> SortedSet(> new> CompareMinHeapNode());> > > for> (> int> i = 0; i minHeap.Add(new MinHeapNode(data[i], freq[i])); // Iterate while size of heap doesn't become 1 while (minHeap.Count != 1) { // Extract the two minimum freq items from min heap left = minHeap.Min; minHeap.Remove(left); right = minHeap.Min; minHeap.Remove(right); // Create a new internal node with frequency equal to the sum of the two nodes frequencies. // Make the two extracted node as left and right children of this new node. // Add this node to the min heap '$' is a special value for internal nodes, not used. top = new MinHeapNode('$', left.freq + right.freq); top.left = left; top.right = right; minHeap.Add(top); } // Print Huffman codes using the Huffman tree built above printCodes(minHeap.Min, ''); } // Driver Code static void Main() { char[] arr = { 'a', 'b', 'c', 'd', 'e', 'f' }; uint[] freq = { 5, 9, 12, 13, 16, 45 }; int size = arr.Length; HuffmanCodes(arr, freq, size); } } // This code is contributed by sdeadityasharma>

Wyjście

f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 

Złożoność czasowa: O(nlogn) gdzie n jest liczbą unikalnych znaków. Jeśli jest n węzłów, funkcja ExtractMin() jest wywoływana 2*(n – 1) razy. ExtractMin() zajmuje czas O(logn) podczas wywoływania minHeapify(). Zatem ogólna złożoność wynosi O(nlogn).
Jeśli tablica wejściowa jest posortowana, istnieje algorytm czasu liniowego. Już niedługo porozmawiamy o tym w kolejnym poście.

Złożoność przestrzenna :- O(N)

Zastosowania kodowania Huffmana:

1. Służą do przesyłania faksów i tekstu.
2. Są używane w konwencjonalnych formatach kompresji, takich jak PKZIP, GZIP itp.
3. Kodeki multimedialne, takie jak JPEG, PNG i MP3, używają kodowania Huffmana (a dokładniej kodów prefiksowych).

Jest to przydatne w przypadkach, gdy występuje ciąg często występujących znaków.

Odniesienie:
http://en.wikipedia.org/wiki/Huffman_coding
Ten artykuł został opracowany przez Aashish Barnwal i sprawdzony przez zespół techcodeview.com.