データファイルには、すべての256文字がほぼ共通であるような8ビット文字列が含まれています。最大文字数は最小文字数の2倍未満です。この場合のハフマン符号化は、通常の8ビット固定長符号を使用するより効率的ではないことを証明する。ハフマン符号化が8ビットシーケンスであることを証明する
-2
A
答えて
3
証明は直接です。仮定する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ラウンドを実行し、その時点でアルゴリズムは終了する。各段階で各ノードがハフマンアルゴリズムによって同じ処理を受けた別のノードに結合されているため、ツリーの各ブランチは同じ長さを持ちます:
これはやや非公式です証拠よりもスケッチのほうが、実際にはより正式なものを書くのに十分なはずです。
関連する問題
- 1. ハフマン符号化のトラバーサル符号化
- 2. 固定長符号化を生成するハフマン符号
- 3. matlabのハフマン符号化(バイナリ値)
- 4. ハフマン符号化で文字列を解凍するには?
- 5. ハフマン符号化の値を保存するには
- 6. GSM 8ビットデータ符号化
- 7. 画像圧縮を考慮すると、ランレングス符号化は常にハフマン符号化より優れていますか?
- 8. アポストロフィを符号化する
- 9. 暗号化証明書
- 10. Javaツリーの枝を走査してビットコードを生成する再帰的メソッドを実装する(ハフマン符号化)
- 11. 教科書のハフマン符号化アルゴリズムを使用して、どのファイルの圧縮率が良いですか?
- 12. 8ビット符号なしPCMを8ビット符号付きPCMに変換
- 13. 符号化シルベスターシーケンス
- 14. ルビーと符号化変換
- 15. android.util.Base64フラグを符号化/復号化する
- 16. X509証明書の暗号化/復号化
- 17. wavをmp3に符号化するアルゴリズム
- 18. ModelState.AddModelErrorがHTMLを符号化します
- 19. 符号化のキャリッジリターン
- 20. 符号化ImplodeでTWIG
- 21. PHPで急なアクセント記号を符号化する
- 22. 引用符で囲まれたprintableとしてMIMETextを符号化する
- 23. ハフマン符号化はどのようにしてdct係数から画像(jpeg)を構成しますか?
- 24. 復号Outlook証明書Androidデバイスの暗号化メールを使用する
- 25. x509証明書と暗号化を使用したデジタル署名
- 26. アクセント符号化でSpreadsheet_Excel_Reader(PHPExcelReader)が失敗する
- 27. Rubyフィード解析:「入力が適切ではありませんUTF-8、符号化してください!
- 28. NSCodingで符号化/復号化を倍増
- 29. Pythonバイトを「符号なし8ビット整数」に変換する
- 30. 符号なしの値を処理していることがわかるたびに「符号なし」を使用する必要がありますか?
どこにいるのですか?これまでのあなたの考えは何ですか?問題にどのようにアプローチしたのですか? –
実際、私はその質問をあまり理解していませんでした。私は256文字または8だけの周波数を考慮する必要がありますか? –
これは、8ビットのバイトが合計256文字のドメインを表しているということです(今日の世界では時代遅れです)。本質的には、これらのバイトの値の頻度は、多かれ少なかれ均等な分布を有するので、それらを表現するためにハフマンツリーで使用されるビットシーケンス、またはバイト値自体と同じ長さになる。また、ファイルをデコードできるようにツリーを保存する必要があります。ハフマンエンコーディングについてもう少し詳しくお読みください! –