אלגוריתם דחיסה של האפמן

לפני תחילת הקורס "אלגוריתמים למפתחים" הכינו עבורכם תרגום של חומר שימושי אחר.

קידוד האפמן הוא אלגוריתם דחיסת נתונים המנסח את הרעיון הבסיסי של דחיסת קבצים. במאמר זה נדבר על קידוד באורך קבוע ומשתנה, קודים הניתנים לפענוח ייחודי, כללי קידומת ובניית עץ האפמן.

אנו יודעים שכל תו מאוחסן כרצף של 0 ו-1 ותופס 8 ביטים. זה נקרא קידוד באורך קבוע מכיוון שכל תו משתמש באותו מספר קבוע של ביטים לאחסון.

נניח שקיבלנו טקסט. כיצד נוכל לצמצם את כמות השטח הנדרש לאחסון תו בודד?

הרעיון המרכזי הוא קידוד באורך משתנה. אנו יכולים להשתמש בעובדה שחלק מהתווים בטקסט מופיעים לעתים קרובות יותר מאחרות (ראה כאן) לפתח אלגוריתם שייצג את אותו רצף של תווים בפחות ביטים. בקידוד באורך משתנה, אנו מקצים לתווים מספר משתנה של סיביות, בהתאם לתדירות שבה הם מופיעים בטקסט נתון. בסופו של דבר, תווים מסוימים עשויים לקחת מעט כמו ביט אחד, בעוד שאחרים עשויים לקחת 1 סיביות, 2 או יותר. הבעיה עם קידוד באורך משתנה היא רק הפענוח הבא של הרצף.

כיצד, לדעת את רצף הביטים, לפענח אותו באופן חד משמעי?

קחו בחשבון את הקו "אבקדאב". יש לו 8 תווים, וכאשר מקודדים אורך קבוע, הוא יצטרך 64 סיביות כדי לאחסן אותו. שים לב כי תדירות הסמל "א ב ג" и "D" שווה ל-4, 2, 1, 1 בהתאמה. בואו ננסה לדמיין "אבקדאב" פחות ביטים, תוך שימוש בעובדה ש "ל" מתרחשת בתדירות גבוהה יותר מאשר "ב"ו - "ב" מתרחשת בתדירות גבוהה יותר מאשר "ג" и "D". נתחיל בקידוד "ל" עם ביט אחד שווה ל-0, "ב" נקצה קוד של שני סיביות 11, ובאמצעות שלוש סיביות 100 ו-011 נקודד "ג" и "D".

כתוצאה מכך נקבל:

a
0

b
11

c
100

d
011

אז הקו "אבקדאב" נקודד כ 00110100011011 (0|0|11|0|100|011|0|11)באמצעות הקודים שלמעלה. עם זאת, הבעיה העיקרית תהיה בפענוח. כאשר אנו מנסים לפענח את המחרוזת 00110100011011, נקבל תוצאה מעורפלת, שכן ניתן לייצג אותה כך:

0|011|0|100|011|0|11    adacdab
0|0|11|0|100|0|11|011   aabacabd
0|011|0|100|0|11|0|11   adacabab 

...
וכו '

כדי למנוע אי בהירות זו, עלינו לוודא שהקידוד שלנו עונה על מושג כמו כלל קידומת, אשר בתורו מרמז שניתן לפענח את הקודים רק בדרך ייחודית אחת. כלל הקידומת מבטיח שאף קוד אינו קידומת של אחר. בקוד, אנו מתכוונים לביטים המשמשים לייצוג תו מסוים. בדוגמה למעלה 0 הוא קידומת 011, מה שמפר את כלל הקידומת. לכן, אם הקודים שלנו עומדים בחוק הקידומת, אז נוכל לפענח באופן ייחודי (ולהיפך).

בואו נחזור על הדוגמה שלמעלה. הפעם נקצה לסמלים "א ב ג" и "D" קודים העונים על כלל הקידומת.

a
0

b
10

c
110

d
111

עם הקידוד הזה, המחרוזת "אבקדאב" יקודד כ 00100100011010 (0|0|10|0|100|011|0|10). אבל 00100100011010 כבר נוכל לפענח באופן חד משמעי ולחזור למחרוזת המקורית שלנו "אבקדאב".

קידוד האפמן

כעת, לאחר שעסקנו בקידוד באורך משתנה ובכלל הקידומת, בואו נדבר על קידוד האפמן.

השיטה מבוססת על יצירת עצים בינאריים. בו, הצומת יכול להיות סופי או פנימי. בתחילה, כל הצמתים נחשבים לעלים (טרמינלים), המייצגים את הסמל עצמו ואת משקלו (כלומר, תדירות ההתרחשות). הצמתים הפנימיים מכילים את משקל התו ומתייחסים לשני צמתים צאצאים. בהסכמה כללית, קצת «0» מייצג בעקבות הענף השמאלי, ו «1» - בצד ימין. בעץ מלא N עלים ו N-1 צמתים פנימיים. מומלץ כי בעת בניית עץ האפמן, יש להשליך סמלים שאינם בשימוש כדי לקבל קודי אורך אופטימליים.

