3部構成の1/3が今日で終了、らしい。
前回の補足
- ブロック化すると、どうして効率が良くなるか?
- 理想と現実の違いがあるから
- 理想的な符号語長は実数値、現実では整数値
- 頻繁に「悪化」して、ときどき「改善」される→理想と現実のギャップ
- 確率が大きくなるとギャップは大きくなる傾向がある
- ブロック化をすると全体的に
は小さくなる傾向がある
- ブロック符号化の運用について
- 末尾でブロック化できないのでは?
- 長さ10の等長ブロック化で25個の通報がきた...
- 運用で問題を回避する
- 最終ブロクだけ別扱いをする
算術符号化法
装置化が簡単で効率が良い符号化法装置化が簡単で効率が良い符号化法。- 符号器の内部で対応表を保持しておく必要があるが、その対応表が巨大になりがち
- 算術符号化法は対応表を使わない(on-the-fly)で符号化、複合を行なう
- コンパクトな実装になる => mobile機器とか?
- 通報系列全体を一つの符号化系列に変換 => そもそもうまくいくのか...?
- 系列発生確率と累積発生確率を使う
- こいつを数直線で表わすことを考える => 系列と部分区間との対応関係を表現してやる
- 占拠している区間の情報を表現する、累積確率を表として持っておかずに...
- 区間の木構造表現を利用
- 発生確率と累積確率を再帰的に計算
- 実数値 => 対応系列
- xがL(wB)より大きいか小さいかを見ていくだけ
- 代表させる実数xをどう表現するか?
- 該当する区間内で表現長が最小のものを選びたい
の小数点以下を...する
- 再帰計算で復元することを考えるとやっぱりスピードは遅くなりがちなんだろうか
- と思ったら、乗算を使わない近似計算の手法が研究されているらしい
Lempel-Ziv法
通報の発生確率が事前にわからない場合の符号化法通報の発生確率が事前にわからない場合の符号化法。- 2スキャン方式 => 一回なめてしまう=> 符号化が遅い
- Lempel-Ziv法というのは様々な圧縮ツールで使われている
- どのような情報源に対しても効率がいい(ユニバーサル符号化)
LZ77方式
- 過去に出現したパターンとの最長一致を考える
- 「動的に」ブロック化
- 一つのブロックを(i, l, x)のpairで表現
- (2, 2, D)は2つ戻って、2つコピーしてきて、最後にDをつけるという意味
- 性能評価は飛ばすらしい
- が、巨大な整数値を扱わないといけない場合が増える => 扱いにくい...
- 表現長を越える場合ばブロックを分割する必要がある
LZ78方式
- 3つのpairではなく(b,x)の2つのpairで表現
- 「b個前のブロックに文字xを追加したもの」 => ブロックのサイズはそっちで計算して!
- LZ77方式では、ブロックのサイズがボトルネックだった
- 「b個前のブロックに文字xを追加したもの」 => ブロックのサイズはそっちで計算して!
許容範囲内での情報劣化と引き換えに、効率を稼ぐ符号化法
画像や音声の符号化法について画像や音声の符号化法について。- 詳しくは専門の授業で
- 非可逆符号の相互情報量
- 可逆符号よりも小さな相互情報量しか担っていない
- 非可逆符号の相互情報量
