問題タブ [huffman-code]

ファイルのランダムな読み取り/書き込みを可能にする最適な圧縮アルゴリズムは何ですか?

適応圧縮アルゴリズムが問題外であることはわかっています。

そして、ハフマンエンコーディングが問題外であることは知っています。

ランダムな読み取り/書き込みを可能にする、より優れた圧縮アルゴリズムを持っている人はいますか?

ブロックで記述すれば、任意の圧縮アルゴリズムを使用できると思いますが、理想的には、一度にブロック全体を解凍する必要はありません。しかし、これを行う簡単な方法とブロック境界を知る方法について提案がある場合は、お知らせください。これが解決策の一部である場合は、読み取りたいデータがブロック境界をまたいでいる場合の対処方法も教えてください。

あなたの回答の文脈では、問題のファイルが100GBであると仮定してください。最初の10バイトを読みたい場合もあれば、最後の19バイトを読みたい場合もあり、17バイトを読みたい場合もあります真ん中のバイト。.

NEED などのハフマン コードを使用して単語をエンコードする方法

Javaで可変長ビット文字列を使用してバイナリデータをデコードする最良の方法を誰か教えてもらえますか?

例えば：

バイナリ データは 10101000 11100010 01100001 01010111 01110001 01010110 です。

次の 01、100、110、1110、1010 のいずれかの最初の一致を見つける必要があるかもしれません...

この場合、一致は 1010 になります。残りのバイナリ データについても同じことを行う必要があります。ビット文字列の長さは最大 16 ビットで、バイト境界を越えることができます。

基本的に、ヘッダーのハフマン テーブルから作成したビット文字列を使用して、JPEG をハフマン デコードしようとしています。私はそれを行うことができますが、それは非常に面倒です。バイナリデータを含むすべてを最初に Stringbuffers に変換していますが、それが正しい方法ではないことはわかっています。

文字列バッファにすべてをロードする前に、バイナリの数値だけを使用してみましたが、もちろん、00011 のようなコードの先頭の 0 を無視することはできません。ビットごとの演算子などを使用して、何らかの巧妙な方法があるはずです。これですが、ビットマスクや左方向シフトなどを説明するページをじっと見つめていましたが、まだ手がかりがありません!

助けてくれてありがとう！

編集：

すべての提案をありがとう。ハフマンのものでは標準的な方法のように思われるので、私は二分木アプローチを採用しました。ハフマン コードはツリーを使用して作成されるため、これは非常に理にかなっています。また、検索に必要なバイナリ データを大きな整数に格納する方法についても検討します。複数の回答を正解としてマークする方法がわかりませんが、ありがとうございます。

私はこれを自分で解決できると思っていましたが、まったく前進していないようです。

わかりました、背景：

jpg ファイルの FFC4、DHT (Define Huffman Table) ヘッダーによって提供される情報からコードのハフマン ツリーを作成する必要があります。DHT ヘッダーは、ハフマン テーブルを次のように定義します。

1) 一連の 16 バイト。各バイトは、n ビットのハフマン コードを持つシンボルの数を定義します。ここで、n は一連のバイトの位置です。(それは意味がありましたか?!!) たとえば、16 進数の生データは次のとおりです。

00 01 05 01 01 01 ... 00

この意味は：

2) 16 バイトのリストの後に、実際のシンボル自体が続きます。例えば：

00 01 02 03 04 05 06 07 08 09 0A 0B

3) 2 つの部分を組み合わせると、
1 ビットの 00 コード。
2 ビットの 01 コード: リストから最初のシンボルを取得: 00
3 ビットの 05 コード: リストから次の 5 つのシンボルを取得: 01 02 03 04 05
.. など

4) 最後に、上記の情報から実際のハフマン コードを計算する必要があります。あなたが数学の天才なら、特定のビット長で新しいコードごとに適切なビット数で 2 進数をインクリメントするだけで、これらのコードを計算できることにすでに気づいているかもしれません。ビット長が増えたら、単純に 2 進数をインクリメントしてから 2 倍にして続行します。これらの二分木を手で描いてみると、誰の目にも明らかです...

