Кодиращ алгоритъм на Хафман

В този урок ще научите как работи Huffman Coding. Също така ще намерите работещи примери за кодиране на Huffman в C, C ++, Java и Python.

Huffman Coding е техника за компресиране на данни, за да се намали размерът им, без да се губят детайли. За първи път е разработен от Дейвид Хъфман.

Huffman Coding обикновено е полезно за компресиране на данните, в които има често срещани символи.

Как работи Huffman Coding?

Да предположим, че низът по-долу трябва да бъде изпратен по мрежа.

Първоначален низ

Всеки символ заема 8 бита. В горния низ има общо 15 знака. По този начин 8 * 15 = 120за изпращането на този низ са необходими общо битове.

Използвайки техниката на Huffman Coding, можем да компресираме низа до по-малък размер.

Кодирането на Huffman първо създава дърво, използвайки честотите на символа и след това генерира код за всеки символ.

След като данните са кодирани, те трябва да бъдат декодирани. Декодирането се извършва с помощта на същото дърво.

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

Кодирането на Huffman се извършва с помощта на следните стъпки.

  1. Изчислете честотата на всеки символ в низа. Честота на низ
  2. Сортирайте символите в нарастващ ред на честотата. Те се съхраняват в приоритетна опашка Q. Символи, сортирани според честотата
  3. Направете всеки уникален знак като листен възел.
  4. Създайте празен възел z. Задайте минималната честота на лявото дете на z и втората минимална честота на дясното дете на z. Задайте стойността на z като сума от горните две минимални честоти. Получаване на сумата от най-малко числа
  5. Премахнете тези две минимални честоти от Q и добавете сумата в списъка с честоти (* означава вътрешните възли на фигурата по-горе).
  6. Поставете възел z в дървото.
  7. Повторете стъпки от 3 до 5 за всички знаци. Повторете стъпки от 3 до 5 за всички знаци. Повторете стъпки от 3 до 5 за всички знаци.
  8. За всеки нелистов възел задайте 0 на левия ръб и 1 на десния ръб. Задайте 0 на левия ръб и 1 на десния ръб

За изпращане на горния низ по мрежа, трябва да изпратим дървото, както и горния компресиран код. Общият размер е даден от таблицата по-долу.

Характер Честота Код Размер
A 5 11. 5 * 2 = 10
Б. 1 100 1 * 3 = 3
° С 6 0 6 * 1 = 6
д 3 101 3 * 3 = 9
4 * 8 = 32 бита 15 бита 28 бита

Без кодиране общият размер на низа беше 120 бита. След кодиране размерът се намалява до 32 + 15 + 28 = 75.

Декодиране на кода

За декодиране на кода можем да вземем кода и да преминем през дървото, за да намерим символа.

Нека 101 трябва да бъде декодиран, можем да преминем от корена, както е показано на фигурата по-долу.

Декодиране

Кодиращ алгоритъм на Хафман

създайте приоритетна опашка Q, състояща се от всеки уникален знак. сортирайте след това във възходящ ред на техните честоти. за всички уникални символи: създайте newNode извлечете минимална стойност от Q и я присвойте на leftChild на newNode извлечете минимална стойност от Q и я присвойте на rightChild на newNode изчислете сумата от тези две минимални стойности и я присвойте на стойността на newNode insert този newNode в дървото връщане rootNode

Примери за Python, Java и C / C ++

