データ圧縮技術の基本と仕組み
著者：岡野原大輔 藤本健 小川秀明
分類：ＣＰ参考書
評価：★★★★
鬱鬱です
こういう日はゲームでもやって気分を紛らわしましょう。ヨッシーアイランドはだいぶ飽きてきました。植木の法則のゲームや犬夜叉を少しやりました。マニアックなゲームだけではよくないので、サモンナイトをやりました。最近ＤＳでコナンのゲームが発売して欲しいなと思っていたが、ＤＳなんて物を持っていないことに気づき余計うつうつになりました。
うつうつです
こういう日はよくわからないことをやりだします。
名前がもし日本人一人ひとりを区別するためのコードのようなものだったとしたら、いったい何文字で完全に区別できるのだろうと考え出して30分ぐらいすごしたりした
ひらがなは旧字も合わせて全部で117文字（たぶん）なので日本の人口1億300万人を区別しようとするとlog117(1.3*10~8)となるので4文字あれば十分表現できるのではないかと思う。しかもこれは4文字で固定した場合の話で、1～4文字とすればもっと多くの情報をもたせることもできる。
漢字も含むともしかしたら一文字で１億3000万通りぐらいできるのではないかと思う
と言うことで情報の話が出たので圧縮についてです。
//////////////////////////////////////////////////////////////////////
ランレングス法
Huffman法
ＬＺ法 ＬＺ７７法 一度出た単語を（a,b）a始めからの距離、bその単語の長さで表す
ＬＺ７８ データから単語帳を作りその単語帳を元に圧縮する
ＬＺＳＳ スライディングウィンドウを作りこれから見る単語の長さをまず適当に決めて、それがスライディングウィンドウにないか調べる
ＬＺＷ 辞書に長さが一の単語を登録する（アルファベット）ファイルを一文字読み込んで、バッファの後ろに加える
算術圧縮法 全体を１と見てそれを何分割かしてその数をデータに置き換える
例 0.0=a ０．５＝b
RangeCode法 上位８桁が決まった時点で出力
割り算は全てシフトを使う
BlockSorting法 巡回データを作る ソートする
1 axsaca aaxsac
2 xsacaa acaaxs
3 sacaax axsaca
4 acaaxs caaxsa
5 caaxsa sacaax
6 aaxsac xsacaa
各列の末尾を読む→csaaxa
これは巡回データの5番目
サイズは変わらないが圧縮しやすくなる
PPM法 次の文字を今までの内容から予測
コメント