最強の圧縮アルゴリズムを語ろう

1 名前：デフォルトの名無しさん [2006/04/26(水) 11:57:53 ] 2bit , 3bit , 5bit ずつに頻度を取る。 2bitがいい成績だったら2bitをひとかたまりにして 2ブロック、3ブロック、5ブロックで頻度をとる。 これを繰り返す。 258 名前：デフォルトの名無しさん mailto:sage [2006/05/28(日) 19:41:32 ] 組み込み系で圧縮を考えると、最悪でも数ms、できればμsの時間で 処理しないと、いけないですよね？ ということは、組み込み系でソフトウェア圧縮はむかない？ 実装している人がいましたら、どのような用途で使ってますか？ そもそも、ここにファームウェア開発の人がいるかわかりませんが 259 名前：デフォルトの名無しさん mailto:sage [2006/05/28(日) 19:54:16 ] はてなマーク多いな 260 名前：デフォルトの名無しさん mailto:sage [2006/05/28(日) 20:09:17 ] なんかずれてるな。 メモリの中身が判らないのに向いてるも何もあったもんじゃない。 そもそもメモリとファイルで違いなんかないだろ。 テキストとか画像とか音楽とかなんかの設定値とか、 それぞれ性質が全然違う。 こういう場合は素直にハフマンが良い。 261 名前：デフォルトの名無しさん mailto:sage [2006/05/28(日) 23:54:18 ] >>257 ＞バイナリデータに特化した圧縮アルゴリズムを考えればいいのでしょうか？ PC で扱えるデータは「全て」」バイナリデータですよ。 >>258 CPUのスペックもデータの帯域もわからないのに、向くも向かないも・・・ 圧縮はそもそも用途が少ないような。 展開の方は結構ソフトウェア実装も多いみたいだけど。 262 名前：デフォルトの名無しさん mailto:sage [2006/05/29(月) 19:53:12 ] LANコントローラあたりの設計だと、圧縮していたような・・・ 忘れた。 263 名前：デフォルトの名無しさん [2006/05/30(火) 20:53:24 ] ZigZagスキャンでもしとけよw 264 名前：デフォルトの名無しさん mailto:sage [2006/05/31(水) 01:21:55 ] なつかしの540アルゴリズム 「aaaaababababcabc」 　↓ a:aaaaabbbbb b:aaacc c:a 　↓ 「aaaaabbbbbaaacca」 　↓MTF 「a0000b0000100c01」 　↓適当にエントロピー圧縮。 （ﾟдﾟ）ｳﾏｰ 265 名前：デフォルトの名無しさん mailto:sage [2006/06/03(土) 14:13:13 ] ホシュ 266 名前：デフォルトの名無しさん [2006/06/05(月) 05:39:33 ] >>258 モデムのデータ圧縮 267 名前：デフォルトの名無しさん mailto:sage [2006/06/09(金) 04:39:23 ] ところで、結局>>1のビット羅列による圧縮はＦＡ出たの？ ﾓﾚ昔ハフマン圧縮勉強した直後の頃に似たようなこと考えたことあった。 最終的には、ファイルを"0"(0x30)と"1"(0x31)に変換してから普通に辞書圧縮したら論理的に近似可能だということに気付いた。 で詳細は忘れたが、実際にやってみて（´･ω･`）ｼｮﾎﾞｰﾝだった記憶がある。 ＦＡが出たなら知りたひ・・・ 268 名前：デフォルトの名無しさん mailto:sage [2006/06/09(金) 08:47:12 ] FAという訳ではないんだが一応答えらしきものを示しておこうか。 一般に辞書との一致で置き換えるアルゴリズムは圧縮率が悪い。 何故か？ 今、abc...bcd...abcdという文字列があったとする。 3つ目のabcdを符号化したい。 選択肢としてabc|dとすることも出来るし、 またはa|bcdとすることも出来る。 場合によってはa|b|c|dとしてもいい。 そしてこれらの選択肢は全て結果が等しい、つまり等価なわけだ。 同じ結果に対して別の選択肢が存在するという事は、 それはつまり冗長だということになる。 等価であるならば一つに纏めて確率を上げなければならない。 極端な例を挙げるとすると、纏め(られ)ないということは、 aaaabbbcという文字列があって、これの確率を求めた時に、 1. a 3/8 2. a 1/8 3. b 3/8 4. c 1/8 このような状態になってしまうことを意味するわけだ。 'a'を符号化する時に1,2のどちらを選んでも結果は等しい。 しかしこの時、'a'の確率は4/8でなくてはいけない。 しかし実際には分かれてしまっているため、1の'a'を選んで符号化しなければならず、 'a'一文字につき1/8ずつ無駄を増やしているということになる。 じゃあどうすればいいのか？ 書くのが疲れたので終わり。ごめん。 269 名前：デフォルトの名無しさん mailto:sage [2006/06/09(金) 22:29:04 ] ここでいう最強は 圧縮率がよいアルゴリズム？ それとも同じ圧縮率でも高速なアルゴリズム？ それとも実装が簡単でそこそこ高速かつ圧縮率のよいアルゴリズム？ あと、特許とかあるからわからんけど、そういうものにかからないで なるべく速いアルゴリズムといったらなんでしょうか？ やはり、特許がきになる・・・ 270 名前：デフォルトの名無しさん mailto:sage [2006/06/09(金) 23:41:22 ] >>267 >>111が圧縮率の悪さに唖然として開発停止して以来誰も作り出すような発言や完成したような発言はしていないように思うがどうか。 >>269 スレタイから察するに3つそれぞれの意味での「最強」なのでしょう。 271 名前：デフォルトの名無しさん mailto:sage [2006/06/10(土) 03:34:17 ] BlockSort+適応型符号化でいいような。 何が最強かも定義がわからんし。 272 名前：デフォルトの名無しさん mailto:sage [2006/06/22(木) 21:08:18 ] スレ違いなのはわかっています。 ですが教えてもらえないでしょうか？ zipファイルのパスワードを解析したいのですが そういったことは出来るのでしょうか？ 273 名前：デフォルトの名無しさん mailto:sage [2006/06/22(木) 23:54:56 ] >>272 このスレッドはプログラム板にあるわけだが、 プログラム板(作る人が技術的な話をするとこ)ではなくて、 ソフトウェア板(使う人がいろいろな話をするとこ)のスレッド一覧を、 適当な単語でページ内検索しなさい。 「教えて」とか「質問」とか検索するといいよ。 274 名前：デフォルトの名無しさん mailto:sage [2006/06/23(金) 01:01:16 ] わかりました。 他のスレを探してみます。 スレタイからして実際にしようとした人とか 詳しい人が多そうとか思っちゃいました。 275 名前：デフォルトの名無しさん mailto:sage [2006/06/23(金) 01:05:23 ] いやだから、鼬害だってばさ。 276 名前：デフォルトの名無しさん mailto:sage [2006/06/26(月) 12:01:57 ] ネットにデータをうｐってハッシュ値をURLにすればよい 277 名前：デフォルトの名無しさん mailto:sage [2006/06/27(火) 06:50:57 ] live23.2ch.net/test/read.cgi/livecx/1151356052/ 66 名前：名無しでいいとも！[sage] 投稿日：2006/06/27(火) 06:47:46.25 ID:3HXDRC1i 　zicoって何かの圧縮形式みたいじゃね？ というわけで、ここでなんか圧縮形式が完成したらジーコ形式って名前にすることに決定。 278 名前：デフォルトの名無しさん mailto:sage [2006/06/27(火) 07:28:48 ] 間違っても最強にしちゃいかんな むしろ元サイズより増えるくらいでいいんじゃね？ 279 名前：デフォルトの名無しさん mailto:sage [2006/07/01(土) 12:02:56 ] G Compression Archiverはどう？ 280 名前：デフォルトの名無しさん mailto:sage [2006/07/03(月) 06:25:40 ] 鼬害だって言ってるだろ、池沼か？ 281 名前：デフォルトの名無しさん [2006/07/09(日) 03:19:12 ] >>278 まぁ、どんなファイルに対してもサイズを縮めることができるような可逆圧縮は存在しないからなぁ。 282 名前：デフォルトの名無しさん mailto:sage [2006/07/09(日) 16:54:18 ] つまり、元サイズより大きくなるのが合理的だ、と？ 283 名前：デフォルトの名無しさん mailto:sage [2006/07/10(月) 08:55:58 ] そうだけど？ 究極的には圧縮はただの変換(写像)だから、 「元のサイズ+適用したかしないかの1bit」が最小の期待値になる。 284 名前：デフォルトの名無しさん mailto:sage [2006/07/10(月) 23:24:00 ] >>278 無圧縮圧縮を思い出した。 285 名前：デフォルトの名無しさん mailto:sage [2006/07/26(水) 09:52:03 ] 72.14.235.104/search?q=cache:z5jvOgJbrB0J:download.microsoft.com/download/1/6/a/16acc601-1b7a-42ad-8d4e-4f0aa156ec3e/WMPhotoSpec_v10.doc+WMPhotoSpec_v10.doc&hl=ja&gl=jp&ct=clnk&cd=1&client=firefox 286 名前：デフォルトの名無しさん mailto:sage [2006/09/04(月) 22:09:10 ] 保守 287 名前：デフォルトの名無しさん [2006/09/30(土) 17:21:29 ] あげあげ 288 名前：デフォルトの名無しさん mailto:sage [2006/10/09(月) 17:34:23 ] 圧縮のアルゴリズムって特許とか色々ありすぎ。 何を使って作ったらいいのかわからん 289 名前：デフォルトの名無しさん mailto:sage [2006/10/09(月) 17:52:55 ] 誰も思いつかないような新しい方法を考えればいいんじゃね？ 290 名前：デフォルトの名無しさん mailto:sage [2006/10/09(月) 18:45:00 ] >>289 その発想は無かったわ。 291 名前：デフォルトの名無しさん mailto:sage [2006/10/09(月) 19:03:06 ] もう、出尽くしてない？ 292 名前：デフォルトの名無しさん mailto:sage [2006/10/09(月) 19:06:54 ] いつの時代も雑魚はそう言う。 そしてコロンブスに卵で殴り殺されるんだ。 293 名前：デフォルトの名無しさん mailto:sage [2006/10/09(月) 20:15:26 ] 量子コンピュータやDNAコンピュータで使えるアルゴリズムという 未開拓な分野もあるぞ 294 名前：デフォルトの名無しさん mailto:sage [2006/10/09(月) 21:38:11 ] paq8とかlzmaとかtek5辺りのハードウェアアクセラレータまだー? apache/firefoxで使えるようになるのはいつー? 295 名前：デフォルトの名無しさん mailto:sage [2006/10/11(水) 11:48:18 ] 誰も思いついていないような新しい方法 1. 16進ダンプを画面表示する。 2. 全て暗記する。 3. 何かのキーワードでそれを思い出せるようにする。 4. 別のコンピュータの前に座る。 5. キーワードを思い出す。 6. 全て打ち込む。 このようにすることにより何Gバイトのデータであったとしても キーワードの長さに圧縮することがfhdsfdsjfけおwlw 296 名前：デフォルトの名無しさん mailto:sage [2006/10/11(水) 12:29:20 ] 2. が無理だと思われ 297 名前：デフォルトの名無しさん mailto:sage [2006/10/11(水) 13:22:13 ] >>296 πを何千桁も覚える人がいるんだからいつかそのうちできるようになるさ。 なんだったら事前に bzip2 圧縮して小さくしておけばf;ぇkwlけ２いfそb 298 名前：デフォルトの名無しさん mailto:sage [2006/10/11(水) 13:39:40 ] >>297 π は 10 桁。 www.f7.dion.ne.jp/~moorend/news/2005020901.html 299 名前：デフォルトの名無しさん mailto:sage [2006/10/12(木) 22:38:29 ] >>295 人間という外部記憶装置に保存するわけですな 300 名前：デフォルトの名無しさん mailto:sage [2006/10/12(木) 22:53:09 ] それはしんどいですな 301 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 03:54:09 ] そうだ、紙に穴を開けて保存するのはどうだろう？ オルゴールと同じ原理だ。 302 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 04:01:14 ] 鉛筆で書けば消せるし、また書けるよ！ 303 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 05:39:49 ] もはや圧縮アルゴリズムではないなｗ 304 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 05:51:03 ] 任意・ランダムで生成される32ビット情報を 24(または23）ビットにまでビット幅を圧縮してみて下さい。 intの値をfloatの仮数に埋め込みます。 305 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 12:54:04 ] >>304 それ何の意味があるの? #そもそも無理だし。 306 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 14:12:44 ] 意味があるかよりも、32bitを24bitに圧縮する方法ってことでしょ？ 32bitが特定（や有限・決まっている）の値なら簡単なんだけどね。 307 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 16:38:42 ] いやだから、24ビットに圧縮しても32ビットの空間を消費するなら意味ないじゃん。 308 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 17:03:47 ] 上位8ビットが非ゼロならば、情報源を含むその辺り（空間的に）の 機械や生き物が破壊されてしまうようなシステムを構築すれば良い。 表現できないものは無かったことにするという圧縮方法。 上位8ビットの違いによる差異を認識できるものを全て破壊する という方法もある。 誰にも違いがわからなければロスレスであるという手法。 309 名前：デフォルトの名無しさん mailto:sage [2006/10/13(金) 17:19:37 ] >>304 xが32ビット整数だとして、C言語で書くと x = (x >> 8) & 0x00ffffff; 但し不可逆。 全ての取りうる値での可逆圧縮は不可能。 310 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 01:13:45 ] >>308-309 y=x & 0x00FFFFFF これで x の8ビットを違うアルゴリズム処理すれば良さそう。 当然可逆圧縮・復元できないと意味ないけど、 残り8ビットは256通りだから、そんなに不可能ってほどでもない。 311 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 01:31:40 ] 32*3 = 24*4 詰めかえるだけなら圧縮とは言わないが。 前提が無いと、できるともできないともいえない。 312 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 01:44:38 ] >>311 ＞詰めかえるだけなら圧縮とは言わないが。 ｺﾗ！ ｳｿ言っちゃいかんにょ。 313 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 04:35:39 ] >>312 いわねーよ 314 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 22:56:30 ] >>313 置き換えで圧縮する、固定長符号化もたまには思い出してください(つД・) 315 名前：デフォルトの名無しさん mailto:sage [2006/10/14(土) 22:57:34 ] 符号化 316 名前：デフォルトの名無しさん mailto:sage [2006/10/15(日) 02:35:52 ] >>314 任意の固定長符号で置き換えるなんて話お前しかしてねーよ 317 名前：デフォルトの名無しさん mailto:sage [2006/10/15(日) 09:22:11 ] なんというか問題が難しかったようですね。 int32の情報ををfloatの仮数に埋め込むというのは一例です。 intで表現される色情報 a|r|g|b を24bit構造体 struct Enc_T {char val[3];}に 埋め込むとか考えると、やる気出ますか？ もっと簡単な問題だと、32bitを31bitに圧縮してください。 圧縮率は (31/32)*100パーセントになります。 8bitを7bitでもいいけど。 318 名前：デフォルトの名無しさん mailto:sage [2006/10/15(日) 10:46:59 ] >>317 話が摩り替わってるじゃん。 int32bitをfloat32bitの仮数部に入れるって話は消費情報量を削減できてないだろ。 単に有効情報量が減るだけじゃん。 319 名前：デフォルトの名無しさん mailto:sage [2006/10/15(日) 10:52:00 ] >>318 >>304によると32ビット情報を24ビット(23ビット）に圧縮してからだと思うが もしかして、float f=3.14f; int j=(int)f と勘違いしてないか？ 320 名前：デフォルトの名無しさん mailto:sage [2006/10/15(日) 10:59:12 ] 32ビットの情報を24ビットに圧縮しても、その情報を32ビットのマスに入れたんじゃ意味ないだろと言っている。 321 名前：デフォルトの名無しさん mailto:sage [2006/10/15(日) 11:17:35 ] >>320 なんと言うのか、話が逸れてるんだよな… 32ビットのマスに入れるかどうかじゃなくて、 圧縮する方法・アルゴリズムが重要なんじゃないのか その使い方や用途は君が関知する問題じゃないだろ？ 322 名前：デフォルトの名無しさん mailto:sage [2006/10/15(日) 11:51:10 ] ランダムな32ビット整数を24ビットに圧縮するという話についてなら、とっくに無理と言ってるが。 323 名前：デフォルトの名無しさん mailto:sage [2006/10/15(日) 12:19:03 ] どうして？ 324 名前：デフォルトの名無しさん mailto:sage [2006/10/15(日) 12:49:06 ] 32bitに圧縮しきれない可能性があるからじゃないか？ 325 名前：デフォルトの名無しさん mailto:sage [2006/10/15(日) 13:44:45 ] 32MBを24MBに圧縮できる（アルゴリズムがある）のだから 32bitを24bitに圧縮も考え次第で出来るだろ。 アルゴリズムというのは、そういうのじゃないのか？ ところで、無理とか不可能とか何を根拠に言ってるんだろう。 326 名前：デフォルトの名無しさん mailto:sage [2006/10/15(日) 15:47:13 ] みんな考えてる問題の定義と目的がバラバラのようだし、 議論は無理。問題の説明が足りなさ過ぎる。 勝手に考えると、 元が解らなくなっている可能性があってもいいなら aだけ捨てたら？と思ってしまうが。 32bitを31bitにしたかったら、どこか1bit捨てたら？ 327 名前：デフォルトの名無しさん mailto:sage [2006/10/15(日) 16:42:58 ] 圧縮のアルゴリズムで特許をとられないのって、何があるの？ 328 名前：デフォルトの名無しさん mailto:sage [2006/10/15(日) 17:07:08 ] このスレはレベル低いな。 これじゃ優秀な奴は誰も来ないぞ。 ところで「とられない」ってどこの言葉だ？ 329 名前：デフォルトの名無しさん [2006/10/15(日) 17:11:21 ] 特許に引っかからないのは？って聞きたいんだろ？ 330 名前：デフォルトの名無しさん mailto:sage [2006/10/15(日) 17:33:09 ] >>329 おまえはエスパーのようだが、どこの惑星から来た？ 331 名前：デフォルトの名無しさん mailto:sage [2006/10/15(日) 18:11:16 ] >>327 すでに切れた特許なら再び取られることは無いだろうな 332 名前：デフォルトの名無しさん mailto:sage [2006/10/15(日) 20:36:32 ] >>325 > ところで、無理とか不可能とか何を根拠に言ってるんだろう。 情報量を考えれば自明だからちゃんと勉強しろ。 圧縮後のデータは最大で24MBの情報量しか持ち得ないのに、 それを伸長するのにどうやったら任意の32MBデータが出現しうるんだよ。 まあ、 　> 32MBを24MBに圧縮できる（アルゴリズムがある）のだから というところから、圧縮を魔法かなにかと勘違いしてるのは分かるが。 333 名前：デフォルトの名無しさん mailto:sage [2006/10/15(日) 20:47:45 ] >>325 「32Mを24Mに圧縮できる」というのは結果論であって そのアルゴリズムで常に24Mに収まるという事ではない。 32Mのデータを24Mに圧縮できる「可能性」があるというだけで 32Mを24Mに確実に圧縮できるアルゴリズムというわけではなく 最悪の場合32Mのデータは32Mの容量を必要とする。 もしもどんなデータでも確実に32M→24Mに圧縮できるとしたら その24Mのデータも確実に18Mになるわけで、そうやって圧縮していけば データは無限に小さく圧縮できるはずだが、そうはならないよな？ 32Mが24Mに圧縮できるのは、32Mのデータの中に冗長な情報が含まれているからで 結局は平均情報量に近づく事はできてもそれ以下になる事はない。 そして完全にランダムな32bitのデータは 冗長な情報が全く含まれていない32bitのデータという意味 (もし出現パターンがあるならそれも情報と考えられる)なので ランダム32bitデータを24bitにするには8bit捨てるしかない。 334 名前：デフォルトの名無しさん mailto:sage [2006/10/15(日) 23:16:38 ] どんな 32bit のデータでも常に 24bit に圧縮できるアルゴリズムがあれば、 それを何度か繰り返し使えば世の中のすべての情報は 24bit にまで圧縮できることになるな。 335 名前：デフォルトの名無しさん mailto:sage [2006/10/15(日) 23:32:29 ] 　　　　　　　　　　[ﾟдﾟ] 　　　　　　　　　 　[ヽ□ 　　　　　 　　　　　|　 |　 □□□□□□□□□□□□□□□□□□□□□□□□□ 　　　　　　　　[ﾟдﾟ] 　　　　　　　 　[ヽ日 　 　　　　　　　|　 |　 日日日日日日日日日日日日日 　　　　　[ﾟдﾟ] 　　　　 　[ヽ品 　　　　　 |　 |　 品品品品品品品品 　　[ﾟдﾟ] 　 　[ヽ昌 　　 |　 |　 昌昌昌昌 ヽ[ﾟдﾟ]ノ 　 [＿]　  　|　 |　 　晶晶 336 名前：デフォルトの名無しさん mailto:sage [2006/10/15(日) 23:38:12 ] そこでTHCompですよ。 337 名前：デフォルトの名無しさん mailto:sage [2006/10/16(月) 00:58:09 ] いまオレすごい圧縮を考えたんだ！ データの最後のbitが0だったらそのbitを削るんだ。 1だったらそのまま。 これで1/2の確立でどんなデータ、 ランダムなデータでも1bit削れるよ！ 同じ感じで後ろ（先頭でもいいけど）1byteが0x00なら削って、 0x00以外ならそのまま。 1/256の確立で1byte圧縮できるよ！ 338 名前：デフォルトの名無しさん mailto:sage [2006/10/16(月) 01:09:42 ] >>337 削るのはいいんだがどうやって復元するつもりだ？ 339 名前：337じゃないけど mailto:sage [2006/10/16(月) 01:18:14 ] まずはそのまま、エラーが出なければOK。 駄目なら最後に0をくっつける。 これでどんなデータでも復元できるよ。 1byteのも同じ感じで、エラーが出なければOK。 駄目なら最後に1byte分の0x00をくっつける。 付けても付けなくても同じ結果を得られる場合もあると思うが そのときはどっちでもいいんだよ！ 340 名前：デフォルトの名無しさん mailto:sage [2006/10/16(月) 01:21:46 ] 運まかせ 341 名前：デフォルトの名無しさん mailto:sage [2006/10/16(月) 01:31:11 ] >>339 その方法だとエラー検査のための仕組みを別に用意しなければいけなくて、 それを厳密に行うためには圧縮前のデータと同じだけの容量が必要になる。 342 名前：デフォルトの名無しさん mailto:sage [2006/10/16(月) 02:56:15 ] 必要な32bitデータの入ったマシンをカメラで撮るんだ そしたらそのマシンは捨ててしまう これで圧縮が出来た 後でそのデータが必要になったら、フィルムを現像して思い出に浸ろう 写真の裏にマシン名も書いておくと良いな 343 名前：デフォルトの名無しさん mailto:sage [2006/10/16(月) 14:08:00 ] どんな 32bit のデータでも常に 1bit に圧縮できるアルゴリズムがあれば、 それを何度か繰り返し使えば世の中のすべての情報は 1bit にまで圧縮できることになるな。 344 名前：デフォルトの名無しさん mailto:sage [2006/10/16(月) 15:12:08 ] >>343 つまり全ての情報は同じって事。あなたとわたしも全く同じ。 345 名前：デフォルトの名無しさん mailto:sage [2006/10/16(月) 15:14:41 ] ここは哲学的なインターネットですね。 346 名前：デフォルトの名無しさん mailto:sage [2006/10/16(月) 15:23:25 ] つまり、熱的終焉だな。 347 名前：デフォルトの名無しさん mailto:sage [2006/10/16(月) 15:48:03 ] ここは物理学的なインターネットですよ 348 名前：デフォルトの名無しさん mailto:sage [2006/10/16(月) 20:29:50 ] じゃあ俺は情緒的に 349 名前：デフォルトの名無しさん mailto:sage [2006/10/17(火) 00:52:06 ] >>344 待て、1bitなんだから0か1で全ての情報は二つに分けられることに 350 名前：デフォルトの名無しさん mailto:sage [2006/10/17(火) 01:06:39 ] Lz77 351 名前：デフォルトの名無しさん mailto:sage [2006/10/17(火) 12:21:41 ] >>349 完全平衡状態に至って熱的死を迎えるか、 再度収縮して次のビッグ・バンが起きるか、 の2つってことか。 352 名前：デフォルトの名無しさん mailto:sage [2006/10/17(火) 13:27:41 ] 猫を殺したくなければそれ以上踏み込んじゃいかん 353 名前：デフォルトの名無しさん mailto:sage [2006/10/17(火) 14:34:14 ] 半分死んでいて半分生きている猫 354 名前：デフォルトの名無しさん mailto:sage [2006/10/17(火) 15:18:40 ] 轢かれて体半分潰れたが運悪く首は折れなかった みたいな感じか 355 名前：デフォルトの名無しさん mailto:sage [2006/10/18(水) 00:53:48 ] 0.5bitの情報を記録できる素子がほしい 356 名前：デフォルトの名無しさん mailto:sage [2006/10/18(水) 03:02:37 ] >>355 おまいの脳細胞 357 名前：デフォルトの名無しさん mailto:sage [2006/10/18(水) 03:17:57 ] >>355 素子2単位で1bit分の情報を記録するようにすればいいだけじゃまいか 358 名前：デフォルトの名無しさん mailto:sage [2006/10/18(水) 05:39:05 ] それはつまり今の3.5in 750GBのハードディスクを作れる技術が 1.5TBで作れるようになるまで待てと言ってるのか？ 359 名前：デフォルトの名無しさん mailto:sage [2006/10/18(水) 11:00:01 ] なんだ、来ない間にずいぶんと白熱してたんだね。 もう解決してるんだけど、つまんない話ばっかりでお前らには教えてやんない。 >>335,>>337は少し面白かったけど、まだまだ。 360 名前：デフォルトの名無しさん mailto:sage [2006/10/18(水) 12:46:53 ] みんなもホントは解決してるから大丈夫。 361 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 21:29:22 ] 最強の圧縮アルゴリズムっていうけど、 それってどんなの？　オレ的には、 １つのアルゴリズムで結果を帰還させて 圧縮できなくなるまで繰り返すようなのが 美しいと思うのだけど。 362 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 21:33:47 ] 俺的には傾向を見つけ出してそれに基づいて圧縮するのが美しいと思うけど 363 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 21:39:44 ] >>361 だから、それって具体的にどうやるわけ？ 364 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 22:34:01 ] あまりのアホさに361をスルーしたが、 362と363が俺の言いたかったことを言い尽くしていたことに感動した。 365 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 23:15:05 ] >>361 感動した！！ 366 名前：361 mailto:sage [2006/10/19(木) 23:32:27 ] 具体的な方法については言及しないつもりでした。 ただなんとなく美しい気がしたので。 自分では無理な気がしています。 具体的に無理な理由を説明できるならお願いしたいのですが・・ 逆に出来るよ！というのであればなおさらお願いしますー 367 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 23:52:18 ] >>361 その性質をもつ自明な圧縮の例 圧縮 f (x) とは 　x == 0 のとき 0 　x > 0 のとき x-1 何度か繰り返せば、どんな数も 0 に圧縮できる。 368 名前：デフォルトの名無しさん mailto:sage [2006/10/19(木) 23:59:57 ] 復元は何になるの？ 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 ＞そしてこれらの選択肢は全て結果が等しい、つまり等価なわけだ。 ＞同じ結果に対して別の選択肢が存在するという事は、 ＞それはつまり冗長だということになる。 詳しい理論や真偽の程はともかく、感覚的に納得の行く説明�dクス >>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" 　↑ でした。 しかもノートに答えが載ってました、はははは。(^^ゞ …吊ってきます。

---

---

[ 新着レスの取得/表示 (agate) ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef