情報源 は 4 個の記号 を、それぞれ次の確率で出力する。 符号記号を とする 3 元の語頭符号で の各記号を 1 個ずつ符号化するとき、1 記号あたりの平均符号長 （ は の符号語の長さ）の最小値を求めよ。
D 元ハフマン符号
記号数 が となるよう確率 0 のダミー記号を補って、 元（例: 3 元）のハフマン符号を構成し、平均符号長の最小値を求められる
前提
- ハフマン符号 （大学数学 情報理論・符号理論）
この技能までの道筋（23 技能）
読み込み中…
右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
一覧で見る（前提が先）
- 分数のたし算・ひき算 （算数 計算と数のきまり）
- 小数の四則計算 （算数 計算と数のきまり）
- 正負の数の加法・減法 （中学数学 数と式）
- 分数のかけ算・わり算 （算数 計算と数のきまり）
- 四則の混じった計算の順序 （算数 計算と数のきまり）
- 正負の数の乗除・累乗と四則混合 （中学数学 数と式）
- 約数の見つけ方 （算数 整数の性質）
- 素因数分解と約数の個数 （算数 整数の性質）
- 平方根の意味と根号の簡単化 （中学数学 数と式）
- 根号の乗除と加減 （中学数学 数と式）
- 指数の拡張と指数関数 （数学II 指数関数と対数関数）
- 語頭符号とクラフトの不等式 （大学数学 情報理論・符号理論）
- 対数の定義と性質 （数学II 指数関数と対数関数）
- 樹形図で数え上げる （算数 場合の数）
- 積の法則と和の法則 （算数 場合の数）
- 和の法則・積の法則と樹形図 （数学A 場合の数と確率）
- 順列・円順列・重複順列 （数学A 場合の数と確率）
- 組合せ （数学A 場合の数と確率）
- 確率の定義と和事象・余事象 （数学A 場合の数と確率）
- 期待値 （数学A 場合の数と確率）
- 確率変数と確率分布 （数学B 統計的な推測）
- エントロピー （大学数学 情報理論・符号理論）
- ハフマン符号 （大学数学 情報理論・符号理論）
説明
個の符号記号 を使う語頭符号（例: 3 元なら ）のうち、1 記号あたりの平均符号長 が最小になるものを作る方法です。2 元ハフマン符号では「確率の小さい 2 つをまとめる」操作をくり返しましたが、 元では「小さい 個をまとめる」操作をくり返します。ただし記号数 によっては最後にうまく 1 つにまとまりません。そこで、あらかじめ確率 のダミー記号を補って数をそろえます。電話のトーン信号や 3 値論理など、2 種類より多い記号で送る場面で使います。
なぜそうしてよいのか
元の符号語は、各節点から 本の枝（ラベル ）が出る木の葉に対応します。すべての内部節点がちょうど 個の子をもつ木（満ちた 分木）を考えます。根だけの木は葉が 1 個です。葉を 1 つ選んで 個の子に分けるたびに、葉は 個ずつ増えます。したがって、満ちた 分木の葉の数は必ず の形、つまり になります。逆向きに見ると、ハフマンの「 個を 1 個にまとめる」操作は 1 回ごとに個数を 減らします。最後にちょうど 1 個（根）で終わるには、最初の個数が でなければなりません。
記号数 がこの条件を満たさないとき、最適な符号の木には使われない枝が残ります。空いた枝が浅い位置にあれば、深い符号語をそこへ移して平均符号長を下げられます。また深い位置の空きが複数の節点に散らばっていれば、1 つの節点に寄せて符号語を短くできます。そのため、最適な符号では空きはすべて最も深い 1 つの節点の下に集まり、その数は 個以下です。この空きに確率 のダミー記号を置けば、満ちた 分木になります。ダミーは確率が なので に何も加えません。
あとは 2 元のときと同じ理屈が使えます。確率の小さい 個は、最も深い所で兄弟にできます。それらを 1 個（確率は和）にまとめると、記号数が 減った同じ形の問題になり、 の条件も保たれます。これをくり返して得られる符号が最適です。 は、まとめてできた節点（根を含む）の確率の総和に等しくなります。各記号の確率は、その記号から根までにある内部節点の数、つまり符号長 回だけ数えられるからです。
手順
補うダミーの個数 を決める: を満たす を選ぶ（ なら常に ）。
確率 のダミー記号を 個加え、全部で 個の記号を確率の小さい順に並べる。
確率の最も小さい 個をまとめて 1 つの節点にし、その確率を 個の確率の和とする。これを 1 個になるまでくり返す（毎回ちょうど 個まとめられる）。
木を根からたどり、各節点から出る 本の枝に を割り当てて符号語を読む。ダミーの符号語は使わない。
平均符号長 を計算する。検算として、まとめてできた節点の確率の総和と一致することを確かめる。
例題
情報源の 6 個の記号 がそれぞれ確率 で出る。3 元（符号記号 ）の語頭符号の平均符号長 の最小値を、3 元ハフマン符号を構成して求めよ。
例題の解答
手順1: なので である。 は なので、 となる は である。
手順2: 確率 のダミー を加えて 7 個にし、小さい順に並べる: 。
手順3: 小さい 3 個 をまとめて節点 （確率 ）を作る。残りは の 5 個になる。次に小さい 3 個 をまとめて節点 （確率 ）を作る。残りは の 3 個である。最後にこの 3 個をまとめて根（確率 ）とする。
手順4: 根から , , とする。 の下は , , とする。 の下は , とし、 は使わない。符号長は が 1、 が 2、 が 3 である。
手順5: となる。検算すると、まとめた節点の確率の和は で一致する。よって最小値は である。
答え:
よくある誤り
ダミーを補わずに小さい 3 個をまとめ始めてしまう誤り。例題でそうすると 、次に となり、最後は の 2 個しか残りません。根の枝が 1 本余り、 と最適でなくなります。正しくは先にダミー 1 個を補い、最小値は です。
ダミーの個数を「 を の倍数にする」と決めてしまう誤り。例えば で にしようと を補うと、まとめる操作で となり 1 個で終わりません。正しくは なので より です（）。
ダミーを最後の段階で補ったり、確率 でない記号として扱ったりする誤り。ダミーは最初に確率 として加えます。確率 なので最初の（最も深い）まとめに入り、 に寄与しません（）。ダミーの符号語は実際には使いません。
下限との比較で 2 を底とするエントロピーをそのまま使う誤り。 元符号では と比べます（ は底 2）。 なら を で割った値が下限です。
この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。
入口の問題
情報源 は 4 個の記号 を、それぞれ次の確率で出力する。この情報源を、符号記号 を用いる 3 元語頭符号で 1 記号ずつ符号化する。1 記号あたりの平均符号長 （ は の符号語の長さ）の最小値を、3 元ハフマン符号を構成して求めよ。
情報源 は 4 個の記号 を、それぞれ次の確率で出力する。符号記号を とする 3 元語頭符号で の各記号を符号化するとき、1 記号あたりの平均符号長 （ は の符号語の長さ）の最小値を求めよ。
この技能を使う問題
情報源記号 がそれぞれ確率
で独立に発生する無記憶情報源がある。この情報源の各記号に、符号アルファベット の語を符号語として割り当てる 3 元の瞬時符号（どの符号語も他の符号語の接頭語にならない符号）を考える。このような符号の平均符号長（1 記号あたりの符号語の長さの期待値）の最小値を求めよ。情報源 は 6 個の記号 を次の確率で出力する。
符号アルファベットを とする 3 元の瞬時符号（語頭符号）で の記号を 1 記号ずつ符号化するとき、1 記号あたりの平均符号長の最小値を求めよ。情報源記号 を、それぞれ確率
で独立に出力する無記憶情報源がある。各記号に、符号アルファベット の語を 対 に割り当てる 元の語頭符号（どの符号語もほかの符号語の語頭にならない符号）を考える。元の語頭符号のうち、 記号あたりの平均符号長 （ は の符号語の長さ）が最小になるものについて、その平均符号長 を求めよ。
情報源記号 を、それぞれ確率
で発生する記憶のない情報源がある。各情報源記号に、符号アルファベット の記号列（空でないもの）からなる符号語を つずつ割り当て、どの符号語もほかの符号語の接頭語にならないようにする（ 元の瞬時符号）。このような符号のうち、情報源記号 個あたりの平均符号長 （ は の符号語の長さ）の最小値を求めよ。