【 情報 ハフマン木 】 ハフマン符号化では、なぜハフマン木を用いるのですか？ 例えばテキストデータ

【 情報 ハフマン木 】
ハフマン符号化では、なぜハフマン木を用いるのですか？

例えばテキストデータが「AABAAAECAABADAAABC」だった場合、
普通に出現回数の高い順に「A、B、C、D＝E」と並び替え、
出現回数が多い方から順番に「0、1、01、10」としてはいけないのでしょうか？

インターネットで検索をしたり、解説動画もみましたが、どうしても理解できませんでした。
どなたかわかりやすく教えて下さい。

No.1 回答者： Tacosan 回答日時： 2022/10/11 23:12

「0、1、01、10」だと出現する記号 (5種) に対して符号が 4種しかないからその時点で不適切だ. あとハフマン符号には「接頭符号である」という特徴があるがこれではそれも成り立たない. 例えば「01」という符号があったときに, これが「0 と 1 の 2つの符号からなる」ともとれるし「01 という 1つの符号である」と見ることもできて, これだけでは元に戻せなくなってしまう.

で本題.
あなたが質問文で挙げたようなデータならそれでいいんだけど, 一般にはうまくいかないことがある. 例えば
AAAABBBCCCDD
というテキストに対しては, 単純に出現回数によって
A → 0, B → 10, C → 110, D → 111
とするよりも
A → 00, B → 01, C → 10, D → 11
とした方が全体として符号が短くなる. 実際, 前者の符号化では (符号の区切りを空白で表すとして)
0 0 0 0 10 10 10 110 110 110 111 111
であるのに対し後者では
00 00 00 00 01 01 01 10 10 10 11 11
となる.