Algorithms/Huffman coding

ترميزات اللاحقة Prefix Codes هي ترميزات (تسلسلات من البتات) توضع بطريقة لا يكون فيها الترميز الموضوع لحرف معين لاحقة لترميز موضوع لحرف آخر، ويعتمد ترميز هوفمان Huffman على هذه الخاصية في ضمان عدم وجود أي لبس عند إجراء عملية فك الترميز.

فلو فرضنا -على سبيل المثال- أنّ لدينا الأحرف a, b, c, d وأنّ الترميزات المقابلة لها هي ‎00, 01, 0 ,1‎، فإنّ هذا الترميز سيؤدي إلى حدوث لبس في عملية فك الترميز؛ وذلك لأنّ الترميز المسند إلى الحرف c هو لاحقة للترميزين المسندين إلى الحرفين a و b، بمعنى أنّه لو كان تدفق البتات المضغوط هو 0001 فهذا يعني أنّ فك الضغط عن هذا التدفق أحد المخرجات التالية: cccd أو ccb أو acd أو ab.

يتكون ترميز هوفمان من جزأين أساسين هما:

1. بناء شجرة هوفمان من الحروف المدخلة.
2. التنقل عبر شجرة هوفمان وإسناد الترميزات إلى الحروف.

خطوات بناء شجرة هوفمان

شجرة هوفمان هي عبارة عن مصفوفة تتضمن حروفًا فريدة إلى جانب تردد ظهورها وخروجها frequency of occurrences and output.

يمكن بناء شجرة هوفمان باتباع الخطوات التالية:

1. إنشاء عقدة ورقية leaf node لكل حرف فريد في المصفوفة وبناء كومة صغرى تضم جميع العقد الورقية (تستخدم الكومة الصغرى كرتل أولوية. تستخدم قيمة حقل التردد للمقارنة بين عقدتين في الكومة الصغرى. يكون الحرف الذي يمتلك أدنى قيمة للتردد عقدة الجذر).
2. استخراج العقدتين اللتين تمتلكان أقل قيمة للتردد في الكومة الصغرى.
3. إنشاء عقدة داخلية جديدة تكون قيمة التردد فيها مساوية لمجموع ترددات العقدتين السابقتين، وجعل العقدة الأولى كعقدة بنوية يسرى والعقدة الثانية كعقدة بنوية يمنى، ثم إضافة هذه العقدة إلى الكومة الصغرى.
4. تكرار الخطوتين 2 و 3 إلى أن تبقى عقدة واحدة فقط في الكومة، وتكون العقدة الباقية عقدة الجذر وبهذا يكتمل بناء الشجرة.

يوضح المثال التالي خطوات بناء شجرة هوفمان:

character   Frequency
    a            5
    b           9
    c           12
    d           13
    e           16
    f           45

1. بناء كومة صغرى تحتوي على 6 عقد تمثل كل عقدة منها جذر الشجرة مع عقدة واحدة.
2. استخراج العقدتين اللتين تمتلكان أدنى قيمة للتردد من الكومة الصغرى، ثم إضافة عقدة داخلية جديدة تساوي قيمة التردد فيها مجموع قيمتي التردد للعقدتين المستخرجتين أي ‎5 + 9 = 14‎.

تحتوي الكومة الصغرى الآن على 5 عقد 4 منها هي جذور للشجرات مع عنصر واحد في كل شجرة، وعقدة واحدة في الكومة الصغرى وهي جذر لشجرة مع 3 عناصر.

character Frequency

c 12

d 13

Internal Node 14

e 16

f 45

1. استخراج العقدتين اللتين تمتلكان أدنى قيمة للتردد من الكومة الصغرى، ثم إضافة عقدة داخلية جديدة تساوي قيمة التردد فيها مجموع قيمتي التردد للعقدتين المستخرجتين أي ‎12 + 13 = 25‎.

تحتوي الكومة الصغرى الآن على 4 عقد 2 منها هي جذور للشجرات مع عنصر واحد في كل شجرة، وعقدتان في الكومة الصغرى وهي جذر لشجرة مع أكثر من عقدة واحدة.

character           Frequency
Internal Node          14
       e               16
Internal Node          25
       f               45

1. استخراج العقدتين اللتين تمتلكان أدنى قيمة للتردد من الكومة الصغرى، ثم إضافة عقدة داخلية جديدة تساوي قيمة التردد فيها مجموع قيمتي التردد للعقدتين المستخرجتين أي ‎14 + 16 = 30‎.

تحتوي الكومة الصغرى على ثلاث عقد الآن.

character          Frequency
Internal Node         25
Internal Node         30
      f               45

