【2ch】圧縮アルゴリズム【オリジナル】

学生の頃書いた二段階ソート法によるBW変換（当時のコメント削って５０行）
もっと速いバージョンはバグが入ったので、今作りなおしている。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static unsigned char *pText;
static int gLen;
int compare(const void *a, const void *b) {
　int l = gLen - ((*(int *)a < *(int *)b) ? *(int *)b : *(int *)a);
　int r = memcmp((const char *)(&pText[*(int *)a]),
　　　　　　　　 (const char *)(&pText[*(int *)b]), l);
　return (r == 0) ? (*(int *)b -*(int *)a) : r;
}

int main(int argc, char *argv[]) {
　FILE *fp;
　unsigned char *str;
　int i, j, k, l, *aArray, *aNext, pos, list[256], sum[256];

　if (argc < 2) {puts("usage> exec infile"); return -1;}
　fp = fopen(argv[1], "rb");
　fseek(fp, 0, SEEK_END); gLen = ftell(fp); rewind(fp);
　pText = str = (unsigned char *)malloc(gLen +1);
　fread(str, 1, gLen, fp);
　str[gLen] = 0;

　aArray = (int *)calloc(gLen +1, sizeof(int));　/* これが suffix array */
　aNext = (int *)malloc(sizeof(int) *(gLen +1));
　for (i = 0; i < 256; i++) {
　　list[i] = -1;
　　sum[i] = 0;
　}
　for (i = gLen; i >= 0; i--)
　　if (str[i] > str[i +1])　sum[str[i]] += 1;
　　else {
　　　aNext[i] = list[str[i]];
　　　list[str[i]] = i;
　　}
　for (pos = i = j = k = 0; j < 256; j++) {
　　pos = i = sum[j] + pos;
　　for (l = list[j]; l >= 0; l = aNext[l])　aArray[pos++] = l;
　　qsort(aArray + i, pos - i, sizeof(int), compare);
　　for (l = i - sum[j]; l < i; l++) {
　　　if (aArray[k] == 0) k++;
　　　aArray[l] = aArray[k++] -1;
　　}
　}
　return 0;
}

うわーん、これもバグありのバージョンを持ってきちゃった・・・打つ。

>>853-854 におけるmain関数内の次の部分を置き換えてほしいでつ

int i, j, l, *aArray, *aNext, pos, list[256], sum[256], typeA[256], t = 0;

...

　for (i = gLen; i >= 0; i--)
　　if (str[i] > str[i +1]) {
　　　sum[str[i]] += 1;
　　　t++;
　　}
　　else {
　　　aNext[i] = list[str[i]];
　　　list[str[i]] = i;
　　}
　for (pos = i = j = 0; j < 256; j++) {
　　pos = i = sum[j] + pos;
　　for (l = list[j]; l >= 0; l = aNext[l])　aArray[pos++] = l;
　　qsort(aArray + i, pos - i, sizeof(int), compare);
　　typeA[j] = i - sum[j];
　}
　for (i = 0; t >= 0; t--) {
　　if (aArray[i] == 0) i++;
　　aArray[typeA[str[aArray[i] -1]]++] = aArray[i++] -1;
　}