נשתמש בתור עדיפות לבניית עץ האפמן, כאשר הצומת בעל התדר הנמוך ביותר יקבל את העדיפות הגבוהה ביותר. שלבי הבנייה מתוארים להלן:

1. צור צומת עלים עבור כל תו והוסף אותם לתור העדיפות.
2. בעוד שיש יותר מגיליון אחד בתור, בצע את הפעולות הבאות:
   • הסר את שני הצמתים עם העדיפות הגבוהה ביותר (התדירות הנמוכה ביותר) מהתור;
   • צור צומת פנימי חדש, שבו שני הצמתים הללו יהיו ילדים, ותדירות ההתרחשות תהיה שווה לסכום התדרים של שני הצמתים הללו.
   • הוסף צומת חדש לתור העדיפות.
3. הצומת היחיד שנותר יהיה השורש, וזה ישלים את בניית העץ.

תארו לעצמכם שיש לנו טקסט שמורכב רק מתווים "א ב ג ד" и "ו", ותדרי המופע שלהם הם 15, 7, 6, 6 ו-5, בהתאמה. להלן איורים המשקפים את שלבי האלגוריתם.

נתיב מהשורש לכל צומת קצה יאחסן את קוד הקידומת האופטימלי (הידוע גם כקוד Huffman) התואם לתו המשויך לאותו צומת קצה.

עץ האפמן

להלן תמצאו את היישום של אלגוריתם הדחיסה של Huffman ב-C++ וב-Java:

#include <iostream>
#include <string>
#include <queue>
#include <unordered_map>
using namespace std;

// A Tree node
struct Node
{
	char ch;
	int freq;
	Node *left, *right;
};

// Function to allocate a new tree node
Node* getNode(char ch, int freq, Node* left, Node* right)
{
	Node* node = new Node();

	node->ch = ch;
	node->freq = freq;
	node->left = left;
	node->right = right;

	return node;
}

// Comparison object to be used to order the heap
struct comp
{
	bool operator()(Node* l, Node* r)
	{
		// highest priority item has lowest frequency
		return l->freq > r->freq;
	}
};

// traverse the Huffman Tree and store Huffman Codes
// in a map.
void encode(Node* root, string str,
			unordered_map<char, string> &huffmanCode)
{
	if (root == nullptr)
		return;

	// found a leaf node
	if (!root->left && !root->right) {
		huffmanCode[root->ch] = str;
	}

	encode(root->left, str + "0", huffmanCode);
	encode(root->right, str + "1", huffmanCode);
}

// traverse the Huffman Tree and decode the encoded string
void decode(Node* root, int &index, string str)
{
	if (root == nullptr) {
		return;
	}

	// found a leaf node
	if (!root->left && !root->right)
	{
		cout << root->ch;
		return;
	}

	index++;

	if (str[index] =='0')
		decode(root->left, index, str);
	else
		decode(root->right, index, str);
}

// Builds Huffman Tree and decode given input text
void buildHuffmanTree(string text)
{
	// count frequency of appearance of each character
	// and store it in a map
	unordered_map<char, int> freq;
	for (char ch: text) {
		freq[ch]++;
	}

	// Create a priority queue to store live nodes of
	// Huffman tree;
	priority_queue<Node*, vector<Node*>, comp> pq;

	// Create a leaf node for each character and add it
	// to the priority queue.
	for (auto pair: freq) {
		pq.push(getNode(pair.first, pair.second, nullptr, nullptr));
	}

	// do till there is more than one node in the queue
	while (pq.size() != 1)
	{
		// Remove the two nodes of highest priority
		// (lowest frequency) from the queue
		Node *left = pq.top(); pq.pop();
		Node *right = pq.top();	pq.pop();

		// Create a new internal node with these two nodes
		// as children and with frequency equal to the sum
		// of the two nodes' frequencies. Add the new node
		// to the priority queue.
		int sum = left->freq + right->freq;
		pq.push(getNode('', sum, left, right));
	}

	// root stores pointer to root of Huffman Tree
	Node* root = pq.top();

	// traverse the Huffman Tree and store Huffman Codes
	// in a map. Also prints them
	unordered_map<char, string> huffmanCode;
	encode(root, "", huffmanCode);

	cout << "Huffman Codes are :n" << 'n';
	for (auto pair: huffmanCode) {
		cout << pair.first << " " << pair.second << 'n';
	}

	cout << "nOriginal string was :n" << text << 'n';

	// print encoded string
	string str = "";
	for (char ch: text) {
		str += huffmanCode[ch];
	}

	cout << "nEncoded string is :n" << str << 'n';

	// traverse the Huffman Tree again and this time
	// decode the encoded string
	int index = -1;
	cout << "nDecoded string is: n";
	while (index < (int)str.size() - 2) {
		decode(root, index, str);
	}
}

