ハフマン符号
固定長符号
削減
エントロピー

記号 回数 符号 ビット 合計ビット

ハフマン符号化についての詳しい情報

ハフマン符号ビルダー

英語の e のようによく使われる文字が、z のような珍しい文字と同じビット数を使う必要があるでしょうか。ハフマン符号化は、よく現れる記号に短い符号を、まれな記号に長い符号を割り当て、しかもそれを可能な限り最良の方法で行います。テキストを入力するか例を選んで、ハフマン木を1ステップずつ作ってみましょう。最も軽い2つの木が新しいノードの下にまとまることを何度も繰り返し、最後に木が1つ残ります。すると上からのそれぞれの道筋が1つの符号を表し、符号化されたビット列の中で各記号を追跡できます。 テキストを入力するか例を選んでください。どの記号も、回数を持った1枚の葉から始まります。構築を1ステップずつ進めましょう。各ステップでは最も軽い2つの木を、重みがその合計である新しいノードの下にまとめ、木が1つになるまで続けます。そうすると、上から葉までの道筋がその記号の符号になります。左は 0、右は 1 です。葉、表の行、ビット列の一部をクリックすると1つの記号を追跡でき、合計を固定長符号やエントロピーと比べられます。

使い方

  1. テキストを入力または貼り付けるか、ABRACADABRA や MISSISSIPPI RIVER などの例を選びます。
  2. 「次のステップ」で構築を1ステップずつ進めるか、「再生」を押します。各ステップで最も軽い2つの木が、重みがその合計であるノードの下にまとまります。
  3. 木が完成したら、葉、表の行、ビット列の一部をクリックして1つの記号を追跡し、タイルで合計を比べます。

木の作り方

各記号が何回現れるかを数え、それぞれを回数で重み付けした1枚の葉だけの木にします。そして簡単な1ステップを繰り返します。重みが最も小さい2つの木を取り出し、重みがその合計である新しいノードの下につなげるのです。ステップごとに木が1つ減るので、n 個の記号なら n − 1 ステップで1つの木が残ります。まれな記号は最初にまとめられて深いところに位置し、よく現れる記号は遅くまとめられて上の近くに位置します。

符号の読み方

上から下へたどります。左へ進むと 0、右へ進むと 1 が加わります。葉までの道筋がその記号の符号です。記号は葉にしかないので、どの符号も別の符号の先頭部分にはなりません。そのため、ビット列は区切りなしで復号できます。ビットに従って木を下り、葉に着いたらその記号を書き出して、また上から始めるのです。ABRACADABRA の場合、ハフマン符号は 23 ビットで済み、1文字3ビットの固定長符号では 33 ビットかかります。

よくある質問

ハフマン符号が最良なのはなぜですか?

各記号に整数個のビットからなる専用のビット列を割り当てる符号の中で、与えられた回数に対して合計がこれより短いものはありません。証明は構築の手順に沿って進みます。最適な符号では、最もまれな2つの記号を常に最も深い階層の兄弟にでき、それらをまとめると同じ種類のより小さな問題が残ります。ビットの総数は、木のすべての内部ノードの重みの合計に等しくなります。

接頭符号とは何ですか?

0、10、110、111 のように、どの符号語も別の符号語の先頭部分になっていない符号です。この性質があるので、復号器は符号語がどこで終わるかを常に知ることができ、区切りなしでビット列を読めます。ハフマン符号はどれも接頭符号です。記号は木の葉にしかないからです。

ハフマン木は1つに決まりますか?

完全にではありません。2つの木の重みが同じなら、どちらを先に取ってもよく、左右を入れ替えることもできます。選び方が違えば符号も違いますが、ビットの総数は常に同じです。このビルダーは同じ重みのときの選び方を常に同じにしているので、同じテキストからは常に同じ木ができます。

ハフマン符号はエントロピーにどこまで近づきますか?

平均符号長はエントロピー以上で、エントロピーを上回る分は1ビット未満です。「半分ずつ減る回数」の例のように、すべての確率が2分の1のべき乗のときは、エントロピーにぴったり等しくなります。算術符号化や最新のレンジコーダーは整数ビットの制約を避け、さらに近づきます。

テキストはどこかに送信されますか?

いいえ。木と符号はお使いのブラウザー内で計算され、テキストはこのブラウザーのローカルストレージに保存されます。

試してみますか?

ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。

エディターへ