ハフマン符号化

ハフマン符号化は、可逆データ圧縮アルゴリズムです。このアルゴリズムでは、さまざまな文字を入力するために可変長コードが割り当てられます。コードの長さは、文字が使用される頻度に関連しています。最も頻度の高い文字のコードは最小で、頻度の最も低い文字のコードは長くなります。

主に2つの部分があります。最初の1つはハフマンツリーを作成し、もう1つはツリーをトラバースしてコードを検索します。

たとえば、いくつかの文字列「YYYZXXYYX」について考えてみます。文字Yの頻度がXより大きく、文字Zの頻度が最も低くなっています。したがって、Yのコードの長さはXよりも短く、XのコードはZよりも小さくなります。

• 頻度に応じて各文字にコードを割り当てるための複雑さは、O（n log n）

  です。

入力 −「ACCEBFFFFAAXXBLKE」などの異なる文字の文字列
出力 −さまざまな文字のコード：

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

アルゴリズム

huffmanCoding（string）

入力 −異なる文字の文字列。

出力 −個々の文字のコード。

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、および前の呼び出しから割り当てられたコード

出力 −各文字に割り当てられたコード

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

例

#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);
}

出力

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