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
- Zbuduj drzewo Huffmana na podstawie wprowadzonych znaków.
- 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.
- 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)
- Wyodrębnij dwa węzły z minimalną częstotliwością ze sterty min.
- 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.
- 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
jak zamienić string na int
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++
Linux $home
// 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> |
cpp równa się
>
>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:
- Służą do przesyłania faksów i tekstu.
- Są używane w konwencjonalnych formatach kompresji, takich jak PKZIP, GZIP itp.
- 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.