データ構造とアルゴリズム-HuffmanツリーとHuffman符号化

ハフマンツリーは特殊な構造の二叉木であり、ハフマンツリーによって設計されたバイナリプレフィックス符号化であり、ハフマン符号化とも呼ばれ、通信分野で広く応用されている.word 2 vecモデルでは,階層Softmaxを構築する過程で,Huffmanツリーの知識も用いた.
通信では、送信された文字をバイナリ文字列に変換する必要があり、送信されたメッセージが「AFTERDATAEARAREAREARTAREA」であると仮定し、現在はそのメッセージを符号化する必要がある.

一、ハフマンの木の基本概念

ツリーには、以下に示すツリーについて、いくつかの基本的な概念があります.

パス

パスとは、ある木において、あるノードから別のノードへの分岐からなるパスであり、ノード8からノード1へのパスを下図に示す.

経路長

パス長はパス上のブランチの数を指し、上図ではパス長は2である.

ノードの重み

ノードの重みとは、図中の各ノードの値のように、ツリー内の各ノードに与えられた非負の値を指す.

ノードの重み付き経路長

ノードの重み付きパス長とは、ルートノードからノードまでのパス長とノードの重みの積を指します.たとえば、1ノードの重み付きパス長は:2です.

ツリーの重み付きパス長

ツリーの重み付きパスの長さは、すべてのリーフノードの重み付きパスの長さの和を指します.
このような概念があり、Huffmanツリーについては、次のように定義されています.
nの重み値をn個の葉ノードとして与え、1本の二叉木を構築し、この二叉木の重み付き経路長が最小に達すると、このような二叉木を最適二叉木と呼び、Huffman木とも呼ばれる.
以上の定義から分かるように,Huffmanツリーは重み付き経路長が最も小さい二叉木であり,上の二叉木に対してその構造が完成したHuffmanツリーは次のようになる.

二、ハフマンツリーの構築

上記のHuffmanツリーから分かるように,ノードの重みが小さいほど,ツリーのルートノードから遠くなる.では、ハフマンの木をどのように構築すればいいのでしょうか.上記のメッセージを例にとると、まず、各文字の出現回数をノードとして統計する必要がある.
次に、Huffmanツリーを構築します.

次の手順を繰り返します.

各ノードを重み値でソート:D-F-T-E-R-A

重み値が最も小さい2つのノードを選択し、ここではDとFのために新しいノードを生成し、ノードの重みはこの2つのノードの重みの和であり、2

である.

最後のルートノード

のみが残るまで
上記の手順に従って、このメッセージのHuffmanツリーの生成プロセスは次のとおりです.
ツリー内のノードの構造は次のとおりです.

#define LEN 512
struct huffman_node{
        char c;
        int weight;
        char huffman_code[LEN];
        huffman_node * left;
        huffman_node * right;
};

Huffmanツリーの構築手順は次のとおりです.

int huffman_tree_create(huffman_node *&root, map<char, int> &word){
        char line[MAX_LINE];
        vector<huffman_node *> huffman_tree_node;

        map<char, int>::iterator it_t;
        for (it_t = word.begin(); it_t != word.end(); it_t++){
                //  
                huffman_node *node = (huffman_node *)malloc(sizeof(huffman_node));
                node->c = it_t->first;
                node->weight = it_t->second;
                node->left = NULL;
                node->right = NULL;
                huffman_tree_node.push_back(node);
        }


        //  Huffman 
        while (huffman_tree_node.size() > 0){
                //  weight 
                sort(huffman_tree_node.begin(), huffman_tree_node.end(), sort_by_weight);
                //  
                if (huffman_tree_node.size() == 1){//  
                        root = huffman_tree_node[0];
                        huffman_tree_node.erase(huffman_tree_node.begin());
                }else{
                        //  
                        huffman_node *node_1 = huffman_tree_node[0];
                        huffman_node *node_2 = huffman_tree_node[1];
                        //  
                        huffman_tree_node.erase(huffman_tree_node.begin());
                        huffman_tree_node.erase(huffman_tree_node.begin());
                        //  
                        huffman_node *node = (huffman_node *)malloc(sizeof(huffman_node));
                        node->weight = node_1->weight + node_2->weight;
                        (node_1->weight < node_2->weight)?(node->left=node_1,node->right=node_2):(node->left=node_2,node->right=node_1);
                        huffman_tree_node.push_back(node);
                }
        }

        return 0;
}

