ホフマン符号

ホフマン符号化は無損データ圧縮アルゴリズムです。このアルゴリズムでは、異なる文字に対して可変長コードが割り当てられます。コードの長さは文字の使用頻度に関連しており、最も頻繁に使用される文字には最も短いコードが割り当てられ、最も頻繁に使用されない文字には長いコードが割り当てられます。

主に2つの部分があります。1つはホフマン木の作成、もう1つはその木を遍历してコードを検索します。

例えば、文字列「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（文字列）

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

出力-各文字のコード。

開始
　　　ホフマン木用のノードを定義します。ノードには文字、頻度、左子ノード、右子ノードがあります。
　　　各文字の頻度を保存するリスト‘freq’を作成し、最初はすべて0に設定します
　　　文字列の各文字cに対して
　　　　　　freqリストの文字chの頻度を増やします。
　　　完了
　　　すべての種類の文字chに対して
　　　　　　chの頻度がゼロでない場合、chとその頻度を優先キューQのノードとして追加します。
　　　完了
　　　while　Q　is　not　empty　do
　　　　　　Qからアイテムを削除して、ノードの左子ノードに割り当てます
　　　　　　Qからアイテムを削除して、ノードの右子ノードに割り当てます
　　　　　　割り当てられたコードを見つけるためにノードを traverses
　　　完了
終了

traverseNode（n：ノード、コード）

入力-ヒュッフマン木のノードn、および前回の呼び出しで割り当てられたコード　

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

if　left　child　of　node　n　≠　φ　then
　　　traverseNode(leftChild(n),　code+’0’)　//左子ノードを traverses
　　　traverseNode(rightChild(n),　code+’1’)　//右子ノードを traverses
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　{　//<　演算子はキューの中の優先度を検出するために使用されます
　　　　　　return　freq　>a.freq;
　　　}
　　　void　traverse(string　code　=　"")const{
　　　　　　if(child0!=NULL){
　　　　　　　　　child0->traverse(code+'0');　//コードを左子として0を追加する
　　　　　　　　　child1->traverse(code+'1);　//追加する　1　コードを右子として持つ
　　　　　　}else{
　　　　　　　　　cout << "Data: " << data << "，頻度: " << freq << "，コード: " << code << endl;
　　　　　　}
　　　}
};
void　huffmanCoding(string　str){
　　　priority_queue<node>　qu;
　　　int　frequency[256];
　　　for(int　i　=　0;　i<256;　i++)
　　　　　　frequency[i]　=　0;　//全ての頻度をクリアする
　　　for(int　i　=　0;　i<str.size();　i++{
　　　　　　frequency[int(str[i])]++;　//頻度を増加させる
　　　}
　　　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());　//キューから左子を取得して削除する
　　　　　　qu.pop();
　　　　　　node　*c1　= new node(qu.top());　//キューから右子を取得して削除する
　　　　　　qu.pop();
　　　　　　qu.push(node(c0,　c1));　//二つの子供の頻度を合計して、キューに再度追加する
　　　}
　　　cout << "The Huffman Code: " << endl;
　　　qu.top().traverse();　//ツリーを巡回してコードを取得する
}
main(){
　　　string str = "ACCEBFFFFAAXXBLKE";　//arbitray string to get frequency
　　　huffmanCoding(str);
}

出力結果

The　Huffman　Code：
データ：　K,　頻度：　1,　コード：　0000
データ：　L,　頻度：　1,　コード：　0001
データ：　E,　頻度：　2,　コード：　001
データ：　F,　頻度：　4,　コード：　01
データ：　B,　頻度：　2,　コード：　100
データ：　C,　頻度：　2,　コード：　101
データ：　X,　頻度：　2,　コード：　110
データ：　A,　頻度：　3,　コード：　111