ツリー、すべてのバイトのエンコードされた値、エンコードされたテーブルとデコードされたテーブル、エンコードされたファイルのバイナリ ファイルにエンコードされたファイルがあります。2 つの質問があります。十分なはずですか？そして、デコードテーブルとエンコードされたファイルをどのタイプのファイルに保存する必要がありますか? 私はJavaを使用しています。
1 に答える
1
正規ツリーを生成する場合、エンコードされていない値の順に、各バイトのコードの長さを格納するだけで済みます。ハフマン コードの最大長は個別のエンコードされていない値の数であり、最小長は 1 であるため、各長さは 1 バイトに収まります。(gzip ライブラリは、オーバーヘッドをさらに削減するために長さをハフマン エンコードします。)
コードが標準的であると仮定して、長さのリストから完全なツリーを生成する簡単なアルゴリズムがあります。
実際には、少なくとも 2 つの正規のエンコーディング スタイルが考えられます。どちらの場合も、指定された長さのコードは、元のエンコードされていないバイトと同じ順序になります。ウィキペディアで説明されている標準的なコードでは、短いコードは長いコードの前に配置されます (つまり、最短のコードはすべてゼロです。しかし、より一般的な標準的な形式では、長いコードを先頭に配置するため、最長のコードはすべてゼロになります。ウィキペディアの記事には、標準コーディングの形式を生成するためのアルゴリズム; もう 1 つの形式は同様に単純です。
最長コード優先形式の利点は、任意のコードの最後のビットのみが非ゼロ (はアルファベット サイズ) であることを実証できることです。言い換えれば、各コードは、いくつかのゼロビットとそれに続くゼロと1の混合の最大1「バイト」で構成されます。このプロパティは、デコードを高速化するのに役立ちます。ceil(log2n)n
于 2013-04-14T19:10:15.833 に答える