問題タブ [huffman-code]

通話記録の長いリストにuser_idsをエンコードしようとしています。これらのレコードの中で最もスペースを占める部分は、発信者と受信者のシンボルです。最もアクティブな発信者に短い記号を割り当てるマップを作成します---これにより、ファイルの全体的なサイズ（したがってI / O時間）を抑えることができます。

各シンボルが何回使用されるかを事前に知っています---言い換えれば、相対的な確率分布を知っています。さらに、生成されるコードがハフマンコードのように「プレフィックスフリー」であることが重要ではありません。では、最高のエンコーディングスキーム、つまり、最も圧縮率が高く、迅速な実装が存在するものは何でしょうか。

答えは、圧縮スキームを指すだけでなく、そのエンコーディングスキームの実装も指す必要があります。

ハフマンコーディングの宿題に取り組んでいます。ハフマン アルゴリズムは既に完成していますが、バイナリ ファイルで動作するように少し変更する必要があります。関連する問題を読むのに時間を費やしましたが、おそらくデータ型とバイナリ ファイルの理解が不足しているため、まだ少し苦労しているので、以前の質問を繰り返さないことを願っています (関連するコードは投稿しません)プログラムのハフマン部分に）。

キー フレーズは次のとおりです。「コードワードにマップされる各シンボルは 4 バイトのバイナリ文字列であると想定できます。」そして、私が知っていると思うのは、Char は 1 バイトを表し、unsigned int は 4 バイトを表すということです。 、そのため、一度に入力 4 バイトを unsigned int バッファーに読み取ってから、プログラムのハフマン部分のデータを収集する必要があると推測しています。

これはデータを処理する良い方法のように見えますか? 1、2、または 3 バイトしか残っていない場合、ファイルの最後をどのように処理すればよいですか? そのため、バッファを unsigned int として構造体に格納しています。好奇心から、バッファを文字列に再キャストするにはどうすればよいですか?
編集:ハフマン圧縮ファイルのヘッダーを保存する最良の方法は何ですか?

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

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

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

ありがとう

私のプログラムはハフマン コードをchar[8]変数に格納します。unsigned char変数に格納したい。私はそれを行いますが、次のコードを使用してファイルを抽出したときに機能しなかったため、正しく機能するとは思いません。

ハフマン符号をファイルに保存したい。これどうやってするの？ハフマン コードを文字列に保存していますが、生成されたファイルのサイズが元のファイルよりも大きくなります。

コードでコメントアウトされた行に示されているように、structモジュールを使用してメソッドを試しましたが、うまくいきませんでした。基本的に2つのオプションがあります。コードごとにバイナリデータコードを記述するか（私のコードは3〜13ビットの長さのビットのシーケンスです）、n文字の文字列全体を変換します（この場合はn = 25000 +）。バイナリデータに。しかし、どちらの方法も実装する方法がわかりません。コード：

JTファイルを読み込もうとしています。JTファイルには、ハフマンアルゴリズムを使用して圧縮された情報が含まれている場合があります。ハフマンツリーを構築しているときに問題が発生しました。ノード間で使用する比較によっては、2つのシンボルの頻度が同じ場合に発生する実装にあいまいさがあり、順序が異なる場合があり、ツリーの一部のブランチが反転します。そのため、適切なハフマンツリーを構築できません。誰かが以前にこの問題に直面したことがありますか？これに対する解決策はありますか？

現在、大量のテキストを iPad に保存する必要があるアプリを開発しています。私の質問は、ハフマン符号化のようなアルゴリズムは実際に本番環境で使用されているのでしょうか? 非常に単純な圧縮アルゴリズムが必要なだけです (膨大な量のテキストはなく、より効率的な保存方法のみが必要です)。Huffamn のようなものは機能しますか? 他の種類の圧縮ライブラリを調べる必要がありますか?

上記のコードは、ハフマン ツリーを生成する必要があります。ただし、形成されるバイナリ ツリーは正しくありません。文字を含むすべてのノードはリーフまたは子のないノードである必要がありますが、一部のアルファベット ノードにはまだ子があります。コードの何が問題になっていますか?

ハフマン エンコーディング文字列をバイナリ python に変換する方法に問題があります。

この質問には、ハフマン アルゴリズムは関係ありません。

次のようになります。

エンコードされたハフマン文字列を取得できます01010101010。注、これは文字列です。

しかし今、文字列表現を実際のバイナリに保存したいと考えています。

ハフマンでエンコードされた文字列では、すべての 0 と 1 がbyteです。

私が欲しいのは、すべての 0 と 1 が少しです。

どうすればPythonでそれを行うことができますか?

編集1：

私の問題を十分に明確に説明していないことを許してください。

0 と 1 を 2 進数に書き込む現在のアプローチについて説明します。

たとえば、文字列 s='010101010' をコード化できます。

1. 私はintそれを整数に変換するために使用します
2. 次にunichr、それを文字列に変換して、ファイルに書き込むことができるようにします
3. 文字列をバイナリモードでファイルに書き込みます

また、ハフマン コードをデコードするには、ファイルを読み取る必要があります。

だから私のアプローチは、

1. ファイルからバイトを読み取る
2. それらをintに戻します
3. int をバイナリ表現文字列に変換します。
4. 文字列をデコードする

そして、ステップ 2で問題が発生し、私は無知になりました。

一部のハフマン文字列は短く ( のように10)、一部は長く ( 010101010101001) になる可能性があります。これにより、int値のバイト長が異なります(短い文字列には1バイトしかかからないものもあれば、長い文字列には2バイト以上かかるものもあります)

次のコードは、私の問題を示しています。

一部で秒単位で1 バイトずつ読み込んでいますが、これは実際には正しくありません。文字列10010101010は 2 バイトを占めるためです。

ファイルからそれらのバイトを読み取るとき、一度に何バイトを読み取る必要がありますか?