問題タブ [huffman-code]

私はハフマンデコーダーを実装しようとしてきましたが、最初の試みでは、デコードアルゴリズムの選択が最適ではなかったため、パフォーマンスが低下していました。

テーブルルックアップを使用してハフマンデコードを実装しようと思った。しかし、私はサブテーブルの生成に少しこだわっており、誰かが私を正しい方向に向けてくれることを望んでいました。

プレフィックス コードは、コードが別のコードのプレフィックスではないコードのセットです。たとえば、次のセットはプレフィックス コードです。

n = 8メンバーと。これらは通常、ある種のハフマン木で作成されていると思います。

私の質問は次のとおりです。「n」個のメンバーを持つバイナリ プレフィックス コードを生成する関数を作成するのを手伝ってくれませんか?

このようなもの：

list<int> GenerateBinaryPrefixCodes(int n);

また、必要条件は、ビットの合計が最小化されるという意味で「最適」であることです。

C/C++/C#/似たようなものでの回答を希望します。これは実際には宿題ではありませんが、良いハードウェアの問題になりそうなので、そのようにタグ付けしました。

ありがとう！

私はここでさまざまなことを試してきましたが、うまくいかないようです。入力は「abbcccddddeeeee」で、リンクされたリスト a、b、c、d、e がそれぞれ頻度 1、2、3、4、5 で返されます。

ただし、何らかの理由で、実行したさまざまなテストに基づいて、次のツリーが表示されるようです。

誰かが私を助けてくれたら最高です。私は信じられないほど、信じられないほどイライラしています。

ありがとうございました！

だから現在、私はハフマン木を作成するプログラムを持っています。ツリーは、次のフィールドを持つ「H ノード」で構成されます。ノードに含まれる文字)。

リンク リストからノードを追加してハフマン ツリーを作成しました。ツリーが正しく作成されたことはわかっています。ツリーを作成するときに、親ノードを指定したときにノードに伝えました。それが親の「右」の場合、そのコード文字列は 1 で、左の場合は 0 です。ただし、明らかにツリー全体が作成された後、各ノードは0 か 1 のどちらかしかありませんが、まだ 00100101 のような文字列はありません。私の質問は、このツリーを取得したので、それをたどることができますか? 各子に親のコードと子自身のコードを与えるという考えは理解していますが、これを達成するためにツリーをループする方法がわかりません。

前もって感謝します。

多数の文字列を管理するアプリケーションがあります。文字列はパスのような形式で、多くの共通部分がありますが、明確なルールはありません。それらはファイルシステム上のパスではありませんが、そのように考えることができます。メモリ消費を最適化する必要があることは明らかですが、パフォーマンスを大幅に犠牲にすることはありません。

私は 2 つのオプションを検討しています: -データを zip 形式で保存
するクラスを実装しますが、固定の辞書が必要で、現在このためのライブラリを見つけることができません。compressed_stringバイトではなく、言葉でハフマンが欲しい。
- 文字列部分にある種のflyweightパターンを実装します。

この問題は一般的な問題のように見えますが、それに対する最善の解決策は何か、またはこの問題を対象とするライブラリを誰かが知っているかどうか疑問に思っています。

ありがとう

Java でハフマン エンコーディング アルゴリズムを実装しました。プライオリティ キューを使用して、ルートからリーフまでツリーをトラバースし、シンボルが入力に現れる回数に基づいて #=000011 としてエンコーディング例を取得します。すべて問題なく、ツリーは正常に構築されており、エンコーディングは期待どおりです。しかし、取得している出力ファイルは元のファイルよりもサイズが大きくなっています。現在、ツリーの左側のノードと右側のノードをトラバースするときに、文字列に「0」と「1」を追加しています。おそらく、最終的には各文字に 8 ビットすべてを使用することになり、圧縮には役立ちません。これらのビットを必要な文字値に変換する必要があると推測しています。これらの文字が使用するビット数が 8 より少ないため、元のファイルの圧縮バージョンが得られます。Javaで文字を操作してビットを減らすことで圧縮を達成する方法を教えてください。ありがとう

ハフマンを使用して、文字列内の固定長コードに必要な文字あたりのビット数をどのように決定しますか？文字列内のさまざまな文字の数を、その数を2進数で表すよりも数えると、固定長になると思いましたが、機能しません。たとえば、「letty lotto like lots of lolly」という文字列では、引用符を除いて10個の異なる文字があります（10 = 0101（4ビット）なので、すべての文字を4ビットで表すことができると思いました）。 fの周波数は1で、4ではなく11111（5ビット）としてエンコードされます。

大量のページセットのHTMLコードをMySQLデータベースに保存するWebクローラーをPythonで作成しています。データの処理を開始する前に、保存と処理の方法が最適であることを確認したいと思います。私はしたいと思います：

• データベースで使用されるストレージスペースを最小限に抑えます。おそらく、HTMLコード、ハフマンエンコーディング、またはその他の形式の圧縮を最小限に抑えます。全文検索の可能性を維持したいのですが、ハフマン符号化のような圧縮アルゴリズムでこれが可能かどうかはわかりません。

• 大量の行をエンコードして格納するために必要なプロセッサの使用量を最小限に抑えます。

この問題または同様の問題について、誰か提案や経験がありますか？多数のHTTPリクエストと正規表現に加えて、最適な圧縮が必要になることを考えると、Pythonはこれを行うのに最適な言語ですか？

そのため、学校の課題のためにハフマン圧縮/圧縮解除を作成する必要があり、周波数を格納する優先キューを使用するのに問題があります。

頭を悩ませている 2 つのファイルはHCNode.hpp、 とmain.cpp. オーバーロードしたHCNode.hppファイルと、次のように優先度キューを初期化しようとしbool operator<(const HCNode& other) たmain.cppとき:

コンパイラは私にたくさんのエラーをスローします

編集：これはエラーの1つです

/usr/include/c++/4.6/bits/stl_queue.h:391:9: 'std::priority_queue<_Tp, _Sequence, _Compare>::priority_queue(const _Compare&, const _Sequence&) からインスタンス化 [with _Tp = HCNode, _Sequence] = std::vector, _Compare = std::less]'<br> compress.cpp:134:59: ここからインスタンス化

ほとんどのエラーは、ライブラリとの何らかの競合によるものと思われます。

気にしないで、問題を修正しました。教師のコードが不完全でした。それでもこの投稿を見てくれた方々、ありがとうございます。