Кодування Хаффмана — це алгоритм стиснення даних без втрат. Ідея полягає в тому, щоб призначити коди змінної довжини вхідним символам, довжина призначених кодів базується на частотах відповідних символів.
Коди змінної довжини, призначені вхідним символам Префіксні коди означає, що коди (послідовності бітів) призначаються таким чином, що код, призначений одному символу, не є префіксом коду, призначеного будь-якому іншому символу. Таким чином кодування Хаффмана забезпечує відсутність неоднозначності під час декодування згенерованого бітового потоку.
Розберемо префіксні коди на контрприкладі. Нехай є чотири символи a, b, c і d, а їхні відповідні коди змінної довжини дорівнюють 00, 01, 0 і 1. Це кодування призводить до неоднозначності, оскільки код, призначений c, є префіксом кодів, призначених a і b. Якщо стислий бітовий потік дорівнює 0001, розпакований вихід може бути cccd або ccb або acd або ab.
Побачити це для програм кодування Хаффмана.
Кодування Хаффмана складається з двох основних частин
- Побудуйте дерево Хаффмана з введених символів.
- Перейдіть по дереву Хаффмана та призначте коди персонажам.
Алгоритм:
Називається метод, який використовується для побудови оптимального префіксного коду Кодування Хаффмана .
Цей алгоритм будує дерево знизу вгору. Ми можемо позначити це дерево через Т
Нехай |c| бути кількістю листків
|c| -1 – кількість операцій, необхідних для об’єднання вузлів. Q — пріоритетна черга, яку можна використовувати під час побудови бінарної купи.
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) }> Етапи створення дерева Хаффмана
Вхідні дані — це масив унікальних символів разом із частотою їх появи, а вихідні дані — дерево Хаффмана.
- Створіть кінцевий вузол для кожного унікального символу та побудуйте мінімальну купу всіх кінцевих вузлів (Мінальна купа використовується як пріоритетна черга. Значення поля частоти використовується для порівняння двох вузлів у мінімальній купі. Спочатку найменш частий символ знаходиться в корінь)
- Витягніть два вузли з мінімальною частотою з мінімальної купи.
- Створіть новий внутрішній вузол із частотою, що дорівнює сумі частот двох вузлів. Зробіть перший витягнутий вузол лівим дочірнім вузлом, а інший витягнутий вузол – правим дочірнім. Додайте цей вузол до мінімальної купи.
- Повторюйте кроки №2 і №3, доки купа не міститиме лише один вузол. Вузол, що залишився, є кореневим вузлом, і дерево завершене.
Розберемося з алгоритмом на прикладі:
character Frequency a 5 b 9 c 12 d 13 e 16 f 45>
Крок 1. Побудуйте мініатюрну купу, яка містить 6 вузлів, де кожен вузол представляє корінь дерева з одним вузлом.
Крок 2 Витягніть два вузли мінімальної частоти з мінімальної купи. Додайте новий внутрішній вузол із частотою 5 + 9 = 14.
Ілюстрація кроку 2
Тепер мінімальна купа містить 5 вузлів, де 4 вузли є коренями дерев з одним елементом кожен, а один вузол купи є коренем дерева з 3 елементами
character Frequency c 12 d 13 Internal Node 14 e 16 f 45>
крок 3: Витягніть два вузли мінімальної частоти з купи. Додайте новий внутрішній вузол з частотою 12 + 13 = 25
Ілюстрація кроку 3
Тепер мінімальна купа містить 4 вузли, де 2 вузли є коренями дерев з одним елементом кожен, а два вузли купи є коренем дерева з більш ніж одним вузлом
character Frequency Internal Node 14 e 16 Internal Node 25 f 45>
крок 4: Витягніть два вузли мінімальної частоти. Додайте новий внутрішній вузол з частотою 14 + 16 = 30
Ілюстрація кроку 4
Тепер min heap містить 3 вузли.
character Frequency Internal Node 25 Internal Node 30 f 45>
крок 5: Витягніть два вузли мінімальної частоти. Додайте новий внутрішній вузол з частотою 25 + 30 = 55
Ілюстрація кроку 5
Тепер min heap містить 2 вузли.
character Frequency f 45 Internal Node 55>
Крок 6: Витягніть два вузли мінімальної частоти. Додайте новий внутрішній вузол з частотою 45 + 55 = 100
мураха проти maven
Ілюстрація кроку 6
Тепер min heap містить лише один вузол.
character Frequency Internal Node 100>
Оскільки купа містить лише один вузол, алгоритм зупиняється на цьому.
Кроки для друку кодів із Huffman Tree:
Пройдіть сформоване дерево, починаючи з кореня. Підтримувати допоміжний масив. Переходячи до лівого дочірнього елемента, запишіть 0 в масив. Переходячи до правого дочірнього елемента, запишіть 1 у масив. Роздрукувати масив, коли зустрічається листовий вузол.
Кроки для друку коду з HuffmanTree
Коди такі:
character code-word f 0 c 100 d 101 a 1100 b 1101 e 111>Рекомендована практика Кодування Хаффмана Спробуйте!
Нижче наведено реалізацію вищезазначеного підходу:
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->зліва = temp->right = NULL;> >temp->дані = дані;> >temp->freq = частота;> > >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->розмір = 0;> > >minHeap->емкость = місткість;> > >minHeap->масив = (>struct> MinHeapNode**)>malloc>(> >minHeap->місткість *>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->array[left]->freq> >array[smallest]->частота)> >smallest = left;> > >if> (right size> >&& minHeap->масив [справа]->freq> >array[smallest]->частота)> >smallest = right;> > >if> (smallest != idx) {> >swapMinHeapNode(&minHeap->масив [найменший],> >&minHeap->масив[idx]);> >minHeapify(minHeap, smallest);> >}> }> > // A utility function to check> // if size of heap is 1 or not> int> isSizeOne(>struct> MinHeap* minHeap)> {> > >return> (minHeap->розмір == 1);> }> > // A standard function to extract> // minimum value node from heap> struct> MinHeapNode* extractMin(>struct> MinHeap* minHeap)> > {> > >struct> MinHeapNode* temp = minHeap->масив[0];> >minHeap->array[0] = minHeap->array[minHeap->size - 1];> > >--minHeap->розмір;> >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->розмір;> >int> i = minHeap->розмір - 1;> > >while> (i> >&& minHeapNode->частота>>> > >minHeap->масив[i] = minHeap->масив[(i - 1) / 2];> >i = (i - 1) / 2;> >}> > >minHeap->масив[i] = minHeapNode;> }> > // A standard function to build min heap> void> buildMinHeap(>struct> MinHeap* minHeap)> > {> > >int> n = minHeap->розмір - 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->ліворуч) && !(корінь->праворуч); } // Створює мінімальну купу ємності, // що дорівнює розміру, і вставляє всі символи // data[] у мінімальну купу. Початковий розмір // мінімальної купи дорівнює місткості 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; } // Основна функція який будує дерево Хаффмана struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Крок 1: Створіть мінімальну купу ємності // дорівнює розміру .Спочатку існують режими, що дорівнюють розміру struct MinHeap(minHeap)(data,freq,size); Крок 2: Витягніть два мінімальних // частоти з купи зліва = extractMin(minHeap); // Крок 3: Створіть новий внутрішній вузол із // сумою частоти двох вузлів // Зробити два витягнутих вузла // лівим і правим дочірніми вузлами // Додати цей вузол до мінімальної купи // '$' є спеціальним значенням для внутрішніх вузлів. used top = newNode('$', left->freq + right->freq); top->left = ліворуч; top->right = праворуч; insertMinHeap(minHeap, top); } // Крок 4: Вузол, що залишився, є // кореневим вузлом, і дерево готове. повертає extractMin(minHeap); } // Друкує коди Хаффмана з кореня Huffman Tree. // Він використовує arr[] для зберігання кодів void printCodes(struct MinHeapNode* root, int arr[], int top) { // Призначити 0 лівому краю та повторювати if (root->left) { arr[top] = 0 ; printCodes(root->left, arr, top + 1); } // Призначити 1 правому краю та повторити if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // Якщо це кінцевий вузол, то // він містить один із вхідних // символів, вивести символ // і його код із arr[] if (isLeaf(root)) { printf('%c: ', корінь->дані); printArr(arr, top); } } // Основна функція, яка створює // Дерево Хаффмана та друкує коди шляхом обходу // побудованого дерева Хаффмана void HuffmanCodes(char data[], int freq[], int size) { // Побудова дерева Хаффмана struct MinHeapNode* root = buildHuffmanTree(дані, частота, розмір); // Друк кодів Хаффмана за допомогою // дерева Хаффмана, побудованого над int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Код драйвера int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f '}; int freq[] = { 5, 9, 12, 13, 16, 45 }; int size = sizeof(arr) / sizeof(arr[0]); HuffmanCodes(arr, freq, size); повернути 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->зліва = temp->right = NULL;> >temp->дані = дані;> >temp->freq = частота;> > >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->розмір = 0;> > >minHeap->емкость = місткість;> > >minHeap->масив = (>struct> MinHeapNode**)>malloc>(> >minHeap->місткість *>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->array[left]->freq> >array[smallest]->частота)> >smallest = left;> > >if> (right size> >&& minHeap->масив [справа]->freq> >array[smallest]->частота)> >smallest = right;> > >if> (smallest != idx) {> >swapMinHeapNode(&minHeap->масив [найменший],> >&minHeap->масив[idx]);> >minHeapify(minHeap, smallest);> >}> }> > // A utility function to check> // if size of heap is 1 or not> int> isSizeOne(>struct> MinHeap* minHeap)> {> > >return> (minHeap->розмір == 1);> }> > // A standard function to extract> // minimum value node from heap> struct> MinHeapNode* extractMin(>struct> MinHeap* minHeap)> > {> > >struct> MinHeapNode* temp = minHeap->масив[0];> >minHeap->array[0] = minHeap->array[minHeap->size - 1];> > >--minHeap->розмір;> >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->розмір;> >int> i = minHeap->розмір - 1;> > >while> (i> >&& minHeapNode->частота>> >array[(i - 1) / 2]->freq) {> > >minHeap->масив[i] = minHeap->масив[(i - 1) / 2];> >i = (i - 1) / 2;> >}> > >minHeap->масив[i] = minHeapNode;> }> > // A standard function to build min heap> void> buildMinHeap(>struct> MinHeap* minHeap)> > {> > >int> n = minHeap->розмір - 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->ліворуч) && !(корінь->праворуч); } // Створює мінімальну купу ємності, // що дорівнює розміру, і вставляє всі символи // data[] у мінімальну купу. Початковий розмір // мінімальної купи дорівнює місткості 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; } // Основна функція який будує дерево Хаффмана struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Крок 1: Створіть мінімальну купу ємності // дорівнює розміру .Спочатку існують режими, що дорівнюють розміру struct MinHeap(minHeap)(data,freq,size); Крок 2: Витягніть два мінімальних // частоти з купи зліва = extractMin(minHeap); // Крок 3: Створіть новий внутрішній вузол із // сумою частоти двох вузлів // Зробіть два витягнуті вузли // лівим і правим дочірніми вузлами // Додайте цей вузол до мінімальної купи // '$' є спеціальним значенням для внутрішніх вузлів. used top = newNode('$', left->freq + right->freq); top->left = ліворуч; top->right = праворуч; insertMinHeap(minHeap, top); } // Крок 4: Вузол, що залишився, є // кореневим вузлом, і дерево готове. повертає extractMin(minHeap); } // Друкує коди Хаффмана з кореня Huffman Tree. // Він використовує arr[] для зберігання кодів void printCodes(struct MinHeapNode* root, int arr[], int top) { // Призначити 0 лівому краю та повторювати if (root->left) { arr[top] = 0 ; printCodes(root->left, arr, top + 1); } // Призначити 1 правому краю та повторити if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // Якщо це кінцевий вузол, то // він містить один із // вхідних символів, вивести символ // і його код з arr[] if (isLeaf(root)) { cout ': '; printArr(arr, top); } } // Основна функція, яка створює // Дерево Хаффмана та друкує коди шляхом обходу // побудованого дерева Хаффмана void HuffmanCodes(char data[], int freq[], int size) { // Побудова дерева Хаффмана struct MinHeapNode* root = buildHuffmanTree(дані, частота, розмір); // Друк кодів Хаффмана за допомогою // дерева Хаффмана, побудованого над int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Код драйвера int main() { char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f '}; int freq[] = { 5, 9, 12, 13, 16, 45 }; int size = sizeof(arr) / sizeof(arr[0]); HuffmanCodes(arr, freq, size); повернути 0; }> |
дійсні ідентифікатори java
>
>
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>->дані = дані;> >this>->freq = частота;> >}> };> > // For comparison of> // two heap nodes (needed in min heap)> struct> compare {> > >bool> operator()(MinHeapNode* l, MinHeapNode* r)> > >{> >return> (l->freq> r->freq);> >}> };> > // Prints huffman codes from> // the root of Huffman Tree.> void> printCodes(>struct> MinHeapNode* root, string str)> {> > >if> (!root)> >return>;> > >if> (root->дані !=>'$'>)> >cout ': ' << str << '
'; printCodes(root->ліворуч, str + '0'); printCodes(root->right, str + '1'); } // Основна функція, яка будує дерево Хаффмана та // друкує коди шляхом обходу побудованого дерева Хаффмана void HuffmanCodes(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Створення мінімальної купи та вставлення всіх символів data[] priority_queue compare> minHeap; for (int i = 0; i minHeap.push(new MinHeapNode(data[i], freq[i])); // Ітерація, поки розмір купи не стане 1 while (minHeap.size() != 1 ) { // Витягти два мінімальних елемента з купи зліва = minHeap.pop(); справа = minHeap.pop(); // Створити новий внутрішній вузол з // частотою, що дорівнює сумі частот двох вузлів // Додайте цей вузол до мінімальної купи '$' спеціальне значення // для внутрішніх вузлів, не використовується top = new MinHeapNode('$', left->freq + right->freq); top->left = right; minHeap.push (top); } // Друкувати коди Хаффмана за допомогою // дерева Хаффмана, побудованого вище printCodes(minHeap.top(), ''); // Код драйвера int main() { char arr[] = { ' a', 'b', 'c', 'd', 'e', 'f' }; int freq[] = { 5, 9, 12, 13, 16 , 45 }; int size = sizeof(arr) / sizeof(arr[0]); повернути 0; } // Цей код створено Aditya Goel> |
>
>
Java
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) { // перший хв витяг. HuffmanNode x = q.peek(); q.poll(); // другий хв витяг. HuffmanNode y = q.peek(); q.poll(); // новий вузол f, який дорівнює HuffmanNode f = new HuffmanNode(); // до суми частот двох вузлів // присвоєння значень вузлу f. f.data = x.data + y.data; f.c = '-'; // перший витягнутий вузол як лівий дочірній елемент. f.left = x; // другий витягнутий вузол як правий дочірній елемент. f.праворуч = y; // позначення вузла f як кореневого вузла. корінь = f; // додати цей вузол до пріоритетної черги. q.add(f); } // друкуємо коди, обходячи дерево printCode(root, ''); } } // клас вузла є базовою структурою // кожного вузла в дереві Хаффмана. class HuffmanNode { int data; char c; HuffmanNode ліворуч; HuffmanNode справа; } // клас компаратора допомагає порівняти вузол // на основі одного з його атрибутів. // Тут ми будемо порівнювати // на основі значень даних вузлів. class MyComparator implements Comparator { public int compare(HuffmanNode x, HuffmanNode y) { return x.data - y.data; } } // Цей код створено 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}') # символи для дерева Хаффмана chars = ['a', 'b', 'c', 'd', 'e', 'f'] # частота символів freq = [5, 9, 12, 13, 16, 45] # список, що містить невикористані вузли nodes = [] # перетворення символів і частот # у вузли дерева Хаффмана для x в діапазоні (len(chars)): heapq .heappush(nodes, node(freq[x], chars[x])) while len(nodes)> 1: # відсортувати всі вузли в порядку зростання # на основі їх частоти left = heapq.heappop(nodes) right = heapq .heappop(nodes) # призначити значення напряму цим вузлам left.huff = 0 right.huff = 1 # об'єднати 2 найменші вузли, щоб створити # новий вузол як їхній батьків newNode = node(left.freq+right.freq, left. символ+правий.символ, ліворуч, праворуч) heapq.heappush(nodes, newNode) # Дерево Хаффмана готове! 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) { // перший хв витяг. нехай x = q[0]; q.shift(); // другий хв витяг. нехай y = q[0]; q.shift(); // новий вузол f, який дорівнює let f = new HuffmanNode(); // до суми частот двох вузлів // присвоєння значень вузлу f. f.data = x.data + y.data; f.c = '-'; // перший витягнутий вузол як лівий дочірній елемент. f.left = x; // другий витягнутий вузол як правий дочірній елемент. f.праворуч = y; // позначення вузла f як кореневого вузла. корінь = f; // додати цей вузол до пріоритетної черги. q.push(f); q.sort(function(a,b){return a.data-b.data;}); } // друкуємо коди, обходячи дерево printCode(root, ''); // Цей код створено avanitrachhadiya2155> |
>
>
C#
введення рядка в java
// 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> |
>
>Вихід
f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111>
Часова складність: O(nlogn), де n – кількість унікальних символів. Якщо є n вузлів, extractMin() викликається 2*(n – 1) разів. extractMin() займає O(logn) часу, оскільки викликає minHeapify(). Отже, загальна складність дорівнює O(nlogn).
Якщо вхідний масив відсортований, існує алгоритм лінійного часу. Незабаром ми обговоримо це в нашій наступній публікації.
Складність простору: - O(N)
Застосування кодування Хаффмана:
- Вони використовуються для передачі факсів і тексту.
- Вони використовуються у звичайних форматах стиснення, таких як PKZIP, GZIP тощо.
- Мультимедійні кодеки, такі як JPEG, PNG і MP3, використовують кодування Хаффмана (якщо точніше, коди префіксів).
Це корисно у випадках, коли є ряд символів, які часто зустрічаються.
Посилання:
http://en.wikipedia.org/wiki/Huffman_coding
Цю статтю зібрано Аашішем Барнуалом і перевірено командою techcodeview.com.