Tässä opetusohjelmassa opit kuinka Huffman Coding toimii. Löydät myös toimivia esimerkkejä Huffman-koodauksesta C, C ++, Java ja Python.
Huffman-koodaus on tekniikka tietojen pakkaamiseen pienentämään sen kokoa menettämättä mitään yksityiskohtia. Sen kehitti ensin David Huffman.
Huffman-koodaus on yleensä hyödyllistä pakata tietoja, joissa on usein esiintyviä merkkejä.
Kuinka Huffman Coding toimii?
Oletetaan, että alla oleva merkkijono lähetetään verkon kautta.
Alkuperäinen merkkijono
Jokainen merkki vie 8 bittiä. Yllä olevassa merkkijonossa on yhteensä 15 merkkiä. Siten 8 * 15 = 120tämän merkkijonon lähettämiseen tarvitaan yhteensä bittejä.
Huffman Coding -tekniikkaa käyttämällä voimme pakata merkkijonon pienempään kokoon.
Huffman-koodaus luo ensin puun merkin taajuuksia käyttäen ja luo sitten koodin jokaiselle merkille.
Kun tiedot on koodattu, ne on purettava. Dekoodaus tapahtuu samalla puulla.
Huffman-koodaus estää epäselvyydet dekoodausprosessissa käyttämällä etuliitekoodin käsitettä eli. merkkiin liittyvää koodia ei saa olla minkään muun koodin etuliitteessä. Yllä luotu puu auttaa ylläpitämään omaisuutta.
Huffman-koodaus tehdään seuraavien vaiheiden avulla.
- Laske merkkijonon kunkin merkin taajuus.
Merkkijonon taajuus - Lajittele merkit kasvavassa taajuusjärjestyksessä. Nämä tallennetaan prioriteettijonoon Q.
Merkit lajitellaan taajuuden mukaan - Tee jokaisesta ainutlaatuisesta merkistä lehtisolmu.
- Luo tyhjä solmu z. Määritä pienin taajuus z: n vasemmalle lapselle ja toinen toinen taajuus z: n oikealle lapselle. Aseta z: n arvo kahden yllä olevan taajuuden summaksi.
Pienimpien lukujen summan saaminen - Poista nämä kaksi vähimmäistaajuutta Q: sta ja lisää summa taajuuksien luetteloon (* tarkoita sisäisiä solmuja yllä olevassa kuvassa).
- Lisää solmu z puuhun.
- Toista vaiheet 3–5 kaikille merkeille.
Toista vaiheet 3–5 kaikille merkeille. 
Toista vaiheet 3–5 kaikille merkeille. - Määritä jokaiselle ei-lehtisolmulle 0 vasempaan reunaan ja 1 oikeaan reunaan.
Määritä 0 vasempaan reunaan ja 1 oikeaan reunaan
Yllä olevan merkkijonon lähettämiseksi verkon kautta meidän on lähetettävä puu ja yllä oleva pakattu koodi. Kokonaiskoko on annettu alla olevassa taulukossa.
| Merkki | Taajuus | Koodi | Koko |
|---|---|---|---|
| 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 bittiä | 15 bittiä | 28 bittiä |
Ilman koodausta merkkijonon koko oli 120 bittiä. Koodauksen jälkeen koko pienennetään kokoon 32 + 15 + 28 = 75.
Koodin dekoodaus
Koodin purkamiseksi voimme ottaa koodin ja kulkea puun läpi löytääksesi merkin.
Olkoon 101 dekoodattava, voimme siirtyä juuresta kuten alla olevassa kuvassa.
Dekoodaus
Huffman-koodausalgoritmi
luo prioriteettijono Q, joka koostuu jokaisesta yksilöllisestä merkistä. lajittele sitten taajuuksiensa nousevassa järjestyksessä. kaikille yksilöllisille merkeille: luo newNode poimi vähimmäisarvo Q: sta ja määritä se leftChild of newNode poimi vähimmäisarvo Q: sta ja määritä se rightChild of newNode laskee näiden kahden vähimmäisarvon summa ja määritä se newNode-lisäyksen arvoon tämä newNode puuhun palaa rootNode
Python-, Java- ja C / C ++ -esimerkkejä
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.
