ترميز هوفمان

هو خوارزمية ضغط بيانات غير مفقودة. في هذه الخوارزمية، يتم تخصيص رموز طول متغير لكل حرف. طول الرمز يتعلق بتردد الحرف. الحرف الأكثر تردداً يحصل على أقصر رمز، بينما يستخدم رمز أطول للحرف الأقل تردداً.

هناك جزأين رئيسيين. الأول هو إنشاء شجرة Huffman، والآخر هو استكشاف الشجرة لتحديد الرموز.

على سبيل المثال، لنفكر في بعض النصوص 'YYYZXXYYX'، فإن تردد الحرف Y أكبر من X، وتردد Z الأدنى. لذلك، طول رمز Y أقصر من X، وأطول رمز X سيكون أقصر من Z.

• تعقيد توزيع الرموز بناءً على تردد كل حرف هو O(n log n)

الإدخال　- نص بأحرف مختلفة، مثل 'ACCEBFFFFAAXXBLKE'.
الإخراج　- رموز الأحرف المختلفة:

البيانات: K، التردد: 1، الرمز: 0000
البيانات: L، التردد: 1، الرمز: 0001
البيانات: E، التردد: 2، الرمز: 001
البيانات: F، التردد: 4، الرمز: 01
البيانات: B، التردد: 2، الرمز: 100
البيانات: C، التردد: 2، الرمز: 101
البيانات: X، التردد: 2، الرمز: 110
البيانات: A، التردد: 3، الرمز: 111

الخوارزمية

huffmanCoding (النص)

الإدخال- نص بأحرف مختلفة.

الإخراج- رمز كل حرف.

بداية
　　　تعريف عقدة تحتوي على حرف، وتردد، وأبناء اليسرى والأيمن للعقدة في شجرة Huffman.
　　　إنشاء قائمة 'freq' لتخزين تردد كل حرف، في البداية جميعها 0
　　　لفوائد كل حرف c في النص.
　　　　　　زيادة تردد الحرف ch في قائمة التردد.
　　　تم
　　　لجميع أنواع الحروف ch.
　　　　　　إذا كان تردد ch غير صفر فإن أضف ch و تردده كعقدة في مجموعة الأداء Q.
　　　تم
　　　بينما Q غير فارغة ففعل
　　　　　　remove item from Q and assign it to left child of node
　　　　　　remove item from Q and assign to the right child of node
　　　　　　traverse the node to find the assigned code
　　　تم
النهاية

traverseNode(n: نقطة، الكود)

الإدخال-نقطة الهوفمان n، وكود التخصيص المرسل في المرة السابقة　

الإخراج-كود تخصيص كل حرف

if left child of node n ≠ φ then
　　　traverseNode(leftChild(n), code+’0’) //traverse through the left child
　　　traverseNode(rightChild(n), code+’1’) //traverse through the right child
else
　　　عرض الأحرف والبيانات للنقطة الحالية.

مثال

#include<iostream>
#include<queue>
#include<string>
using namespace std;
struct node{
　　　int freq;
　　　char data;
　　　const node *child0, *child1;
　　　node(char d, int f = -1){ //assign values in the node
　　　　　　data = d;
　　　　　　freq = f;
　　　　　　child0 = NULL;
　　　　　　child1 = NULL;
　　　}
　　　node(const node *c0, const node *c1){
　　　　　　data = 0;
　　　　　　freq = c0->freq + c1->freq;
　　　　　　child0 = c0;
　　　　　　child1 = c1;
　　　}
　　　bool operator<(const node &a) const { //< operator performs to find priority in queue
　　　　　　return freq > a.freq;
　　　}
　　　void traverse(string code = "")const{
　　　　　　if(child0!=NULL){
　　　　　　　　　child0->traverse(code+'0'); //add 0 with the code as left child
　　　　　　　　　child1->traverse(code+'1'); //add 1 with the code as right child
　　　　　　}else{
　　　　　　　　　cout << "Data: " << data << ", Frequency: " << freq << ", Code: " << code << endl;
　　　　　　}
　　　}
};
void huffmanCoding(string str){
　　　priority_queue<node> qu;
　　　int frequency[256];
　　　for(int i = 0; i<256; i++)
　　　　　　frequency[i] = 0; //clear all frequency
　　　for(int i = 0; i<str.size(); i++){
　　　　　　frequency[int(str[i])]++; //increase frequency
　　　}
　　　for(int i = 0; i<256; i++){
　　　　　　if(frequency[i]){
　　　　　　　　　qu.push(node(i, frequency[i]));
　　　　　　}
　　　}
　　　while(qu.size() > 1){
　　　　　　node *c0 = new node(qu.top()); //get left child and remove from queue
　　　　　　qu.pop();
　　　　　　node *c1 = new node(qu.top()); //get right child and remove from queue
　　　　　　qu.pop();
　　　　　　qu.push(node(c0, c1)); //add freq of two child and add again in the queue
　　　}
　　　cout << "The Huffman Code: " << endl;
　　　qu.top().traverse(); //traverse the tree to get code
}
main(){}
　　　string str = "ACCEBFFFFAAXXBLKE"; //arbitray string to get frequency
　　　huffmanCoding(str);
}

نتائج الخروج

الكود الهوفمان:
البيانات: K، التردد: 1، الرمز: 0000
البيانات: L، التردد: 1، الرمز: 0001
البيانات: E، التردد: 2، الرمز: 001
البيانات: F، التردد: 4، الرمز: 01
البيانات: B، التردد: 2، الرمز: 100
البيانات: C، التردد: 2، الرمز: 101
البيانات: X، التردد: 2، الرمز: 110
البيانات: A، التردد: 3، الرمز: 111