＞856
よくわかんないけど最後のforはもっと長くループさせないとだめじゃない?
たとえば、最後までまわすとか
for (i = j = 0; j < gLen; j++) {

>>857
そうでつた。元のソースではそうなってたのに・・・撃つ。

超hoshu

AA の

圧縮方法は

文字サイズを小に！！

>>860-862
kterm + lynx で見て、unreadable にすればいいのだ！

>>863
Tiny なら、全体のバランスを調整するときに使ったことはあるが。
（IEのフォントサイズ小みたいに）

unreadable は本当に読めないし、つぶれるからいまいち。

http://pcweb.mycom.co.jp/news/2002/11/13/09.html
これってどうなのさ

>>865
強敵だな（ｗ

>865
lossyな圧縮か。比べてもあまり意味ないな…

ソースネクストは、JPEG/GIFなどの画像ファイルを圧縮してファイルサイズを縮小できる
圧縮ソフトを発表した。

使用されているCATアルゴリズムは、圧縮アルゴリズムを複数用いるこ とで、例えば画像
であれば「建物」「空」といったパーツごとに最適な圧縮アルゴリズムを選択し、ファイルサ
イズを縮小する。

同社調査によれば、3.33MBのJPEG画像が、ZIP圧縮の場合3.31MBにしかならなかった
ものを、114KBにまで縮小できた。

不可逆圧縮だが、見た目上はほとんど変わらない画像になる。複数のアルゴ リズムを
利用するにもかかわらず、　

「圧縮・解凍時間ともに短時間」　である点も 特徴だ。
http://pcweb.mycom.co.jp/news/2002/11/13/09.html

不可逆圧縮興味なし。

要するに画像を圧縮してるんであって、JPEGファイルを圧縮してるわけじゃない。
MPEG1をMPEG4にコンバートしてるようなもんだろ?
ZIPと比べてるのは不当表示だよ。

まさにMPEG4のオブジェクト圧縮に似てるね。

JPEG2000とか同じく不可逆で縮みそうなものと比べるべきだわな

で、これはなんてフリーソフトが元なの？

http://pc3.2ch.net/test/read.cgi/software/1034921591/483-

494：◆Ukspgzd3n6：sage：02/11/13 (水) 23:54 ID:3tJrW3s5
http://www.quikcat.com/
超縮は、↑の QuikCAT Messaging Optimizer の
日本語版・・・のような気がするなぁ。拡張子も同じ .qcf だし。
英語版だけど、試用できるっぽい。

495：名無しさん＠お腹いっぱい。：sage：02/11/13 (水) 23:57 ID:7Pz0RnHA
↑にあるのはただのデコーダなだけじゃない？

496：◆Ukspgzd3n6：sage：02/11/14 (木) 00:05 ID:SsZE8nfL
>>495
あ・・・そうだった。
でも、圧縮する方法あり。
http://www.quikcat.com/products/qmo/qmo_tryit.htm
要するに、[email protected] にファイルを
送ると､圧縮して返送してくれる。
ちょっと試してみる。

>>875
まだ [email protected] からの返事が無い。

ちなみに、フリーソフトの Compressed File Reader は 6MB もする。
何だかと思えば、解凍ルーチンの DLL が妙にデカい。


相当複雑なアルゴリズムなんだろうなぁ。多分。

>>876
> 相当複雑なアルゴリズムなんだろうなぁ。多分。
て、そんなこと無いな。(・∀・;)

そこへメールだしても、ファイル盗まれるだけ

>>878
漏れは、盗まれても構わないファイルを送ったYo

しかし、きちんと「圧縮してくれ」と文面に書いておかないと駄目かも。
未だに返事は来ないし。

大方英語が向こうに伝わっていないのではないか。
翻訳サイトなんか当てにならない。

英語分かる人にチェックしてもらった方がよいね
翻訳サイトが不自然な英語であることを見抜けないなら

あきらめたのか？

バイトペアエンコーディングをもうちょっと詳しく知りたい。Ｃマガの
情報である程度はわかったけど、詳しいインプリメンテーションが
よくわからん。何か情報ない？

>>883
ttp://mcgi2.nifty.ne.jp/cgi-bin/thread.cgi?user_id=VZV05226&disp_no=1068&log_no=484&msg_per_page=10&def=10
これじゃ不満なのか？
（ﾟ∀ﾟ）Sﾀﾝ ﾆ ｱﾔﾏﾚ！

>>884
いや、情報はありがたいのだが、そのレベルはＣマガに出ているのよ。
ただＣマガのソースってコメントがほとんどないし、バグは残ってるし
で今ひとつわからん（展開スタック不足だった＞Ｃマガソース）。
ちなみに、その掲示板の「アスキー128を８ビットで〜」のくだりは半分
間違い。バイナリデータの圧縮にも効果はあるし、圧縮パラメータの
設定次第だがLZW法に近い圧縮率が得られる。しかも圧縮は遅いが
展開は高速（ビットレベルで符号化しないから当然）。

Cマガ版にあったバグ除いた(多分)コード見つけた。（英語）
http://www.csse.monash.edu.au/cluster/RJK/Compress/problem.html
http://www.csse.monash.edu.au/cluster/RJK/Compress/bpe.c
http://www.csse.monash.edu.au/cluster/RJK/Compress/bpd.c

日本語の解説のページは数年前はあったんだけど今は消えてる。

>>885 設定次第だがLZW法に近い圧縮率が得られる。
んなこたぁない。
割り当てキャラクタ数を最適化したとしてもLZファミリには及ばないよ

>>887
同意

＞ちなみに、その掲示板の「アスキー128を８ビットで〜」のくだりは半分
＞間違い。バイナリデータの圧縮にも効果はあるし、圧縮パラメータの
＞設定次第だがLZW法に近い圧縮率が得られる。

オリジナルのBPEは純粋に7ビットASCIIオンリーだったはず。
バイナリ対応やLZW並みの圧縮率というのは、改良版ではないか？

>>883-888

Gage[1994]が見つからなかったが（雑誌の記事だから?）、
調べてみると、BPEには単純版と改良版があるらしいぞ。
そもそもその単純版が、1994年よりももっと前（70年代〜80年）に
提案された別の方法を改善したものとして存在し、
それをさらにバイナリデータ対応、LZW並みの圧縮性能にしたのがGageらしい。

やぱーり、The C Users Journal, February 1994 edition か
Cマガジンを読むしかないのか。

>>887
885だけど、それは頻出バイトペアや未使用キャラクタの余り数、圧縮ブロックの
サイズ設定とかでかなり違ってくると思われ。LZWに適したデータ分布やBPEに
適したデータ分布は当然あると思うし、頭ごなしに全否定するのもどうかと思うが。

で、圧縮率に関しては「近い」というのがミソで、LZW以上の圧縮を得ようとは思わ
ない。展開が非常に高速で（展開のコストが安く）実用になる圧縮率があることが
重要なんだよ。実際にCマガのをデバッグしたソースでバイナリを圧縮してみたが
多くの場合で半分から４５％程度に縮んでいた。これくらいなら十分。

>>886
>>889
ありがとう、参考になった。

>>890
検証してないけど、LZWってBPEより必ず圧縮率がいいんじゃないか？
両者とも、SEQUITORと同じ系に属するだろ？
で、両者が作る辞書のモデルを解析して比較してみれば、
その関係がわかると思うんだけど・・・。

BPEの辞書はLZWの増分分解で作成される辞書と同じ形になる・・・と思うし、
後は出現頻度順か、出現順かの違いくらいで・・・。

多分誰か解析していると思うなぁ・・・njNECで探してみるか。

超縮はJPEG2000だった！？
ttp://homepage1.nifty.com/author/qcf/jpegqcf.htm

>>893
Sﾀﾝの粗相、もとい予想、大当たりですね。

　ところでところで、オフィスノアの動画圧縮 Nancy codec って、どんなアルゴリズム使ってるか、ご存じない？ 　特許情報調べればわかるのかもしれんのですが…。

>>895
差分とって、誤差が一定になるまで出力しない、っていうのじゃなかったかなぁ？
どっかの紹介記事にそういう説明があった気がする。
試しにやってみても、全然縮まなかったので、
もちろんもっとそれ以上の何かが必要なのだろうけど。

今日、Cマガのyz2の記事読んだんだけど
なんでファイルサイズをわざわざテキストで
出力するかイマイチ理解出来ん。
小さいファイルなら元ファイルのサイズを出力する
と確かに無駄な部分が出てくるが、それだったら
１６進表記でテキスト出力した方が効率か良いよう
な気がする・・・数字＋アルファベットで３６進数で表記とか・・・
ってここまで面倒な事はしなくていいか（ｗ

>>897
Elias符号使えば？

>>897
記事にワケが書いてあったと思う。

それに、テキストで出力しておけば、事実上どこまでも
大きいファイルサイズも表現できると思うが。

>>899
別にテキストじゃなくても同じことができるし
テキストを使わないほうが小さくなることに変わりはない。

>>900
そりゃね。
Filesize のビット数を記録すれば問題ないことだし。

#テキストだとしても、ヘッダごと圧縮すれば問題ないかも。

>>901
そのために>>898に書いてあるような符号化法を使うんだろ？？？？

>>900
ヘッダのサイズなんて大きな圧縮ファイルでは誤差の範囲だろ。
”Keep it simple, stupid.（単純なままにしとけって言っただろ！このヴォケが！）”だ。

>>903
数値1つエンコードするのが複雑だというくらいなら
そもそも圧縮プログラムなんて論外だろ。

だいいち、2進10進変換＋10進2進変換がエリアス符号に比べて
そんなにシンプルかよ。糞ヴォケ。

テキスト使うなんて白痴もいいところ。

Ｃマガ読んでないから知らないけど、
書庫内のファイル名も圧縮対象にするってこと？
識別用のマジックナンバー以外はやっちゃってもいいかもね。
リスト出力に多少時間かかりそうだけど。

どうでもいいけど、作るんなら統合アーカイバPrjのDLL形式にも
対応して欲しい。（GCAとか対応してたっけ？）
わざわざ独自にＧＵＩ作ったりしてるのあるけど、無駄にしか思えない。

つーかファイルサイズなんてリトルエンディアンのint64でいいんじゃないのか。

Elias = イライアス

「イライアス」の符号よりも、アーカーバの場合は、
「やまもと・おち」のフラッグ符号がいいかもしれないよ。
最適性の確保は難しいが、高速で、符号自身で誤り伝搬を防げるから。

まあ何にしろ、10^15程度の数値を表現するには60ビット程度あれば
一意復号可能な符号などいくらでもあるわけで。
（もちろんそれらは、加算無限大の数値をいくらでも表現できる）

板違いの気配で悪いと思っています。
以下のCABファイルの中身を抽出したいのですが、可能でしょうか？

◆現象
○通常のCABファイル(Windows Cabinet)ではないようです
○WindowsOSなどのCABは、バイナリエディタで見ると、先頭が
　「MSCF」(4d 53 43 46)と始まり、その後に
　中のファイル名一覧が文字から見て取れますが、
　問題のCABは、「ISc(」(49 53 63 28)で始まり、中のファイルは解らない。

◆ソフト例
○Norton全般(SystemWorks2002(英語)、AntiVirus2002(日本)、
　Utilities(日本語)すべてのCAB))。
○某ファックスソフト
○タイピングソフト(特打ヒーローズ　名探偵コナン)
　が同じ形式であるように確認できました。

Installshieldやね。
Xacrettはどうだ？

Installshieldやね。
Xacrettはどうだ？

XacRett成功しました。。
InstallShieldでしたか。。。
ありがとうございますた。

>>910-913
別の板でも見たぞこの野郎

つまり、やま○き氏は、Elias符号を始めとする、
整数のユニバーサル符号化法を知らないということでよろしいか？

>>906
統合アーカイバ形式のDLLに仕立てるには、少々書き直さなきゃ
いけないと思う。

確かに YZ2 の GUI は使いにくいし、yz2dlg.dll もそのまま使えるほどの
完成度じゃない。

>>915
知らないというか、知ってても使っていないというか。
提案してみようかなぁ。

>>915
簡単にエンコード・デコード出来てかつ人が見て読める形式だと
文字列化しかないんじゃないの。

とマジレスしてみる。

こんなのﾊｹｰｿ

ttp://multix.jp/download/other/BNC.LZH

>>917
だから何度も何度も書かれているとおり他に簡単な符号化は山ほどあるし、
人が見て読める必要は全く無いし、文字列にしたら損。

必死だな。。。

こんなのﾊｹｰｿ

ttp://kamakura.cool.ne.jp/miyax/

>>918
途中なにやってるんだかﾜｶﾝﾈｰ!んだけどLZ78と
BPEを掛け合わせたようなﾔｼだｿﾚ。圧縮ソース
に対して可変長文字列比較でなく２文字長固定
(32ビット幅固定を意識か？)だけで探索掛けてる
のと構築された辞書自体が圧縮されてる上その
辞書ｿﾉﾓﾉを順次圧縮後ﾃﾞｰﾀとして吐くのが特徴？
辞書サイズは4096個バイトペア分だが仮に圧縮
率50%に達してれば(LRUが効き出すまでに)8000
個相当分はキープしてるわけか…。LZSSが短距
離、LZWが中距離ならこれは長距離走者っぽい。
(ｽﾀｰﾄ直後はLZW以上のｽﾛｰﾍﾟｰｽぶりだわ)
仮に“ababab...”なんてデータを1GBほど食わすと
30個ほどしか辞書項目消費しないあたりはｷｼｮｲ。
＃展開速度はLZSSより遅いがLZWよりは早いな

>>922
文章見ているだけだとSEQUITORとかMPMに近いように思えてしまう。
ソースプログラムまだ読んでない。読もう。

>>921
しまった！標的に気づかれたぞ・・・




ようこそ！

文脈ソート法っていえばSﾀｿだよね。ﾊｧﾊｧ

>>1がおいてけぼりにされてる感があるけど

中身を半分に削って拡張子を.2chにしてしまえばいいだろう

WAVEファイルって音楽のジャンル(ジャズや演歌など）ごとに独特のパターンって
あったりしますか？
圧縮はあまりよく分からないのですが、音楽ジャンルごとに効率の良い
圧縮アルゴリズム（ロスレスで）つくれないかな？とふと思ったもので・・・・・・・

これからあげる圧縮アルゴリズムの欠点は
圧縮時間と展開時間とデータの保証がないと言うことだ。
だから、２Ch圧縮。

FTPでもHTTPでも特殊なポートでもいいが、
ある取り決めのデータのハッシュキーで存在するURL(IPでも可)を生成し圧縮。
URLはもちろん更に都合良く圧縮。展開ではURLを展開し、
そのURLより、更に圧縮されたデータをWEBよりダウンロード。
更に合成し展開する。(驚異的な圧縮が可能だ！！ゴラァ！！)
（欠点は、URLが存在しなくなった時だが、それは問題にする気は無い。
展開出来ないだけだ。2Chダシ）
リソース共有圧縮と展開。

>>928
それやるんなら現状でもWinMXで万事OKな気が（^^;

>>928
それは「圧縮」とは別の概念だということはかなり過去から言われているが・・・
データ圧縮はShannon limitとともに語らなければならないのである。

フトン圧縮袋使え！！

>>927
ジャンルごとにエンコーダ・デコーダ用意すんの？
誰も使わんだろ。

>>927
ジャンルというより楽器の種類・数・編成によるんじゃない。
楽器の音色と音符を抽出・分離してやれば驚異的な圧縮が可能だよ。
さらに音色は複数の曲にまたがって使用可能だから使えば使うほど圧縮率が上がる優れもの。

>>933
MIDIとどこが違うん？

>>934
MIDIの音色・音階表記は究極の圧縮ともいえる。
現在の研究では、複数の音色（せいぜい３和音）を、
単体の音に分解することがようやくできるようになったレベル。

>>935
しかしそれでは同じ楽器でもストラディバリウスとか名器の音色が
表現できなくなるというワナ

>>936
楽器ナンバーにどんどん登録して・・・
となると辞書のインデックスと同じことになるだろうか。

それでもかなりの圧縮にはなりそうだ。

>>937
よく考えてみると、演奏者の腕も表現できないというワナ

モー娘の圧縮率高そうだな

基本的な演奏における符号化は次の要素でよろしい？

演奏者 ＋ 会場 ＋ MIDI信号（楽器 ＋ 音色 ＋ 時間）

>>930 データ圧縮はShannon limitとともに語らなければならないのである。

そんな事、誰が決めたんですら?

>>941
数学的に…、って意味じゃないのかねぇ。
Shannon limit (てかエントロピー？)って可逆圧縮と不可逆圧縮の絶対境界線だっけ？

>>942
＞Shannon limit (てかエントロピー？)って可逆圧縮と不可逆圧縮の絶対境界線だっけ？

無歪み圧縮は、Shannon限界までしか圧縮できないことが数学的に証明されていますね。
有歪み圧縮もShannonのレート定義が重要ですしね。

ま、何にしろ通信と圧縮はShannonが創生したしたわけで。

Rissanen等の研究によれば、情報圧縮の限界は計算できない事が証明されてるのではなか?
限界はあるけど、それを計算するアルゴリズムは存在しないってゆーよーな。
→ Shannon limit は計算できない（から議論してもしゃーない）!?

# うろ覚えスマソ

>>944
それは一般情報源についてかな。

Shannon limit は定義だから。
H(P) = -�� p_i log p_i, p_i in P

入力が乱数列みたいなときは、シャノンさまが限界かもしれないけど。
2ch みたいに繰り返しの多い入力に対する圧縮の限界も評価できる
んすか？

>>946
あるモデルを想定して、そのモデルの下でのエントロピー達成度を調べることで評価される。
もしすべてのモデルについて評価できるならば、
全体の評価が出来るわけだが、すべてのモデルを評価できないので、
特定のモデル（LZ77, LZW, ブロックソート法, などで考えるとよい）などを使うわけだ。

どちらにしろ、>>945の式H(P)よりも小さくはならない。

>>946
情報源によってエントロピーが異なるから、
シャノン限界（945 も言ってるけど定義なので値は前提によって異なる） も変わる。

参考：
炉辺夜話
http://www.ne.jp/asahi/personal/kobayashi-osamu/Writings/Essays/BF.13.html
http://www.ne.jp/asahi/personal/kobayashi-osamu/Writings/Essays/BF.14.html

2ch がテンプレだけで構成されていると考えて、
特定のテンプレの出現頻度が高い、と単純化して考えれば分かりやすいと思う。
英文で特定のアルファベットの出現頻度が高いのと同様になるから。

日本語のエントロピー、歌の歌詞のシャノンエントロピー、
新聞文章のシャノンエントロピー、2ch 文章のシャノンエントロピー…
はどのように異なるかという話になる。
適当な数をサンプリングして計算すれば圧縮限界の理論値も出せるかと。

＞適当な数をサンプリングして計算すれば圧縮限界の理論値も出せるかと。

そ、それは理論値ではなく実測値（実験値）では・・・
理論値は数学的に証明できるものでないと。

つーか、一般情報源に対する理論値を証明できたらチューリング賞ものですね。

う、そうだな。すまん。

>>950
謝りついでに、次スレあけおめことよろ

>>949
できない(理論値などでない)ことがわかっている。
対象物を限定すれば、特定のものを1ビットに圧縮できる一方、
限定しなければ(あらゆるデータが一律に出現する)、
圧縮など不可能で、無意味だから。
圧縮とは、存在しそうも無い膨大な種類のデータでは大きくなるかわりに、
ごく一部のデータだけを小さくする技術。

>>952

ん？ そんなことはないですよ。
最近は韓先生などが、一般情報源に対する漸近的圧縮限界を証明されました。
これには情報スペクトル理論が用いられています。

韓先生と共著で一般情報源の理論的限界について考察されている、山本先生の紹介ページ
http://www.i.u-tokyo.ac.jp/mi/staff/yamamoto-j.html
論文を当たってみてください。

>>953
論文読まないとなんともいえないが、この場合「一般情報源」に特殊な偏りがあるんだろうね。
でなければ、圧縮は不可能であることは自明。
明確な偏りがある場合、対象としているデータと濃度が決まれば理論値は簡単に出る。
一つのデータを一個の巨大な整数値とみなし、その出現確率を使って
算術圧縮した時のビット数が、圧縮率の限界になる。
もちろんこれは理論値であって、実用にはならないが。

参考ページ
http://www.hn.is.uec.ac.jp/~han/Spectrum-preface.html

今すぐ読める論文
http://search.ieice.org/jpn/2001/files/j000a06.htm#j84-a,6,698

＞「一般情報源」に特殊な偏りがあるんだろうね。

つうか、単に確率分布があるだけで。
それに見合った符号化（サイズの増減は確率分布による）ができるわけで。
その確率分布の特性にエルゴード性や、定常性が存在するか否かが、
一般情報源かどうかを区別しているわけですね。

>>956
>>957
>>958
サンキュー。予想通りだった。つーかこれ当たり前のことで、ある尺度で捉えた場合の
理論的限界は求まっても、真の限界はわかんないよ。
例えば、π１００万桁の数値を圧縮するとする。これを乱数列と見なした場合の限界は
この方法で求まるが、πを数ビットに、他のものを多少増やす圧縮方法もあるわけ。

>>959
えっと、それはたぶん何を語っているかの方向の違いですね。
何を目的として情報源符号化を語るかを注意しないといけないということには、同意です。

他の方（特に初学者）に注意しておいて欲しいのは、次のこと。
すべてのデータを圧縮できる符号は存在しない、は、真です。そして
一般情報源の理論的限界を達成するような符号は存在する、も、真です。

＞例えば、π１００万桁の数値を圧縮するとする。これを乱数列と見なした場合の限界は
＞この方法で求まるが、πを数ビットに、他のものを多少増やす圧縮方法もあるわけ。

それは一般情報源の符号化ではない

>>960
>>961
でも、漏れ達の周りのデータって「一般情報源」から外れるものばかり
テキストも音楽も画像も単なる「一般情報源」では無い罠

>>961
>>962
いや、パイのデータを短くするような符号化法は、
最適な符号ではないことは確かだが、一般情報源の符号化であることに違いはないだろう。
最適な符号は、パイだったらパイのエントロピーに符号化する。
（パイのエントロピーはほぼランダムなものと同程度であるらしいから）

テキストや音楽のデータは、一般情報源からの出力と考えられる。
したがってその確率分布が圧縮しやすければ圧縮になり、
ランダムならば圧縮にならない。

>>963
最適な符号で無いのに、πのエントロピーに符号化するのがなんで最適な符号になるの？
それはあくまで、乱数列と見なした場合のことだよね。
そうでない方法、「π６５５３６桁」みたいに圧縮する方法もある。

>>964
最適な符号とは、あらゆる入力に対して、そのエントロピーまで符号化できる符号。
一方、特定の入力を短くするのは、最適でない符号。

で、パイを符号化するために「パイｎ桁」とするのは、実は「符号」ではない。
それはモデル化だな。

他にも、
この楽曲は「ｘｘ交響曲」である、というような上の方で議論のあった、
音楽データのMIDI化みたいな符号化法も、実はモデル化ということ。

で、パイ＝3.1415926535...
という数値そのものをたとえば２バイトで表現するとか、
そういった「符号」を考えるならば、最適ではない符号ということで。

>>963
> テキストや音楽のデータは、一般情報源からの出力と考えられる。
> したがってその確率分布が圧縮しやすければ圧縮になり、

それだけじゃないってことを言っている。例えば、
「観自在菩薩行深般若」の後、何がくるか圧縮できるでしょ？
確率分布だけで圧縮する以上の方法があるの。

音楽もそう。一定のリズム、人間が作る音楽の特性、そう言ったものを取り入れるか、
入れないかで、最適な符号なんて変わってしまうよ。
画像もウェーブレットを使った高次元の処理をすることで、1次元のデータ列とみた場合とは
結果が変わってくる。

>>966
えーと多分>>965を読む前に書かれたと思いますが、一応>>965の追記も兼ねて。

データ圧縮（情報源符号化）は、次の要素からなっています。
モデル化　＋　確率推定　＋　符号化

用語の使い方の問題かもしれませんが、一般に「符号化」といった場合は、
すでに確率が与えられている場合のみの操作を表します。
たとえば、符号化の族には、Huffman符号や算術符号、が入りますが、
LZ77やPPMなどは「符号化」ではありません。
またHuffman符号などで、記号の頻度を求める前処理がありますが、
それもモデル化であり、純粋にHuffman符号といった場合には、
すでに確率が与えられている必要があるわけです。

＞「観自在菩薩行深般若」の後、何がくるか圧縮できるでしょ？
＞確率分布だけで圧縮する以上の方法があるの。

したがって、続く文字列を推定するのは「モデル化」
モデル化によって得られた知識から、確率を算出するのが「確率推定」、
得られた確率をビット列に変換するのが「符号化」です。

>>965
モデル化を考えない符号なら、そのデータの存在確率で算術圧縮するのが
最適で、とっくに解決している。
現実のデータの圧縮を考えるのなら、モデル化は避けられないし、
乱数列と見なすのも一つのモデルに過ぎない。
で、漏れは、乱数列と見なすこと自体が最適でないと思うわけ。
乱数列と見なした場合は、そのデータの存在確率で算術圧縮すればいいと思うわけ。

流れがおえないのですが、結局用語の問題ということでよろしいですか？>>967

(･┏┓･) ＜まあもちつけｳﾞｧｰ

松

H(P) = -Σ p_i log p_i, p_i in P (>>945)は、各p_iが独立というモデルの下でのシャノン限界（情報量）では？
モデルが異なれば、限界も異なるはず。
で、どのモデルが適当かを決める一般的なアルゴリズムは存在しない(>>944)?
モデル化できなければ、確率推定もできないし、エントロピーも計算できないし、（最適）符号化もできない(>>967).
今ある圧縮符号は、思いつきで決めたモデルに基づく最適符号にすぎないから、もっといろんなモデルを考えよう(>>964,>>966)!
…という理解でよろしいでしょうか？

>>944 Rissanen等の研究によれば、情報圧縮の限界は計算できない
>>972 どのモデルが適当かを決める一般的なアルゴリズムは存在しない

これって正しいんでつか?

埋め

＞H(P) = -Σ p_i log p_i, p_i in P (>>945)は、各p_iが独立というモデルの下での

ちうよりは、情報量をつきつめていくと、単体では確率など存在しなくても、
各記号の出現確率に基づくShannon限界への漸近式が得られるという。

たとえば、LZ78法などは確率を一切、陽に用いていないにも関わらず、その冗長度は、
H(P) + O(loglog n / log n)
となるわけでつ。

梅竹、梅竹

埋め

埋め

&rlo;デフォルトの&lro;名無し&rlo;さん

　

　
　
　
　
　
　
　
　
　
　
　
　

>>975
LZ78が必ずしも得意としていない無記憶情報源（各p_iが独立）モデルで評価した場合はそうなりまつが、それではLZ78の実力は測れないでじょ?

埋め

結局、中途半端な圧縮のアイデアは出たものの、中途半端な圧縮には誰も興味無しという感じで埋め。

>>975,>>982
ttp://hirosuke.sr3.t.u-tokyo.ac.jp/pdfs/ibis2001.pdf によれば、
冗長度 O(loglog n / log n) になるのは LZ77 の有限次数マルコフ情報源に対して。
LZ78 の冗長度は O(1 / log n) らしい。

スレ違いな質問ですいませんがMPEG-1 Audio の圧縮方法や
そのプログラム（もし載ってたら）が詳しく載ってる書籍ってご存知ないですか？
興味があるのでちょっと勉強してみたいのですが、なかなか見つからなくて・・・・
ＨＰでもいいのでもし知っていたら教えてください。

スレ違い質問すいません ＞＜

数学的知識のない人向けにﾁｮｲ補足、てかﾋﾝﾄ?

LZ77/LZSSの場合、符号化されたトークンは
(スライド辞書内のインデックス+文字長)を現している。
で、これが12+4ビットで、が3〜18文字長を示す場合、
18バイトまでの文字列が16ビット=2バイトで置換できる
ことになる。従ってこのケースの最高圧縮率は1/9よね?
同様にトークンのビット数を増やしていって得ることができる
圧縮率を見ていって、方程式を導き出したのが(以下略)

LZ78/LZWの場合は、あるトークンは以前に出現した別の
ふたつのトークンまたはリテラル文字を結合した文字列を意味している。
この階層化されたトークンをすべて展開すると、リテラル文字を葉に持つ
二分木構造を持っていることが解かる。この木を作るには
根(現在のトークン)の左右の子が既知でなくちゃいけないから、
以前のトークンとは現トークンの1/2の情報量(葉)を持っている。
こうして葉に至るまで分解して並べると、出現する根の数(＝圧縮結果)は
全体の葉の数(＝圧縮源)の O(1 / log n) 以下にはなりえない。(合ってる…?)

>>986
あったけど潰れた.
第三の脳室ってとこ.

>>989
ttp://www5c.biglobe.ne.jp/~atsu/index.htm
まちがった. ここだった.

いえーい

へろー

>>988-989
ありがとうございました＾＾
勉強してきます！