何となく 圧縮 - 基本的なアルゴリズムの再勉強

1日情報収集しただけでもかなりの量のアルゴリズムが出てきました。
昔独学したものばかりでしたがほぼ忘れてたので、もう1度頭に叩き込みました。

今回情報収集するにあたり以下のサイト
「M.Hiroi’s Home Page 」の「Lightweight Language」
がとても情報が整理されており、理論の説明、実際のコード、実行結果などが事細かに記載さされておりとても役に立ちました。
「M.Hiroi’s」様大変感謝いたします。
http://www.geocities.jp/m_Hiroi/light/index.html

私が今回やろうとしてるのは、音声やMPEG等動画系によく使われている次のフレームの画像を前後のフレーム情報から演算によって予測生成する技術を汎用データの圧縮に利用して実装してみようかと思っています。
なので、圧縮にはかなりの演算パワーが必要で、解凍にもそれなりの演算パワーが必要なヘビーな圧縮フォーマットになっていくかと思います。

基本的なアルゴリズムのキーワード

ランレングス圧縮
ハフマン圧縮
レンジコーダー圧縮
ブロックソーティング
PPM (Prediction by Partial Matching)
ブロックソート法
PackBits
Switched Run Length Encoding (SRLE)
ゼロランレングス (Zero Length Encoding)
γ符号 (unary 符号)
δ符号
二分木
CBT符号 (Complete Binary Tree)
ゴロム・ライス符号(Golumb)
ライス (Rice) 符号
シャノン・ファノ符号
ハフマン符号
平均符号長
算術符号
レンジコーダ (Range Coder)
LZ77 (スライド辞書法)
LZ 符号 (Zip-Lempel 符号)
LZ 符号は「辞書に基づく符号化方式 (辞書法, dictionary-based coding) 」
LZ77 符号は「スライド辞書法」
LZ78 符号は「動的辞書法」
LZSS 符号
特許の問題
データ圧縮と特許
http://oku.edu.mie-u.ac.jp/~okumura/compression/patents.html
LZB 符号
LZW 符号
レンジコーダ (Range Coder)
有限文脈モデル
マルコフ情報源モデル
接尾辞配列 (suffix array : サフィックスアレイ)
AA 木 (Arne Andersson tree)
赤黒木 (red-black tree)
接尾辞木 (suffix tree)
Union-Find

データ圧縮
http://ja.wikipedia.org/wiki/%E3%83%87%E3%83%BC%E3%82%BF%E5%9C%A7%E7%B8%AE

カテゴリ「データ圧縮規格」にあるページ
http://ja.wikipedia.org/wiki/Category:%E3%83%87%E3%83%BC%E3%82%BF%E5%9C%A7%E7%B8%AE%E8%A6%8F%E6%A0%BC

ZIP
http://ja.wikipedia.org/wiki/ZIP_(%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB%E3%83%95%E3%82%A9%E3%83%BC%E3%83%9E%E3%83%83%E3%83%88)

gzip
http://ja.wikipedia.org/wiki/Gzip

bzip2
http://ja.wikipedia.org/wiki/Bzip2

RAR
http://ja.wikipedia.org/wiki/RAR

NTCS
http://ja.wikipedia.org/wiki/NTSC

音声圧縮
http://ja.wikipedia.org/wiki/%E9%9F%B3%E5%A3%B0%E5%9C%A7%E7%B8%AE

可逆圧縮
http://ja.wikipedia.org/wiki/%E5%8F%AF%E9%80%86%E5%9C%A7%E7%B8%AE

非可逆圧縮
http://ja.wikipedia.org/wiki/%E9%9D%9E%E5%8F%AF%E9%80%86%E5%9C%A7%E7%B8%AE

JPEG
http://ja.wikipedia.org/wiki/JPEG
PNG (Portable Network Graphics)
http://ja.wikipedia.org/wiki/Portable_Network_Graphics

MPEG-1
http://ja.wikipedia.org/wiki/MPEG-1

MPEG-2
http://ja.wikipedia.org/wiki/MPEG-2

MPEG-4
http://ja.wikipedia.org/wiki/MPEG-4

H.264 / MPEG-4 AVC
http://ja.wikipedia.org/wiki/H.264

フレーム間予測
http://ja.wikipedia.org/wiki/%E3%83%95%E3%83%AC%E3%83%BC%E3%83%A0%E9%96%93%E4%BA%88%E6%B8%AC

フラクタル圧縮
http://ja.wikipedia.org/wiki/%E3%83%95%E3%83%A9%E3%82%AF%E3%82%BF%E3%83%AB%E5%9C%A7%E7%B8%AE

フーリエ変換 (Fourier transform)
http://ja.wikipedia.org/wiki/%E3%83%95%E3%83%BC%E3%83%AA%E3%82%A8%E5%A4%89%E6%8F%9B

超解像技術 (Super-resolution)
http://ja.wikipedia.org/wiki/%E8%B6%85%E8%A7%A3%E5%83%8F%E6%8A%80%E8%A1%93

ベクトル (vector)
http://ja.wikipedia.org/wiki/%E3%83%99%E3%82%AF%E3%83%88%E3%83%AB

MP3
http://ja.wikipedia.org/wiki/MP3

FLAC
http://ja.wikipedia.org/wiki/FLAC

誤り検出訂正
http://ja.wikipedia.org/wiki/%E8%AA%A4%E3%82%8A%E6%A4%9C%E5%87%BA%E8%A8%82%E6%AD%A3

CRC (Cyclic Redundancy Check, CRC)
http://ja.wikipedia.org/wiki/%E5%B7%A1%E5%9B%9E%E5%86%97%E9%95%B7%E6%A4%9C%E6%9F%BB

ECC (誤り検出訂正 / エラー検出訂正)
http://ja.wikipedia.org/wiki/%E8%AA%A4%E3%82%8A%E6%A4%9C%E5%87%BA%E8%A8%82%E6%AD%A3

MD5
http://ja.wikipedia.org/wiki/MD5

ブロックノイズ(blockiness)
http://ja.wikipedia.org/wiki/%E3%83%96%E3%83%AD%E3%83%83%E3%82%AF%E3%83%8E%E3%82%A4%E3%82%BA

AES (Advanced Encryption Standard)
http://ja.wikipedia.org/wiki/Advanced_Encryption_Standard

 

QRコード
http://ja.wikipedia.org/wiki/QR%E3%82%B3%E3%83%BC%E3%83%89
http://www.qrcode.com/

iQRコード
http://ja.wikipedia.org/wiki/QR%E3%82%B3%E3%83%BC%E3%83%89#iQR.E3.82.B3.E3.83.BC.E3.83.89
http://www.qrcode.com/codes/iqr.html

Similar Posts:

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

CAPTCHA


Time limit is exhausted. Please reload CAPTCHA.

コメントは承認待ちです。表示されるまでしばらく時間がかかるかもしれません。