Данните могат да бъдат компресирани с помощта на техниката на кодиране на Huffman, за да станат по-малки, без да се губи информация. След Дейвид Хъфман, кой го е създал в началото? Данните, които съдържат често повтарящи се знаци, обикновено се компресират с помощта на кодиране на Huffman.

Добре известен алгоритъм на Greedy е кодирането на Huffman. Размерът на кода, разпределен за символ, зависи от честотата на знака, поради което се нарича алчен алгоритъм. Променливият код с къса дължина се присвоява на знака с най-висока честота и обратното за знаците с по-ниска честота. Той използва кодиране с променлива дължина, което означава, че дава на всеки знак в предоставения поток от данни различен код с променлива дължина.

Правило за префикс

По същество това правило гласи, че кодът, който е присвоен на символ, не трябва да бъде префикс на друг код. Ако това правило бъде нарушено, могат да се появят различни неясноти при декодирането на създаденото дърво на Хъфман.

Нека разгледаме илюстрация на това правило, за да го разберем по-добре: За всеки знак е предоставен код, като например:

 a - 0 b - 1 c - 01 

Ако приемем, че произведеният битов поток е 001, кодът може да бъде изразен, както следва, когато се декодира:

gimp как да премахнете отметката

 0 0 1 = aab 0 01 = ac 

Какво представлява процесът на кодиране на Huffman?

Кодът на Хъфман се получава за всеки отделен знак основно в две стъпки:

• Първо създайте дърво на Хъфман, като използвате само уникалните знаци в предоставения поток от данни.
• Второ, трябва да продължим през конструираното дърво на Хъфман, да присвоим кодове на знаците и след това да използваме тези кодове, за да декодираме предоставения текст.

Стъпки, които трябва да предприемете в кодирането на Huffman

Стъпките, използвани за конструиране на дървото на Хъфман с помощта на предоставените знаци

 Input: string str = 'abbcdbccdaabbeeebeab' 

Ако в този случай за компресиране на данни се използва кодиране на Huffman, следната информация трябва да бъде определена за декодиране:

направете докато java

• За всеки знак, кодът на Хъфман
• Дължина на кодирано по Huffman съобщение (в битове), средна дължина на кода
• Използвайки формулите, описани по-долу, се откриват последните две от тях.

Как може да се изгради дърво на Хъфман от входни знаци?

Първо трябва да се определи честотата на всеки знак в предоставения низ.

1. Подредете знаците по честота, възходящо. Те се съхраняват в опашка с приоритет Q/min-heap.
2. За всеки отделен знак и неговата честота в потока от данни създайте листов възел.
3. Премахнете двата възела с двете най-ниски честоти от възлите и новият корен на дървото се създава с помощта на сумата от тези честоти.
   • Направете първия извлечен възел свое ляво дете, а вторият извлечен възел свое дясно дете, докато извличате възлите с най-ниска честота от min-heap.
   • Към min-heap добавете този възел.
   • Тъй като лявата страна на корена винаги трябва да съдържа минималната честота.
4. Повторете стъпки 3 и 4, докато остане само един възел в купчината или всички символи са представени от възли в дървото. Дървото е завършено, когато остане само основният възел.

Примери за кодиране на Huffman

Нека използваме илюстрация, за да обясним алгоритъма:

Алгоритъм за кодиране на Хъфман

Етап 1: Изградете min-heap, в който всеки възел представлява корена на дърво с един възел и съдържа 5 (броя уникални символи от предоставения поток от данни).

Стъпка 2: Получете два минимални честотни възела от min heap в стъпка втора. Добавете трети вътрешен възел, честота 2 + 3 = 5, който се създава чрез свързване на двата извлечени възела.

• Сега има 4 възела в min-heap, 3 от които са корени на дървета с по един елемент всеки и 1 от които е корен на дърво с два елемента.

Стъпка 3: Вземете двата възела с минимална честота от купчината по подобен начин в стъпка три. Освен това добавете нов вътрешен възел, образуван чрез свързване на двата извлечени възела; неговата честота в дървото трябва да бъде 4 + 4 = 8.

• Сега, когато минималната купчина има три възела, един възел служи като корен на дървета с един елемент, а два възела на купчина служат като корен на дървета с множество възли.

Стъпка 4: Вземете двата минимални честотни възела в четвърта стъпка. Освен това добавете нов вътрешен възел, образуван чрез свързване на двата извлечени възела; неговата честота в дървото трябва да бъде 5 + 7 = 12.

• Когато създаваме дърво на Хъфман, трябва да гарантираме, че минималната стойност е винаги от лявата страна и че втората стойност е винаги от дясната страна. В момента изображението по-долу показва образуваното дърво:

Стъпка 5: Вземете следните два възела с минимална честота в стъпка 5. Освен това добавете нов вътрешен възел, образуван чрез свързване на двата извлечени възела; неговата честота в дървото трябва да бъде 12 + 8 = 20.

Продължете, докато всички отделни знаци бъдат добавени към дървото. Дървото на Хъфман, създадено за определен състав от герои, е показано на горното изображение.

