データ ファイルには、256 文字すべてがほぼ同じように 8 ビット文字のシーケンスが含まれています。最大文字頻度は、最小文字頻度の 2 倍未満です。この場合のハフマン符号化は、通常の 8 ビット固定長符号を使用するよりも効率的ではないことを証明してください。
2671 次
1 に答える
3
証明は直接です。文字が出現頻度の昇順でソートされていると仮定します。f(1) と f(2) が最初に結合されて f'(1) になることがわかっており、f(2) >= f(1) および 2*f(1) > f(256) であるため、これが勝ちました。 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(256) < 2*f(1) <= f'(1) および f'(128) <= 2*f(256) なので、f'(128) <= 2*f(256) ) < 4*f(1) <= 2*f'(1)。したがって、f'(128) < 2*f'(1)、
条件はこのラウンドで成り立つので、すべてのラウンドで同じように成り立つと主張するのは簡単です。Huffman は、すべてのノードが 1 つのルート (128、64、32、16、8、4、2、1) に結合されるまで 8 ラウンドを実行し、その時点でアルゴリズムが終了します。各段階で、各ノードは、その時点までにハフマン アルゴリズムによって同じ処理を受けた別のノードに結合されるため、ツリーの各ブランチは同じ長さ (8) になります。
これはやや非公式で、実際には証明というよりスケッチに近いものですが、より正式なものを書くには十分すぎるはずです。
于 2012-01-24T14:36:32.230 に答える