Подаци се могу компримовати коришћењем технике Хафмановог кодирања како би постали мањи без губитка информација. После Дејвида Хафмана, ко га је створио на почетку? Подаци који садрже знакове који се често понављају се обично компримују коришћењем Хафмановог кодирања.

Добро познати Грееди алгоритам је Хуффман Цодинг. Величина кода додељеног карактеру зависи од фреквенције карактера, због чега се назива похлепним алгоритамом. Променљиви код кратке дужине се додељује карактеру са највећом фреквенцијом, и обрнуто за карактере са нижим фреквенцијама. Користи кодирање променљиве дужине, што значи да сваком карактеру у датом току података даје различит код променљиве дужине.

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

У суштини, ово правило каже да код који је додељен знаку не сме бити префикс другог кода. Ако се ово правило прекрши, могу се појавити различите нејасноће приликом декодирања Хафмановог стабла које је креирано.

Погледајмо илустрацију овог правила да бисмо га боље разумели: За сваки знак је обезбеђен код, као што је:

 a - 0 b - 1 c - 01 

Под претпоставком да је произведени ток битова 001, код се може изразити на следећи начин када се декодира:

 0 0 1 = aab 0 01 = ac 

Шта је процес Хафмановог кодирања?

Хафманов код се добија за сваки посебан карактер првенствено у два корака:

• Прво направите Хафманово дрво користећи само јединствене знакове у пруженом току података.
• Друго, морамо наставити кроз конструисано Хафманово дрво, доделити кодове знаковима, а затим користити те кодове за декодирање датог текста.

Кораци које треба предузети у Хуффман кодирању

Кораци који се користе за конструисање Хафмановог стабла користећи дате знакове

 Input: string str = 'abbcdbccdaabbeeebeab' 

Ако се Хафманово кодирање користи у овом случају за компресију података, за декодирање се морају одредити следеће информације:

• За сваки лик, Хафманов код
• Дужина поруке коју је кодирао Хафман (у битовима), просечна дужина кода
• Користећи формуле покривене у наставку, откривене су последње две од њих.

Како се Хафманово дрво може конструисати од улазних знакова?

Прво се мора одредити учесталост сваког знака у датом низу.

1. Поређајте знакове по учесталости, растући. Они се чувају у К/мин-хеап приоритетном реду.
2. За сваки посебан знак и његову учесталост у току података, креирајте лисни чвор.
3. Уклоните два чвора са две најниже фреквенције из чворова, а нови корен стабла се креира користећи збир ових фреквенција.
   • Учините први екстраховани чвор његовим левим подређеним, а други екстраховани чвор његовим десним дететом док извлачите чворове са најнижом фреквенцијом из мин-гомиле.
   • У мин-хеап додајте овај чвор.
   • Пошто лева страна корена увек треба да садржи минималну фреквенцију.
4. Понављајте кораке 3 и 4 све док на хрпи не остане само један чвор, или сви ликови нису представљени чворовима у стаблу. Стабло је готово када остане само коренски чвор.

Примери Хафмановог кодирања

Хајде да користимо илустрацију да објаснимо алгоритам:

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

Корак 1: Направите минималну хрпу у којој сваки чвор представља корен стабла са једним чвором и садржи 5 (број јединствених знакова из датог тока података).

Корак 2: Набавите два чвора минималне фреквенције из минималне гомиле у другом кораку. Додајте трећи унутрашњи чвор, фреквенција 2 + 3 = 5, који се ствара спајањем два издвојена чвора.

• Сада постоје 4 чвора у минималној хрпи, од којих су 3 корени дрвећа са по једним елементом, а од којих је 1 корен дрвета са два елемента.

Корак 3: Узмите два чвора минималне фреквенције из гомиле на сличан начин у трећем кораку. Додатно, додајте нови унутрашњи чвор формиран спајањем два издвојена чвора; његова фреквенција у стаблу треба да буде 4 + 4 = 8.

• Сада када минимална хрпа има три чвора, један чвор служи као корен стабала са једним елементом, а два чвора хрпе служе као корен стабала са више чворова.

4. корак: Узмите два чвора минималне фреквенције у четвртом кораку. Додатно, додајте нови унутрашњи чвор формиран спајањем два издвојена чвора; његова фреквенција у стаблу треба да буде 5 + 7 = 12.

• Када креирамо Хафманово стабло, морамо осигурати да је минимална вредност увек на левој страни и да је друга вредност увек на десној страни. Тренутно, слика испод приказује стабло које се формирало:

5. корак: Узмите следећа два чвора минималне фреквенције у кораку 5. Додатно, додајте нови унутрашњи чвор формиран спајањем два издвојена чвора; његова фреквенција у стаблу треба да буде 12 + 8 = 20.