Сега, за всеки възел, който не е лист, присвоете 0 на левия край и 1 на десния край, за да създадете кода за всяка буква.

Правила, които трябва да следвате за определяне на теглото на ръбовете:

• Трябва да дадем тегло на десните ръбове 1, ако дадете тегло на левите ръбове 0.
• Ако на левите ръбове се даде тегло 1, на десните ръбове трябва да се даде тегло 0.
• Може да се използва всяка от двете гореспоменати конвенции.
• Следвайте обаче същия протокол и при декодиране на дървото.

След претеглянето модифицираното дърво се показва, както следва:

Разбиране на Кодекса

• Трябва да преминем през дървото на Хъфман, докато стигнем до листовия възел, където присъства елементът, за да декодираме кода на Хъфман за всеки знак от полученото дърво на Хъфман.
• Теглата на възлите трябва да бъдат записани по време на обхождането и разпределени към елементите, разположени в конкретния листов възел.
• Следният пример ще ви помогне да илюстрирате допълнително какво имаме предвид:
• За да получим кода за всеки символ от горната снимка, трябва да обходим цялото дърво (докато всички листови възли бъдат покрити).
• В резултат на това създаденото дърво се използва за декодиране на кодовете за всеки възел. По-долу е даден списък с кодовете за всеки знак:

По-долу е изпълнението в 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->left = temp->right = NULL; temp->data = data; temp->freq = 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->size = 0; minHeap->capacity = capacity; minHeap->array = (struct MinHeapNode**)malloc( minHeap->capacity * 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]->freq) smallest = left; if (right size && minHeap->array[right]->freq array[smallest]->freq) smallest = right; if (smallest != idx) { swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]); minHeapify(minHeap, smallest); } } // A utility function to check // if size of heap is 1 or not int isSizeOne(struct MinHeap* minHeap) { return (minHeap->size == 1); } // A standard function to extract // minimum value node from heap struct MinHeapNode* extractMin(struct MinHeap* minHeap) { struct MinHeapNode* temp = minHeap->array[0]; minHeap->array[0] = minHeap->array[minHeap->size - 1]; --minHeap->size; 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->size; int i = minHeap->size - 1; while (i && minHeapNode->freq array[(i - 1) / 2]->freq) { minHeap->array[i] = minHeap->array[(i - 1) / 2]; i = (i - 1) / 2; } minHeap->array[i] = minHeapNode; } // A standard function to build min heap void buildMinHeap(struct MinHeap* minHeap) { int n = minHeap->size - 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 left) && !(root->right); } // Creates a min heap of capacity // equal to size and inserts all character of // data[] in min heap. Initially size of // min heap is equal to capacity struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) { struct MinHeap* minHeap = createMinHeap(size); for (int i = 0; i array[i] = newNode(data[i], freq[i]); minHeap->size = size; buildMinHeap(minHeap); return minHeap; } // The main function that builds Huffman tree struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) { struct MinHeapNode *left, *right, *top; // Step 1: Create a min heap of capacity // equal to size. Initially, there are // modes equal to size. struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size); // Iterate while size of heap doesn't become 1 while (!isSizeOne(minHeap)) { // Step 2: Extract the two minimum // freq items from min heap left = extractMin(minHeap); right = extractMin(minHeap); // Step 3: 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 = newNode('$', left->freq + right->freq); top->left = left; top->right = right; insertMinHeap(minHeap, top); } // Step 4: The remaining node is the // root node and the tree is complete. return extractMin(minHeap); } // Prints huffman codes from the root of Huffman Tree. // It uses arr[] to store codes void printCodes(struct MinHeapNode* root, int arr[], int top) { // Assign 0 to left edge and recur if (root->left) { arr[top] = 0; printCodes(root->left, arr, top + 1); } // Assign 1 to right edge and recur if (root->right) { arr[top] = 1; printCodes(root->right, arr, top + 1); } // If this is a leaf node, then // it contains one of the input // characters, print the character // and its code from arr[] if (isLeaf(root)) { printf('%c: ', root->data); printArr(arr, top); } } // The main function that builds a // Huffman Tree and print codes by traversing // the built Huffman Tree void HuffmanCodes(char data[], int freq[], int size) { // Construct Huffman Tree struct MinHeapNode* root = buildHuffmanTree(data, freq, size); // Print Huffman codes using // the Huffman tree built above int arr[MAX_TREE_HT], top = 0; printCodes(root, arr, top); } // Driver code 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); return 0; } 

Изход

 f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 …………… Process executed in 1.11 seconds Press any key to continue. 

