Huffman Coding -Wikipedia、無料百科事典

Posted on by
before-content-x4

ハフマンコーディング

Ilustracja
ハフマンコーディングの例
after-content-x4

ハフマンコーディング （ ハフマンコーディング ） – 最も簡単で簡単に実装できる方法の1つ [初め] 。 1952年にアメリカのデイビッド・ハフマンによって開発されました [2] 。

Huffmanアルゴリズムは、非定常データ圧縮の最も効果的なコンピューティングシステムの1つではないため、実際には単独では使用されていません。多くの場合、さまざまな圧縮システムの最後の段階として使用されます。完璧ではありませんが、シンプルで特許制限がないために使用されます。これは、貪欲なアルゴリズムを使用する例です。

「あるかどうか」というフレーズから生成されたハフマンの木

ソースアルファベット（シンボルコレクション）が与えられます

s = { バツ 初め 、 … 、 バツ n } {displaystyle s = {x_ {1}、dots、x_ {n}}}

そして彼に関連する確率のセット

p = { p 初め 、 … 、 p n } 。 {displaystyle p = {p_ {1}、dots、p_ {n}}。}

通常、シンボルはバイトですが、違うものは違うという障害はありません（例：文字のペア）。特定のデータセット、たとえば、特定の言語のテキストの標識の頻度を決定することにより、確率を事前に決定できます。ただし、より多くの場合、それらは各データセットに対して個別に決定されます。

Huffman Codingは、コードワード（ビット文字列）の作成で構成され、その長さは確率に反比例します

after-content-x4
p 私 。 {displaystyle p_ {i}。}

すなわちデータ中にシンボルが発生する（発生する可能性がある）ことが多いほど、ビットが少なくなります。

ハフマンのプロパティは次のとおりです。

  • プレフィックスコードです。これは、別の単語の始まりであるコードワードがないことを意味します。
  • コードワードの平均長は、最小のプレフィックスコードです。
  • 確率が異なる場合、つまり
  • コードの2つの最も可能性の高いシンボルの単語は、等しい長さを持っています。

圧縮は、記号を受信コードに置き換えることにあります。

Huffman staticコーディングアルゴリズム [ 編集 | コードを編集します ]

ハフマンアルゴリズム：

  1. セットSから各シンボルの確率（または発生頻度）を指定します
  2. ノードにストアを組み合わせたバイナリツリーのリストを作成します：シンボル、確率。最初は、木は根のみで構成されています。
  3. リストに複数のツリーがある限り、繰り返します。
    1. ルートに保存された最小確率で、リストから2本の木を削除します。
    2. 根に新しい木を挿入します。その根は、除去された木の確率の合計であり、それ自体が左と右の被写体になります。ツリールートはシンボルを保存しません。

リストに残るツリーは呼び出されます ハフマンツリー – ルートに保存される確率は1に等しく、木の葉に記号が書かれています。

Huffmanアルゴリズムは、同じ確率がある場合、リストからツリーを選択する順序でどのような順序で指定されていないため、最終的なアルゴリズムです。また、どの木が左または右の被験者になるように削除されたかを決定しません。ただし、採用されたソリューションに関係なく、平均コードの長さは同じままです。

コードワードは、ハフマンツリーに基づいて作成されます。アルゴリズムは次のとおりです。

  1. ツリーの各左端は0、右1を割り当てます（もちろん反対です）。
  2. 根から各葉まで木の奥深くを通過します（シンボル）：
    1. 右折する場合は、値が1のビットコードに追加します。
    2. 左折した場合は、0ビットを0に追加します。

コードワードの長さは、ツリー内のシンボルの深さに等しく、バイナリ値はツリー内の位置に依存します。

Przykład

例 [ 編集 | コードを編集します ]

シンボルのコレクションが与えられます

s = { a 、 b 、 c 、 d } {displaystyle s = {a、b、c、d}}

それに応じて発生する可能性について

p = { 0 、 初め ; 0 、 2 ; 0 、 3 ; 0 、 4 } 。 {displaystyle p = {0 {、} 1; 0 {、} 2; 0 {、} 3; 0 {、} 4}。}

アルゴリズムに応じたソースアルファベットコーディング（その横の図のようなマーク）：

  1. （a）および（b）を接続する（a + b）= 0.3; （c）= 0.3; （d）= 0.4。
  2. ツリー（a + b）をシンボル（c）に接続し、要素（（a + b） + c）= 0.6および（d）= 0.4を取得します。
  3. ツリー（（a + b） + c）をシンボル（d）に接続します。これで、1つのフリーノード（root）のみがあります – ツリー（（a + b） + c） + d）= 1.0を取得します。
  4. 個々のシンボルのコードの計算は次のとおりです。
    • a = lewo、lewo、lewo = 000
    • b =左、左、右= 001
    • c =左、右= 01
    • d = law = 1

簡単に確認できるように、平均コードの長さは次のとおりです。

