応用情報技術者 試験情報＆徹底解説

ハフマン符号化方式で二分木を作る際
まず最初にグループと出現確率を降順に並べてから作ると思います。
例えば下記にまとめたとして一番下から作っていくと思います。最初はECを加算して12
次にAECで24になると思いますが、図にする際にAECの図を作るときにAを左 ECを右 それをつなげてAECが真ん中、次にAECDを計算しますが図にするとDを右、AECを左 それをつなげて
AECDが真ん中となると思いますが、例えばAを右、ECを左、Dを左、AECを右などに逆にして作ってもいいのでしょうか？二分木で左右に振り分ける際のルールなどはありますか？
B 56%
D 20
A 12
E 8
C 4

> Aを右、ECを左、Dを左、AECを右などに逆にして作ってもいいのでしょうか？

はい，大丈夫です。
・左の子／右の子の位置を交換しても，
・左の子／右の子の位置は替えずに二分木の枝にそれぞれ割り当てる0/1を交換しても，
ハフマン符号化による効果は変わりません。

このパターンはどうでしょうAを右、ECを左、Dを右、AECを左などに逆にして作ってもいいのでしょうか？

組み方によっては1,0の割り当てがかわってくると思うのですが？大丈夫なのですか？

はい，大丈夫です。と No.2 で回答しました。

No.1の例において，出現確率が少ないものからペアにする操作は必ず次の(1)～(4)の順になります。

(1) 4%と8%をペアにする
(2) 12%と(4%＋8%)をペアにする
(3) 20%と(12%＋(4%＋8%))をペアにする
(4) (20%＋(12%＋(4%＋8%)))と56%をペアにする

この順でハフマン木を作成したのなら，左/右をどちらにしようが，0/1をどちらにしようが，ハフマン符号化による効果は変わりません。

具体例を挙げるなら，次のどの順でハフマン木を作っても，
Bが1bit長，Dが2bit長，Aが3bit長，EとCが4bit長になります。

(B, (D, (A, (C, E))))
(B, (D, (A, (E, C))))
(B, (D, ((C, E), A)))
(B, (D, ((E, C), A)))
(B, ((A, (C, E)), D))
(B, ((A, (E, C)), D))
(B, (((C, E), A), D))
(B, (((E, C), A), D))
((D, (A, (C, E))), B)
((D, (A, (E, C))), B)
((D, ((C, E), A)), B)
((D, ((E, C), A)), B)
(((A, (C, E)), D), B)
(((A, (E, C)), D), B)
((((C, E), A), D), B)
((((E, C), A), D), B)

念のため。例えば，
(B, (D, (A, (C, E)))) の規則でハフマン符号化したデータを
(((A, (E, C)), D), B) という別の規則で復号することはできません。

この投稿は投稿者により削除されました。(2024.09.25 11:17)