ハフマン符号化が8ビットシーケンスであることを証明する

Question

データファイルには、すべての256文字がほぼ共通であるような8ビット文字列が含まれています。最大文字数は最小文字数の2倍未満です。この場合のハフマン符号化は、通常の8ビット固定長符号を使用するより効率的ではないことを証明する。

Answer 1

証明は直接です。仮定するw.l.o.g.文字は周波数の昇順にソートされます。 f（1）とf（2）は最初にf '（1）に結合され、f（2）> = f（1）と2 * f（1）> f f（256）が何かと結合されるまで結合されません。同様に、f（3）とf（4）はf '（2）> = f'（1）> f（256）でf '（2）に結合されます。このように続けて、f（253）とf（254）をf '（127）> =>> = f'（1）> f（256）にまとめる。最後に、f（255）とf（256）は、f '（128）> = f'（127）> = ...> = f '（1）に結合される。 f '（128）< = 2 * f（256）= f'（1）およびf '（128）< = 2 * f（256） （1）< = 2 * f '（1）。 Ergo、f '（128）< 2 * f'（1）は、ハフマンアルゴリズムの第1ラウンドで保持されたのと同じ条件です。

このラウンドでは条件が成立するため、同様にすべてのラウンドを保持すると主張するのは簡単です。ハフマンは、すべてのノードがルート（128,64,32,16,8,4,2,1）に結合されるまで8ラウンドを実行し、その時点でアルゴリズムは終了する。各段階で各ノードがハフマンアルゴリズムによって同じ処理を受けた別のノードに結合されているため、ツリーの各ブランチは同じ長さを持ちます：

これはやや非公式です証拠よりもスケッチのほうが、実際にはより正式なものを書くのに十分なはずです。