問題タブ [huffman-code]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
jpeg - JPEGエンコーディング技術
JpegはHufmanコードを使用していると聞きました。ハフマンコードとは何ですか？
algorithm - ハフマン「ターミネーター」ビット文字列
動機
P2P ソフトウェアのように、部分的にダウンロードされるハフマン圧縮ファイルを想像してみてください。最初にファイル全体にディスク領域を割り当ててから、ランダムなファイル チャンクのダウンロードを開始します。ハフマン コードの 1 つ (ただしどれかはわかりません) は終了コードであるため、このコードがデコードされた場合は停止します。ファイルがいくつかの huffman 圧縮ストリームで構成されていると仮定すると、ダウンロードが完了する前にそれらのいくつかを解凍することを試みることができます。
ここで、ディスク スペースを事前に割り当てる方法が重要です。ハフマン ストリームが開始されたとしますが、まだ完了していないため、事前に割り当てられたディスク スペースが不足しているとします。通常、このスペースはすべて 0 なので、ハフマン コードでシンボルをデコードし続けます00..。これが最終コードでない場合、「無効な」データに気付かず、事前に割り当てられたスペースが 2 GB ある場合は、無駄なデコードを行っていることになります。
そのため、できるだけ早くデコードを停止する方法でスペースを事前に割り当てたいと考えています。
質問
「ハフマン ターミネータ」として機能する最短のビット文字列を探しています。つまり、この文字列をデコードすると、すべてのハフマン コードが少なくとも 1 回デコードされるため、確実に終了コードを受け取ることができます。これは、長さ1..nビットのハフマン コードのすべての組み合わせで機能するはずです。
00..注: 上記の仮想シナリオ (エンド コードとして使用、まだダウンロードされていないチャンクを検出するために P2P セグメント データを使用)に対する簡単な解決策があることは知っていますが、これは「ハフマン ターミネータ」の理論的な使用法を示すシナリオの例にすぎません。ビット文字列、私はこのシナリオを解決することに興味はありませんが、「ハフマンターミネーター」として機能するビット文字列を生成/見つけるためのアルゴリズム/方法/アイデアを探しています。
例
n = 2、[0, 1]、[00, 01, 1]、[0, 10, 11]の可能なハフマン コードの組み合わせを見てみましょう[00, 01, 10, 11]。1..n次に、可能なすべての長さのビット シーケンス( 0、1、00、01、10)を含むビット文字列から始めましょう11。
001011
さまざまなハフマン コードの組み合わせでデコードすると、次のようになります (ハフマン コードはシンボルに割り当てられますA..D)。
これは良いスタートであり、最初の 3 つのハフマン コードはすべて既にデコードされていますが、 でデコードすると[00, 01, 10, 11]、シンボルB(ハフマン コード01) が失われます。それでは、これをビット文字列に追加しましょう。
00101101
n=2これは、長さが 8 ビットの有効な「ハフマン ターミネータ」です。このバイトを使用してディスク領域を事前に割り当てておけば、2 ビットを超えないすべてのハフマン コードを確実に終了させることができます。各シンボルを 1 回デコードするn=2ための組み合わせの最小の長さであるため、より短いターミネータ文字列が存在しないこともわかっています。[00, 01, 10, 11]
n=3、 （43ビット）の「ハフマンターミネータ」も見つけました0001011001110100111010011100010101111101110が、それが正しいかどうか100％確信が持てず、最短のものかどうかもわかりません。
私が探しているもの
特定の のハフマン ターミネータを検索または生成するアルゴリズム/アイデア
n。私の試みは例に似ています: 開始文字列を生成し、必要に応じてビットを追加して、すべての異なるハフマン コードの組み合わせを満たします。しかし、もっと良い方法があると確信しています。特定のハフマンターミネータ
n=8およびn=16この問題 (または類似の問題) に関する論文/リンクがある場合。
ボーナス
「ハフマン ターミネータ」を見つけるためのボーナス ポイントは、ビット位置 から開始しても機能する1..nため、データが以前にデコードされた場合でも終了し、最初のビットで新しいハフマン コードに到達して開始することはありません。
image - ハフマンコードテーブル
Jpegのハフマンテーブルに何が含まれているのかわかりませんでした。誰かがこれを説明してもらえますか？ありがとう
decoding - ハフマンでエンコードされたビットストリームからメッセージをデコードする方法は?
ハフマンでエンコードされたビットストリームからメッセージをデコードする方法は? ハフマンアルゴリズムの考え方がよくわかりません。
私が理解している限り、「私の名前はXYZです」というテキストメッセージが表示されたとします。
次に、エンコード プロセスは次のようになります。 1. 文字の頻度を数えます。2. 度数を値で並べ替えます。3. ツリーを構築します。4. 左端を 0、右端を 1 と見なしてツリーをトラバースし、目的のメッセージ文字に到達します。5. コードを連結してビット ストリームを見つけます。
問題は、エンコードされたビット ストリームから元のメッセージを見つけるにはどうすればよいかということです。
ハフマン木をもう一度構築する必要があると思います。
しかし、ビット ストリームからハフマン ツリーを構築するにはどうすればよいでしょうか。
file - ハフマンツリーをエンコードされたビットストリームと一緒にファイルとして保存する基本的な手法は何ですか？
ハフマンエンコードされたビットストリームをバイナリファイルとして保存するにはどうすればよいですか？
algorithm - ハフマン木を構築する際の優先度はどのように選択されますか?
私のキャラクターとその頻度が次のようになっているとします。
ツリーを構築するとき、ステップ 2 で次のようになります。
さて、2 つの 3 があるので、それらの優先度をどのように決定できるでしょうか?
ハフマン コーディングでは、これは次のように見なされます。
なんで？
optimization - haskellにバイト文字列全体を保存しないように強制するにはどうすればよいですか？
私はアカデミックな目的でhaskellに関する小さな（比較的）アプリケーションを書いています。このコードhttp://www.haskell.org/haskellwiki/Toy_compression_implementationsに基づいて、ハフマン圧縮を実装しています。
このコードの私の変種はここhttps://github.com/kravitz/har/blob/a5d221f227c27fd1c5587217a29a169a377521a6/huffman.hsであり、遅延バイト文字列を使用します。RLE圧縮を実装したとき、入力ストリームを1つのステップで処理するため、すべてがスムーズでした。しかし、ハフマンはそれを2回処理し、その結果、評価されたバイト文字列がメモリに格納されます。これは、大きなファイルには適していません（ただし、比較的小さなファイルの場合は、ヒープに割り当てられるスペースも多すぎます）。これは私の疑いだけではありません。プロファイリングでは、ヒープのほとんどがバイト文字列の割り当てによって消費されていることも示されているためです。
また、ファイル内のストリームの長さをシリアル化すると、メモリに完全なバイト文字列が読み込まれる可能性があります。ghcが親切でストリームを数回再評価すると言う簡単な方法はありますか？
zlib - テキストデータを圧縮してテキストとして保存するライブラリ
Web ページを圧縮テキスト ファイル (CSV) に保存したいと考えています。最適な圧縮を実現するために、1000 の Web ページのセットを提供したいと考えています。次にライブラリは、このコンテンツに最適な「辞書」を作成するのに時間を費やす必要があります。明らかな「辞書」エントリの<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">1 つは であり、ほとんどすべての Web ページに存在するため、%1 などとして保存される可能性があります。このようにカスタマイズされた辞書を作成することで、私の場合、圧縮率は 99% になるはずです。
私の質問は、これを行うためのライブラリが MIT または同様のリベラルなライセンスを使用して Windows に存在するかどうかです。そうでない場合、推奨する汎用圧縮ライブラリはありますか。zlib で少し試してみましたが、バイナリ データが出力されます。このバイナリデータをテキストに変換すると、元のテキストより長くなってしまうのではないかと心配です。
編集: テキストを CSV ファイルに保存し、データベースや Excel にインポートできるようにする必要があります。
c++ - 文字列からの 2 つのキーでマップを塗りつぶします。文字と頻度 c++
私は地図に慣れていないので、これを行う最善の方法が少しわかりません。このタスクは、ハフマン符号による圧縮に関するものです。これが私が持っているものです。
上記はオンラインで見つけた方法の 1 つですが、何も印刷できませんでした
テキスト ファイルから を読み込んで、文字列のファイルラインにデータを入力しました。
これは、マップにデータを入力するために試した 2 番目の方法です。char 値は正しくありません。記号とスマイリーフェイスです。
これは私が地図を印刷しようとした方法です
getFreq メソッドを実行すると、プログラムがクラッシュします。どちらでもエラーは発生しません。2 番目の方法では、char 値は意味がありません。両方の方法を同時に実行していないことに注意してください。
洞察をいただければ幸いです。ありがとうございます。初心者なのでお手柔らかに(;_;)
huffman-code - 標準ハフマンツリーを構築する最も効率的な（*）方法は何ですか？
Aは、A[0]がアルファベットの0番目の文字の頻度を保持する配列であると想定します。
コードの長さを計算する最も効率的な（*）方法は何ですか？確かではありませんが、効率はメモリ使用量または必要な手順の観点から考えられます。
私が興味を持っているのは、アルファベットの0番目の文字のコード長（ビット数）を含む配列です。ここで、コードは、周波数配列から構築された標準ハフマンツリーから取得されますL。L[0]