- 1 名前：デフォルトの名無しさん [2006/04/26(水) 11:57:53 ]
- 2bit , 3bit , 5bit ずつに頻度を取る。
2bitがいい成績だったら2bitをひとかたまりにして
2ブロック、3ブロック、5ブロックで頻度をとる。
これを繰り返す。
- 369 名前：デフォルトの名無しさん mailto:sage [2006/10/20(金) 00:07:52 ]
- 「どんな数も」ってのは間違いか。入力は自然数限定ってことで。
＞復元は何になるの？
何度繰り返したかを覚えておいて逆関数（1足す)をその回数繰り返せばよい。
- 370 名前：デフォルトの名無しさん [2006/10/20(金) 01:26:57 ]
- 最強を語る前に最弱を語ろうではないか？
- 371 名前：デフォルトの名無しさん mailto:sage [2006/10/20(金) 02:28:42 ]
- 圧縮になってないのは自明だな。
- 372 名前：デフォルトの名無しさん mailto:sage [2006/10/20(金) 06:39:02 ]
- どんな頑張っても圧縮率には限界があるんだから
なに食わせてもソコソコ縮んで程ほどの圧縮解凍速度
そういうのが良いアルゴリズム。
さらに実装したときに悪意のあるデータによって
セキュリティが脅かされるような不具合が生じない事や
暗号化などまで考慮されていると最高
- 373 名前：デフォルトの名無しさん mailto:sage [2006/10/20(金) 09:34:25 ]
- >>369
その回数はどこで覚えておくの？
- 374 名前：369 mailto:sage [2006/10/20(金) 09:56:10 ]
- >>373
「繰り返し適用して・・・」という手法をとる以上、圧縮後のデータとは別の
どこかに記録するより他ないんじゃないかな。人間が覚えておく等。
- 375 名前：デフォルトの名無しさん mailto:sage [2006/10/20(金) 11:48:41 ]
- >>362
そのアルゴリズムは結構出尽くしているかも…
視点を変えてみると面白い！
- 376 名前：デフォルトの名無しさん mailto:sage [2006/10/20(金) 18:33:36 ]
- 近似する式にするってのすごいよね。
- 377 名前：デフォルトの名無しさん mailto:sage [2006/10/20(金) 19:29:24 ]
- どういうこと？
- 378 名前：361 mailto:sage [2006/10/21(土) 22:32:18 ]
- 自分で圧縮したデータが、自分にとって都合のいいデータであること
なんてないよね。きっと。
圧縮ってデータの傾向を利用して可能性を省くことだから、
圧縮後のデータは傾向が消えてるだろうし。
２つのアルゴリズムで交互に通せばいいのか？
でもさまざまな傾向に対応できるように
いろいろなアルゴリズムを用意して・・・とやると
>>362ですよね
結局は>>372に落ち着くと・・・。
>>367
基本の形、ということでしょうか。
圧縮できるところは圧縮して、出来ないところはそのまま。
繰り返すたびにデータが変化していって、だんだん圧縮できなくなる。
そんなイメージ？
- 379 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 00:27:04 ]
- エントロピーが云々で何とかかんとか
- 380 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 13:53:49 ]
- もともと自分にとって都合のいいデータって絶対に存在しないでしょ？
何を言ってるんだ、こいつは。
- 381 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 16:42:45 ]
- >>30
1001010110101、というのを、a・sinA+b・cosB+…+n・sinN、みたいな、合成波形としてとらえて行く。
圧縮・展開時には、フーリエ変換を使用する。
パラメータとして、a、A、b、B、…、n、N、だけを設定してやればよく、効率の良い圧縮となる。
とかは、既出？
- 382 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 18:39:45 ]
- ずいぶん工学よりだけど、圧縮アルゴリズムなんてそんなもんだよ。
もうすこし具体的に書かないと言いたいことが見えてこないから、
既出かどうかは分からない。
- 383 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 18:49:02 ]
- 少なくとも、非可逆圧縮には利用されているのは間違いなさそうな気がする
- 384 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 18:56:40 ]
- >>381
一時話題になった、可逆で1/100に圧縮できるというアルゴリズムが
そんな方法だった。
もちろん、一斉に「ダウト！」を喰らってたがｗ
- 385 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 19:32:48 ]
- データによっては十分可能だと思うが
- 386 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 19:38:45 ]
- スーパーマンが両手で炭の塊を圧縮したらダイヤモンドになってたが、
別物になっちゃうのはアウトだな。
スーパーマン使えねえ。
- 387 名前：デフォルトの名無しさん [2006/10/22(日) 19:44:37 ]
- 高温・高圧
だからどうしてなったのか不明だな
- 388 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 20:17:57 ]
- しかもカット済みのダイヤが出てきたもんな・・・
- 389 名前：361 mailto:sage [2006/10/22(日) 20:44:43 ]
- >>380
「都合が良い」の度合いの問題ですよ～
実用していて発生するデータの内で。
そりゃ作ろうと思えばいくらでも作れますから。
やっぱいくら考えても
１つのアルゴリズムで繰り返して使う・・・なんて思いつきませんわぁ
処理時間は処理回数と比例するだろうから
組み合わせを全て試して最適解を出すようなタイプかなぁ
とは なんとなく思いますが。経験上
コテハンは最後にしときます
- 390 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 20:49:59 ]
- 圧縮で良書がないね～
- 391 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 22:10:42 ]
- 圧縮でかよ！
- 392 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 23:31:15 ]
- >>287ぐらいまでの停滞っぷりが嘘のようだw
- 393 名前：デフォルトの名無しさん [2006/10/22(日) 23:38:27 ]
- でも、本当に圧縮技術の良書ってないよね。
なんで？
- 394 名前：デフォルトの名無しさん mailto:sage [2006/10/22(日) 23:43:18 ]
- 論文嫁
- 395 名前：デフォルトの名無しさん [2006/10/24(火) 21:20:41 ]
- >>390
Cマガジン
圧縮アルゴリズム
が
あんま余計なこと書いてなくてよい。
- 396 名前：デフォルトの名無しさん mailto:age [2006/10/30(月) 15:35:26 ]
- 対象が何かを分析し、対象の種類と特徴によってアルゴリズムを可変させるのが
最強のアルゴリズムであって、１つのアルゴリズムだけですべてを適用させる
汎用のアルゴリズムなどあるわけないだろ。ｗｗｗｗｗｗｗｗｗｗｗｗｗ
- 397 名前：デフォルトの名無しさん mailto:sage [2006/10/30(月) 19:59:09 ]
- 新しいアルゴリズムは開発しないのか？
- 398 名前：デフォルトの名無しさん mailto:sage [2006/10/31(火) 11:43:02 ]
- 助けてアルゴマン！
- 399 名前：デフォルトの名無しさん mailto:sage [2006/10/31(火) 16:26:51 ]
- >>268
＞そしてこれらの選択肢は全て結果が等しい、つまり等価なわけだ。
＞同じ結果に対して別の選択肢が存在するという事は、
＞それはつまり冗長だということになる。
詳しい理論や真偽の程はともかく、感覚的に納得の行く説明㌧クス
>>270ﾓﾚにもそのように思える。
しかしそれはﾓﾚの頭が悪い所為かも知れないと思って聞いてみた。
- 400 名前：デフォルトの名無しさん mailto:sage [2006/11/02(木) 13:19:10 ]
- zip32.dllとzlib使った自前のプログラムで比較したんだけど圧縮率に結構差がある。
zip32.dllはdeflateだけじゃないの？
- 401 名前：デフォルトの名無しさん [2006/11/06(月) 01:12:51 ]
- >>395
圧縮アルゴリズムは
アルゴリズムの説明は確かにいいかもだけど
プログラムについての説明がない、ソースコードのリストがあるだけ
- 402 名前：デフォルトの名無しさん mailto:sage [2006/11/06(月) 01:34:37 ]
- C言語の入門書でも読んでろ
- 403 名前：デフォルトの名無しさん [2006/11/06(月) 01:41:22 ]
- そうしとくぜ
- 404 名前：デフォルトの名無しさん [2006/11/06(月) 15:11:05 ]
- >>400
7z で -tgzip -mx=9 オプション指定すると、もっと圧縮された .gz
形式がでるよ。
- 405 名前：デフォルトの名無しさん [2006/11/06(月) 18:38:21 ]
- アルゴリズムばかｗｗｗｗ
- 406 名前：デフォルトの名無しさん mailto:sage [2006/11/06(月) 20:02:01 ]
- なに興奮してんの(^_^;
- 407 名前：デフォルトの名無しさん mailto:sage [2006/11/07(火) 13:41:46 ]
- アルゴリズム体操
- 408 名前：デフォルトの名無しさん mailto:sage [2006/11/11(土) 00:11:08 ]
- アルゴリラ？
- 409 名前：デフォルトの名無しさん [2006/11/30(木) 12:59:35 ]
- >>26まで読んだ俺様が以降を読まずにレス
>>1エントロピーと言う言葉をぐぐってからこないと
大恥かくことになるよ
もうおそかったらごめん
- 410 名前：デフォルトの名無しさん mailto:sage [2006/12/01(金) 13:56:45 ]
- ボクの部屋はエントロピーが増大する一方です。
- 411 名前：デフォルトの名無しさん [2006/12/01(金) 17:55:25 ]
- ぼくのおちんこは(
- 412 名前：デフォルトの名無しさん mailto:sage [2006/12/02(土) 00:59:32 ]
- CRCエラーです
伸張出来ません
- 413 名前：デフォルトの名無しさん mailto:sage [2006/12/03(日) 01:11:57 ]
- 伸ばすことに成功しました。
しかし、ふにゃふにゃになり硬くなることはありません。
- 414 名前：デフォルトの名無しさん mailto:sage [2006/12/03(日) 19:24:36 ]
- p2pの圧縮ソフトはどうだろうか。
1kぐらいのファイルに保存することができる。
- 415 名前：デフォルトの名無しさん mailto:sage [2006/12/06(水) 17:00:19 ]
- >>414
p2pのって、どういう意味だ? ファイルが分割されてあちこちのサーバにあるとか?
- 416 名前：デフォルトの名無しさん mailto:sage [2006/12/07(木) 11:33:09 ]
- それって結局はthcompよね
- 417 名前：デフォルトの名無しさん [2006/12/16(土) 02:31:58 ]
- 質問させてください。
テキストファイルではなく、プログラム形式のバイナリファイルを
圧縮及び解凍する目的で利用するなら、どのような圧縮解凍アルゴリズムが
適しているでしょうか？
現状の候補はLZSSです。
また採用する条件は以下です。
・解凍スピードが著しく遅くないこと。
・WEB上でC言語のプログラムソースサンプルが公開されていること。
他に思いつくのはここでもでてくる以下のものたちです。
ハフマン
LZ
BPE
アドバイスお願い致します。
- 418 名前：デフォルトの名無しさん mailto:sage [2006/12/16(土) 06:28:48 ]
- >>417
既存の自爆形式で何か不満でも?
- 419 名前：デフォルトの名無しさん mailto:sage [2006/12/16(土) 15:08:32 ]
- upx
- 420 名前：デフォルトの名無しさん mailto:sage [2006/12/20(水) 20:57:34 ]
- 何でもいいんじゃないか？
例えば、あえてテキスト用途の圧縮方式を使ってもいいんだ！という意気込みがないとねぇ。
- 421 名前：デフォルトの名無しさん mailto:sage [2006/12/20(水) 22:01:20 ]
- どうでもいいことかも知れないけど、
テキストの圧縮を考えると、日本語と
欧米では事情が違うよなぁ。
UNICODEなんか、漢字がばらばらに
なってるから、圧縮難しそうと思う。
- 422 名前：デフォルトの名無しさん mailto:sage [2006/12/22(金) 08:54:02 ]
- 感じがバラバラにならない文字コードに変換してから圧縮するんだ
- 423 名前：デフォルトの名無しさん mailto:sage [2006/12/25(月) 14:28:59 ]
- というか、文字の意味なんかどうでもいいから圧縮に都合が良いように
変換すれば良いんではないか?
- 424 名前：デフォルトの名無しさん mailto:sage [2006/12/28(木) 01:04:08 ]
- 0を白、1を黒と見立ててイラストロジックにすればかなり圧縮されるのでは？
素人考えスマソ
- 425 名前：デフォルトの名無しさん mailto:sage [2006/12/28(木) 01:12:08 ]
- >>424
まさにその考えで実装されたのが、FAXで使用される modified Huffman
（実態は連長圧縮に近い）
より数学的に 0/1 の列を置き換えるのが、数え上げ法と Elias 符号
- 426 名前：デフォルトの名無しさん mailto:sage [2006/12/28(木) 01:56:17 ]
- modified Huffmanって白と黒の数を数えるんでしたよね？
イラストロジックの様に黒の数だけを記録して白の数を完全に無くしてしまえば
データにもよるけれどかなり削れるんじゃないかなぁ、と
イラストロジック自体絶対に解けるものじゃないのが難点ですが
解凍時間に制限がなければ何時かは解凍できるんじゃ・・・という希望
- 427 名前：デフォルトの名無しさん [2006/12/28(木) 08:23:31 ]
- >>426
適当なイラストロジックで必要なビット数計ってごらん。大した圧縮率にならないから。
- 428 名前：デフォルトの名無しさん [2006/12/28(木) 08:28:52 ]
- >>426
＞イラストロジックの様に黒の数だけを記録して白の数を完全に無くしてしまえば
イラストロジックは横だけでなく、縦方向の情報もあるので、そもそも倍になっている。
縦横の情報より、黒白にすれば一次元で表され効率がいい。
- 429 名前：デフォルトの名無しさん mailto:sage [2006/12/28(木) 13:32:13 ]
- 流れ読まずに書き込み
>>26
それはTHcompのアルゴリズムじゃないか？
>>29
Web上に辞書を置けば解決。
っていうか、既にアップデートした段階で圧縮されているともいえる。
つまり俺らは既に最強の圧縮アルゴリズムを意識することなく使っている？
- 430 名前：デフォルトの名無しさん mailto:sage [2006/12/28(木) 22:03:33 ]
- >>429
物怖じせず、正直に言うと、
バカじゃないの？
- 431 名前：デフォルトの名無しさん mailto:sage [2006/12/28(木) 22:39:01 ]
- 暗黙の了解という言葉の意味を理解しているならば軽率な発言は出来ないはずだ。
情報の本質を理解している者ならばなおのこと。
- 432 名前：デフォルトの名無しさん mailto:sage [2006/12/29(金) 00:24:56 ]
- >>426
黒だけとかにすると、場合によっては解凍不能になるのは別に置いといて、
何ビット単位で並べるかによって圧縮率は異なるから（確率的に。なぜなら圧縮するデータが異なるため。）
いかに（時間的に）効率よく圧縮できるか、又いかに圧縮率を高められるかにおいてかなり疑問なのだが。
- 433 名前：暇人13世 ◆tAo.kQ2STk mailto:sage [2006/12/29(金) 00:48:59 ]
- 思いついた。
まず配列に圧縮するデータを1bitづつ入れて、配列a[]とする。
変数iを設け、初期値0とする。
a[i]が0ならiを進めまくる。a[i]が1になるまで。
a[i]からa[a.lenght]までに0がなければ終了する。
a[i]が1ならa[i]からa[a.lenght]までをローテートする。a[i]が0になるまで。
この時のiの値と、回した回数を記録する。
結果的に配列a[]は0000.....00001111.....1111という配列になるので、最後に0の数と1の数を記録する。
解凍は、逆の計算を行えば出来るはず。
実装面倒なので誰かテスト頼む。つーか既にあったら教えてくれ。名前。
- 434 名前：デフォルトの名無しさん mailto:sage [2006/12/29(金) 01:41:49 ]
- >>433
MTF/UTC/ORTの族に近いと思う。いわゆる順列符号とか再帰時間符号。
ローテート回数が再帰時間に相当するようだから、当たらずといえども遠からずかと。
あと、0/1列上だと、数え上げ符号や算術符号が存在しているので、
少なくともこれらより優れていそうなものじゃないと。
- 435 名前：暇人13世 ◆tAo.kQ2STk mailto:sage [2006/12/29(金) 01:52:14 ]
- 実装してみたらアルゴリズムが悪いのか相当遅かった。
それと、iの値を記録せずに前回のiとの差分を記録した方が記録効率がいいことが分かった。
後ひとつは、出力結果をさらにハフマンとかで圧縮しないとファイルがでかい。
（ただし0と1の比がかなり偏っているので再圧縮は効率が高そう）
>>434
情報thx。調べてみる。
- 436 名前：369 mailto:sage [2007/01/09(火) 13:45:12 ]
- >>433
iの値が0の連続の個数（のようなもの）、回した回数が1の連続の個数ってことで
たんなるランレングスのように思えるが・・・
- 437 名前：デフォルトの名無しさん mailto:sage [2007/01/09(火) 22:31:21 ]
- torrentファイルを使う。
- 438 名前：デフォルトの名無しさん [2007/01/13(土) 18:59:19 ]
- 仮にﾃｷｽﾄﾌｧｲﾙだとして出現頻度が
Aが6回
Bが2回
Cが1回
Dが1回
だとすると、本来一文字に2bit使うとして、ハフマン圧縮なら
Aは1bitで済むから0.5倍
Bは2bitだから1倍
Cは3bitだから1.5倍
Dも3bitだから1.5倍
これに出現頻度を掛けると、
Aは0.5*0.5で0.25、Bは1*0.2で0.2、Cは1.5*0.1で0.15、Dも1.5*0.1で0.15
で元の0.8倍のサイズに圧縮できる
つまり元が2bit*10文字で20bitだから、0.8倍なら16bit、4bit削減できた事になる
でも全体の60％が一つの文字に集中してた場合で2割offなんて
ISOﾌｧｲﾙを圧縮するのには余り期待は出来ないね
それと、これって圧縮実行する以前に、1度ファイルを読み切らせて、
出現頻度表を作らせた時点で解るよね？
>>1の人が言う風なﾉﾘで、2bit長から、31bit長までの30通りの頻度表を最初に作らせて
予定される圧縮率を先に算出させれば良いんでしょ？それで一番割の良い物を実行
でもこのｹｰｽだと仮に4文字とも0.25に近い割合の出現頻度だとするとｵｰﾊﾞｰﾍｯﾄﾞが出るんじゃない？
って事は算術圧縮とか、RangeCoderとかでないと駄目ぽなのか
- 439 名前：デフォルトの名無しさん [2007/01/13(土) 19:05:53 ]
- 最強の圧縮はゴミ箱だ
- 440 名前：デフォルトの名無しさん mailto:sage [2007/01/14(日) 00:52:13 ]
- うん。
確かに最近の OutlookExpress は最適化を行うと
dbx ファイルがごみ箱にもコピーされるようになったね。
- 441 名前：デフォルトの名無しさん mailto:sage [2007/01/28(日) 19:42:26 ]
- 展開の速さならLZO
- 442 名前：デフォルトの名無しさん [2007/02/03(土) 13:13:52 ]
- 以下の条件を満たすオープンソースの圧縮、伸張アルゴリズムはありませんか？
WEB上で公開されているものであれば良いです。
■条件
LZSS法、ハフマン符号化以外
（すでに所有しているため）
ハフマン符号化よりも伸張のスピードが速いもの。
圧縮時のスピードは問いません。
伸張が早ければそれでよいです。
>>441さんのLZOはよさそうですが、
プログラムソースを見つけることができませんでした。
よろしくお願い致します。
- 443 名前：デフォルトの名無しさん mailto:sage [2007/02/03(土) 13:21:55 ]
- wiki.osask.jp/?tek1/comp
- 444 名前：デフォルトの名無しさん [2007/02/03(土) 15:12:30 ]
- ウェーブレットとかの話はでないんだな
- 445 名前：デフォルトの名無しさん mailto:sage [2007/02/03(土) 15:18:41 ]
- >>442
BPEでいいじゃん。
- 446 名前：デフォルトの名無しさん mailto:sage [2007/02/03(土) 15:20:31 ]
- >>442
調べる能力もないのかおまいは。
ぐぐったら一番上に出てきたぞ。
- 447 名前：デフォルトの名無しさん mailto:sage [2007/02/04(日) 02:13:33 ]
- 実用レベルだとLZ77+ハフマンが一番速いよ。
つかLZOもLZ77だし。
LZ77はただのメモリコピーだから一番速い。
ハフマンはやり方次第で表引きに出来るからこれも相当速い。
>>442
という訳で、その条件を満たすものはないよ。残念ながら。
まだ遅いと感じてるなら実装が悪いだけ。
- 448 名前：デフォルトの名無しさん mailto:sage [2007/02/04(日) 03:35:56 ]
- >>444
残念ながらここの住民のほとんどは、高等な数学を扱えるほど頭がよくありません。
マルチエンコードみたいな技術の動きを読み取るほどの視野も持ち合わせていません。
まあ書き込みをざっとみればわかるだろ。
- 449 名前：デフォルトの名無しさん mailto:sage [2007/02/04(日) 05:11:54 ]
- >>447
ハフマンよりレンジコーダーのほうが速くね？
- 450 名前：デフォルトの名無しさん mailto:sage [2007/02/04(日) 06:33:23 ]
- >>449
いや、ハフマンの方が2,3倍速い。
Athlon64 X2 2.0GHzのマシンでRam Disk上で計測した場合、
ハフマン 60-80MB/s
レンジ 20-30MB/s
こんな感じ。
どっちもcで書いて結構チューニングしてる。
ファイルのi/oも含んでるから、
圧縮率の分だけ気持ちレンジコーダの方が有利かな。
LZとかなしで純粋に1byteずつ符号化した場合ね。
あ、上の数字は復号だよ。
符号化も同じようなもんだけど。
- 451 名前：デフォルトの名無しさん mailto:sage [2007/02/04(日) 09:39:05 ]
- 上からモノ言ってる奴って他のスレでもそうだが、
自分から答えを教えるってことしないよな。
他人の非難は出来るけど、その実、自分で答えを
導き出せない、レベルの低い奴なのだろうか？
まぁ、2ch見てる程度の人間だから仕方がないかも。
他人の非難しかしない奴より、なんでもいいから、
自分の意見を述べる奴の方がましってのは、
どこにあっても同じだと思う。
- 452 名前：デフォルトの名無しさん mailto:sage [2007/02/04(日) 09:56:47 ]
- まあ、なんだ、落ち着けよ。
こんな過疎スレで誰に言ってるのかよく分からんが。
- 453 名前：デフォルトの名無しさん mailto:sage [2007/02/04(日) 10:05:33 ]
- コピペだ反応すんな
- 454 名前：デフォルトの名無しさん mailto:sage [2007/02/04(日) 12:25:59 ]
- >>451
どこを縦読み?
- 455 名前：デフォルトの名無しさん [2007/02/04(日) 14:05:56 ]
- >>450
ハフマンのが速いって怪しいな。もしかして静的ハフマンか？
動的なら木の操作が入る分、ハフマンの方が不利だろ。
SSE2を使って最適化したレンジコーダがハフマンに劣ることってありえない。
一度チューニングしたそのコードを書いてみ。
- 456 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 02:09:26 ]
- 0圧縮
- 457 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 05:23:19 ]
- >>455
怪しいと言われても実測値だからねぇ。
もしかしなくても静的ハフマンだよ。
動的ハフマンなんて普通使わないでしょ。
木も使わないよ。
SSEは使ったことないから比較出来ないです。ごめん。
アセンブラあまり使えないし。
ただレンジコーダはSIMD化出来る部分が少ないはずなんだよね。
1bitにつき必ず一回は整数の乗算か除算が必要だしね。
ハフマンはシフトと表引きだけで済むからずっと速いはずなんだけど。
気になるなら実験してみて下さいな。
>450で出した数字より遅いなら最適化が十分でないですよ。
ただのハフマンならzip(deflate)やcab(lzx)と同じ位の速度がでるはず。
- 458 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 10:26:28 ]
- >>457
実測値が怪しいんじゃなくて、君の最適化が怪しいって事。
実測値でしか語らず、理論値で説明できないのは、どうして速いかという検証が君ができていないってことだ。
静的ハフマンならテーブル引き＋ストリーム出力でほぼ最速になるのは当たり前。
で、レンジコーダの方だが、こっちも静的でいいなら、少ない乗算でできる。テーブル引きとそうかわらん。
SSE2なら乗算平均1clock以下で演算できるから、ほとんど変わらない。
1bitにつきというが、一体どんなレンジコードなんだ？そんな馬鹿なことは普通はしない。
PPMとかのソース見たことないんじゃないの？
静的では若干ハフマンが有利な程度でほとんど変わらんし、
動的ではレンジコーダの方が圧倒的に上。
- 459 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 13:52:03 ]
- >>458
458さんのレンジコーダはそんなに速いの？
とりあえずハフマンは静的でレンジコーダは動的でいいよね？
最初からそのつもりで書いてたんだけど。
動的ハフマンとか静的レンジコーダってあまり見ないし。
正直SSE2はよく分からんのだけど(もうSSE4まで出てるんだっけ？)、
例えばアルファベットサイズが256ならシンボル確定するのに
8bit分の8回バイナリサーチするよね？
ここの部分が一番時間がかかってるはずなんだけど、
ここってそんなに速く出来るの？
いきなりPPMとか言われたりして、
どうも話がかみ合ってない感じなんだけど、
実験用のバイナリどこかに上げようか？
- 460 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 14:03:56 ]
- >>459
＞とりあえずハフマンは静的でレンジコーダは動的でいいよね？
ダメだろ。条件をどちらかに揃えないで比較するのはおかしい。
- 461 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 14:07:42 ]
- >>459
＞いきなりPPMとか言われたりして、
最強の圧縮アルゴリズムを語るこのスレなら、知っていて当然の基礎知識。
＞実験用のバイナリどこかに上げようか？
バイナリじゃなくて、問題箇所のソースを上げてくれ。
- 462 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 14:14:12 ]
- >>459
エンコードするのに、バイナリサーチする馬鹿は普通いない。
それとも「圧縮」の話から、「展開」の話に摩り替えてるの？
- 463 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 14:20:29 ]
- >>462
悪い俺が馬鹿だった。アンカーたどったら元は伸張の話みたいだ。orz
- 464 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 14:22:15 ]
- >>460
おかしいといっても実際動的ハフマンとか静的レンジコーダって殆ど使われてないし。
それにハフマンも動的と静的じゃ殆ど別のアルゴリズムと言って良いくらい違いがあるんだけど。
自分が言ってたのは一般的に使われてる静的ハフマンと動的レンジコーダなんだよ。
事実上この2つ以外を使うことってないと思うんだけど。
動的か静的かで条件を揃えるのって実用上無意味な比較なんじゃないのかな。
>>461
いやPPMは知ってるけどハフマンとかレンジコーダの話をしてていきなり
>PPMとかのソース見たことないんじゃないの？
とか言われても困っちゃうんだけど。
ソースは上げられません。ごめん。
>>462
自分が書いたのは
>>447,450,457,459で
>>442からの流れでデコードの話をしてるんだよ。
別に摩り替えてないと思うんだけど。
なんでそんなに攻撃的なのか分かりません。
もう少し落ち着いて話をしませんか？
- 465 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 14:50:31 ]
- >>464
＞おかしいといっても実際動的ハフマンとか静的レンジコーダって殆ど使われてないし。
動的ハフマンがあまり使われないのは、速度の劣化に対する圧縮率の向上があまりないから。
レンジコードだと動的にしても、あまり速度が遅くならず、圧縮率の向上が見られるから、動的で使うことが多いだけ。
＞自分が言ってたのは一般的に使われてる静的ハフマンと動的レンジコーダなんだよ。
でも速度比較するなら、どっちも静的にすればいい。その程度のこともできないの？
理解せずにレンジコーダをつかっているとしか思えん。
＞ソースは上げられません。ごめん。
なぜ？ビルドできなくてもいいし、部分的にでも上げる事が出来ない理由があるの？
- 466 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 14:52:53 ]
- >>464
＞事実上この2つ以外を使うことってないと思うんだけど。
そんなのアプリの用途の問題であって、アルゴリズムの比較とは何の関係もない。
実際、静的算術圧縮を使う事だって普通にある。
＞動的か静的かで条件を揃えるのって実用上無意味な比較なんじゃないのかな。
無意味じゃないよ。条件そろえないほうが無意味。
- 467 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 14:56:18 ]
- >>464
＞>PPMとかのソース見たことないんじゃないの？
＞とか言われても困っちゃうんだけど。
PPMのレンジコーダのコードは優秀。
- 468 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 15:00:54 ]
- なんか妙に絡まれてるけどなんでだろう？
やっぱり話がかみ合ってないんだよなぁ。
ソース上げろと言われてもその前にあなたが出してくださいよ、
という話になってしまうし。
私がヘボグラマーでレンジコーダの方が速いということで終了しましょう。
バイナリのアップは止めておきます。
- 469 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 15:03:31 ]
- >>467
どのPPM？
Dmitry Shkarin？
- 470 名前：お呼びじゃない? mailto:sage [2007/02/05(月) 15:07:12 ]
- PPMと聞くと、画像ファイルフォーマットか濃度かカントリーミュージックしか思い浮かばない漏れが来ましたよ。
- 471 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 15:08:15 ]
- >>465
アルゴリズムの実行効率の優劣を論じてるんじゃなくて、
＞ハフマン符号化よりも伸張のスピードが速いもの。
＞圧縮時のスピードは問いません。
＞伸張が早ければそれでよいです。
って話じゃなかったっけ。
>>45が勘違いしてエンコードの話始めてから話が変になったが。
- 472 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 15:58:28 ]
- >>468
＞なんか妙に絡まれてるけどなんでだろう？
静的と動的という、機能的に違うもので無意味な比較をしているから。
圧縮率無視すれば、ハフマンより速いレンジコーダだって書ける。
- 473 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 16:04:17 ]
- >>472
そんなに違わなくね？
圧縮展開って意味なら大差ないような。
ストリームに対応出来るかどうかとか？
- 474 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 16:11:49 ]
- >>473
全然違う。
静的なら頻度表が必要。動的なら不要。
出現確率の変化に動的なら対処できるが、静的では不可能。
- 475 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 16:17:25 ]
- >>474
ブロックに分割したらダメなのか？
- 476 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 16:18:23 ]
- >>474
それって単に多少の圧縮率の話ですよね。
それで「全然違う」かどうかは入力の性質次第かと思うが。
「機能的に違う」「全然違う」と言えるような差異としては
＞ストリームに対応出来るかどうかとか？
の方が適切なんじゃない？
- 477 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 16:21:05 ]
- まぁ、ストリームっても大概バッファリングするんだから
そんなに違いがあるとも思えないけどな。
- 478 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 16:32:25 ]
- >>476
静的も動的も、ストリームに対応するかしないかはどっちも一緒。
どっちもたいていブロックに分割した上で、対応する。
- 479 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 16:33:37 ]
- つまり動的か静的かはあまり意味がないってことか。
- 480 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 16:37:22 ]
- >>479
違うよ。
動的か静的かは、確率変動に対応できるかどうかという違いがある。
静的は展開が速いが無駄なデータが多くなるし、圧縮時は無駄なリードが発生する。
- 481 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 16:44:28 ]
- >>480
それって結局圧縮率の問題じゃね？
出現確率の変化の仕方次第じゃ動的な方が圧縮率悪かったりするよ？
それに動的だと出現しないシンボルが無駄になるんだよな。
エスケープ使うとますます遅くなるしな。
- 482 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 17:03:35 ]
- >>481
圧縮率無視するなら、そもそも圧縮なんかしないでいいだろ。
圧縮率が上がればその分読み込みも速くなるから無視は出来ないと思うが。
動的が圧縮率悪くなるわけではない。実装がタコだとそうなるけど。
理論値では動的のほうが必ず上になる。出現しないシンボルは、静的のテーブルの分で相殺できる。
静的に適したデータなら、動的が無駄に遅くなるという点は同意だが。
- 483 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 17:26:15 ]
- >>482
>圧縮率無視するなら、そもそも圧縮なんかしないでいいだろ。
べつにそんな事言ってないぞ。
ていうか圧縮率の問題は比較する上で静的動的と本質的に関係なくね？
>動的が圧縮率悪くなるわけではない。実装がタコだとそうなるけど。
いんや実装の問題じゃないよ。
どんな実装をしても変化を捉えられないケースは必ずある。
>理論値では動的のほうが必ず上になる。
逆じゃね？
動的だと任意の位置のシンボルの出現確率はそれまでの文脈から決定されるわけだから、
どのシンボルも常に確からしい確率を与えられるとは限らないでしょ。
静的だと区間における出現確率をあらかじめ調査するから、
その区間に限っては任意のシンボルは必ず確からしい確率が与えられるはず。
頻度表の分動的より悪くなることが多いと思うけど。
>出現しないシンボルは、静的のテーブルの分で相殺できる。
出来るとは限らないでしょ。
テーブルのサイズは決まってないわけだし。
作り方次第じゃ数バイトで済んだりするよ。
- 484 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 17:36:19 ]
- >>483
＞ていうか圧縮率の問題は比較する上で静的動的と本質的に関係なくね？
関係あるよ。これは確率論だから。
＞どんな実装をしても変化を捉えられないケースは必ずある。
その場合は静的と同じに出来る。動的の下限が静的なんだが。
＞動的だと任意の位置のシンボルの出現確率はそれまでの文脈から決定されるわけだから、
＞どのシンボルも常に確からしい確率を与えられるとは限らないでしょ。
＞静的だと区間における出現確率をあらかじめ調査するから、
ここまでは正解。
＞その区間に限っては任意のシンボルは必ず確からしい確率が与えられるはず。
ここが間違い。
例えば、区間内に「AAAA...AAAABBBB....BBBB」というデータが与えられた場合、
静的だとA、Bの確率が0.5になる。
シャッフルしたらエントロピーが上がり、情報量が下がることはわかると思うが、
静的では圧縮率に変化が起こらないことから、そういった要素を無視しているのはわかるよな？
＞作り方次第じゃ数バイトで済んだりするよ。
数バイトで済む場合、動的のほうの無駄も、同程度以下で済ますことが出来る。
情報量の計算すればわかることだが。
- 485 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 17:56:05 ]
- >>484
>ここが間違い。
>例えば、区間内に「AAAA...AAAABBBB....BBBB」というデータが与えられた場合、
>静的だとA、Bの確率が0.5になる。
ん？その区間の確率は理論上A,Bともに0.5で正しいはずだけど。
「ABABABAB...ABABABAB」も「AAAAAAAA...BBBBBBBB」も同じだよ？
どのシンボルも(AとBしかないけど)この区間においては確からしい確率が与えられてるでしょ。
極端な話「AAAAAAAAAAA」だけのデータは静的だと確率が1になるよね？ある意味ランレングス。
動的だと1/2, 2/3, 3/4, 4/5...n-1/nとなっていく訳だ。
で、極端な話0.9999999999になることはあっても決して1にはならない。
理論的には静的な方が良くなるのは分かるよね？
動的符号化は常に被符号語が未知であるが故に確からしい確率を与えることが出来ない。
>シャッフルしたらエントロピーが上がり、情報量が下がることはわかると思うが、
???
エントロピーが上がって、情報量が上がるの間違いだよね？
文脈次第では？
- 486 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 18:10:00 ]
- >>485
＞ん？その区間の確率は理論上A,Bともに0.5で正しいはずだけど。
「ABABABAB...ABABABAB」も「AAAAAAAA...BBBBBBBB」も同じだよ？
静的の場合はそうだが、動的の場合は違う。
動的の場合、前者は、ABともにほぼ0.5にでき、後者は、静的よりも効果的に圧縮できる。
＞動的だと1/2, 2/3, 3/4, 4/5...n-1/nとなっていく訳だ。
とは限らない。もちろんその手の変化があるという意味では正解だが、
その変化の仕方はタコなアルゴリズム。
＞で、極端な話0.9999999999になることはあっても決して1にはならない。
そうだよ。静的の場合その情報を頻度テーブルに書き込むわけだが、
動的の場合は、その差が動的な符号中に拡散するだけのこと。
＞理論的には静的な方が良くなるのは分かるよね？
理論的には、良くならない。
高圧縮のアルゴリズムはすべて動的になっていることからもわかるはずだが。
どうしても分からないなら、2値のモデルで検証してみることだ。
区間内に出現確率の変化がある場合、動的のほうが必ず良くなるから。
そして変化が無い場合でも、動的でも静的と同レベルに抑える方法があることがわかる。
＞エントロピーが上がって、情報量が上がるの間違いだよね？
エントロピーが上がる＝情報量が下がるだよ。
シャッフルしたら情報量が下がるのがわからん？
- 487 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 18:15:11 ]
- 「AAAB」
静的
A:3/4
A:3/4
A:3/4
B:1/4
-> 27/256 = 0.10546875
動的
A:1/2
A:2/3
A:3/4
B:1/5
-> 6/120 = 0.05000000
- 488 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 18:18:07 ]
- >>487
頻度テーブルの情報量を加えてごらん。
- 489 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 18:23:20 ]
- >>とは限らない。もちろんその手の変化があるという意味では正解だが、
>>その変化の仕方はタコなアルゴリズム。
どんな入力に対しても対応できる方法は存在しないよ。
>>高圧縮のアルゴリズムはすべて動的になっていることからもわかるはずだが。
残念。
それらは一般的な情報源に対して高圧縮率なだけ。
例えばPAQやPPM*よりLZが倍近く高圧縮になるケースが実在する。
- 490 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 18:25:19 ]
- >>489
＞それらは一般的な情報源に対して高圧縮率なだけ。
＞例えばPAQやPPM*よりLZが倍近く高圧縮になるケースが実在する。
だから、それは特殊な場合だろ。平均的には論理的に動的のほうが上というのがわからんの？
- 491 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 18:27:02 ]
- >>488
1bitでイイ？
- 492 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 18:29:06 ]
- >>491
どうやって表現するんだ？AAAAとAAABとAABBとABBBとBBBBが区別できないといけないだろ。
- 493 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 18:33:53 ]
- 以下の条件を満たすオープンソースの圧縮、伸張アルゴリズムはありませんか？
WEB上で公開されているものであれば良いです。
■条件
LZSS法、ハフマン符号化以外
（すでに所有しているため）
ハフマン符号化よりも伸張のスピードが速いもの。
圧縮時のスピードは問いません。
伸張が早ければそれでよいです。
- 494 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 18:33:58 ]
- だからよ、テーブルは任意サイズでもいいわけよ。
てことは少なくとも頻度表を除けば平均的な
区間圧縮率は静的な方が上なんだよ。
で、これにテーブルをどうするかって位の差なんだよなこれがさ。
最初から辞書として持っててもいいわけだ。
実際PAQとかDurilcaとかはテーブル持ってんだよね。
- 495 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 18:42:03 ]
- >>494
＞だからよ、テーブルは任意サイズでもいいわけよ。
誰もそれを否定していないが？
情報量から限界があるから、無駄をなくすことができるだけで、下限は情報量によって決る。
＞てことは少なくとも頻度表を除けば平均的な
＞区間圧縮率は静的な方が上なんだよ。
必要な頻度表を除けばというのはインチキだな。
最悪時の動的のロスもその程度だから、必要な頻度表を含めば動的も静的もほとんど変わらない。
しかし、区間中に確率の差がある場合、動的の方が理論的には良くなる。
＞最初から辞書として持っててもいいわけだ。
持っててもいいが、持っていなくてもいい。
- 496 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 18:49:29 ]
- >>493
ランレングス
- 497 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 19:03:14 ]
- だからさ頻度表は任意だから加えたらどっちが上かは
その時点で決められないんだよな。
>最悪時の動的のロスもその程度だから、必要な頻度表を含めば動的も静的もほとんど変わらない。
なら動的の方が良いとは限らないのでは？
>しかし、区間中に確率の差がある場合、動的の方が理論的には良くなる。
なぜ？
入力に対してどんなに対応を切り替えようが
動的である限り常に最悪のパターンは存在する。
どんなBitのパターンであっても同じだよ？
つまりどんな入力に対しても頻度表を除けば常に静的な方が圧縮率は上。
動的符号化は常に被符号語が未知であるが故に確からしい確率を与えることが出来ない。
最適な確率・符号長を与えられない時点で平均的には必ず静的より悪くなる。
その上でこれに加える頻度表は任意でいい訳よ。
どんな形で頻度表が作られるかは不明。サイズも不明。
だから動的が理論的に必ず良いというのはおかしいのさ。
そもそも頻度表が加わるから大きくなると言ってるけど
どんな形で頻度表を持たせるかは言及してないでしょ。
- 498 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 19:08:53 ]
- >>497
＞つまりどんな入力に対しても頻度表を除けば常に静的な方が圧縮率は上。
馬鹿。
- 499 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 19:11:32 ]
- >>498
馬鹿はないだろ馬鹿は。
でも間違ってないだろ？
- 500 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 19:13:40 ]
- いやでもこれが間違っているとなると
シャノンの情報理論も間違ってることになるんじゃ？
- 501 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 19:15:21 ]
- >>497
＞動的符号化は常に被符号語が未知であるが故に確からしい確率を与えることが出来ない。
＞最適な確率・符号長を与えられない時点で平均的には必ず静的より悪くなる。
間違い。
静的は全体で確率を求めるため、局所的な確率を効率よく求めることが出来ない。
最適な確率・符号長を与えられない時点で平均的には必ず動的より悪くなる。
静的なアルゴリズムを選択する場合でも、
ブロックにわけることで、擬似的に動的っぽい効果は得られるが。
- 502 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 19:19:43 ]
- 局所的な確率はどうやって求めんのよ？
どんな入力に対しても最適にする事は出来ないんだよ？
実装の問題とかじゃなくてさ。
- 503 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 19:21:46 ]
- >>502
＞局所的な確率はどうやって求めんのよ？
ベイズ推定
- 504 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 19:22:42 ]
- AAAB,AABA,ABAA,BAAA
これを動的符号化で期待値求めてみてよ。
- 505 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 19:26:07 ]
- >>504
A=aが1000個の固まり
B=bが1000個の固まり
に展開して、aとbで符号化してみたらどう？
- 506 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 19:28:11 ]
- 分かんないかなあ、次の文字が未知である以上
何やったって既知である静的符号化より区間平均が悪くなるのに。
特殊な情報源に強くする事は出来ても全般は無理よ。
- 507 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 19:37:17 ]
- >>505
母数を大きく取るのね。
500/1000
501/1001
502/1002
500/1003
0.062499813247569977380545675660332
大きくとるほどに変化に強くなる。
- 508 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 19:54:14 ]
- ああそうだ、動的の方が良くなるパターンに言及してなかったよ。
動的な符号化ってのはさ大体の場合、頻度の累計値が決まってんのよ。
で、一定期間(1bit毎でも)で頻度表を更新するんだけど、
これのおかげで静的で言うところの区間が可変になるんだな。
だからシンボルが連続したりすると圧縮率が良くなるんだ。
で、シンボルがランダムだと悪くなったりするんだ。
テキストとか所謂圧縮しやすい情報源だと偏りがあるから良く効くんだよ。
で、ランダムだと全然ダメだったりするんだ。
で、あらゆる全てのビットパターン(未知の情報源)をトータルすると
結局、静的符号化が上回るんだよ。
- 509 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 23:05:45 ]
- >>508
＞で、あらゆる全てのビットパターン(未知の情報源)をトータルすると
やっぱりお前は馬鹿だな。
全ビットのパターンをトータルするなら圧縮しない方が一番いい。そんなこともわからないのかよ…。
- 510 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 23:12:32 ]
- >>509
理論値を語ってるんじゃなかったんか。
- 511 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 23:14:22 ]
- >>506
じゃあ、君の考えだとPPM法を静的にした方が圧縮率が上がるということ？
そんなことやる奴なんていないと思うが。
- 512 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 23:15:54 ]
- >>510
全パターンなら、理論値だろうと実測値だろうと一緒だろ。圧縮しないのが最強だ。
- 513 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 23:26:12 ]
- >>511
頻度表を除けば理論上はそうなるよ。
まあ当たり前なんだけどさ。
頻度表をどうするかはまた別の話。
durilcaとかは自前でテキスト用に辞書をもってたりする。
実用上はもちろん頻度表は動的に作ることになるだろうけどね。
>>512
理論的に必ず動的が上だって言うからそれは違うだろって話をしてたんだよ。
究極的には圧縮しないのが最強なのは全くもってその通り。
可逆圧縮はただの変換なんだから、
どんなアルゴリズムを用いたとしても、
入力サイズ+圧縮したかしないかの1bitが最小の期待値になる。
n通りのビットパターンはn通りのビットパターンでしか表現できない。
- 514 名前：デフォルトの名無しさん mailto:sage [2007/02/05(月) 23:47:50 ]
- 理論的に語るなら得意な情報源のみ取り出して上だというのは
おかしいだろという話なんだよ。
実際存在しうるデータってのはランダムの方が圧倒的に多いんだよ。
>>511
abcabcabcab
ときてabの次に何が来るか考えたら分かるよ。
cが来るだろうなと思って実際にcがきたとしても、
動的符号化はc以外の文字にも常に確率を割り当てなきゃならない。
既知であれば必ず最適な符号長が割り当てられる。
- 515 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:17:03 ]
- >>514
＞実際存在しうるデータってのはランダムの方が圧倒的に多いんだよ。
馬鹿だなー。実在するデータは、ランダムの方が少ないから、圧縮アルゴリズムが有効なんだよ。
- 516 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:19:38 ]
- >>513
何度も言うが、頻度表除いたらダメだろ。情報が頻度表に移動しているだけなんだから。
根本的に情報理論がわかってないんとちゃう？
- 517 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:30:46 ]
- >>514
＞動的符号化はc以外の文字にも常に確率を割り当てなきゃならない。
＞既知であれば必ず最適な符号長が割り当てられる。
それが違うんだな。既知であるためには、先行して情報が与えられている必要がある。
その情報の量と、動的の場合に確率を割り当てる量というのは、実は同じ。
しかし静的の場合、局所確率に適応できないため、原理的に最適な符号を割り当てることが出来ない。
圧縮率がシャッフルさせても変化しないというのは、
文字の前後との相関性の情報量を利用できていないということに他ならない。
圧縮というのは、出現の偏りによって圧縮するのであって、単なる出現確率だけよりも、
時系列情報（既出文字との相関性）の偏りを利用できた方が、一般的に圧縮率は向上する。
- 518 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:32:21 ]
- >>515
有効じゃないなんて誰も言ってないだろ。
理論的に話してるんだから考えうるデータは全部考慮しなきゃならんだろ。
>>516
>何度も言うが、頻度表除いたらダメだろ。情報が頻度表に移動しているだけなんだから。
それはそう。
だが動的にすれば常に理論上圧縮率が良くなるのは違うだろ？
頻度表をどう持たせてどう使うかはまた別の話。
そもそも動的にしたことで偏った情報源で圧縮率が良くなるのを
理論値だなんて言うからおかしくなるんだよ。
- 519 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:36:57 ]
- 局所的な確率が良くなっているのはワーストケースとの
トレードオフなんだよ。
圧縮率が良くなった時だけ見てるからそうなるんだよ。
よーく考えてみてよ。
理論上の話なんだから。
- 520 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:37:18 ]
- >>518
＞だが動的にすれば常に理論上圧縮率が良くなるのは違うだろ？
理論上、実際に使うデータでは平均的に圧縮率が向上する。
なお、現実と一致しないような理論は理論ではなく空論。
＞頻度表をどう持たせてどう使うかはまた別の話。
動的だってそれ専用の表に符号を追い出すことは出来る。
そんなもの切り離して考える方がどうかしている。
＞そもそも動的にしたことで偏った情報源で圧縮率が良くなるのを
動的にしたことで偏るんじゃなくて、偏りが抽出できるだけ。
始めから偏ったデータを使っているから圧縮アルゴリズムに意味が出てくるの。
- 521 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:38:22 ]
- >>519
理論上というのは、ランダムとか全パターンのことじゃないぞ。
根本的に何か勘違いしていると思われ。
- 522 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:42:58 ]
- >>520
なぁ、おかしくないか？
ワーストケースを考慮しないのが理論的なのか？
圧縮しやすいデータを対象にして話すのは結構だけど、
だったら理論て言葉はなしにするべきだろ。
実際tar化されたファイルとかで圧縮・非圧縮のが混ざってたりして
動的が不利になるケースとかもあるんだよ？
- 523 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:44:15 ]
- 最適な予測で符号を求める方法も、あらかじめ符号をもつのも、情報量的には実は同じ。
- 524 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:44:55 ]
- >>521
じゃあ理論上てのはどんなのだよ。
人それぞれ対象が違ったらそれこそ話が合わないじゃないか。
- 525 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:48:35 ]
- >>523
究極的にはそれはその通り。
だが符号表を除けば除いた残りの部分は必ず動的より良くなる。
当たり前すぎる。
動的が常に理論的に上ってのは間違い。
- 526 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:49:13 ]
- >>522
圧縮しやすいではなく、圧縮可能なデータ。いろいろな偏りが含まれていることが前提になる。
程度の差は様々でいいが、出現確率に差があり、相関性にも差があるのが、現実のデータ。
そういう差がないなら、それはただの乱数列であって、圧縮アルゴリズムを適用する対象外だ。
乱数であることを検出したら、圧縮しないで転送すればいいだけ。
動的でも静的でもいいが、不利になったりするのは、実装上の問題であって、情報の理論的な問題ではない。
- 527 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:49:53 ]
- 本来持っている情報量を下回る圧縮は出来ないってことだね。
- 528 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:51:21 ]
- >>525
＞だが符号表を除けば除いた残りの部分は必ず動的より良くなる。
除けばなんて話はしていない。合わせたら動的の方が良くなる。
静的で頻度表に全部符号を置けば、良くなるどころか０ビットに圧縮可能だが、そんなものは圧縮とは言わない。アホ過ぎる。
- 529 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:52:28 ]
- >>527
そういうこと。その中で、動的は時系列情報を利用できる。
- 530 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:54:03 ]
- >>526
>圧縮しやすいではなく、圧縮可能なデータ。いろいろな偏りが含まれていることが前提になる。
圧縮可能かどうかはアルゴリズム次第なんだって。
そんな前提条件があるなら先に言ってくれよ。
>そういう差がないなら、それはただの乱数列であって、圧縮アルゴリズムを適用する対象外だ。
じゃあ理論値て言葉はなしにしてくれよ。
- 531 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:55:44 ]
- >>529
時系列情報て、それは結局ワーストケースとのトレードオフなんだって。
- 532 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:56:20 ]
- >>530
理論値は理論値。確率や相関性を分散とかを適当に設定すればいいのであって。
全パターンというのは、そもそも圧縮を考える上で無意味なこと。
- 533 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:58:10 ]
- >>531
そんなことを言うなら、頻度表もワーストケースとのトレードオフだ。バカバカしい。
- 534 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 00:58:52 ]
- >>532
理論値てのは普通全部含めるだろ？
いい加減理論値って言葉はやめなよ。
特定の場合のみなら理論とはかけ離れてる。
- 535 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 01:01:29 ]
- >>533
バカバカしい、って理論の話じゃなかった訳？
あなたの理論は特定のアルゴリズムで圧縮できる
特定のファイルにのみ適用されるの？
- 536 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 01:06:48 ]
- >>534
＞理論値てのは普通全部含めるだろ？
含めないよ。偏りがないなら圧縮できないで終了だから。
n次相関がどれだけとか、分散がどれだけとか、偏りがあることが前提になる。
- 537 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 01:11:08 ]
- >>535
特定のアルゴリズムというわけではないよ。
現実のデータというのは、高次相関性があるわけ。
どんなアルゴリズムもその相関性を利用して圧縮を行う。
全次元で相関性が0なら、完全な乱数列であり、圧縮理論の対象外になる。
多かれ少なかれ、相関性があることが前提になる。
そして、その相関性を高次まで多く利用できるアルゴリズムが圧縮率が上がるということなの。
- 538 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 01:13:09 ]
- やっぱり根っこのところで考え方が違い過ぎて議論になってないね。
とりあえず前提条件も話さずに特定の場合のみ取り出して
「理論上は…」ってのだけは止めるべきだと思うよ。
- 539 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 01:18:31 ]
- >>538
理論上は静的の方が冗長な情報が含まれるから劣るんだよ。
シャッフルしたときとの差の情報が使われていないからね。
ただ、現実には理論値が出せないことがあるから、静的な方がいいこともあるだけ。
「情報量」で考えられないやつにはわからないかもしれんが。
- 540 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 01:20:18 ]
- >>537
無限にアルゴリズムが存在する中では高次相関とかは無意味なんだって。
完全な乱数列かどうかなんて判定は出来ないんだから。
全次元の判定なんて不可能でしょ。
というか理論と言う時点で全ての情報源は等価である事が前提だと思うんだけど。
- 541 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 01:29:29 ]
- >>540
＞全次元の判定なんて不可能でしょ。
だから、どれだけの次元を利用できるかということになる。
静的なら最低の相関性だけしか使わないが、
それ以上の相関性を利用できれば理論上、圧縮率が上がるのは当たり前なんだよ。
＞というか理論と言う時点で全ての情報源は等価である事が前提だと思うんだけど。
そんなんだったら、確率論も、情報理論もいらんがな。
これらは何らかの偏りがあることでしか意味がないから。
- 542 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 01:32:05 ]
- 一応断っておくがあなたの主張については
後だしの前提条件を踏まえる限りは概ね正しいと思うよ。
ただし議論するときは前提条件はきちんと提示するべきだね。
- 543 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 01:37:52 ]
- >>542
全パターンなんて基地外じみた条件こそ後出しだろ。
まともな情報理論で語るなら、そんなわかりきったことを持ち出して議論を無意味にしたりはしないのが普通。
- 544 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 11:42:47 ]
- 結局のとこ全パターン厨って何が言いたいの？
- 545 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 12:39:19 ]
- もう終わりにしろよ。
- 546 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 16:58:04 ]
- どうして情報源の設定をしないのだろうか。
エルゴード情報源くらいを仮定してみては？
- 547 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 23:20:22 ]
- >>541
理想論の放棄＝客観的なアルゴリズム比較の放棄
と同等だわな。
- 548 名前：デフォルトの名無しさん mailto:sage [2007/02/06(火) 23:23:28 ]
- >>546
同意。
現代の圧縮アルゴリズム論は、もう情報源の設定が必須だな。
なんでも使える汎用アルゴリズムなんて、曖昧で議論も検証も不毛になりがち。
- 549 名前：デフォルトの名無しさん mailto:sage [2007/02/07(水) 08:42:10 ]
- Lempel-Zivについて。
"IM■ULM■UM■ULM■UND■UM■ULM■HERUM"をLempel-Zivで圧縮したらどんな風になるんでしょう？
↓ここでは最初に全部のアルファベット読み込んでるけど
ttp://en.wikipedia.org/wiki/LZW
上の例では無駄が多くなっちゃうよね？だから、動的に読むことにした。
自分で辞書とコードを作ってみたんで合ってるかどうか確認してやってください。
0 I
1 IM
2 M
3 M■
4 ■
5 ■U
6 U
7 UL
8 L
9 LM
10 M■U
11 ■UM
12 UM
13 M■UL
14 ■UL
15 ULM
16 LM■
17 M■UN
- 550 名前：デフォルトの名無しさん mailto:sage [2007/02/07(水) 08:43:09 ]
- 18 ■UN
19 UN
20 N
21 ND
22 D
23 D■
24 ■UM■
25 M■ULM
26 ■ULM
27 ULM■
28 LM■H
29 M■H
30 ■H
31 H
32 HE
33 E
34 ER
35 R
36 RU
- 551 名前：デフォルトの名無しさん mailto:sage [2007/02/07(水) 08:44:06 ]
- 原文字＝Lempel-Zivコード
I=0
M=2
■=4
U=6
L=8
M■=3
U=6
M■U=10
LM=9
■U=5
N=20
D=21
■UM=11
■UL=14
M■=3
H=31
E=33
R=35
UM=12
…どうでしょう？
- 552 名前：デフォルトの名無しさん mailto:sage [2007/02/07(水) 09:00:01 ]
- ja.wikipedia.org/wiki/LZ78
- 553 名前：デフォルトの名無しさん mailto:sage [2007/02/07(水) 09:15:44 ]
- >>552
ア、ナルほど。
1のIMや3のM■はもっと後にコード化されるみたいですね。
もう一度やってみます。
- 554 名前：デフォルトの名無しさん mailto:sage [2007/02/07(水) 09:36:59 ]
- 再挑戦です。今度こそ、どうでしょうか？
0 I
1 M
2 ■
3 U
4 L
5 M■
6 ■U
7 UM
8 M■U
9 UL
10 LM
11 M■UN
12 N
13 D
14 ■UM
15 M■UL
16 LM■
17 ■H
18 H
19 E
20 R
- 555 名前：デフォルトの名無しさん mailto:sage [2007/02/07(水) 09:37:45 ]
- 原文字＝コード
I=0
M=1
■=2
U=3
L=4
M=1
■=2
U=3
M■=5
U=3
L=4
M■U=8
N=12
D=13
■U=6
M■U=8
LM=10
■=2
H=18
E=19
R=20
UM=7
…合ってますか？
- 556 名前：549 mailto:sage [2007/02/07(水) 11:28:47 ]
- "IM■ULM■UM■ULM■UND■UM■ULM■HERUM"
ではなくて
"IN■ULM■UM■ULM■UND■UM■ULM■HERUM"
↑
でした。
しかもノートに答えが載ってました、はははは。(^^ゞ
…吊ってきます。
|
 |