Python Java C C ++ 
 # Huffman Coding in python string = 'BCAADDDCCACACAC' # Creating tree nodes class NodeTree(object): def __init__(self, left=None, right=None): self.left = left self.right = right def children(self): return (self.left, self.right) def nodes(self): return (self.left, self.right) def __str__(self): return '%s_%s' % (self.left, self.right) # Main function implementing huffman coding def huffman_code_tree(node, left=True, binString=''): if type(node) is str: return (node: binString) (l, r) = node.children() d = dict() d.update(huffman_code_tree(l, True, binString + '0')) d.update(huffman_code_tree(r, False, binString + '1')) return d # Calculating frequency freq = () for c in string: if c in freq: freq(c) += 1 else: freq(c) = 1 freq = sorted(freq.items(), key=lambda x: x(1), reverse=True) nodes = freq while len(nodes)> 1: (key1, c1) = nodes(-1) (key2, c2) = nodes(-2) nodes = nodes(:-2) node = NodeTree(key1, key2) nodes.append((node, c1 + c2)) nodes = sorted(nodes, key=lambda x: x(1), reverse=True) huffmanCode = huffman_code_tree(nodes(0)(0)) print(' Char | Huffman code ') print('----------------------') for (char, frequency) in freq: print(' %-4r |%12s' % (char, huffmanCode(char)))
 // Huffman Coding in Java import java.util.PriorityQueue; import java.util.Comparator; class HuffmanNode ( int item; char c; HuffmanNode left; HuffmanNode right; ) // For comparing the nodes class ImplementComparator implements Comparator ( public int compare(HuffmanNode x, HuffmanNode y) ( return x.item - y.item; ) ) // IMplementing the huffman algorithm public class Huffman ( public static void printCode(HuffmanNode root, String s) ( if (root.left == null && root.right == null && Character.isLetter(root.c)) ( System.out.println(root.c + " | " + s); return; ) printCode(root.left, s + "0"); printCode(root.right, s + "1"); ) public static void main(String() args) ( int n = 4; char() charArray = ( 'A', 'B', 'C', 'D' ); int() charfreq = ( 5, 1, 6, 3 ); PriorityQueue q = new PriorityQueue(n, new ImplementComparator()); for (int i = 0; i 1) ( HuffmanNode x = q.peek(); q.poll(); HuffmanNode y = q.peek(); q.poll(); HuffmanNode f = new HuffmanNode(); f.item = x.item + y.item; f.c = '-'; f.left = x; f.right = y; root = f; q.add(f); ) System.out.println(" Char | Huffman code "); System.out.println("--------------------"); printCode(root, ""); ) )
 // Huffman Coding in C #include #include #define MAX_TREE_HT 50 struct MinHNode ( char item; unsigned freq; struct MinHNode *left, *right; ); struct MinHeap ( unsigned size; unsigned capacity; struct MinHNode **array; ); // Create nodes struct MinHNode *newNode(char item, unsigned freq) ( struct MinHNode *temp = (struct MinHNode *)malloc(sizeof(struct MinHNode)); temp->left = temp->right = NULL; temp->item = item; temp->freq = freq; return temp; ) // Create min heap struct MinHeap *createMinH(unsigned capacity) ( struct MinHeap *minHeap = (struct MinHeap *)malloc(sizeof(struct MinHeap)); minHeap->size = 0; minHeap->capacity = capacity; minHeap->array = (struct MinHNode **)malloc(minHeap->capacity * sizeof(struct MinHNode *)); return minHeap; ) // Function to swap void swapMinHNode(struct MinHNode **a, struct MinHNode **b) ( struct MinHNode *t = *a; *a = *b; *b = t; ) // Heapify 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) ( swapMinHNode(&minHeap->array(smallest), &minHeap->array(idx)); minHeapify(minHeap, smallest); ) ) // Check if size if 1 int checkSizeOne(struct MinHeap *minHeap) ( return (minHeap->size == 1); ) // Extract min struct MinHNode *extractMin(struct MinHeap *minHeap) ( struct MinHNode *temp = minHeap->array(0); minHeap->array(0) = minHeap->array(minHeap->size - 1); --minHeap->size; minHeapify(minHeap, 0); return temp; ) // Insertion function void insertMinHeap(struct MinHeap *minHeap, struct MinHNode *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; ) void buildMinHeap(struct MinHeap *minHeap) ( int n = minHeap->size - 1; int i; for (i = (n - 1) / 2; i>= 0; --i) minHeapify(minHeap, i); ) int isLeaf(struct MinHNode *root) ( return !(root->left) && !(root->right); ) struct MinHeap *createAndBuildMinHeap(char item(), int freq(), int size) ( struct MinHeap *minHeap = createMinH(size); for (int i = 0; i array(i) = newNode(item(i), freq(i)); minHeap->size = size; buildMinHeap(minHeap); return minHeap; ) struct MinHNode *buildHuffmanTree(char item(), int freq(), int size) ( struct MinHNode *left, *right, *top; struct MinHeap *minHeap = createAndBuildMinHeap(item, freq, size); while (!checkSizeOne(minHeap)) ( left = extractMin(minHeap); right = extractMin(minHeap); top = newNode('$', left->freq + right->freq); top->left = left; top->right = right; insertMinHeap(minHeap, top); ) return extractMin(minHeap); ) void printHCodes(struct MinHNode *root, int arr(), int top) ( if (root->left) ( arr(top) = 0; printHCodes(root->left, arr, top + 1); ) if (root->right) ( arr(top) = 1; printHCodes(root->right, arr, top + 1); ) if (isLeaf(root)) ( printf(" %c | ", root->item); printArray(arr, top); ) ) // Wrapper function void HuffmanCodes(char item(), int freq(), int size) ( struct MinHNode *root = buildHuffmanTree(item, freq, size); int arr(MAX_TREE_HT), top = 0; printHCodes(root, arr, top); ) // Print the array void printArray(int arr(), int n) ( int i; for (i = 0; i < n; ++i) printf("%d", arr(i)); printf(""); ) int main() ( char arr() = ('A', 'B', 'C', 'D'); int freq() = (5, 1, 6, 3); int size = sizeof(arr) / sizeof(arr(0)); printf(" Char | Huffman code "); printf("--------------------"); HuffmanCodes(arr, freq, size); )
 // Huffman Coding in C++ #include using namespace std; #define MAX_TREE_HT 50 struct MinHNode ( unsigned freq; char item; struct MinHNode *left, *right; ); struct MinH ( unsigned size; unsigned capacity; struct MinHNode **array; ); // Creating Huffman tree node struct MinHNode *newNode(char item, unsigned freq) ( struct MinHNode *temp = (struct MinHNode *)malloc(sizeof(struct MinHNode)); temp->left = temp->right = NULL; temp->item = item; temp->freq = freq; return temp; ) // Create min heap using given capacity struct MinH *createMinH(unsigned capacity) ( struct MinH *minHeap = (struct MinH *)malloc(sizeof(struct MinH)); minHeap->size = 0; minHeap->capacity = capacity; minHeap->array = (struct MinHNode **)malloc(minHeap->capacity * sizeof(struct MinHNode *)); return minHeap; ) // Swap function void swapMinHNode(struct MinHNode **a, struct MinHNode **b) ( struct MinHNode *t = *a; *a = *b; *b = t; ) // Heapify void minHeapify(struct MinH *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) ( swapMinHNode(&minHeap->array(smallest), &minHeap->array(idx)); minHeapify(minHeap, smallest); ) ) // Check if size if 1 int checkSizeOne(struct MinH *minHeap) ( return (minHeap->size == 1); ) // Extract the min struct MinHNode *extractMin(struct MinH *minHeap) ( struct MinHNode *temp = minHeap->array(0); minHeap->array(0) = minHeap->array(minHeap->size - 1); --minHeap->size; minHeapify(minHeap, 0); return temp; ) // Insertion void insertMinHeap(struct MinH *minHeap, struct MinHNode *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; ) // BUild min heap void buildMinHeap(struct MinH *minHeap) ( int n = minHeap->size - 1; int i; for (i = (n - 1) / 2; i>= 0; --i) minHeapify(minHeap, i); ) int isLeaf(struct MinHNode *root) ( return !(root->left) && !(root->right); ) struct MinH *createAndBuildMinHeap(char item(), int freq(), int size) ( struct MinH *minHeap = createMinH(size); for (int i = 0; i array(i) = newNode(item(i), freq(i)); minHeap->size = size; buildMinHeap(minHeap); return minHeap; ) struct MinHNode *buildHfTree(char item(), int freq(), int size) ( struct MinHNode *left, *right, *top; struct MinH *minHeap = createAndBuildMinHeap(item, freq, size); while (!checkSizeOne(minHeap)) ( left = extractMin(minHeap); right = extractMin(minHeap); top = newNode('$', left->freq + right->freq); top->left = left; top->right = right; insertMinHeap(minHeap, top); ) return extractMin(minHeap); ) void printHCodes(struct MinHNode *root, int arr(), int top) ( if (root->left) ( arr(top) = 0; printHCodes(root->left, arr, top + 1); ) if (root->right) ( arr(top) = 1; printHCodes(root->right, arr, top + 1); ) if (isLeaf(root)) ( cout

Huffman Coding Complexity

The time complexity for encoding each unique character based on its frequency is O(nlog n).

Extracting minimum frequency from the priority queue takes place 2*(n-1) times and its complexity is O(log n). Thus the overall complexity is O(nlog n).

Huffman Coding Applications

  • Huffman coding is used in conventional compression formats like GZIP, BZIP2, PKZIP, etc.
  • For text and fax transmissions.

Интересни статии...