アルゴリズムと計算量の問題

各文字の符号語の長さは、その文字の葉の深さ（根からの辺の数）に等しい。したがって求めるビット数は
$$\sum (\text{出現回数})\times (\text{葉の深さ})$$
である。

木の構成 重みの小さい $2$ 本を順にまとめていく。

1. 重み $\{3,4,6,7,10,15\}$ から $3$（A）と $4$（B）をまとめて重み $7$ の木を作る。残りは $\{6,7,7,10,15\}$。
2. $6$（C）と重み $7$ の木 $1$ 本をまとめて重み $13$ の木を作る（重み $7$ の木は D と、A・B をまとめた木の $2$ 本があり、どちらを選んでもよい）。残りは $\{7,10,13,15\}$。
3. $7$ と $10$ をまとめて重み $17$。残りは $\{13,15,17\}$。
4. $13$ と $15$ をまとめて重み $28$。残りは $\{17,28\}$。
5. $17$ と $28$ をまとめて重み $45$。これで $1$ 本の木になる。

ビット数の計算 各文字の出現回数は、その葉の祖先にあたる内部頂点（まとめるたびに作った根）それぞれの重みに $1$ 回ずつ足し込まれている。祖先の内部頂点の個数は葉の深さに等しいので、ビット数は、まとめるたびに作った新しい木の重みの和に等しい。
$$7+13+17+28+45=110.$$

確認 手順 2 の選び方で木の形は $2$ 通りあるが、どちらも同じビット数になることを深さから直接確かめる。

(i) 手順 2 で C と D をまとめた場合：手順 3 で A・B の木（重み $7$）と E がまとまり、手順 4 で C・D の木と F がまとまる。各文字の深さは次のとおり。

$$3\cdot 3+4\cdot 3+6\cdot 3+7\cdot 3+10\cdot 2+15\cdot 2=9+12+18+21+20+30=110.$$

(ii) 手順 2 で C と A・B の木をまとめた場合：手順 3 で D と E がまとまり、手順 4 で A・B・C の木（重み $13$）と F がまとまる。各文字の深さは次のとおり。

$$3\cdot 4+4\cdot 4+6\cdot 3+7\cdot 2+10\cdot 2+15\cdot 2=12+16+18+14+20+30=110.$$

どちらの場合も $110$ となり、内部頂点の重みの和から求めた値と一致する。

よって答えは $110$。

重み $3,4,6,7,10,15$ でハフマン法を実行する。

1. $3+4=7$ → 残り $6,7,7,10,15$
2. $6+7=13$ → 残り $7,10,13,15$
3. $7+10=17$ → 残り $13,15,17$
4. $13+15=28$ → 残り $17,28$
5. $17+28=45$

符号化後の総ビット数は、各文字の（出現回数）×（符号長）の和で、これは併合で作った内部節点の重みの和に等しい: $7+13+17+28+45=110$。

検算（符号長）: 2 手目で重み 7 の木は $\{A,B\}$ の木か D のどちらか。例えば $6$ と D(7) を併合した場合: 符号長は F:2, E:3, {A,B}(7):3 → A,B は 4, C:3, D:3 ... 実際に計算すると F:2(15×2=30)、E:3(30)、C:3(18)、D:3(21)、A:4(12)、B:4(16) で $30+30+18+21+12+16=127$ にならないため整理し直す。

正しくは、手順 2 で 6 と併合するのは未併合の D(7) か {A,B}(7) のどちらでもよい（等しい重み）。{A,B}(7) と 6 を併合した場合: ({A,B},C)=13 → 3 手目 7(D)+10(E)=17 → 4 手目 13+15=28 → 5 手目 17+28=45。符号長: F=2, ({A,B},C) は深さ 2 で C=3, A,B=4, D=3, E=3。ビット数: F 15×2=30、C 6×3=18、A 3×4=12、B 4×4=16、D 7×3=21、E 10×3=30 で $30+18+12+16+21+30=127$。

これは内部節点の和 110 と合わないので再確認する。木は 根(45) → 子 17 と 28。17=D+E なので D,E は深さ 2。28 = 13(({A,B},C)) + F(15) なので F は深さ 2、13 は深さ 2、C は深さ 3、{A,B}(7) は深さ 3、A,B は深さ 4。したがって D:2, E:2, F:2, C:3, A:4, B:4。ビット数 $7\cdot 2+10\cdot 2+15\cdot 2+6\cdot 3+3\cdot 4+4\cdot 4=14+20+30+18+12+16=110$。上の 127 は深さの数え間違いだった。

よって総ビット数は $110$。