読者です 読者をやめる 読者になる 読者になる

ハフマン符号の性能との限界、その他の符号化

情報理論

前回の復習

  • 4元のハフマン符号
    • 何種類か木の作りかたがある => どの作り方がいいんだろう、どうやったら作れるだろう
    • 仮想的な点を作って3k + 1個の節点を容易してあげればいいんじゃないんだろうか

ハフマン符号の性能と限界

  • ハフマン符号は理解しやすくて、しかも性能がよい
    • 性能がよいのはどれくらいよいのか?
  • 通報一個に符号一個を割り当てる
  • 平均符号長の限界定理
    • 任意の符号について、平均符号長は必ずL \geq H_1(S)となる
    • どんな効率的な符号化でも、平均符号長は一次エントロピー以上になる
    • かなり重要な定理!!
  • 平均符号長がL < H_1(S) + 1となるような符号を構成することができる

シャノンの補助定理

\sum_{i =1}^M q_i \leq 1 を満たす任意の正数q_1, q_mに対し、
- \sum_{i =1}^M p_i \log_2 q_i \leq - \sum_{i =1}^M p_i \log_2 p_i = H_1(s)
等号成立はp_1 = q_1, \cdots, p_M = q_Mのとき、かつそのときのみ。

  • クラフトの不等式とシャノンの補助定理を使うと上の定理が証明できる
  • ハフマン符号についてはもっと強いことが言えて、ハフマン符号よりも平均符号長の小さな瞬時符号は存在しない、ということまで言える
    • 証明は略

ハフマン符号化の拡張

  • ハフマン符号は2元の情報源の符号化には向かない
  • 複数の通報をまとめて符号化(ブロック化符号)を考える
    • 通報あたりの平均符号長を1以下にできるかも
    • 2元情報源の符号化にも使える...かも?
  • まず、通報の系列をブロック化する
  • ブロック化された通報の系列をハフマン符号化する
  • 符号語の系列を得る
  • 平均符号長は改善されたけど、2つずつでブロック化するとして、3つきたときとかはどうするの?
  • ブロック長を大きくすると一通報あたりの平均符号長は小さくなる

ブロック符号化と平均符号長

  • 「ブロック長を大きくすると一通報あたりの平均符号長は小さくなる」はどこまでよくなるのか?
  • n個単位でブロク化した通報 = n次拡大情報源S^nの通報1個

情報源符号化定理

  • 一通報当たりの平均符号長に換算すると\frac{H_1(S_n)}{n} \leq \frac{L_n}{n} < \frac{H_1(S^n)}{n} + \frac{1}{n}という不等式を得る
  • nを無限大に飛ばした場合、極限エントロピーを使って、H(S) \leq L \leq H(s) + \epsilonに持っていける
    • シャノンの情報源符号化定理!!

情報源符号化の限界

  • 結論としては、ブロック長を長くしてハフマン符号を使えば効率的にはベスト
    • だが、極限エントロピーを越えることはできない
  • ハフマン符号化は実用面から見るとデメリットがある
    • 通報の発生確率をあらかじめ知っておく必要がある
    • A => 01というような対応表をメモリに持っておくとすると、ブロック長が長くなるにつれて対応表が巨大になっていってします
      • ブロック長に関して、指数関数的に増えてしまう

非等長ブロックハフマン符号化

  • 対応表が巨大になってしまうのをどうにかしたい
    • ブロックの長さとして異なるものを許そう
  • 頻出パターンに対しては、短い符号を割り当てたい
  • どうやってパターンを定義しよう?
    • 非等長ブロックハフマン符号化
  • 例のやつだと一通報あたりの符号長はブロック長3のときと同程度の効率を達成している
    • 持っておかないといけない対応表として、少なくなっている!!ということ
  • 入力のデータをどういう風に切るかという複雑さは発生してしまう

ランレングス符号化

  • 同じ記号が連続して出てくるものに注目しよう
    • 同じものが続くやつだけ見ればいいから、非等長ブロックハフマン符号化より簡単?
  • すっごい長い連続しているやつがきたら上限以下のものに短く分割する
  • 通報の出現頻度に偏りがあるときに、有効な符号化の方法
  • ラン長の長さはどうやって決めるのがよいのかしら?
  • ランレングス符号化は非等長ブロックハフマン符号化の特殊なケースと考えることもできる