استخراج العقدتين اللتين تمتلكان أدنى قيمة للتردد من الكومة الصغرى، ثم إضافة عقدة داخلية جديدة تساوي قيمة التردد فيها مجموع قيمتي التردد للعقدتين المستخرجتين أي ‎25 + 30 = 55‎.

تحتوي الكومة الصغرى على عقدتين الآن.

character     Frequency
       f         45
Internal Node    55

1. استخراج العقدتين اللتين تمتلكان أدنى قيمة للتردد من الكومة الصغرى، ثم إضافة عقدة داخلية جديدة تساوي قيمة التردد فيها مجموع قيمتي التردد للعقدتين المستخرجتين أي ‎45 + 55 = 100‎.

تحتوي الكومة الصغرى على عقدة واحدة الآن.

character      Frequency
Internal Node    100

تتوقف الخوارزمية عند هذه النقطة لأنّ الكومة الصغرى تحتوي على عقدة واحدة فقط.

طباعة الترميزات من شجرة هوفمان

يمكن طباعة الترميزات من شجرة هوفمان بالتنقل عبر الشجرة المتكوّنة بدءًا من جذرها، وإنشاء مصفوفة مساعدة تضاف إليها القيمة 0 عند التحرك إلى العقدة البنوية اليسرى، والقيمة 1 عند التحرك إلى العقدة البنوية اليمنى. تطبع المصفوفة عند ملاقاة عقدة ورقية.

ينتج المثال السابق الترميزات التالية:

character   code-word
    f          0
    c          100
    d          101
    a          1100
    b          1101
    e          111

تنفيذ الخوارزمية

تعرض الأمثلة التالية طريقة تنفيذ خوارزمية ترميز هوفمان في عدد من لغات البرمجة:

• C++‎:

#include <iostream> 
#include <cstdlib> 
using namespace std; 

// يمكن تجنب استخدام هذا الثابت
// بحساب ارتفاع شجرة هوفمان
#define MAX_TREE_HT 100 

// عقدة في شجرة هوفمان
struct MinHeapNode { 

	// أحد الحروف المدخلة
	char data; 

	// تردد الحرف
	unsigned freq; 

	// العقدتان البنوية اليمنى واليسرى لهذه العقدة
	struct MinHeapNode *left, *right; 
}; 

// كومة صغرى: مجموعة من عقد الكومة الصغرى (أو شجرة هوفمان)
struct MinHeap { 

	// حجم الكومة الصغرى الحالي
	unsigned size; 

	// سعة الكومة الصغرى
	unsigned capacity; 

	// مصفوفة تضم مؤشرات لعقد الكومة الصغرى
	struct MinHeapNode** array; 
}; 

// دالة مساعدة تخصّص عقدة في الكومة الصغرى
// تضمّ الحرف المعطى إلى جانب تردد الحرف
struct MinHeapNode* newNode(char data, unsigned freq) 
{ 
	struct MinHeapNode* temp 
		= (struct MinHeapNode*)malloc
(sizeof(struct MinHeapNode)); 

	temp->left = temp->right = NULL; 
	temp->data = data; 
	temp->freq = freq; 

	return temp; 
} 

// دالة مساعدة لإنشاء كومة صغرى بالسعة المعطاة
struct MinHeap* createMinHeap(unsigned capacity) 

{ 

	struct MinHeap* minHeap 
		= (struct MinHeap*)malloc(sizeof(struct MinHeap)); 

	// الحجم الحالي هو 0
	minHeap->size = 0; 

	minHeap->capacity = capacity; 

	minHeap->array 
		= (struct MinHeapNode**)malloc(minHeap-> 
capacity * sizeof(struct MinHeapNode*)); 
	return minHeap; 
} 

// دالة مساعدة للتبديل بين عقدتين في الكومة الصغرى
void swapMinHeapNode(struct MinHeapNode** a, 
					struct MinHeapNode** b) 

{ 

	struct MinHeapNode* t = *a; 
	*a = *b; 
	*b = t; 
} 

void minHeapify(struct MinHeap* minHeap, int idx) 

{ 

	int smallest = idx; 
	int left = 2 * idx + 1; 
	int right = 2 * idx + 2; 

	if (left < minHeap->size && minHeap->array[left]-> 
freq < minHeap->array[smallest]->freq) 
		smallest = left; 

	if (right < minHeap->size && minHeap->array[right]-> 
freq < minHeap->array[smallest]->freq) 
		smallest = right; 

	if (smallest != idx) { 
		swapMinHeapNode(&minHeap->array[smallest], 
						&minHeap->array[idx]); 
		minHeapify(minHeap, smallest); 
	} 
} 

