問題タブ [huffman-code]

ハフマンコーディングでエンコードされたデータベースがあります。ここでの目的は、関連するデコーダーを使用して GPU にコピーすることです。次に GPU でデータベースをデコードし、CPU にコピーして戻さずに、このデコードされたデータベースで処理を行います。

私はハフマンの専門家には程遠いですが、私が知っている少数の情報によると、これは本質的に制御構造に基づくアルゴリズムのようです。基本的なアルゴリズムでは、シリアライズされた操作が多くなると思います。

私の2つの質問は次のとおりです。

• ハフマンコーディング用の効率的な GPU バージョンが存在するかどうか知っていますか?
• そうでない場合、GPU に適合する (つまり、制御構造が少ない) ハフマン アルゴリズムが存在すると思いますか? または、効率的なハフマン デコードが GPU では効率的でないことを知っている (そして参照を提供できる) かもしれません。

他の制約も見られますが、重要ではありません: - GPU はツリーを処理するのにあまり効率的ではありませんでした: バイナリ ツリーは従来の配列に格納できます - ワークロードのバランスをとるのが難しい場合があります: 後で説明します

私のアルゴリズムの教科書から：

毎年開催される郡競馬には、互いに競ったことのない 3 頭のサラブレッドが参加します。興奮して、あなたは彼らの過去 200 レースを研究し、これらを 4 つの結果 (1 位 (「1 位」)、2 位、3 位、その他) の確率分布として要約します。

一番予想しやすい馬は？この問題に対する定量的なアプローチの 1 つは、圧縮率を調べることです。各馬の履歴を 200 個の値 (1 位、2 位、3 位、その他) の文字列として書き留めます。これらの実績文字列をエンコードするために必要なビットの総数は、ハフマンのアルゴリズムを使用して計算できます。これは、Aurora では 290 ビット、Whirlwind では 380 ビット、Phantasm では 420 ビットになります (チェックしてください!)。Aurora はエンコードが最も短いため、強い意味で最も予測可能です。

彼らはどのようにしてファンタズムの 420 を得たのですか? 私は400バイトを取得し続けます:

最初に結合、その他 = 0.4、2 番目、3 番目に結合 = 0.6。各位置をエンコードする 2 ビットで終了します。

ハフマン符号化アルゴリズムについて誤解しているものはありますか?

教科書はこちらから入手できます: http://www.cs.berkeley.edu/~vazirani/algorithms.html (156 ページ)。

プロジェクトの場合、バイナリ文字列を（配列の）バイトに変換し、それをバイナリのファイルに書き出す必要があります。

ハフマン符号化を使用して文をコード文字列に変換したとします。たとえば、文が次の場合： "hello" h = 00 e = 01、l = 10、o = 11

その場合、文字列表現は0001101011になります。

どうすればそれをバイトに変換できますか？<-その質問が意味をなさない場合、それはビット/バイトのビット単位のシフトについてほとんど知らないためであり、それは1と0の操作に関係しています。

これは私が学校の設定で遭遇した質問ですが、私を悩ませ続けているので、ここで質問することにしました.

ハフマン圧縮では、固定長シーケンス (文字) が可変長シーケンスでエンコードされます。コード シーケンスの長さは、ソース文字の頻度 (または確率) によって異なります。

私の質問は次のとおりです。その文字が単一ビットでエンコードされる最小最高文字頻度は何ですか?

私のC++ 教科書のデータ構造の基礎では、ハフマンコーディングの2ページの定義と、上記のコードが示されています。私にとって、この本は十分に詳細ではなかったので、グーグルを行い、ハフマン符号化のプロセスがどのように機能するかを学びました。教科書は、上記のコードの最後にハフマンツリーが作成されると主張しています。しかし、ハフマンツリーは完全なツリーである必要はないので、私には間違っているように見えますが、上記のコードは、のために常に完全なツリーを提供するようですheap.push()。では、誰かがこのコードが間違っていないことを私に説明できますか？

