問題タブ [huffman-code]

Aは、A[0]がアルファベットの0番目の文字の頻度を保持する配列であると想定します。

コードの長さを計算する最も効率的な（*）方法は何ですか？確かではありませんが、効率はメモリ使用量または必要な手順の観点から考えられます。

私が興味を持っているのは、アルファベットの0番目の文字のコード長（ビット数）を含む配列です。ここで、コードは、周波数配列から構築された標準ハフマンツリーから取得されますL。L[0]

結果のアルファベットがバイナリではない状況で、ハフマン コーディング ツリーを簡単に一般化できますか? たとえば、あるテキストを 3 進数で書き出すことによって圧縮したい場合でも、書き出す文字ごとにプレフィックスのないコーディング システムを構築できます。ハフマン構成の単純な一般化 (二分木ではなく k 分木を使用) は、正しく効率的に機能するでしょうか? それとも、この構造は非常に非効率的なコーディング スキームにつながるのでしょうか?

圧縮された多数のファイル (.txt) でテキストを検索できる必要があります。圧縮は別のものに変更されるか、独自のものになることさえあります。すべてのファイルを解凍することを避け、検索文字列を圧縮 (エンコード) し、圧縮されたファイルで検索したい。これは、すべてのファイルに対して同じコードブックでハフマン圧縮を使用することで可能になるはずです。私は車輪を再発明したくないので..誰かがこのようなことを行うライブラリや、実装およびテストされたハフマンアルゴリズム、あるいはより良いアイデアを知っていますか?

前もって感謝します

Lossless 圧縮のための Huffman Coding について本当に助けが必要です。試験が迫っていて、これを理解する必要があります。これを理解するために作成された簡単なチュートリアルを知っている人はいますか、誰かが説明してくれますか?

試験の質問は次のようになります。

アルファベットが [A, B, C] で、既知の確率分布が P(A)=0.6、P(B)=0.2、P(C)=0.2 であるとします。簡単にするために、エンコーダーとデコーダーの両方が、メッセージの長さが常に 3 であることを認識していると仮定して、ターミネーターは必要ありません。

1. メッセージ ACB をハフマン コーディングでエンコードするには、何ビットが必要ですか? シンボルごとにハフマン ツリーとハフマン コードを提供する必要があります。(3 点)

2. 算術符号化でメッセージ ACB をエンコードするには、何ビットが必要ですか? エンコード プロセスの詳細を提供する必要があります。(3 点)

3. 上記の結果を使用して、ハフマン符号化に対する算術符号化の利点について説明します。(1 点)

答え:

1. ハフマンコード：A-1、B-01、C-00。エンコード結果は10001なので5ビット必要。(3 点)

2. 算術符号化のエンコード プロセス: シンボル 低高範囲 0.0 1.0 1.0 A 0.0 0.6 0.6 C 0.48 0.6 0.12 B 0.552 0.576 0.024 最終的なバイナリ コードワードは 0.1001、つまり 0.5625 です。したがって、4 ビットが必要です。(3 点)

3. ハフマン符号化では、各シンボルの符号語の長さは整数でなければなりません。しかし、算術符号化では分数になる可能性があります。したがって、上に示した結果のように、算術符号化は多くの場合、ハフマン符号化よりも効率的です。(1 点)

I'm in the process of coding Huffman Code where I import a file, generate huffman code for each character, then output the binary to a file. To import the characters I am using a scanner that reads each character, puts it in a node that has values of the read character and a frequency of 1. Then, the node is added to a PriorityQueue. Since the Node class has a compareTo method that compares only frequency, how can I implement a comparator to this specific PriorityQueue that compares the characters when sorting in queue? Thanks in advanced.

Literal example: The queue of characters should be sorted as follows:

Here are some snippets:

This is the PriorityQueue that needs a custom comparator:

This is the new method I created using a HashMap:

私自身からの別の質問を含め、ハフマン コードに関する多くの質問があることは承知していますが、テキスト ファイルを実際にエンコードする最良の方法は何か疑問に思っています。解凍は些細なことのようです。ツリーをトラバースし、0 で左、1 で右に進み、文字を出力します。

とはいえ、圧縮はどのように行うのでしょうか。どういうわけか、文字のビット表現をツリーのノードに保存しますか? 遭遇するたびにキャラクターをツリーで検索し、手順をたどりますか？これがどのようにコーディングされているかは重要ですか？

これまでのところ、リーフ ノードにバイナリ値が関連付けられていないハフマン ツリーがあります。私の問題は、ツリー内の各文字にバイナリ値を割り当てることです。

ありがとう

私は数日間この問題に苦しんでいます。次のサイトで指定されているデータを使用してツリーを構築するにはどうすればよいですか。

http://www.impulsadventure.com/photo/jpeg-huffman-coding.html、トピックの下:

JPEG ファイル内の実際の DHT

ここでもう一度簡単に説明しますので、

あなたが持っている ：

1. 長さを持つテーブル (bytesvector)
2. データを含むテーブル (bytesvector も)

次に、これら 2 つの引数を使用してバイナリ ツリーを作成します。対応する長さのデータで毎回左から右に埋められます。木に深く入るほど、長さが長くなります。長さは 1 から 16 までさまざまです。サイトを見てください。

今度は、Scheme/Racket でそのようなツリーを作成して、ツリーに移動し、エンコードされた値ごとにテーブルを作成できるようにしたいと考えています。

私が考えているツリーは次のようになります。

以下の説明は、package-merge を使用した長さ制限のあるハフマン コードに関する Wikipedia からの説明です。理解できません、これについていくつか質問があります。

• どのようにパッケージ化しますか?
• どのように合併しますか？
• シンボルのビット列の長さをどのように認識するのですか?

任意のコード ワードに許容される最大長をLとします。p ₁ , …, p nを、エンコードするアルファベットのシンボルの周波数とします_。まず、シンボルをp _i ≤ p _i +1 になるように並べ替えます。^{額面単位 2 -1} , …, 2 ^-<em>LのシンボルごとにL個のコインを作成し、それぞれの貨幣価値p _iを作成します。package-merge アルゴリズムを使用して、額面の合計が n − 1 である最小貨幣価値のコインのセットを選択します。h _iを貨幣価値p _iのコインの数とします。選択されました。長さが制限された最適なハフマン コードは、シンボルiを長さh _iのビット文字列でエンコードします。」

すべてのファイルをハフマン符号でエンコードしたい。シンボルあたりのビット長 (そのハフマン コード) を見つけました。

Java で文字をファイルにエンコードすることは可能ですか: 文字の最小次元ではなく、ビットごとにファイルを読み書きする既存のクラスはありますか?

こんにちは！

このインターネット サイトから、ハフマン アルゴリズムの問​​題を解決する方法を (すべての部分をまとめた場合) 誰か教えてください。

http://www.builderau.com.au/program/python/soa/Huffman-coding-in-Python/0,2000064084,339283616,00.htm

エラー：

ありがとう！