0

私の問題は、100,000 以上の異なる要素があることです。私が理解しているように、ハフマンは、最も一般的な要素に 0 コードを割り当て、次の 10、次の 110、1110、11110 などを割り当てることで機能します。私の質問は、n 番目の要素のコードが n ビット長の場合、確かに 32 番目の項を通過したら、int などの 32 ビット データ型をそのまま送信する方がスペース効率が高いということです。方法論で何かを見逃していませんか？

あなたが提供できる助けに感謝します。私の現在の実装は、

code = (code << 1) + 2;

それぞれの新しいコードを生成する (これは正しいようです!) が、100,000 を超える要素をエンコードできる唯一の方法は、その場しのぎの新しいデータ型で int[] を使用することです。ここで、int から読み取る値にアクセスします。配列を 1 つの連続した長いシンボルとして... 32 ビットの int を転送するほどスペース効率が良くないのですか? それとも、ハフマンがプレフィックス コードを使用して、連続するビット ストリーム内の各一意の値を明確に決定できるケースですか?

ありがとう

4

2 に答える 2

2

あなたの理解は少しずれています-http://en.wikipedia.org/wiki/Huffman_codingを見てください。また、圧縮するには、エンコードされたビットをマシンワードにパックする必要があります。ハフマンでエンコードされたデータは、ビットストリームと考えるのが最適です。

于 2011-06-10T11:29:35.993 に答える
2

プレフィックス コードの原理を理解しているようです。

あなたが言及した100,000以上の異なる要素についてもう少し教えていただけますか?

実際、最速のプレフィックス コード (ユニバーサル コード) には、実際のシンボル周波数に関係なく、事前に生成できる一連のビット シーケンスが含まれます。あなたが言及したように、これらのコードを使用する圧縮プログラムは、最も頻繁な入力シンボルを最も短いビット シーケンスに関連付け、次に最も頻繁な入力シンボルを次に短いビット シーケンスに関連付けます。

あなたが説明するのは、特定の種類のプレフィックスコードである単項コーディングです。単項コーディング システムのもう 1 つの一般的なバリアントは、固定コード "1"、"01"、"001"、"0001"、"00001"、"000001" などに要素を頻度順に割り当てます。

一部の圧縮プログラムは、別の一般的なプレフィックス コードを使用します:エリアス ガンマ コーディング。Elias ガンマ コーディングでは、コードワードの固定セットに要素を頻度順に割り当てます。

1
010
011
00100
00101
00110
00111
0001000
0001001
0001010
0001011
0001100
0001101
0001110
0001111
000010000
000010001
000010010
...

32 番目の Elias ガンマ コードワードの長さは約 10 ビットで、32 番目の単項コードワードの長さの約半分です。100,000 番目の Elias ガンマ コードワードは、約 32 ビット長になります。

注意深く見ると、各 Elias ガンマ コードワードが 2 つの部分に分割できることがわかります。最初の部分は、おなじみの単項コードです。その単項コードは、その特定の Elias ガンマ コードワードの残りの部分で、あと何ビット続くかをデコーダに伝えます。

他にも多くの種類のプレフィックス コードがあります。多くの人は (紛らわしく) すべてのプレフィックス コードを「ハフマン コード」と呼んでいます。

特定のデータ ファイルを圧縮する場合、一部のプレフィックス コードは他のコードよりも圧縮率が高くなります。どちらを使用するかをどのように決定しますか？特定のデータ ファイルに最適なプレフィックス コードはどれですか?

ハフマン アルゴリズム (ハフマン度数表のオーバーヘッドを無視した場合) は、各データ ファイルに最適なプレフィックス コードを正確に選択します。実際のシンボル周波数に関係なく、事前に生成できる特異な「the」ハフマン コードはありません。通常、ハフマン アルゴリズムによって選択されるプレフィックス コードは、ファイルごとに異なります。

ハフマン アルゴリズムは、実際に 100,000 以上の一意の要素がある場合、あまりうまく圧縮されません。ハフマン度数表のオーバーヘッドが非常に大きくなるため、実際にはより優れた正味の圧縮を提供する他の「次善の」プレフィックス コードが見つかることがよくあります。または、まったく異なるデータ圧縮アルゴリズムが、アプリケーションでさらにうまく機能する可能性があります。

「ハフワード」の実装は、約 32,000 の一意の要素で動作するようですが、私が見たハフマン コードの実装の圧倒的多数は、約 257 の一意の要素 (256 の可能なバイト値とテキスト終了インジケータ) で動作します。 .

データを生の「非圧縮」形式でディスクに保存することを検討するかもしれません。(100,000 以上の固有の要素があるため、必然的にこれらの要素の多くを 3 バイト以上に格納することになります)。ハフマン圧縮のこれらの 257 値の実装は、そのファイルを圧縮できます。そのファイルのバイトを 256 の異なるシンボルとして再解釈します。

私の質問は、n 番目の要素のコードが n ビット長の場合、確かに 32 番目の項を通過したら、int などの 32 ビット データ型をそのまま送信する方がスペース効率が高いということです。方法論で何かを見逃していませんか？

プレフィックス コードの直観に反する特徴の 1 つは、一部のシンボル (レア シンボル) がより長いビット シーケンスに「圧縮」されることです。実際に 2^8 の一意のシンボル (考えられるすべての 8 ビットの数値) がある場合、コンプレッサーに 8 ビット以下に制限されたプレフィックス コードを使用させると、圧縮を行うことができなくなります。コンプレッサーがまれな値を拡張できるようにすることで (8 ビットで格納できることがわかっている珍しいシンボルを格納するために 8 ビットを超えるビットを使用するため)、コンプレッサーを解放して、より頻繁なシンボルを格納するために 8 ビット未満を使用できるようにします。 .

関連： 異なる数の最大数、ハフマン圧縮

于 2012-10-10T15:57:18.420 に答える