Huffmano kodavimo algoritmas

Šioje pamokoje sužinosite, kaip veikia „Huffman Coding“. Taip pat rasite veikiančių „Huffman“ kodavimo pavyzdžių C, C ++, „Java“ ir „Python“.

„Huffman Coding“ yra duomenų glaudinimo technika, siekiant sumažinti jų dydį, neprarandant jokių detalių. Pirmą kartą jį sukūrė Davidas Huffmanas.

„Huffman“ kodavimas paprastai yra naudingas norint suspausti duomenis, kuriuose yra dažnai pasitaikančių simbolių.

Kaip veikia „Huffman Coding“?

Tarkime, kad žemiau esanti eilutė turi būti siunčiama per tinklą.

Pradinė eilutė

Kiekvienas simbolis užima 8 bitus. Pirmiau pateiktoje eilutėje iš viso yra 15 simbolių. Taigi 8 * 15 = 120norint išsiųsti šią eilutę reikia iš viso bitų.

Naudodami „Huffman Coding“ techniką, galime suspausti virvelę mažesniu dydžiu.

Huffmano kodavimas pirmiausia sukuria medį naudodamas simbolio dažnius, tada sugeneruoja kodą kiekvienam simboliui.

Kai duomenys yra užkoduoti, juos reikia iššifruoti. Dekodavimas atliekamas naudojant tą patį medį.

„Huffman“ kodavimas užkerta kelią bet kokiam dviprasmumui dekodavimo procese, naudojant priešdėlio kodo koncepciją, t. kodo, susieto su simboliu, neturėtų būti jokio kito kodo priešdėlyje. Aukščiau sukurtas medis padeda išlaikyti nuosavybę.

„Huffman“ kodavimas atliekamas naudojant šiuos veiksmus.

  1. Apskaičiuokite kiekvieno eilutės simbolio dažnį. Stygų dažnis
  2. Rūšiuoti simbolius didėjančia dažnio tvarka. Jie saugomi prioritetinėje eilėje Q. Simboliai, surūšiuoti pagal dažnumą
  3. Padarykite kiekvieną unikalų simbolį kaip lapų mazgą.
  4. Sukurkite tuščią mazgą z. Priskirkite mažiausią dažnį kairiajam z vaikui, o antrąjį - dešiniajam z. Nustatykite z vertę kaip minėtų dviejų minimalių dažnių sumą. Mažiausių skaičių sumos gavimas
  5. Pašalinkite šiuos du minimalius dažnius iš Q ir pridėkite sumą į dažnių sąrašą (* aukščiau esančiame paveiksle pažymėkite vidinius mazgus).
  6. Į medį įkiškite mazgą z.
  7. Pakartokite 3–5 veiksmus visiems simboliams. Pakartokite 3–5 veiksmus visiems simboliams. Pakartokite 3–5 veiksmus visiems simboliams.
  8. Kiekvienam lapų neturinčiam mazgui kairįjį kraštą priskirkite 0, o dešiniajam - 1. Priskirkite 0 kairiajam kraštui ir 1 dešiniajam kraštui

Norėdami išsiųsti aukščiau pateiktą eilutę per tinklą, turime išsiųsti medį ir aukščiau pateiktą suspaustą kodą. Bendras dydis nurodytas toliau pateiktoje lentelėje.

Charakteris Dažnis Kodas Dydis
A 5 11 5 * 2 = 10
B 1 100 1 * 3 = 3
C 6 0 6 * 1 = 6
D 3 101 3 * 3 = 9
4 * 8 = 32 bitai 15 bitų 28 bitai

Be kodavimo, visas eilutės dydis buvo 120 bitų. Užkodavus dydis sumažinamas iki 32 + 15 + 28 = 75.

Kodo dekodavimas

Norėdami iššifruoti kodą, galime paimti kodą ir pereiti per medį, norėdami rasti simbolį.

Leiskite dekoduoti 101, mes galime pereiti nuo šaknies, kaip parodyta žemiau esančiame paveikslėlyje.

Dekodavimas

Huffmano kodavimo algoritmas

sukurkite prioritetinę eilę Q, susidedančią iš kiekvieno unikalaus simbolio. rūšiuoti tada jų dažnių didėjimo tvarka. visiems unikaliems simboliams: sukurkite „newNode“ minimalią vertę iš Q ir priskirkite ją „leftChild of newNode“ išgaukite mažiausią vertę iš „Q“ ir priskirkite „rightChild of newNode“ apskaičiuokite šių dviejų minimalių verčių sumą ir priskirkite ją „newNode“ įterpimo vertei šis newNode į medį grąžina rootNode

„Python“, „Java“ ir „C / C ++“ pavyzdžiai

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

Įdomios straipsniai...