教えてください

りょうさん  
(No.1)
ハフマン符号化方式で二分木を作る際
まず最初にグループと出現確率を降順に並べてから作ると思います。
例えば下記にまとめたとして一番下から作っていくと思います。最初は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
2024.09.18 11:59
jjon-comさん 
AP プラチナマイスター
(No.2)
> Aを右、ECを左、Dを左、AECを右などに逆にして作ってもいいのでしょうか?

はい,大丈夫です。
・左の子/右の子の位置を交換しても,
・左の子/右の子の位置は替えずに二分木の枝にそれぞれ割り当てる0/1を交換しても,
ハフマン符号化による効果は変わりません。
2024.09.18 14:32
りょうさん  
(No.3)
このパターンはどうでしょうAを右、ECを左、Dを右、AECを左などに逆にして作ってもいいのでしょうか?

組み方によっては1,0の割り当てがかわってくると思うのですが?大丈夫なのですか?
2024.09.18 14:39
jjon-comさん 
AP プラチナマイスター
(No.4)
はい,大丈夫です。と 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.18 20:00
harumaruさん 
(No.5)
この投稿は投稿者により削除されました。(2024.09.25 11:17)
2024.09.25 11:17

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの投稿はできません。

その他のスレッド


Pagetop