// دالة مساعدة للتحقق من أنّ حجم الكومة يساوي 1 أو لا
int isSizeOne(struct MinHeap* minHeap) 
{ 

	return (minHeap->size == 1); 
} 

// دالة قياسية لاستخراج العقدة ذي القيمة الدنيا من الكومة
struct MinHeapNode* extractMin(struct MinHeap* minHeap) 

{ 

	struct MinHeapNode* temp = minHeap->array[0]; 
	minHeap->array[0] 
		= minHeap->array[minHeap->size - 1]; 

	--minHeap->size; 
	minHeapify(minHeap, 0); 

	return temp; 
} 

// دالة مساعدة لإدراج عقدة جديدة في الكومة الصغرى
void insertMinHeap(struct MinHeap* minHeap, 
				struct MinHeapNode* minHeapNode) 

{ 

	++minHeap->size; 
	int i = minHeap->size - 1; 

	while (i && minHeapNode->freq < minHeap->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); 
} 

// دالة مساعدة لطباعة عناصر المصفوفة المعطاة
void printArr(int arr[], int n) 
{ 
	int i; 
	for (i = 0; i < n; ++i) 
		cout<< arr[i]; 

	cout<<"\n"; 
} 

// دالة مساعدة للتحقق ممّا إذا كانت العدقة المعطاة عقدة ورقية أو لا
int isLeaf(struct MinHeapNode* root) 

{ 

	return !(root->left) && !(root->right); 
} 

// تنشئ الدالة كومة صغرى بسعة تساوي الحجم المعطى
// data[] وتدرج جميع الحروف في المصفوفة
// في الكومة الصغرى.
// في البداية يكون حجم الكومة الصغرى مساويًا للسعة المعطاة
struct MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) 

{ 

	struct MinHeap* minHeap = createMinHeap(size); 

	for (int i = 0; i < size; ++i) 
		minHeap->array[i] = newNode(data[i], freq[i]); 

	minHeap->size = size; 
	buildMinHeap(minHeap); 

	return minHeap; 
} 

// الدالة الرئيسية المسؤولة عن بناء شجرة هوفمان
struct MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) 

{ 
	struct MinHeapNode *left, *right, *top; 

	// الخطوة الأولى: إنشاء كومة صغرى بالسعة المعطاة
	// في البداية يكون حجم الكومة الصغرى مساويًا للسعة المعطاة
	struct MinHeap* minHeap = createAndBuildMinHeap(data, freq, size); 