ここで、map構造のwordは各文字が現れる頻度であり、ファイルから解析され、解析されたコードは:

int read_file(FILE *fn, map<char, int> &word){
        if (fn == NULL) return 1;
        char line[MAX_LINE];
        while (fgets(line, 1024, fn)){
                fprintf(stderr, "%s
", line);
                // ， 
                char *p = line;
                while (*p != '\0' && *p != '
'){
                        map<char, int>::iterator it = word.find(*p);
                        if (it == word.end()){//  ， 
                                word.insert(make_pair(*p, 1));
                        }else{
                                it->second ++;
                        }
                        p ++;
                }
        }
        return 0;
}

Huffmanツリーを構築した後、Huffmanツリーを巡回するには、先行巡回と中間巡回を使用します.先行巡回のコードは次のとおりです.

void print_huffman_pre(huffman_node *node){
        if (node != NULL){
                fprintf(stderr, "%c\t%d
", node->c, node->weight);
                print_huffman_pre(node->left);
                print_huffman_pre(node->right);
        }
}

中間パスのコードは次のとおりです.

void print_huffman_in(huffman_node *node){
        if (node != NULL){
                print_huffman_in(node->left);
                fprintf(stderr, "%c\t%d
", node->c, node->weight);
                print_huffman_in(node->right);
        }
}

得られた構造は上図の構造と一致した.

三、ハフマンツリーからハフマン符号化を生成する

上記のHuffmanツリーの構成により、Huffmanツリーを用いて各文字を符号化する必要がある.この符号化はHuffman符号化とも呼ばれ、Huffman符号化はプレフィックス符号化であり、1つの文字の符号化は別の文字符号化のプレフィックスではない.ここで約束します.

重み値の小さい最も左のノード、重み値の大きいものを右のノード

とする.

左子符号は0、右子符号は1

従って、上記の符号化形態は、下図のようになる.
上図から、Eノードの符号化は:00、同理、Dノードの符号化は1001
Huffman符号化の実現過程は以下の通りである.

int get_huffman_code(huffman_node *&node){
        if (node == NULL) return 1;
        //  ， 
        huffman_node *p = node;
        queue<huffman_node *> q;
        q.push(p);
        while(q.size() > 0){
                p = q.front();
                q.pop();
                if (p->left != NULL){
                        q.push(p->left);
                        strcpy((p->left)->huffman_code, p->huffman_code);
                        char *ptr = (p->left)->huffman_code;
                        while (*ptr != '\0'){
                                ptr ++;
                        }
                        *ptr = '0';
                }
                if (p->right != NULL){
                        q.push(p->right);
                        strcpy((p->right)->huffman_code, p->huffman_code);
                        char *ptr = (p->right)->huffman_code;
                        while (*ptr != '\0'){
                                ptr ++;
                        }
                        *ptr = '1';
                }
        }


        return 0;
}

上記のコードを使用して、テストの主な関数は次のとおりです.

int main(){
        //  
        FILE *fn = fopen("huffman", "r");
        huffman_node *root = NULL;
        map<char, int> word;
        read_file(fn, word);
        huffman_tree_create(root, word);
        fclose(fn);
        fprintf(stderr, "pre-order:
");
        print_huffman_pre(root);
        fprintf(stderr, "in-order:
");
        print_huffman_in(root);

        get_huffman_code(root);
        fprintf(stderr, "the final result:
");
        print_leaf(root);
        destory_huffman_tree(root);
        return 0;
}

print_leaf関数は、各リーフノードのHuffman符号化を印刷するために使用され、具体的には、以下のように実現される.

void print_leaf(huffman_node *node){
        if (node != NULL){
                print_leaf(node->left);
                if (node->left == NULL && node->right == NULL) fprintf(stderr, "%c\t%s
", node->c, node->huffman_code);
                print_leaf(node->right);
        }
}

destory_huffman_tree関数は、次のように具体的に実装されるHuffmanツリーを破棄するために使用されます.

void destory_huffman_tree(huffman_node *node){
        if (node != NULL){
                destory_huffman_tree(node->left);
                destory_huffman_tree(node->right);
                free(node);
                node = NULL;
        }
}

最終的な結果は次のとおりです.

参考文献

「大話データ構造」

「データ構造」(C言語版)