Реализация на горния код в 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 &amp;&amp; root.right == null &amp;&amp; Character.isLetter(root.c)) { // c is the character in the node System.out.println(root.c + &apos;:&apos; + s); return; } // if we go to left then add &apos;0&apos; to the code. // if we go to the right add&apos;1&apos; to the code. // recursive calls for left and // right sub-tree of the generated tree. printCode(root.left, s + &apos;0&apos;); printCode(root.right, s + &apos;1&apos;); } // main function public static void main(String[] args) { Scanner s = new Scanner(System.in); // number of characters. int n = 6; char[] charArray = { &apos;a&apos;, &apos;b&apos;, &apos;c&apos;, &apos;d&apos;, &apos;e&apos;, &apos;f&apos; }; 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 <n; 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;" functions adds q.add(hn); } create root here we will extract two minimum value from heap each time until its size reduces 1, all nodes are extracted. while (q.size()> 1) { // first min extract. HuffmanNode x = q.peek(); q.poll(); // second min extract. HuffmanNode y = q.peek(); q.poll(); // new node f which is equal HuffmanNode f = new HuffmanNode(); // to the sum of the frequency of the two nodes // assigning values to the f node. f.data = x.data + y.data; f.c = &apos;-&apos;; // first extracted node as left child. f.left = x; // second extracted node as the right child. f.right = y; // marking the f node as the root node. root = f; // add this node to the priority-queue. q.add(f); } // print the codes by traversing the tree printCode(root, &apos;&apos;); } } // node class is the basic structure // of each node present in the Huffman - tree. class HuffmanNode { int data; char c; HuffmanNode left; HuffmanNode right; } // comparator class helps to compare the node // on the basis of one of its attribute. // Here we will be compared // on the basis of data values of the nodes. class MyComparator implements Comparator { public int compare(HuffmanNode x, HuffmanNode y) { return x.data - y.data; } } </n;>

Изход

 f: 0 c: 100 d: 101 a: 1100 b: 1101 e: 111 ………………. Process executed in 1.11 seconds Press any key to continue. 

Обяснение:

Чрез преминаване се създава и декодира дървото на Хъфман. След това стойностите, събрани по време на обхождането, трябва да бъдат приложени към знака, разположен в листовия възел. Всеки уникален знак в предоставения поток от данни може да бъде идентифициран с помощта на кода на Хъфман по този начин. O (nlogn), където n е общият брой знаци, е времевата сложност. ExtractMin() се извиква 2*(n - 1) пъти, ако има n възли. Тъй като extractMin() извиква minHeapify(), времето за изпълнение е O (logn). Следователно общата сложност е O (nlogn). Има линеен времеви алгоритъм, ако входният масив е сортиран. Това ще бъде разгледано по-подробно в предстоящия ни материал.

Проблеми с кодирането на Huffman

Нека поговорим за недостатъците на кодирането на Huffman в тази част и защо не винаги е най-добрият вариант:

списък низ java

• Ако не всички вероятности или честоти на знаците са отрицателни степени на 2, това не се счита за идеално.
• Въпреки че човек може да се доближи до идеала чрез групиране на символи и разширяване на азбуката, методът на блокиране изисква работа с по-голяма азбука. Следователно кодирането на Huffman може да не винаги е много ефективно.
• Въпреки че има много ефективни начини за преброяване на честотата на всеки символ или знак, възстановяването на цялото дърво за всеки от тях може да отнеме много време. Когато азбуката е голяма и вероятностните разпределения се променят бързо с всеки символ, това обикновено е така.

Алгоритъм за конструиране на кода на Greedy Huffman

• Huffman разработи алчна техника, която генерира код на Huffman, идеален префиксен код, за всеки отделен знак във входния поток от данни.
• Подходът използва най-малко възли всеки път, за да създаде дървото на Хъфман отдолу нагоре.
• Тъй като всеки знак получава дължина на кода въз основа на това колко често се появява в дадения поток от данни, този метод е известен като алчен подход. Това е често срещан елемент в данните, ако размерът на извлечения код е по-малък.

Използването на Huffman Coding

• Тук ще говорим за някои практически приложения на Huffman Coding:
• Конвенционалните формати за компресиране като PKZIP, GZIP и т.н. обикновено използват кодиране на Huffman.
• Кодирането на Huffman се използва за прехвърляне на данни чрез факс и текст, тъй като минимизира размера на файла и увеличава скоростта на предаване.
• Кодирането на Huffman (особено префиксните кодове) се използва от няколко мултимедийни формата за съхранение, включително JPEG, PNG и MP3, за компресиране на файловете.
• Кодирането на Huffman се използва най-вече за компресиране на изображения.
• Когато трябва да се изпрати низ от често повтарящи се знаци, това може да бъде по-полезно.

Заключение

• Като цяло кодирането на Huffman е полезно за компресиране на данни, които съдържат често срещани знаци.
• Можем да видим, че знакът, който се среща най-често, има най-кратък код, докато този, който се среща най-рядко, има най-голям код.
• Техниката за компресиране на кода на Хъфман се използва за създаване на кодиране с променлива дължина, което използва различно количество битове за всяка буква или символ. Този метод е по-добър от кодирането с фиксирана дължина, тъй като използва по-малко памет и предава данни по-бързо.
• Прегледайте тази статия, за да имате по-добри познания за алчния алгоритъм.