Наставите док се сви различити знакови не додају стаблу. Хафманово стабло креирано за наведену групу ликова приказано је на горњој слици.

Сада, за сваки нелисни чвор, доделите 0 левој ивици и 1 десној ивици да бисте креирали код за свако слово.

Диана Мари Блацкер

Правила која треба следити за одређивање тежине ивица:

• Требало би да десним ивицама дамо тежину 1 ако левим ивицама дамо тежину 0.
• Ако левим ивицама дате тежину 1, десним ивицама се мора дати тежина 0.
• Може се користити било која од две горе поменуте конвенције.
• Међутим, следите исти протокол и када дешифрујете стабло.

Након пондерисања, измењено стабло се приказује на следећи начин:

Разумевање Кодекса

• Морамо проћи кроз Хафманово стабло док не дођемо до лисног чвора, где је елемент присутан, да бисмо декодирали Хафманов код за сваки знак из резултујућег Хафмановог дрвета.
• Тежине преко чворова морају бити забележене током обиласка и додељене ставкама које се налазе на специфичном лисном чвору.
• Следећи пример ће помоћи да се додатно илуструје шта мислимо:
• Да бисмо добили код за сваки знак на горњој слици, морамо проћи цело дрво (све док се не покрију сви чворови листа).
• Као резултат, стабло које је креирано се користи за декодирање кодова за сваки чвор. Испод је листа кодова за сваки знак:

Испод је имплементација у Ц програмирању:

 // 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. 

Јава имплементација горњег кода:

 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. 

Објашњење:

Преласком, Хафманово дрво се креира и декодира. Вредности прикупљене током обиласка се затим примењују на карактер који се налази на лисном чвору. Сваки јединствени знак у достављеном току података може се идентификовати коришћењем Хафмановог кода на овај начин. О (нлогн), где је н укупан број карактера, је временска сложеност. ЕктрацтМин() се позива 2*(н - 1) пута ако има н чворова. Пошто екстрактМин() позива минХеапифи(), његово време извршења је О (логн). Укупна сложеност је стога О (нлогн). Постоји линеарни алгоритам времена ако је улазни низ сортиран. Ово ће бити детаљније објашњено у нашем наредном чланку.

Проблеми са Хуффман кодирањем

Хајде да разговарамо о недостацима Хафмановог кодирања у овом делу и зашто то није увек најбоља опција:

• Ако нису све вероватноће или фреквенције ликова негативни степен 2, то се не сматра идеалним.
• Иако се може приближити идеалу груписањем симбола и проширењем абецеде, метода блокирања захтева руковање већим алфабетом. Стога, Хафманово кодирање можда није увек веома ефикасно.
• Иако постоји много ефикасних начина да се преброји учесталост сваког симбола или карактера, реконструкција целог стабла за сваки од њих може бити дуготрајна. Када је абецеда велика и дистрибуције вероватноће се брзо мењају са сваким симболом, то је обично случај.

Алгоритам за конструкцију похлепног Хафмановог кода

• Хафман је развио похлепну технику која генерише Хафманов код, идеалан префикс код, за сваки посебан карактер у улазном току података.
• Приступ користи најмање чворова сваки пут да креира Хафманово стабло одоздо према горе.
• Пошто сваки знак прима дужину кода на основу тога колико се често појављује у датом току података, овај метод је познат као похлепни приступ. То је уобичајен елемент у подацима ако је величина преузетог кода мања.

Употреба Хафмановог кодирања

• Овде ћемо говорити о неким практичним употребама Хуффмановог кодирања:
• Конвенционални формати компресије као што су ПКЗИП, ГЗИП, итд. обично користе Хафманово кодирање.
• Хуффман Цодинг се користи за пренос података путем факса и текста јер минимизира величину датотеке и повећава брзину преноса.
• Хафманово кодирање (посебно кодови префикса) користи неколико формата за складиштење мултимедије, укључујући ЈПЕГ, ПНГ и МП3, за компресију датотека.
• Хуффман Цодинг се углавном користи за компресију слике.
• Када се мора послати низ знакова који се често понављају, то може бити од веће помоћи.

Закључак

• Уопштено говорећи, Хуффман Цодинг је од помоћи за компримовање података који садрже знакове који се често појављују.
• Можемо видети да знак који се најчешће појављује има најкраћи код, док онај који се јавља најређе има највећи код.
• Техника компресије Хафмановог кода се користи за креирање кодирања променљиве дужине, које користи различиту количину битова за свако слово или симбол. Овај метод је бољи од кодирања фиксне дужине јер користи мање меморије и брже преноси податке.
• Прођите кроз овај чланак да бисте боље упознали похлепни алгоритам.