頻度が最初の 8 つのフィボナッチ数である次の文字の最適なハフマン コードは何ですか: a : 1、b : 1、c : 2、d : 3、e : 5、f : 8、g : 13、h : 21 ? 周波数が最初の n 個のフィボナッチ数である場合に最適なコードを見つけるためにケースを一般化します。
これは、私が抱えている割り当ての問題の 1 つです。私は率直な答えを求めているのではなく、いくつかのリソースを求めているだけです。
質問に答えるためにピースをまとめるにはどこを見ればよいですか?
12709 次
2 に答える
3
ハフマン コーディング アルゴリズムは、2 つの最小頻度ノードを取り、それらを接続して、頻度が子ノードの合計と等しい親を形成します。シンボルのランダムな頻度では、毎回組み合わせるために少なくとも2つのノードを計算する必要がありますが、頻度のフィボナッチ数列の場合、フィボナッチ数列の数列はハフマン符号化の数列と同じです。
例: - a : 1、b : 1、c : 2、d : 3、e : 5、f : 8、g : 13、h : 21
左に歪んだツリーまたは右に歪んだツリーを形成し、各シンボルのコーディングを簡単な式を使用して導き出すことができます
n がシンボルの数でない場合
= (n-2)*0 + 0
b = (n-2)*0 + 1
c = (n-3)*0 + 1
d = (n-4)*0 + 1
e = (n-5)*0 + 1
. . . 最後 = 1
上記の例では
a = (n-2)*0 + 0 = (6)*0 + 0 = 0000000
b = (6)*0 + 1 = 0000001
c = (5)*0 + 1 = 000001
.......
私はあなたがパターンを得ることを願っています
興味深いのは、平均ビット長の計算です
avg = ((n-1)*2 + sumof((n-i+1)*fib(i)) ここで、(3,n) の i)/(sumof(fib(i)) ここで、(1, n))
上記は直接式に簡略化できます。
于 2013-11-10T18:36:20.067 に答える
2
読む - http://en.wikipedia.org/wiki/Huffman_coding - 特に、「二分木は、左から右に最も確率の低い 2 つのシンボルを取り、それらを組み合わせて別の同等のシンボルを形成する」というフレーズに注意してください。 2 つのシンボルの合計に等しい確率。このプロセスは、シンボルが 1 つになるまで繰り返されます。」
上記はフィボナッチ数列とどのように関係していますか?
于 2013-11-09T21:06:07.360 に答える