ハフマン符号化(Huffman Coding)理解+ハフマンツリー(Huffman Tree)構築方法

前言

実はこれは私がNOIP 2017の初戦の前にすでに学んだ(例年のNOIP初戦の問題を準備していたときに出会った)ことがありますが、ずっと役に立たなかったので、忘れてしまいました.の

ハフマン符号化

概要

ハフマン符号化(Huffman Coding)は、ホフマン符号化とも呼ばれ、符号化方式であり、ハフマン符号化は可変ワード長符号化(VLC)の一種である.ハフマンは1952年に、文字出現確率に完全に基づいて異字ヘッドの平均長が最も短い符号語を構築し、最適符号化と呼ばれる場合があり、一般的にハフマン符号化(ホフマン符号化とも呼ばれる場合もある)と呼ばれる符号化方法を提案した.

方法

栗を挙げることができます.今、電報があります.中には7文字(a 1 a 2 a 3 a 4 a 5 a 6 a 7)があります.それらの出現頻度はそれぞれU:(20 19 18 17 15 10 1)です.最小周波数の2文字a 6とa 7をそれぞれ「1」と「0」に指定し(誰に「1」と「0」を分けるかを気にする必要はない)、それらの周波数を加算して元のa 1~a 5群と併せて新たに並べ替える:(a 1 a 2 a 3 a 4 a 5 a 6′)U′:(20 19 18,17,15 11)a 5とa′6にそれぞれ「1」と「0」を指定すると、さらに周波数加算を行い、再び周波数順に並べ替えた:U〃:(26 20 19 18 17)U〃’:(35 26 20 19)U〃:(39 35 26)U〃:(61 39)最後にU〃〃を得るまで:(100)ヘフマン符号化の具体的な方法:まず出現した周波数サイズで並び、2つの最小の周波数を加算し、新しい周波数と残りの周波数として並び直す.最小の2つの周波数を加算し、最後に1つしか残っていないまで並び直します.加算するたびに加算される2つの周波数に「0」と「1」が与えられ、読み出し時にはこの記号から最後の「1」まで進み、ルート上で出会った「0」と「1」を最下位から最上位に順番に並べて、この記号のヘフマン符号化である.この過程は単純に果物を合併することと理解できる.そして、上記の例では、各文字の符号化は、a 1(01)、a 2(00)、a 3(111)、a 4(110)、a 5(101)、a 6(1001)、a 7(1000)である.これにより、文字の周波数が大きいほど、コード長が小さくなることを保証します.周波数が小さいほど、コード長が長くなります.

ハフマンの木

定義＃テイギ＃

n個の重み値をn個の葉の接点として与え、重み付き経路長(WPL)が最小に達すると、このような二叉木を最適二叉木と呼び、ハフマンツリー(Huffman Tree)とも呼ばれる.ハフマンツリーは,重み付き経路の長さが最も短いツリーであり,重み値の大きいノードは根に近い.

コンセプト

ハフマンツリーの定義に「重み付き経路長」があることを発見しましたが、これは何ですか?ゆっくり見てください.1、経路と経路の長さが1本の木の中で、1つのノードから下に到達できる子供や孫のノード間の通路を経路と呼ぶ.通路内の分岐の数を経路長と呼ぶ.所定のルートノードの層数が1であれば、ルートノードからL番目のレベルノードまでの経路長はL−1である.2、ノードの重み及び重み付き経路の長さ木のノードに何らかの意味を持つ数値を付与すると、この数値をそのノードの重みと呼ぶ.ノードの重み付きパスの長さは、ルートノードからノードまでのパスの長さとノードの重みの積です.3、木の重み付き経路長木の重み付き経路長は、全ての葉結点の重み付き経路長の和としてWPLと記す.木の重み付き経路長はWPL=(W 1*L 1+W 2*L 2+W 3*L 3+…+Wn*Ln)と表記され、N個の重みWi(i=1,2,...n)はN個の葉接点のある二叉木を構成し、対応する葉接点の経路長はLi(i=1,2,...n)である.

こうぞう

n個の重み値があると仮定すると,構築されたハフマンツリーにはn個の葉接点がある.n個の重み値をそれぞれw 1,w 2,...,wnとすると,ハフマンの木の構造規則は,(1)w 1,w 2,...,wnをn本の木がある森と見なす(木ごとに1つの接点しかない);(2)森の中で2つのルートノードの重み値が最も小さい木を選択し、1本の新しい木の左、右のサブツリーとして結合し、新しい木のルートノードの重み値はその左、右のサブツリーのルートノードの重み値の和である.(3)選択した2本の木を森から削除し、新しい木を森に加える.(4)(2)、(3)歩を繰り返し、森に木が1本しか残っていないまで、その木が求められたハフマンの木である.これにより,スタックを用いてO(nlog 2 n)O(nl o g 2 n)に最適化できる.

正確性

では、なぜこのようにして重み付き経路の長さを最小限に抑えることができるのでしょうか.実はこの証明は簡単です.最初はn個のリーフノードがあり,それらはいずれも重みWi(i=1,2,...n)を有し,それらを実点として記した.私たちが操作するたびに、aとbを選択し、a、bをそれぞれcの左右の息子にするように、2つの重み値が最も小さいルートノードを選択します.私たちはa、bの2本の木の中のすべての点の深さ+1に相当し、葉の結点の深さ+1にもなります.一方,a,bの2つのルートノードの重み値は,それぞれのサブツリーの葉接点の重み値に全権的に由来し,これはまたa,bのサブツリーにおける葉接点が将来解答を計算する際の係数(すなわち,それらの深さ)+1になるため,WPL+=w[a]+w[b]となる.最後に、私たちは常にn-1回の操作を行い、私たちは毎回最小の2つのwを取って答えを加えます...これは欲張るのではないでしょうか.しかし、ある操作で最小の2つを選ばないと、答えはもっと悪いことを証明することができます.例えば、3つの点a,b,cが設けられ、w[a]w[c]+w[e]>w[c]+w[d]>w[f]になるので、fはまたマージされます.厳密な数学の方法で証明するなら、私も大会がありません.どのdalaoが知っているかはコメントエリアで教えてください.の

かたわく

#include 
#include 
#define fs for(i=last[x];i;i=next[i])
struct myComp  
{  
    inline bool operator()(const int &a,const int &b){return w[a]multiset<int,myComp>s;// 
multiset<int,myComp>::iterator it;
int a,b,l[N],r[N];//l[i]、r[i] i 
void code(int x)
{
    int i;
    fs s.insert(tov[i]);
    while(s.size()>1)
    {
        it=s.begin();a=*it;s.erase(it);
        it=s.begin();b=*it;s.erase(it);
        w[++p]=w[a]+w[b];
        l[p]=a,r[p]=b;
        s.insert(p);
    }
    if(!s.empty())
    {
        it=s.begin();
        l[x]=*it;
        s.erase(it);
    }
    fs code(tov[i]);
}