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