In diesem Tutorial erfahren Sie, wie Huffman Coding funktioniert. Außerdem finden Sie Arbeitsbeispiele für Huffman-Codierung in C, C ++, Java und Python.
Huffman Coding ist eine Technik zum Komprimieren von Daten, um deren Größe zu reduzieren, ohne Details zu verlieren. Es wurde zuerst von David Huffman entwickelt.
Die Huffman-Codierung ist im Allgemeinen nützlich, um die Daten zu komprimieren, in denen häufig vorkommende Zeichen vorkommen.
Wie funktioniert Huffman Coding?
Angenommen, die folgende Zeichenfolge soll über ein Netzwerk gesendet werden.
Anfangszeichenfolge
Jedes Zeichen belegt 8 Bits. Die obige Zeichenfolge enthält insgesamt 15 Zeichen. Somit sind insgesamt 8 * 15 = 120Bits erforderlich, um diese Zeichenfolge zu senden.
Mit der Huffman-Codierungstechnik können wir den String auf eine kleinere Größe komprimieren.
Die Huffman-Codierung erstellt zuerst einen Baum unter Verwendung der Frequenzen des Zeichens und generiert dann Code für jedes Zeichen.
Sobald die Daten codiert sind, müssen sie decodiert werden. Die Dekodierung erfolgt mit demselben Baum.
Die Huffman-Codierung verhindert jegliche Mehrdeutigkeit im Decodierungsprozess unter Verwendung des Konzepts des Präfixcodes, d. H. Ein mit einem Zeichen verknüpfter Code sollte nicht im Präfix eines anderen Codes enthalten sein. Der oben erstellte Baum hilft bei der Pflege der Eigenschaft.
Die Huffman-Codierung erfolgt mit Hilfe der folgenden Schritte.
- Berechnen Sie die Häufigkeit jedes Zeichens in der Zeichenfolge.
Häufigkeit der Zeichenfolge - Sortieren Sie die Zeichen in aufsteigender Reihenfolge der Häufigkeit. Diese werden in einer Prioritätswarteschlange Q gespeichert.
Zeichen werden nach der Häufigkeit sortiert - Machen Sie jedes einzelne Zeichen zu einem Blattknoten.
- Erstellen Sie einen leeren Knoten z. Weisen Sie dem linken Kind von z die Mindestfrequenz zu und weisen Sie dem rechten Kind von z die zweite Mindestfrequenz zu. Stellen Sie den Wert von z als die Summe der beiden oben genannten Mindestfrequenzen ein.
Die Summe der kleinsten Zahlen erhalten - Entfernen Sie diese beiden Mindestfrequenzen aus Q und fügen Sie die Summe in die Liste der Frequenzen ein (* bezeichnet die internen Knoten in der obigen Abbildung).
- Fügen Sie den Knoten z in den Baum ein.
- Wiederholen Sie die Schritte 3 bis 5 für alle Zeichen.
Wiederholen Sie die Schritte 3 bis 5 für alle Zeichen. 
Wiederholen Sie die Schritte 3 bis 5 für alle Zeichen. - Weisen Sie für jeden Nicht-Blattknoten dem linken Rand 0 und dem rechten Rand 1 zu.
Weisen Sie dem linken Rand 0 und dem rechten Rand 1 zu
Um die obige Zeichenfolge über ein Netzwerk zu senden, müssen wir den Baum sowie den obigen komprimierten Code senden. Die Gesamtgröße ist in der folgenden Tabelle angegeben.
| Charakter | Frequenz | Code | Größe |
|---|---|---|---|
| EIN | 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 Bit | 15 Bits | 28 Bit |
Ohne Codierung betrug die Gesamtgröße der Zeichenfolge 120 Bit. Nach dem Codieren wird die Größe auf reduziert 32 + 15 + 28 = 75.
Code dekodieren
Um den Code zu dekodieren, können wir den Code nehmen und durch den Baum laufen, um das Zeichen zu finden.
Wenn 101 dekodiert werden soll, können wir wie in der folgenden Abbildung von der Wurzel durchqueren.
Dekodierung
Huffman-Codierungsalgorithmus
Erstellen Sie eine Prioritätswarteschlange Q, die aus jedem eindeutigen Zeichen besteht. sortieren Sie dann in aufsteigender Reihenfolge ihrer Frequenzen. für alle eindeutigen Zeichen: Erstellen Sie einen newNode-Extrakt-Minimalwert aus Q und weisen Sie ihn leftChild of newNode zu. Extrahieren Sie den Minimalwert aus Q und weisen Sie ihn rightChild of newNode zu. Berechnen Sie die Summe dieser beiden Minimalwerte und weisen Sie ihn dem Wert von newNode insert ein Dieser neue Knoten in den Baum gibt rootNode zurück
Beispiele für Python, Java und 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.
