以下の説明は、package-merge を使用した長さ制限のあるハフマン コードに関する Wikipedia からの説明です。理解できません、これについていくつか質問があります。
任意のコード ワードに許容される最大長をLとします。p 1 , …, p nを、エンコードするアルファベットのシンボルの周波数とします。まず、シンボルをp i ≤ p i +1 になるように並べ替えます。額面単位 2 -1 , …, 2 -<em>LのシンボルごとにL個のコインを作成し、それぞれの貨幣価値p iを作成します。package-merge アルゴリズムを使用して、額面の合計が n − 1 である最小貨幣価値のコインのセットを選択します。h iを貨幣価値p iのコインの数とします。選択されました。長さが制限された最適なハフマン コードは、シンボルiを長さh iのビット文字列でエンコードします。」
ハフマン コードを作成する別の方法かもしれません。http://cbloomrants.blogspot.com/2010/07/07-02-10-length-limitted-huffman-codes.htmlを見ましたか? IMOパッケージマージアルゴリズムはハフマンツリーを構築していません。ゴロム コードを探します。
はい、コードワードの長さに制限があるハフマン コードを作成する方法にすぎません。
ハフマン コードは、アルファベットのすべての文字を一意に決定できるバイナリ文字列でエンコードします。たとえば、アルファベットが {A, B, C} で、A が B や C よりも一般的である場合、次のエンコーディングがうまく機能します。
A - 0
B - 10
C - 11
0010110 などのエンコードされた文字列は、エンコード ビット文字列の長さがハフマン コードによって既に定義されているため、一意にエンコードできます (ここでは --- 0 で始まるすべての文字列の長さは 1 であり、1 で始まるすべての文字列の長さは2)。したがって、文字列は 0|0|10|11|0 = AABCA にデコードされます。
ここで、ハフマン コードを構築する際の「問題」は、結果として得られるエンコーディングが平均してできるだけ短くなるように、エンコーディング ビット文字列を選択する方法です。あなたの問題には、コードワードの長さがLを超えることができないという追加の制約があります。一般的な考え方は、より一般的なシンボルをエンコードするために短い文字列を使用することです。
package-merge アルゴリズムの詳細は重要ではありません。重要なのは、アルゴリズムを使用して「額面の合計がn - 1 である最小貨幣価値のコインのセット」を選択することです。額面 2 −1、2 −2、... の硬貨があり、それらから合計 100 セントの価値を構築したい場合、このプロセスは、最初に価値 100 の硬貨を用意し、次に分割することと考えることができます。それを 2 つの 50 セント (2 −1 ) にし、その後、コインを好きなだけ半分に分割し続けます (例: 50 セント + 25 セント + 12.5 セント + 12.5 セント)。これは、バイナリ ツリーの構築に対応します。コインを分割するたびに、バイナリ ツリーに内部ノードを作成し、1 レベル深いレベルに 2 つの葉を追加します。
ここで、貨幣価値を最小化するという考えは、「より高い頻度」のシンボルにリンクされている「コイン」は使用するのにより高価であるため、より短いコードを持つことに対応して、それらのコインをより少なく分割したいということです。
詳細は、読者への演習として残されています。