逆ハフマンのアルゴリズムですか？

Question

ハフマンのエンコーディングに問題がありますが、その解決方法やハフマンの逆のエンコーディングであるかどうかはわかりません。しかし、それは間違いなく貪欲なアプローチを使って解決することができます。

---

それぞれの確率に関連付けられた長さのセットを考えてみましょう。即ち

X={a1=(100,1/4),a2=(500,1/4),a3=(200,1/2)} 

は明らかに、すべての確率の総和= 1

は、出発点から他の後の行いずれかに一緒に長さをアレンジ。

例：{a2,a1,a3}この順番で最初から最後まで。

要素のコストを、開始線からこの要素の終わりまでの合計の長さに確率で乗じて定義します。前の配置からそう

：

cost(a2) = (500)*(1/4) 
cost(a1) = (500+100)*(1/4) 
cost(a3) = (500+100+200)*(1/2) 

は、すべてのコストの和としてトータルコストを定義します。例えばcost(X) = cost(a2) + cost(a1) + cost(a3)。 cost(X)

---

を最小限に抑え配置を見つけるアルゴリズムを与える私はいくつかの代替ハフマン木を形成しようとしましたが、それは動作しません。

確率でソートすると失敗します（X = {（100,0.4）、（300,0.6）}と考える）。

長さによるソートも失敗します（X = {（100,0.1）、（300,0.9）}と考える）。

誰かが最適な解法アルゴリズムを助けることができれば、それは素晴らしいことです。

Answer 1

隣接する2つの要素を入れ替えるとどうなるか考えてみましょう。 2つの要素の前後の計算は同じであるため、2つの要素にのみ依存します。

コストがP1L1 + P2（L1 + L2）とP2L2 + P1（L1 + L2）です。あなたがL1/P1 < L2/P2のときに1を最初に入れ替えたいと思ったら、これを減算して代数を正しくしたら単純化してください。チェック - これは少なくともL1 = 0のとき正しい答えを得ます。

Li/Piの昇順に要素をソートしたいと思うので、そうでない場合、隣接する要素をスワップすることで答えを改善することができます要素。