// Huffman coding algorithm
int main()
{
	string text = "Huffman coding is a data compression algorithm.";

	buildHuffmanTree(text);

	return 0;
}

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

// A Tree node
class Node
{
	char ch;
	int freq;
	Node left = null, right = null;

	Node(char ch, int freq)
	{
		this.ch = ch;
		this.freq = freq;
	}

	public Node(char ch, int freq, Node left, Node right) {
		this.ch = ch;
		this.freq = freq;
		this.left = left;
		this.right = right;
	}
};

class Huffman
{
	// traverse the Huffman Tree and store Huffman Codes
	// in a map.
	public static void encode(Node root, String str,
							  Map<Character, String> huffmanCode)
	{
		if (root == null)
			return;

		// found a leaf node
		if (root.left == null && root.right == null) {
			huffmanCode.put(root.ch, str);
		}


		encode(root.left, str + "0", huffmanCode);
		encode(root.right, str + "1", huffmanCode);
	}

	// traverse the Huffman Tree and decode the encoded string
	public static int decode(Node root, int index, StringBuilder sb)
	{
		if (root == null)
			return index;

		// found a leaf node
		if (root.left == null && root.right == null)
		{
			System.out.print(root.ch);
			return index;
		}

		index++;

		if (sb.charAt(index) == '0')
			index = decode(root.left, index, sb);
		else
			index = decode(root.right, index, sb);

		return index;
	}

	// Builds Huffman Tree and huffmanCode and decode given input text
	public static void buildHuffmanTree(String text)
	{
		// count frequency of appearance of each character
		// and store it in a map
		Map<Character, Integer> freq = new HashMap<>();
		for (int i = 0 ; i < text.length(); i++) {
			if (!freq.containsKey(text.charAt(i))) {
				freq.put(text.charAt(i), 0);
			}
			freq.put(text.charAt(i), freq.get(text.charAt(i)) + 1);
		}

		// Create a priority queue to store live nodes of Huffman tree
		// Notice that highest priority item has lowest frequency
		PriorityQueue<Node> pq = new PriorityQueue<>(
										(l, r) -> l.freq - r.freq);

		// Create a leaf node for each character and add it
		// to the priority queue.
		for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
			pq.add(new Node(entry.getKey(), entry.getValue()));
		}

		// do till there is more than one node in the queue
		while (pq.size() != 1)
		{
			// Remove the two nodes of highest priority
			// (lowest frequency) from the queue
			Node left = pq.poll();
			Node right = pq.poll();

			// Create a new internal node with these two nodes as children 
			// and with frequency equal to the sum of the two nodes
			// frequencies. Add the new node to the priority queue.
			int sum = left.freq + right.freq;
			pq.add(new Node('', sum, left, right));
		}

		// root stores pointer to root of Huffman Tree
		Node root = pq.peek();

		// traverse the Huffman tree and store the Huffman codes in a map
		Map<Character, String> huffmanCode = new HashMap<>();
		encode(root, "", huffmanCode);

		// print the Huffman codes
		System.out.println("Huffman Codes are :n");
		for (Map.Entry<Character, String> entry : huffmanCode.entrySet()) {
			System.out.println(entry.getKey() + " " + entry.getValue());
		}

		System.out.println("nOriginal string was :n" + text);

		// print encoded string
		StringBuilder sb = new StringBuilder();
		for (int i = 0 ; i < text.length(); i++) {
			sb.append(huffmanCode.get(text.charAt(i)));
		}

		System.out.println("nEncoded string is :n" + sb);

		// traverse the Huffman Tree again and this time
		// decode the encoded string
		int index = -1;
		System.out.println("nDecoded string is: n");
		while (index < sb.length() - 2) {
			index = decode(root, index, sb);
		}
	}

	public static void main(String[] args)
	{
		String text = "Huffman coding is a data compression algorithm.";

		buildHuffmanTree(text);
	}
}

הערה: הזיכרון המשמש את מחרוזת הקלט הוא 47*8 = 376 סיביות והמחרוזת המקודדת היא רק 194 סיביות, כלומר. הנתונים נדחסים בכ-48%. בתוכנית C++ שלמעלה, אנו משתמשים במחלקה string כדי לאחסן את המחרוזת המקודדת כדי להפוך את התוכנית לקריאה.

מכיוון שמבני נתונים יעילים של תור עדיפות דורשים כל הכנסה O(log(N)) זמן, אבל בעץ בינארי שלם עם N עלים נוכחים 2N-1 צמתים, ועץ ההאפמן הוא עץ בינארי שלם, אז האלגוריתם נכנס פנימה O(Nlog(N)) זמן, איפה N - דמויות.

מקורות:

en.wikipedia.org/wiki/Huffman_coding
en.wikipedia.org/wiki/Variable-length_code
www.youtube.com/watch?v=5wRPin4oxCo

למידע נוסף על הקורס.

מקור: www.habr.com