ファイルを読み込んで各文字スペース記号の頻度をカウントするなどして、ハフマン ツリーを作成しようとしています。Priorityqueue を使用して、アイテムを最小から最大までキューに入れていますが、それらをキューに挿入すると、正しくキューに入れられません。これが私のコードです。ハフマンパッケージ;

import java.io.FileNotFoundException; java.io.FileReader をインポートします。import java.util.ArrayList; java.util.PriorityQueue をインポートします。java.util.Scanner をインポートします。

公開クラス ハフマン {

}

buildTree() メソッドでは、私が問題を抱えている場所です。私がやろうとしているのは、文字/スペース/記号と頻度を int として保持する頻度オブジェクトをキューに入れることです。頻度クラスはこれです。public class Frequency は Comparable { private String s; を実装します。プライベート int n;

}

最小から最大の順にキューに入れるために頻度番号を使用するようにpriorityqueueを取得するにはどうすればよいですか?

以前質問したハフマン木には別の問題があります。コードは次のとおりです。

ここで行う必要があるのは、ツリーを検索して特定の文字のバイナリ コード (011001 など) を見つけるメソッドを作成する必要があることです。これを行う最善の方法は何ですか？AVLツリーが大きい場合は右に、小さい場合は左に行くように、ツリーを通常の検索を行うのではないかと思いました。

ただし、ノードはints doubleなどを使用せず、文字列またはnullとして文字を含むオブジェクトのみを使用して、リーフではなくルートのみを示すためです。もう1つのオプションは、探している葉を見つけるために順番通りに実行することですが、同時に、文字を取得するために何度も右に行ったのか、何度も左に行ったのかをどのように判断するのでしょうか.

私がやろうとしているのは、実際に各文字に到達するためのバイナリ コードを見つけることです。したがって、エンコードしようとしている場合aabbbcccc、左に行くと 0、右に行くと 1 のバイナリ コードを保持する文字列を作成する方法を教えてください。

私が混乱しているのは、ツリーが明らかにバランスが取れておらず、キャラクターが自分のいる場所の右か左かを判断できないため、何かがどこにあるかを判断できないためです. したがって、ツリー全体を検索する必要がありますが、探しているものではないノードに到達した場合は、別のルートに戻って他のリーフに到達する必要があります。

こんにちは私は文字を見つけるためにツリーを再帰的に検索する方法とその文字に到達するためのバイナリコードを理解しようとしています。基本的に目標は、キャラクターのコードを見つけてファイルに書き込むことです。ファイルライターの部分は問題ありませんが、本当の問題はバイナリコードを文字列に入れることです。キャラクターを探している間。助けてください！

これは再帰的メソッドのコードです：

これはFrequencyクラスです。

publicclassFrequencyはComparable{privateStrings;を実装します。private int n; パブリック周波数が残っています。公的周波数権; プライベート文字列biNum; プライベート文字列リーフ;

}

私はこのハフマンツリービルダーに取り組んできました:

コードが英語でやろうとしていることは

すべての文字を頻度とともに優先キューに最低頻度から最高頻度まで追加します。次に、ArrayList al (すべての文字を含む) のサイズについて、最初の 2 つをデキューし、デキューされた 2 つのノードである左と右の子を持つように新しいルートを設定し、デキューされた 2 つの結合された頻度で新しいルートを挿入します。アイテムを優先キューに入れます。メソッドが行うべきことはそれだけです。

このメソッドはハフマン ツリーを構築することになっていますが、正しく構築されていません コードに従ってツリーを手動で構築しましたが、紙に書かれていることはプログラムとは異なります。別のプログラムによって生成された正解は、私の解と同じではありません。入力データ (文字と頻度) は次のとおりです。

周波数はすでにここにあるので、それから読んでいるテキストは問題ではありません。必要なのは、これらの周波数からツリーを構築することだけです。

私はハフマン木に取り組んでおり、探している文字を持つノードを見つけるために木をたどる方法を見つけようとしています。ツリーを検索している間、1 と 0 (0 左 1 右) を使用して探しているノードへのパスの文字列を保持する必要があります。これどうやってするの？