	// إنشاء حلقة تكرارية ما دامت الكومة لا تساوي 1
	while (!isSizeOne(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 printCodes(struct MinHeapNode* root, int arr[], int top) 

{ 

	// إسناد القيمة 0 إلى الطرف الأيسر ثم استدعاء الدالة تعاوديًا
	if (root->left) { 

		arr[top] = 0; 
		printCodes(root->left, arr, top + 1); 
	} 

	// إسناد القيمة 0 إلى الطرف الأيمن ثم استدعاء الدالة تعاوديًا
	if (root->right) { 

		arr[top] = 1; 
		printCodes(root->right, arr, top + 1); 
	} 

	// إن كانت هذه العقدة عقدة ورقية فإنها ستحتوي على أحد الحروف المدخلة
	// لذا ستطبع الشيفرة السابقة الحرف وترميزه من المصفوفة المعطاة
	if (isLeaf(root)) { 

		cout<< root->data <<": "; 
		printArr(arr, top); 
	} 
} 

// الدالة الرئيسية المسؤولة عن بناء شجرة هوفمان
// وتطبع الترميزات بالتنقل عبر الشجرة
void HuffmanCodes(char data[], int freq[], int size) 

{ 
	// إنشاء شجرة هوفمان
	struct MinHeapNode* root 
		= buildHuffmanTree(data, freq, size); 

	// طباعة ترميزات هوفمان باستخدام
	// شجرة هوفمان التي قد تم بناؤها
	int arr[MAX_TREE_HT], top = 0; 

	printCodes(root, arr, top); 
} 

// اختبار الدوال السابقة
int main() 
{ 

	char arr[] = { 'a', 'b', 'c', 'd', 'e', 'f' }; 
	int freq[] = { 5, 9, 12, 13, 16, 45 }; 

	int size = sizeof(arr) / sizeof(arr[0]); 

	HuffmanCodes(arr, freq, size); 

	return 0; 
}

• جافا:

import java.util.PriorityQueue; 
import java.util.Scanner; 
import java.util.Comparator; 

// البنية الرئيسية لكل عقدة موجودة في شجرة هوفمان
class HuffmanNode { 

	int data; 
	char c; 

	HuffmanNode left; 
	HuffmanNode right; 
} 

// يساعد هذا الصنف المقارن في إجراء المقارنة بين العقد بالاعتماد على إحدى خصائصها
// المقارنة هنا معقودة بين العقد بالاعتماد على قيم البيانات في العقدة
class MyComparator implements Comparator<HuffmanNode> { 
	public int compare(HuffmanNode x, HuffmanNode y) 
	{ 

		return x.data - y.data; 
	} 
} 

public class Huffman { 

	// دالة تعاودية تطبع ترميز هوفمان بواسطة
	// التنقل عبر شجرة هوفمان
	// المعامل الثاني في هذه الدالة يمثل ترميز هوفمان الذي تم إنشاؤه
	public static void printCode(HuffmanNode root, String s) 
	{ 

		// null الحالة الأساس. إن كانت الجهتان اليمنى واليسرى تساوي
		// فإن العقدة هي عقدة ورقية
		// ونطبع الترميز الذي تم إنشاؤه بواسطة التنقل عبر الشجرة
		if (root.left 
				== null
			&& root.right 
				== null
			&& Character.isLetter(root.c)) { 

			// c: يمثّل الحرف الموجود في العقدة
			System.out.println(root.c + ":" + s); 

			return; 
		} 

		// يضاف العدد 0 إلى الترميز إن اتجهنا إلى اليسار
		// يضاف العدد 1 إلى الترميز إن اتجهنا إلى اليمين

		// استدعاءات تعاودية للشجرتين الفرعيتين اليمنى واليسرى اللتين تم إنشاؤهما
		printCode(root.left, s + "0"); 
		printCode(root.right, s + "1"); 
	} 

	// الدالة الرئيسية
	public static void main(String[] args) 
	{ 

		Scanner s = new Scanner(System.in); 

		// عدد الحروف
		int n = 6; 
		char[] charArray = { 'a', 'b', 'c', 'd', 'e', 'f' }; 
		int[] charfreq = { 5, 9, 12, 13, 16, 45 }; 

		// إنشاؤ رتل أولوية
		// إنشاء كومة صغرى
		PriorityQueue<HuffmanNode> q 
			= new PriorityQueue<HuffmanNode>(n, new MyComparator()); 

		for (int i = 0; i < n; i++) { 
			// إنشاء كائن لعقدة هوفمان
			// وإضافته إلى رتل الأولوية
			HuffmanNode hn = new HuffmanNode(); 

			hn.c = charArray[i]; 
			hn.data = charfreq[i]; 

			hn.left = null; 
			hn.right = null; 

			تضيف الدالة عقدة هوفمان إلى الرتل
			q.add(hn); 
		} 

		// إنشاء عقدة الجذر
		HuffmanNode root = null; 

		// في هذه الحلقة التكرارية تستخرج أصغر قيمتين من الكومة في كل مرة
		// ويتقلّص حجم الكومة بمقدار 1 وتستمر الحلقة في عملها إلى أن
		// يصل حجم الكومة إلى 1 وتُستخرج جميع العقد
		while (q.size() > 1) { 

			// استخراج القيمة الأولى
			HuffmanNode x = q.peek(); 
			q.poll(); 

			// استخراج القيمة الثانية
			HuffmanNode y = q.peek(); 
			q.poll(); 

			// إنشاء عقدة جديدة
			HuffmanNode f = new HuffmanNode(); 

			// تساوي قيمة العقدة مجموع تردد العقدتين السابقتين
			f.data = x.data + y.data; 
			f.c = '-'; 

			// جعل العقدة المستخرجة الأولى عقدة بنوية يسرى
			// first extracted node as left child. 
			f.left = x; 

			// جعل العقدة المستخرجة الثانية عقدة بنوية يمنى
			f.right = y; 

			// جعل العقدة عقد جذر
			root = f; 

			// إضافة العقدة إلى رتل الأولوية
			q.add(f); 
		} 

		// طباعة الترميزات بالتنقل عبر الشجرة
		printCode(root, ""); 
	} 
}

التعقيد الزمني

يبلغ التعقيد الزمني لخوارزمية ترميز هوفمان المقدار O(nlogn)‎ وتمثّل n عدد الحروف الفريدة. إذا كان هناك n من العقد فإنّ الدالة extractMin()‎ ستستدعى 2‎*(n-1)‎ مرة. يبلغ التعقيد الزمني لعمل الدالة extractMin()‎ المقدار O(logn)‎ وذلك لأنها تستدعي الدالة minHeapify()‎؛ ولهذا يبلغ التعقيد الزمني الكلي المقدار O(nlogn)‎.

مصادر

• صفحة Huffman Coding في توثيق الخوارزميات في موقع GeeksforGeeks.