5) これは、ハフマン コードを作成し、それらを配列に格納するために使用したコードです: (最初に 1 のデータを読み取り、それを配列に入れます: dhtBitnum)

ハフマン コードを生成して順番に保存したら、2) で参照するシンボルを順番に追加するだけです。これはそれほどエレガントではないかもしれませんが、少なくとも機能しているようで、正しいテーブルを作成します。

6) 誰かがまだこれに従っているなら、あなたはメダルに値します。

7) 問題は、配列を毎回検索するのではなく、後で jpg 画像データを効率的にデコードできるように、この情報をバイナリ ツリーに格納することです。残念ながら、上記の jpg ヘッダーで提供される情報から直接これを行うためのクリーンで効率的な方法を見つけることはできません。
私が考えることができる唯一の方法は、最初に上記のようにハフマンコードを作成し、次にコードをある種のアドレスとして使用して、必要に応じてノードを作成し、シンボルを適切な場所に保存する方法を実装することです。しかし、これは私が必要とする情報を複製しているようなラウンドアバウトな方法のように思えます.もっと良くて簡単な方法があるに違いありません.

8) 誰かが私のとりとめのないことを理解していれば、いくつかの提案に非常に感謝しています. これは非常に具体的な問題であることは承知していますが、上記の情報が誰かの役に立てば幸いです。私はまだこれに非常に慣れていないので、私の無知を許してください。理解しやすいコードは特に大歓迎です!

私はハフマン エンコーディング/デコーディング ツールを作成しており、出力ファイル内に保存するために作成されたハフマン ツリーを保存する効率的な方法を探しています。

現在、私が実装している 2 つの異なるバージョンがあります。

1. これは、ファイル全体を 1 文字ずつメモリに読み込み、ドキュメント全体の度数分布表を作成します。これは、ツリーを 1 回出力するだけでよいため、入力ファイルが小さい場合を除いて、効率はそれほど大きな問題ではありません。
2. 私が使用しているもう 1 つの方法は、サイズが約 64 キロバイトのデータのチャンクを読み取り、それに対して周波数分析を実行し、ツリーを作成してエンコードすることです。ただし、この場合、すべてのチャンクの前に、デコーダーがツリーを再構築し、エンコードされたファイルを適切にデコードできるように、周波数ツリーを出力する必要があります。できるだけ多くのスペースを節約したいので、これが効率の良いところです。

これまでの検索では、ツリーをできるだけ小さなスペースに格納する良い方法が見つかりませんでした。StackOverflow コミュニティが良い解決策を見つけるのに役立つことを願っています!

ハフマン ツリーを格納する効率的な方法に関する私の質問に関連するフォローアップの質問として、(ハフマン コーディング出力に基づいて) バイナリ ツリーを検索し、特定のノードへのパスを格納する最速かつ最も効率的な方法は何かと考えていました。 .

これは私が現在持っているものです：

• ルートノードをキューに追加
• キューが空でない間、アイテムをキューからポップします
  • それが私たちが探しているものかどうかを確認してください
    • yes: ヘッド ポインターをたどってルート ノードに戻ります。各ノードにアクセスして、左か右かを確認し、メモします。
    • 検索から抜け出す
  • 左右のノードをキューに入れる

これはハフマン木なので、探しているすべてのエントリが存在します。上記は幅優先検索です。これは、ソース内にあるアイテムがツリーの上位にあることが多いため、ハフマン ツリーに最適であると考えられていますが、追跡する良い方法がわかりません。ノードに配置したヘッド ポインターを使用して、バックトラックせずに特定のノードに到達する方法。

この場合、右/左のすべてのパスも逆の順序で取得しています。たとえば、頭をルートにたどると、ルートから右、左、左、左になることがわかります。 、 左右。または、効率的な方法で 100 を取得することを探している場合は、バイナリで 001。

