4

Jpegのハフマンテーブルに何が含まれているのかわかりませんでした。誰かがこれを説明してもらえますか？ありがとう

4

2 に答える 2

16

ハフマン符号化は、可変長のデータ圧縮方式です。これは、入力ストリームで最も頻繁な値を最小のビット長のエンコーディングに割り当てることによって機能します。

たとえば、入力は文字をバイナリとしてSeems every eel eeks elegantly.エンコードし、他のすべての文字を他のさまざまな長いコードとしてエンコードする場合があります。これらはすべて。で始まります。そうすれば、結果のビットストリームは、すべての文字が固定サイズである場合よりも小さくなります。例として、各キャラクターの量を調べて、一般的なキャラクターを一番上に置くツリーを構築してみましょう。e10

Letter  Count
------  -----
e          10
<SPC>       4
l           3
sy          2
Smvrkgant.  1
<EOF>       1

EOF通常、ファイルには8ビットの倍数が必要なので、ファイルの終わりマーカーがあります。最後のパディングが実際の文字として扱われないようにするためです。

                                 __________#__________
                ________________/______________       \
       ________/________                   ____\____   e
    __/__             __\__             __/__       \
   /     \           /     \           /     \     / \
  /       \         /       \         /      SPC  l   s
 / \     / \       / \     / \       / \
y   S   m   v     /   k   g   \     n   t
                 /\          / \
                r  .        a  EOF

現在、これは必ずしも最も効率的なツリーではありませんが、エンコーディングがどのように行われるかを確立するのに十分です。まず、非圧縮データを見てみましょう。8ビットのエンコーディングを想定すると、これらの31文字（非圧縮データには必要ありませんEOF）は248ビットを使用します。

ただし、上のツリーを使用して文字を検索すると、左側のサブツリーを取得した場合は0ビットを出力し、右側のサブツリーを取得した場合は1ビットを出力すると、次のようになります。

Section      Encoding
----------   --------
Seems<SPC>   00001 1 1 00010 0111 0101                    (20 bits)
every<SPC>   1 00011 1 001000 00000 0101                  (22 bits)
eel<SPC>     1 1 0110 0101                                (10 bits)
eeks<SPC>    1 1 00101 0111 0101                          (15 bits)
elegantly    1 0110 1 00110 001110 01000 01001 0110 00000 (36 bits)
.<EOF>       001001 001111                                (12 bits)

これにより、合計115ビットが得られ、バイトの倍数である必要があるため120に切り上げられますが、それでも非圧縮データの約半分のサイズです。

実際のツリー自体が占めるスペースを追加する必要があるため（a）、通常、このような小さなファイルには価値がありません。そうしないと、もう一方の端でデコードできません。しかし確かに、文字の分布が均一でない大きなファイルの場合、スペースの大幅な節約につながる可能性があります。

つまり、結局のところ、JPEGのハフマンテーブルは、ストリームを使用可能な情報に解凍できるようにするテーブルにすぎません。

JPEGのエンコードプロセスは、いくつかの異なるステップ（色変換、彩度分解能の低下、ブロックベースの離散コサイン変換など）で構成されますが、最後のステップは、各ブロックでのロスレスハフマンエンコードです。画像を読み取るときは逆にします。

（a）おそらく、このテーブルの最小限のストレージの最良のケースは次のようになります。

Size of length section (8-bits) = 3 (longest bit length of 6 takes 3 bits)
Repeated for each byte:
    Actual length (3 bits, holding value between 1..6 inclusive)
    Encoding (n bits, where n is the actual length)
    Byte (8 bits)
End of table marker (3 bits) = 0 to distinguish from actual length above

上記のテキストの場合、次のようになります。

00000011             8 bits

 n  bits   byte
--- ------ -----
001 1      'e'      12 bits
100 0101   <SPC>    15 bits
101 00001  'S'      16 bits
101 00010  'm'      16 bits
100 0111   's'      15 bits
101 00011  'v'      16 bits
110 001000 'r'      17 bits
101 00000  'y'      16 bits
101 00101  'k'      16 bits
100 0110   'l'      15 bits
101 00110  'g'      16 bits
110 001110 'a'      17 bits
101 01000  'n'      16 bits
101 01001  't'      16 bits
110 001001 '.'      17 bits
110 001111 <EOF>    17 bits

000                  3 bits

これにより、テーブルは264ビットになり、圧縮による節約が完全になくなります。ただし、前述のように、入力ファイルが大きくなるにつれてテーブルの影響ははるかに少なくなり、テーブルを完全に回避する方法があります。

この方法では、適応形ハフマンと呼ばれるハフマンの別のバリアントを使用します。これは、テーブルが実際に圧縮データに格納されていない場所です。

EOF代わりに、圧縮中、テーブルは、テーブルに新しい実バイトを導入することを目的とした特別なビットシーケンスで始まります。

テーブルに新しいバイトを導入するときは、導入ビットシーケンスに続いて、そのバイトの8ビット全体を出力します。

次に、各バイトが出力され、カウントが更新された後、テーブル/ツリーは新しいカウントに基づいてリバランスされ、スペース効率が最も高くなります（ただし、速度を向上させるためにリバランスが延期される場合がありますが、同じ延期が行われるようにする必要があります。解凍中の例では、最初の1Kの入力にバイトを追加するたびに、その後は10Kの入力ごとに、最後のリバランス以降に新しいバイトを追加したと仮定します）。

これは、テーブル自体がもう一方の端でまったく同じ方法で構築できることを意味します（解凍）。同じ最小テーブルから始めてEOF、イントロデューサーシーケンスだけを使用します。

解凍中に、イントロデューサシーケンスが表示されたら、それに続くバイト（次の8ビット）をカウントがゼロのテーブルに追加し、バイトを出力してから、カウントを調整してリバランスします（または前述のように延期します）。 ）。

そうすれば、圧縮ファイルとともにテーブルを出荷する必要はありません。もちろん、これは、テーブルのバランスを定期的に再調整するという点で、圧縮と解凍の間にもう少し時間がかかりますが、人生のほとんどのことと同様に、トレードオフです。

于 2011-02-10T06:39:05.953 に答える
0

DHTマーカーは、どのシンボルがコードに関連付けられているかを直接指定しません。これには、特定の長さのコードがいくつあるかをカウントしたベクトルが含まれています。その後、シンボル値を持つベクトルが含まれます。

したがって、デコードする場合は、最初のベクトルからハフマンコードを生成してから、すべてのコードを2番目のベクトルのシンボルに関連付ける必要があります。

于 2011-02-11T08:45:30.820 に答える