l k = p （ a ）） de 3 + p （ b ）） de 3 + p （ c ）） de 2 + p （ d ）） de 初め = 0 、 3 + 0 、 6 + 0 、 6 + 0 、 4 = 初め 、 9。 {displaystyle l_ {k} = p（a）cdot 3+p（b）cdot 3+p（c）cdot 2+p（d）cdot 1 = 0 {、} 3+0 {、} 6+0 {、} 6+0 {、} 4 = 1 {、} 9。}

一定の標識長さの些細なコーディングで必要な2ビット未満です。次に、ソースエントロピーは次のとおりです。

h （ s ）） = – 0 、 初め ログ 2 ⁡ 0 、 初め – 0 、 2 ログ 2 ⁡ 0 、 2 – 0 、 3 ログ 2 ⁡ 0 、 3 – 0 、 4 ログ 2 ⁡ 0 、 4 = 1.846 4 {displaystyle h（s）= -0 {、} 1log _ {2} {0 {、} 1} -0 {、} 2log _ {2} {0 {、} 2} -0 {、} 3log _ {2} {0 {0 {、} -0 {} 4log} 4log = 1 {、} 8464}

– 最適なコーディングは、このような平均コード長によって特徴付けられる必要があります。ただし、それが大きいことがわかります – この場合の効率

H(S)Lkde 100 ％ = 1,84641,9= 97 、 2 ％ 。 {displaystyle {frac {h（s）} {l_ {k}}} cdot 100％= {frac {1 {、} 8464} {1 {、} 9}} = 97 {、} 2％。}}}

デコードは逆プロセスです。考慮された文字列はなります

a b c d 、 {displaystyle abcd、}

これは、としてコーディングされています

00000111。 {displaystyle 00000111.}

コードのビットに従って、ルートから端子ノードに毎回ツリーを渡すことで、適切なシンボルを取得します。

  • 000 [左、左、左]
  • 001 [左、左、右]葉bに到達
  • 01 [左、右]リーフCが到達している
  • 1 [右]葉dが発生します

実用的なアプリケーション [ 編集 | コードを編集します ]

静的ハフマンアルゴリズムを使用する主な問題の1つは、ツリー全体または確率表全体を送信する必要があることです。木の伝送の場合、ノードは順番に訪問されます 予約注文 、内部ノードは1つの鼓動（常に2人の息子がいる）に保存できますが、葉には、シンボル（8ビットなど）を覚えるために必要なビットの数が1つに加えて必要です。たとえば、上記の例のツリーは、（1、0、 ‘d’、1、0、 ‘c’、1、0、 ‘b’、0、 ‘a’）、つまり7 + 4・8 = 39ビットとして保存できます。

ただし、より良い圧縮は、メモリ要件の非常に急速な増加を犠牲にして、たとえ相関していなくても、さらに複数の文字を一度にコーディングすることで得られます。

一度に2文字後のコーディングの例 [ 編集 | コードを編集します ]

前の例のようなシンボルのコレクション

s = { a 、 b 、 c 、 d } {displaystyle s = {a、b、c、d}}

それに応じて発生する可能性について

p = { 0 、 初め ; 0 、 2 ; 0 、 3 ; 0 、 4 } 。 {displaystyle p = {0 {、} 1; 0 {、} 2; 0 {、} 3; 0 {、} 4}。}

シンボルの数が奇妙な場合は、最初または最後のシンボルでいくつかのコンベンションを採用する必要があります。これは実際には大きな問題ではありません。コーディングは次のとおりです。

  • シンボルをペアで接続する-AA、AB、AC、AD、BA、BB、BC、BD、CA、CB、CC、CD、DA、DB、DC、DDをそれぞれ確率で – {0.01; 0.02; 0.03; 0.04; 0.02; 0.04; 0.06; 0.08; 0.03; 0.06; 0.09; 0.12; 0.04; 0.08; 0.12; 0.16}。
  • 木は次の手順に従って成長します。
    1. （AA + AB）= 0,03;
    2. （BA + AC）= 0,05;
    3. （CA +（AA + AB））= 0,06;
    4. （BB + AD）= 0,08;
    5. （by +（not + ac））= 0,09;
    6. （BC + CB）= 0,12;
    7. （（ca +（aa + ab）） + bd）= 0.14;
    8. （DB +（BB + AD））= 0,16;
    9. （（ +（not + ac）） + cc）= 0,18;
    10. (CD + DC) = 0,24;
    11. （（BC + CB） +（（CA +（AA + AB）） + BD）= 0,26;
    12. （DD +（DB +（BB + AD）））= 0,32;
    13. （（（（ +（not + ac）） + cc） +（cd + dc））= 0,42;
    14. （（（BC + CB） +（（CA +（AA + AB）） + BD） +（DD +（DB +（BB + AD））））= 0,58;
    15. （（（（da +（ba + ac）） + cc） +（cd + dc）） +（（（bc + cb） +（（ca +（aa + ab）） + bd） +（dd +（db +（bb + ad）））））））））））

