9

私のアルゴリズムの教科書から：

毎年開催される郡競馬には、互いに競ったことのない 3 頭のサラブレッドが参加します。興奮して、あなたは彼らの過去 200 レースを研究し、これらを 4 つの結果 (1 位 (「1 位」)、2 位、3 位、その他) の確率分布として要約します。

                       Outcome     Aurora   Whirlwind    Phantasm
                        first        0.15      0.30          0.20

                        second       0.10      0.05          0.30

                        third        0.70      0.25          0.30

                        other        0.05      0.40          0.20

一番予想しやすい馬は？この問題に対する定量的なアプローチの 1 つは、圧縮率を調べることです。各馬の履歴を 200 個の値 (1 位、2 位、3 位、その他) の文字列として書き留めます。これらの実績文字列をエンコードするために必要なビットの総数は、ハフマンのアルゴリズムを使用して計算できます。これは、Aurora では 290 ビット、Whirlwind では 380 ビット、Phantasm では 420 ビットになります (チェックしてください!)。Aurora はエンコードが最も短いため、強い意味で最も予測可能です。

彼らはどのようにしてファンタズムの 420 を得たのですか? 私は400バイトを取得し続けます:

最初に結合、その他 = 0.4、2 番目、3 番目に結合 = 0.6。各位置をエンコードする 2 ビットで終了します。

ハフマン符号化アルゴリズムについて誤解しているものはありますか?

教科書はこちらから入手できます: http://www.cs.berkeley.edu/~vazirani/algorithms.html (156 ページ)。

4

1 に答える 1

5

おっしゃる通りです。Phantasm の 200 の結果は、400 ビット (バイトではありません) を使用して表すことができます。Aurora は 290、Whirlwind は 380 が正しいです。

正しいハフマン コードは、次の方法で生成されます。

  1. 0.2 と 0.2 の 2 つの最も可能性の低い結果を組み合わせます。0.4 を取得します。
  2. 次の 2 つの最も可能性の低い結果を組み合わせます: 0.3 と 0.3。0.6 を取得します。
  3. 0.4 と 0.6 を組み合わせます。1.0 を取得します。

代わりにこれを行うと、420 ​​ビットが得られます。

  1. 0.2 と 0.2 の 2 つの最も可能性の低い結果を組み合わせます。0.4 を取得します。
  2. 0.4 と 0.3 を結合します。(違います!) 0.7 を取得します。
  3. 0.7 と 0.3 を結合します。1.0 を取得
于 2010-06-10T16:18:11.303 に答える