Huffman Coding क्या है

Huffman coding उन words को छोटे nicknames देने जैसा है जो आप सबसे ज़्यादा बोलते हैं और rare words को लंबे, overall messages को छोटा बनाते हुए।

In this page:

What is Huffman Coding?
Frequency Table
Merge Two Smallest
Prefix Codes
Practice

Syntax

markup

import heapq
heap = [(freq, symbol) for symbol, freq in frequencies.items()]
heapq.heapify(heap)
while len(heap) > 1:
    f1, left = heapq.heappop(heap)
    f2, right = heapq.heappop(heap)
    heapq.heappush(heap, (f1 + f2, (left, right)))

What is Huffman Coding?

Huffman coding symbols के एक set के लिए एक compact binary code बनाता है frequently-used symbols को छोटे codes और rarely-used symbols को लंबे codes देकर, data store या transmit करने के लिए चाहिए bits की total संख्या घटाते हुए — बिना कोई information खोए।

उदाहरण: What is Huffman Coding?

#include <iostream>
using namespace std;
int main() {
	cout << "Frequent symbols get short codes, rare symbols get long codes -- reduces total bits needed";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Frequent symbols get short codes, rare symbols get long codes -- reduces total bits needed");
	}
}

print("Frequent symbols get short codes, rare symbols get long codes -- reduces total bits needed")

#include <stdio.h>
int main() {
	printf("Frequent symbols get short codes, rare symbols get long codes -- reduces total bits needed");
	return 0;
}

Frequency Table

Algorithm यह count करके शुरू होता है कि input में हर symbol कितनी बार दिखता है; ज़्यादा बार दिखने वाले symbols आखिरकार resulting tree के root के करीब end होंगे और इसलिए छोटे codes पाएंगे।

उदाहरण: Frequency Table

#include <iostream>
#include <map>
using namespace std;
int main() {
	string text = "abracadabra";
	map<char,int> freq;
	for (char c : text) freq[c]++;
	for (auto& p : freq) cout << p.first << ":" << p.second << " ";
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		String text = "abracadabra";
		Map<Character,Integer> freq = new TreeMap<>();
		for (char c : text.toCharArray()) freq.merge(c, 1, Integer::sum);
		for (var e : freq.entrySet()) System.out.print(e.getKey() + ":" + e.getValue() + " ");
	}
}

from collections import Counter
text = "abracadabra"
freq = Counter(text)
for ch, count in sorted(freq.items()):
    print(f"{ch}:{count}", end=" ")

#include <stdio.h>
int main() {
	char text[] = "abracadabra";
	int freq[26] = {0};
	for (int i = 0; text[i]; i++) freq[text[i]-'a']++;
	for (int i = 0; i < 26; i++) if (freq[i]) printf("%c:%d ", 'a'+i, freq[i]);
	return 0;
}

Merge Two Smallest

बार-बार सबसे छोटी combined frequency वाले दो symbols (या partial trees) लेना और उन्हें एक नए internal node में merge करना Huffman tree को bottom up बनाता है, हमेशा currently सबसे सस्ती pair को prioritize करते हुए।

उदाहरण: Merge Two Smallest

#include <iostream>
#include <queue>
using namespace std;
int main() {
	priority_queue<int, vector<int>, greater<int>> pq;
	for (int f : {5, 9, 12, 13, 16, 45}) pq.push(f);
	int a = pq.top(); pq.pop();
	int b = pq.top(); pq.pop();
	pq.push(a + b);
	cout << "Merged " << a << "+" << b << " into new node freq " << a+b;
	return 0;
}

import java.util.*;
public class Main {
	public static void main(String[] args) {
		PriorityQueue<Integer> pq = new PriorityQueue<>(Arrays.asList(5, 9, 12, 13, 16, 45));
		int a = pq.poll(), b = pq.poll();
		pq.add(a + b);
		System.out.println("Merged " + a + "+" + b + " into new node freq " + (a+b));
	}
}

import heapq
pq = [5, 9, 12, 13, 16, 45]
heapq.heapify(pq)
a = heapq.heappop(pq)
b = heapq.heappop(pq)
heapq.heappush(pq, a + b)
print(f"Merged {a}+{b} into new node freq {a+b}")

#include <stdio.h>
int main() {
	int freqs[6] = {5, 9, 12, 13, 16, 45};
	int minIdx = 0;
	for (int i = 1; i < 6; i++) if (freqs[i] < freqs[minIdx]) minIdx = i;
	int a = freqs[minIdx]; freqs[minIdx] = 1000000;
	int min2Idx = 0;
	for (int i = 1; i < 6; i++) if (freqs[i] < freqs[min2Idx]) min2Idx = i;
	int b = freqs[min2Idx];
	printf("Merged %d+%d into new node freq %d", a, b, a+b);
	return 0;
}

Prefix Codes

चूंकि इस tree में कोई code word कभी किसी दूसरे code word का prefix नहीं है, Huffman-encoded bits की एक stream हमेशा left to right unambiguously decode हो सकती है, symbols के बीच separators की ज़रूरत के बिना।

उदाहरण: Prefix Codes

#include <iostream>
using namespace std;
int main() {
	string codeA = "0", codeB = "10", codeC = "11";
	cout << "None of " << codeA << "," << codeB << "," << codeC << " is a prefix of another -- unambiguous decoding";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		String codeA = "0", codeB = "10", codeC = "11";
		System.out.println("None of " + codeA + "," + codeB + "," + codeC + " is a prefix of another -- unambiguous decoding");
	}
}

code_a, code_b, code_c = "0", "10", "11"
print(f"None of {code_a},{code_b},{code_c} is a prefix of another -- unambiguous decoding")

#include <stdio.h>
int main() {
	printf("None of 0,10,11 is a prefix of another -- unambiguous decoding");
	return 0;
}

Practice

इसे हाथ से काम करते हुए, आप दो सबसे छोटी frequencies को combine करते रहते हैं एक नए node में जिसकी frequency उनका sum है, फिर उस combined node को अगले merge के लिए एक नए candidate की तरह treat करते हैं, तब तक जारी रखते हुए जब तक सिर्फ एक tree न बचे।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "Keep combining the two smallest frequencies into a new node, treat it as a candidate for the next merge";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Keep combining the two smallest frequencies into a new node, treat it as a candidate for the next merge");
	}
}

print("Keep combining the two smallest frequencies into a new node, treat it as a candidate for the next merge")

#include <stdio.h>
int main() {
	printf("Keep combining the two smallest frequencies into a new node, treat it as a candidate for the next merge");
	return 0;
}

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Fractional Knapsack Next Lesson → Job Scheduling