2

分散が最小のハフマン符号が望ましいことはよく知られています。私はポーランド語/英語のインターネット全体を掘り下げましたが、これが私が見つけたものです:最小の分散でハフマンコードを構築するには、次のいずれかの方法で関係を断ち切る必要があります(もちろん、ノードの確率が最も重要です):

  • 最短ツリーを表すノードを選択
  • 最も早く作成されたノードを選択します (開始時に作成されたリーフを考慮してください)。

問題は、これらの方法の正しさの証拠を見つけることができなかったことです。誰かがこれらのいずれかを証明できますか?

何でも喜んで明らかにします。

4

1 に答える 1

2

一部のシステムには、「同点の場合、ツリーの最大深度を最小化する選択を行う」よりもさらに強い制約があります。それらは、ツリーの最大深度に厳しい制限を設定します (長さ制限、最小分散ハフマンとも呼ばれます)。コーディング):

私の理解では、問題なく機能するハフマン符号語の長さを制限するためのヒューリスティック アルゴリズムがいくつか開発されていますが、ヒューリスティックが常に可能な限り最適な圧縮を提供するとは限りません。

何人かの人々が「最適な長さ制限されたハフマンコード」に言及しており、それらを見つけるためのアルゴリズムが複数存在するようです:

于 2019-08-01T04:59:58.107 に答える