ルートからノードへのパスをノード内の別の値として保存することも提案されましたが、その目的のために作成した変数が保持できるビット数よりも大きなツリーがあった場合、これは失敗します。データを格納するポイントも大量のメモリを占有します。

ハフマンのアルゴリズムを使用してファイル圧縮を実装しましたが、問題は、圧縮ファイルの解凍、使用されるコーディング ツリー、またはコード自体もファイルに書き込む必要があることです。問題は次のとおりです。圧縮ファイルの先頭にコーディング ツリーを記述する最良の方法は何ですか?

BMP 画像を JPEG に変換する C++ プログラムを作成しています。

私が従おうとしている基本的なアルゴリズムは次のとおりです。

1. RGB カラー スペースを Y、Cb、Cr に変換します。
2. Cb と Cr を 2 ずつダウンサンプリングします (つまり、2*2 の正方形ブロックごとに 4 つの異なる Y 値がありますが、1 つの Cb と 1 つの Cr 値があります)。
3. 各 8*8 ピクセルのデータ単位に DCT を適用します...
4. 次に、Cb と Cr の標準量子化テーブルを使用して、DCT 係数に量子化を適用します。
5. ジグザグに並べます。
6. ハフマン符号化を使用して DC 係数と AC 係数を別々に符号化します。
7. 適切なヘッダーを書き込み、ハフマンでエンコードされた値をファイルに書き込みます...

上記を正しく実行していることを確認しましたが、まだ次の問題があります。

• 生成中の JPEG が正しく表示されません。
• 色の値 R=10 B=10 および G=100 で完全に満たされた小さな 8*8 24 ビット (色深度) の bmp ファイルを作成しました... 64 ピクセルすべてが同じ色です..
• 私がすべてのステップで取得しているデータは次のとおりです...
  • BMP ヘッダー サイズ 40
  • ヘッダーのサイズ 40
  • 幅8
  • 高さ8
  • 飛行機の数 1
  • ピクセルあたりのビット数 24
  • 画像サイズ 194
  • x 解像度 1 メートルあたりのピクセル数 2834
  • 1 メートルあたりの y 解像度ピクセル 2834
  • 色数 0
  • インプ色の数 0
  • (R,B,G)=(10,10,100) の Y Cb Cr 変換は (62,-29,-37) です。

では、まず Y 成分について考えてみましょう。

Y 成分の DCT 係数は次のとおりです。

量子化の後、私が取得している単一のデータ単位のジグザグ順序は、Y コンポーネントの場合です。

上記のジグザグ配列のハフマンコーディングは次のとおりです。

• Y DC コーディング: 00111110
• Y ac コーディング: 1010 (ac ハフマン テーブル (輝度 Y) EOB 値は 1010 の場合)
• 同様に、Cb および Cr コンポーネントのハフマン コーディングは次のとおりです。
• cb dc コーディング: 11000010
• cb ac コーディング: 01 (ac ハフマン テーブル (クロミナンス Cb,Cr) の場合、EOB 値は 01)
• CR DC コーディング: 110101110
• cr ac コーディング: 01

• 私が得る最終的なハフマンコードは次のとおりです。

  001111101010110000100111010111001 長さ 33

そのため、8 で割り切れるように、1 のパディングが行われます。

ここで、個々の 0 または 1 は、実際には JPEG ファイルにそのまま保存する必要があるビットですが、ビットごとにファイルに書き込むことができないため、合計 8 ビットが取得され、基数の整数値に変換されます。 10 となり、1 バイト文字に格納されます。

私が間違っている場所について誰か提案を提供できますか?

私が取り組んでいるプロジェクトでは、O（n）空間にBurrows-WheelerのMoveToFront変換を実装する必要があります。ただし、何らかの理由で、私のコードは、スローするほとんどの値で機能しますが、すべてではありません。

私の実装は次のようになります。

私がここで間違っていることについて何かアドバイスはありますか？英数字以外の文字が検出された場合、これは機能しないようです（つまり、それ自体をエンコードする場合、/ *などがそれを台無しにするようです）。