Thuật toán mã hóa Huffman

Mã hóa Huffman là một thuật toán nén dữ liệu không mất dữ liệu. Trong thuật toán này, một mã có độ dài thay đổi được chỉ định để nhập các ký tự khác nhau. Độ dài mã liên quan đến tần suất các ký tự được sử dụng. Các ký tự thường gặp nhất có mã nhỏ nhất và mã dài hơn cho các ký tự ít thường xuyên nhất.

Chủ yếu có hai phần. Đầu tiên là tạo một cây Huffman và một khác để đi qua cây để tìm mã.

Ví dụ, hãy xem xét một số chuỗi “YYYZXXYYX”, tần số của ký tự Y lớn hơn X và ký tự Z có tần suất ít nhất. Vì vậy, độ dài của mã cho Y nhỏ hơn X và mã cho X sẽ nhỏ hơn Z.

Độ phức tạp để gán mã cho mỗi ký tự theo tần số của chúng là O (n log n)

Đầu vào và Đầu ra

Input:
A string with different characters, say “ACCEBFFFFAAXXBLKE”
Output:
Code for different characters:
Data: K, Frequency: 1, Code: 0000
Data: L, Frequency: 1, Code: 0001
Data: E, Frequency: 2, Code: 001
Data: F, Frequency: 4, Code: 01
Data: B, Frequency: 2, Code: 100
Data: C, Frequency: 2, Code: 101
Data: X, Frequency: 2, Code: 110
Data: A, Frequency: 3, Code: 111

Thuật toán

huffmanCoding (chuỗi)

Đầu vào: Một chuỗi có các ký tự khác nhau.

Đầu ra: Các mã cho từng ký tự riêng lẻ.

Begin
   define a node with character, frequency, left and right child of the node for Huffman tree.
   create a list ‘freq’ to store frequency of each character, initially, all are 0
   for each character c in the string do
      increase the frequency for character ch in freq list.
   done

   for all type of character ch do
      if the frequency of ch is non zero then
         add ch and its frequency as a node of priority queue Q.
   done

   while Q is not empty do
      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
   done
End

traverseNode (n:nút, mã)

Đầu vào: Nút n của cây Huffman và mã được gán từ lần gọi trước

Đầu ra: Mã được gán với từng ký tự

if a 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
   display the character and data of current node.

Ví dụ

#include
#include
#include
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: "< qu;
   int frequency[256];

   for(int i = 0; i<256; i++)
      frequency[i] = 0; //clear all frequency

   for(int i = 0; i1) {
      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 <<"Mã Huffman:" <

Đầu ra

The Huffman Code:
Data: K, Frequency: 1, Code: 0000
Data: L, Frequency: 1, Code: 0001
Data: E, Frequency: 2, Code: 001
Data: F, Frequency: 4, Code: 01
Data: B, Frequency: 2, Code: 100
Data: C, Frequency: 2, Code: 101
Data: X, Frequency: 2, Code: 110
Data: A, Frequency: 3, Code: 111