したがって、適切な標識のペアは次のとおりです。

  • AA – 101010
  • AB – 101011
  • 00011
  • AD – 11111
  • -00010ではありません
  • BB – 11110
  • BC – 1000
  • BD – 1011
  • CA -10100
  • CB – 1001
  • CC – 001
  • CD – 010
  • および-0000
  • DB – 1110
  • DC – 011
  • DD – 110

シンボルのペアあたりのビット数は3.73であるため、シンボルあたりのビット数は1.865です。これは、前の例よりもはるかに優れた圧縮（最大7.68％ではなく6.75％）です。より多くの文字を使用することで、最大圧縮に自由に近づくことができますが、メモリ要件は同時に圧縮されたシンボルの数に指数関数的であるため、メモリはずっと早く削除されます。

メモリ要件が小さいハフマンコーディング [ 編集 | コードを編集します ]

シンボルのペアが（上記の例のように）または3つのシンボル、または一般的なシンボルでコード化されている場合、ハフマンツリーのサイズが大幅に成長します。ハフマンツリーは、デコードできるようにコード化されたメッセージと一緒に保存する必要があります。したがって、ツリーが大きいほど、頻度の低いシンボルのコードが長くなります。 C.ウィーバーは、ハフマンアルゴリズムの変更を提案しました。これにより、ツリーを覚えるために必要なメモリが減少します。このアイデアは、マイケル・ハンカマーによって開発されました。マイケル・ハンカマーは、記事「メモリの要件が削減された修正されたハフマン手続き」に結果を公開しました（ 通信COM-27に関するIEEEトランザクション 、1979年、s。 930–932）。

変更は、Elseと呼ばれる追加の記号の導入で構成されています。 交換 すべてのまれなシンボル – 単一のシンボルがnビットを記述する場合、シンボルはその確率があるときに他のコレクションに移動します

p ⩽ 初め 2N。 {displaystyle pleqslant {frac {1} {2^{n}}。}}

Elseに起因する確率は、彼が置き換えるシンボルの合計に等しくなります。 Elseクラスに属するシンボルをコーディングするとき、Elseのコードは保存され、非圧縮シンボルが保存されます。たとえば、elseコードがある場合

010 2 、 {displaystyle 010_ {2}、}

シンボル「H」をコーディングすることです（ASCIIコード

72 十 = 01101000 2 {displaystyle 72_ {10} = 0101000_ {2}}

）保存されます

010 01101000 2 。 {displaystyle 010,0101000_ {2}。}。

これのおかげで、ツリーはより小さくなります。なぜなら、それは他のものに属さないシンボルのみを保持しているからです。これは十分であるため、他のコレクションのシンボルがメッセージに直接保存されているためです。この変更を使用すると、アルゴリズムの未修飾バージョンに関連して圧縮度をわずかに改善することさえできます。

ハフマンダイナミックコーディングアルゴリズム [ 編集 | コードを編集します ]

動的なハフマンコーディングは、未知の統計のデータコーディングです。
統計は、データが流れるように構築され、どのような記号または特定の数の文字が何ですか 改善します ハフマンツリー。

動的コーディングの利点は、コードコードを送信する必要がないことです。これの代わりに 同一 ツリー補正手順は、コーダーとデコーダーの両方が実行する必要があります。

ハフマンツリーを改善するための2つのアルゴリズムがあります。

  1. Faller-Gallager-Knuthアルゴリズム （オリジネーターはニュートン・フォラーとロバート・ギャラガーでしたが、この方法はドナルド・クヌースによって改善されました）
  2. Vitterアルゴリズム （Jeffrey Vitterによって開発されたFGKメソッドのさらなる改善）。

ベースで FGKアルゴリズム 次の仮定は、ツリーの形式にあります。

  • 各ツリーノットには常に葉があります 2人の子孫 ;
  • カウンターは各ノードに関連付けられています：葉に特定のシンボルのスピーチの数が保存されます（または値 比例 ）、他のノードでは、子供のメーターの合計。
  • ツリーが各ノードに関連する右から左から左に通過し、読み取りメーターを通過すると、非成長数の文字列が取得されます。

の Vitterアルゴリズム 最後の仮定は引き締められました：

  • また、一連の非成長数を取得しますが、最初は同じ値を持つ字幕内で、内部ノードから、そして最後に葉からあります。

葉のメーターが増加すると、アルゴリズムはツリーの小さな断片のみを変更し（一部のノードを移動します）、上記のプロパティを維持します。 Vitterアルゴリズム もう少し複雑ですが、それはより良い結果をもたらします。つまり、より短いコードよりも FKGアルゴリズム 。

その他の非刺された圧縮アルゴリズム [ 編集 | コードを編集します ]

after-content-x4