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
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