圧縮・復元 相談室

■ このスレッドは過去ログ倉庫に格納されています
1デフォルトの名無しさん
垢版 |
NGNG
アルゴリズムは別スレで
2010/03/10(水) 17:39:36
ありがとうございました
でもなんで 2.71828182845904523536028・・・ みたいな変な数字なんだろ
2010/03/10(水) 17:43:26
e = 1/0! + 1/1! + 1/2! + 1/3! + 1/4! + ・・・・
だからさ
2010/03/10(水) 18:03:19
それは自然対数の底だな。

分野によって10（工学関係とか）2（情報関係とか）が底のこともある。
2とかそれ以外が底だったら普通は明示される。
たいてい10かeが底で、底がeの対数は特にlogではなくlnと書かれたりする
（その場合logで示されるのは底が10）。

ネイピア数（ないしオイラー数）eは (1 + (1 / n)) ** n （ ** は冪乗）の n を∞にした
時の極限（ほかにもいろいろな定義はあるが）。いろいろな性質がある。

たとえば、y = e ** x というグラフの傾きは e ** x であるとか。
2010/03/10(水) 18:47:51
logって何が便利なの？
2010/03/10(水) 18:53:07
高校で習うよ
2010/03/10(水) 18:54:06
eとかlogとかって圧縮復元に役に立つの？
2010/03/10(水) 18:57:36
729の役には立たないよ
2010/03/10(水) 21:02:01
>>727
例えば10進数で81桁の数値は64進数だと何桁必要か計算するときにlogを使う。
2010/03/11(木) 13:26:56
６４進数とか要らないなw
2010/03/11(木) 20:41:09
Base64なんかはある意味64進数といえなくもない
2010/03/20(土) 17:05:41
位取りの概念がないじゃない
2010/03/21(日) 11:57:06
は？馬鹿ですか？
736デフォルトの名無しさん
垢版 |
2010/09/17(金) 23:12:57
ぼくではない
2010/11/10(水) 20:50:47
"Move To Front" の改良 良になっていると思います
　過去２Byte値から今の１Byte値を"Move To Front"するテーブルを選ぶ
　　詳しい処理はソースを見てください
http://gmdev.xrea.jp/
　　　[標準10MB] [148.zip]　　実験用実行アプリ　Delphi4 ソース付き　

注意
　実行アプリのウイルスチェックはしてません　
　感染は無いと思いますが自己責任ということで
2010/11/10(水) 23:18:20
学生さんかな？
ここで晒してもしょうがないと思うのだけど…
MTFの改良とか一度は考えるよね
実際にやってみると大したこと無くてがっかりっていう
この手のやつをRecency Rankingというのだけど
頻度が考慮されないから算術符号やハフマン符号と比べるとだめなんだな
もっともっと勉強してちょうだい
2010/11/11(木) 00:25:01
再帰順位符号化法は、理論的にはエントロピーを達成できるよ！できるよ！
2011/07/03(日) 13:21:22.14
なんだ、ただのゴミか
2011/07/07(木) 21:50:49.65
「容量無限のHDD」実現の可能性も、新たな物理現象が発見される - GIGAZINE
http://gigazine.net/news/20110704_limitless_hdd/
2011/07/07(木) 22:30:26.96
LHCでブラックホール圧縮したほうが簡単。
2011/07/07(木) 23:25:05.99
>>741
昔に流行ったπ（円周率）圧縮と原理は同じ
2011/07/08(金) 00:41:50.33
それとは違うだろ
2011/07/08(金) 01:54:35.69
>>741
圧縮と関係ないから。
2011/07/18(月) 16:25:30.65
アキレスと亀みたいな無限圧縮理論があったろ。
あれと似てるねって話だろう。
747デフォルトの名無しさん
垢版 |
2011/08/20(土) 12:26:41.97
基本的なことを教えてください。

①１Mバイトのランダムなデータ列と２Mバイトのランダムなデータ列をファイルにしてzipにしました。
　　圧縮率はどっちが高いですか？

②１Mバイトのランダムなデータ列と１Mバイトの数列（０，１，２・・・ｆｆH・・・）をファイルにしてzipにしました。
　　圧縮率はどっちが高いですか？

③１Mバイトの数列（０，１，２・・・ｆｆH・・・）と２Mバイトの同じ数列（０，１，２・・・ｆｆH・・・）をファイルにしてzipにしました。
　　圧縮率はどっちが高いですか？

できれば、経験的な結果ではなくて、数学的？技術的結果を知りたいです。（経験的結果ももしあれば知りたいです）
よろしくお願いします。
当方ハード屋です。簡単なプログラミングはできるぐらいのキャリアです。
2011/08/20(土) 12:41:46.03
>>747
zipなら自分でやってみればいい。
zipじゃないなら、圧縮率がどうなるかは圧縮アルゴリズムによる。
749デフォルトの名無しさん
垢版 |
2011/08/20(土) 12:45:01.97
>>748
レスどうも。

やっぱりやってみないとわからんものですか・・・
理論的にはどう考えたらいいのかを、聞きたかったんですが。
2011/08/20(土) 12:51:08.48
>>747
ランダムデータは多分全く圧縮出来ない
数列が00hからffhの方はもの凄く縮む
123は全て後者の圧縮率が高いよ
>>748の通り実験あるのみ
751デフォルトの名無しさん
垢版 |
2011/08/20(土) 13:03:32.15
>>750
レス、どうも。

『データ量が多いほうが圧縮率が高くなる傾向がある』

と考えていいのでしょうか？
また質問ですみません。
2011/08/20(土) 13:11:59.31
>>751
いや、zipはLZ法といって
同じパターンを検出して別の符号で置き換えるという仕組みになってる
ランダムデータは繰り返しがないから圧縮出来ないし
数列の方は00h-ffhが繰り返されるからそこで縮むのよ
753デフォルトの名無しさん
垢版 |
2011/08/20(土) 13:27:20.28
>>752
レス、どうも。

よくわかりました。
この場合ランダムデータと言えるか疑問ですが、
もし、ランダムデータでもちょっとでも繰り返しパターンが現れたとして、その大きさも出現率もランダムだとして、この場合少しは圧縮できると思います。
その場合は、

『データ量が多いほうが圧縮率が高くなる傾向がある』

とは理論的に言えないのでしょうか？
実験をして臨床的に？測定はできるでしょうが、まずは頭の中で整理したいので、よろしくお願いします。
2011/08/20(土) 13:36:12.73
>>753
データ(情報源)次第としか言いようがないんだけど
データ量が増えるほど参照可能なデータが増えるので圧縮率は上がる
と言える
ので理屈としてはそれであってる
言うまでもなく計算量は増えるけども
755デフォルトの名無しさん
垢版 |
2011/08/20(土) 14:12:35.01
>>754
ありがとうございます。

ですよね。ランダムデータの共通概念を確認してから話すべきでした。
失礼しました。
2011/08/20(土) 16:35:41.98
圧縮について理論的な裏付けを探しているなら、
次のキーワードについて調べてみるとよいでしょう。
初等的な情報理論の参考書に出ているものです。

情報源（符号化）
エントロピー
ユニバーサル
エルゴード性
エントロピーレート
2011/08/20(土) 17:20:35.51
>>756
どうも。

わからないところが出てきたら、また教えてください。
2011/08/21(日) 00:44:08.36
>>749
やってみないとわからないというより、何を目的に聞いているのかわからないから、答えにくい。
圧縮もzip(LZ法+ハフマン)に限る話なのか、あらゆるアルゴリズムを検討するかによっていろいろ変わってくる。

情報理論的にランダムデータは統計的には圧縮できない。
(圧縮できるケースも０ではないが、できないケースがそれをはるかに上回る)
2011/09/08(木) 00:22:45.54
解凍速度重視でデコーダー書いてアセンブリ出力見て無駄が減り
実測でも速くなってるとお茶が美味い、でへへ
2011/09/22(木) 01:47:33.31
>>510-512関連での質問なのですが、
もし対象のファイルが複数あり、それぞれ違うドライブの場合、
どのように対応すればよいのでしょうか?
2011/10/04(火) 04:33:33.93
7zなら、パスを列挙したリストファイルを渡して圧縮させるコマンドが無かったか？
2011/10/19(水) 17:21:06.75
zip32j.dllで同じファイルを圧縮しても、
出来るzipのCRCが毎回違うってのは正常？

WinRAR使うと毎回CRCは同じなんだが
2011/10/19(水) 17:53:00.10
圧縮ルーチンの中で乱数使ってるんじゃないかな
解凍後のCRCが一致してれば問題なし
2011/10/19(水) 18:29:03.25
>>762
できたzipファイルのCRC、圧縮されたエントリのCRC
どっち？

前者なら最終アクセス時間も記録してるとかって可能性もあるよ。
後者だと理由がサッパリわからんけど。
2011/10/19(水) 19:09:18.86
>>763
なるほど。
確かに解凍後のファイルのCRCは一致してるんで、
実用上問題は無いんですが、ちと気になったもので。
これ常識なのかな、と。

>>764
前者です。

> 最終アクセス時間も記録
これですかね？
2011/10/20(木) 22:51:54.07
スレ違い
767デフォルトの名無しさん
垢版 |
2011/11/29(火) 22:44:34.18
ふと気になってzipの仕様を見ていて疑問に思ったのだけれど、
「中央ディレクトリ」の存在意義ってなんですか？
わざわざローカルファイルヘッダと分離して、しかも書庫末端に配置
させている意味がわからないです。
書庫冒頭ならここを基点にランダムアクセスがしやすい、というのは
想像できるんですが、可変長コメントを終端に許容している時点で
後ろから計算するのも非常にめんどくさいことになってますし。
どうせだし作者にメールでも投げるか、と思ったら作者亡くなってるし。
2011/11/29(火) 23:04:07.92
LZH書庫のゼロ終端と同レベルには必要。
2011/11/29(火) 23:11:50.61
1passで書庫作る場合、中央ディレクトリみたいのをつけようとすると
どうしてもケツにしかつけられないってだけでしょ。
1passで書庫作れるようになってるのはzipの強みの一つだと思うんだが。

例えばlhaはチェックサム書き出すために一旦ヘッダまで戻らなきゃいかんから2passになる。
圧縮データをどっかに保存しておければ1passっぽくできるけど。そのために記憶領域が必要になる。
770767
垢版 |
2011/11/29(火) 23:20:10.21
解凍することだけ考えてて圧縮のこと何も考えてなかった。
なるほど。確かに1passで作れるっていうその点は強みですね。
すごいスッキリしました。ありがとう。
2011/11/29(火) 23:44:11.23
ケツにもコメントの長さつけてくれれば
後ろから読むのが楽だったと思わずにはいられない
2011/11/30(水) 02:12:31.07
ファイル先頭に置くと、ファイルを追加するたびに書庫ファイル全体を
書き直さないといけなくなるよ。
末尾にあれば追加された分と中央ディレクトリ分だけで済む。
2011/11/30(水) 03:49:27.68
インデックスは末尾が当然だな。もしくはシーケンシャルアクセスで良いならTARのようにする。
2011/11/30(水) 13:05:45.71
圧縮と暗号化を両方行いたい場合
先に暗号化してから圧縮すると
圧縮してから暗号化したときに比べて
サイズがかなり大きくなってしまいます
圧縮と暗号化を同時に行うアルゴリズムだと
効率は良くなるのでしょうか？
2011/11/30(水) 13:11:04.03
符号化と暗号化を勉強しろｗ
2011/11/30(水) 13:22:50.71
>>1
2011/11/30(水) 13:25:01.15
まあアルゴリズムの話はともかく
どうして暗号化ツールには圧縮機能がなくて
圧縮ツールには暗号化機能がないのはなぜ？
2011/11/30(水) 14:22:37.76
君が馬鹿だからそういう疑問が出る。
>>775
2011/11/30(水) 14:57:55.25
一番の問題点は仕様がアホみたいに巨大かつ肥大化を続けてることだろう
2011/11/30(水) 15:28:11.94
モチはモチ屋的な思考する人が多いからじゃねーかと思ったが、
圧縮ソフトは暗号化機能つけてるのも結構あるよね。
2011/11/30(水) 15:44:18.70
圧縮するときの符号化した辞書を暗号化すれば医院で内科医
2011/11/30(水) 15:53:09.43
馬鹿には無理
2011/12/02(金) 05:52:08.41
ちょっとした思いつき
ABCCABBCA
というような並びのデータがあるとして、このままではあまり圧縮に適してないが
これを
ABC
CAB
BCA
と並べて右上から右下斜めに読むと
CBBAAACCB
となって圧縮しやすくなる
これを斜め読みアルゴリズムと名付けた

データを二次元に展開すると読み方は横読み、右下斜め読み、縦読み、左下斜め読みの4種類定義できるが
この4種類を順番に適用して圧縮を繰り返すと、可逆を維持したままファイルサイズをものすごく小さくできるかもしれない
これを回転圧縮法と名付けた

暇な人は論文でも書いてみたらお金になるかも
2011/12/02(金) 06:02:58.46
http://ja.wikipedia.org/wiki/%E3%83%96%E3%83%AD%E3%83%83%E3%82%AF%E3%82%BD%E3%83%BC%E3%83%88
2011/12/02(金) 11:35:07.19
馬鹿には無理
786デフォルトの名無しさん
垢版 |
2011/12/02(金) 12:16:26.63
俺も考えたぜ！

１　はなっから元のデータを線形合同法で作る
２　シード値のみ保存

やばい　1/10000000000ぐらいいく
誰か論文作れ
2011/12/02(金) 12:40:08.63
それは似たようなことをIBMが専用チップを作ってやろうとしてたね
2011/12/02(金) 12:44:45.72
馬鹿には無理
2011/12/02(金) 14:28:29.13
データを最適化する手法は昔からあるわけで、恥ずかしいから馬鹿は黙っておけｗ
790デフォルトの名無しさん
垢版 |
2011/12/03(土) 11:06:16.82
静止画・動画とかアプリケーションが既知の場合なら、データの統計的性質分かってるわけだから、予め超巨大な辞書を作ってみんなで共有しておけば、めっちゃ圧縮できそうな気がするんだけど。
なんで未だに離散コサイン変換＋ベクトル量子化で頑張ってるの？

詳しい人おしえて！
2011/12/03(土) 11:19:41.21
それってさ、「ここのURLにデータがあるよ」ってアドレス渡す事と同義なんだよ
データ自体が小さくなるわけじゃないんだ
2011/12/03(土) 11:26:41.08
量子テレポーテーションをうまく応用すれば圧縮に使えるのではないか。
793デフォルトの名無しさん
垢版 |
2011/12/03(土) 12:05:45.58
>>791
データ自体が小さくなるってことじゃね？
画像の元サイズＸ、圧縮後のサイズＹ、枚数Ｎ、辞書のサイズＺとすると

N*X > N*Y + Z

になってれば圧縮できてるよね。
Ｎがでかけりゃでかいほど、辞書でかくしてもいいじゃん。
１Ｇ
2011/12/03(土) 12:22:40.45
研究発明にはこういう馬鹿も必要だ
795デフォルトの名無しさん
垢版 |
2011/12/03(土) 12:49:44.40
しかも、辞書分のＺを全員が共有できてるという前提であれば、

N*X > N*Y

って、すごい圧縮できそうやん！
コサイン基底なんか使わずに、１0ＧByte分くらいの過剰な基底を用意しとけば、画像なんか超小さくなるべ！
2011/12/03(土) 18:32:29.10
>>790
別に頑張ってないよ。
もっと先の技術はちゃんとあるが、馬鹿は知らなくていいよ。

ハッシュ値(またはそれに類するもの)で元のデータを引っ張って来れる仕組みを圧縮と見なすなら、
ファイル共有ソフトは一種の圧縮であり、winnyなりshareなり、既にある。

2011/12/03(土) 18:34:54.58
>>795
ならないよ。
JPEGエンコーダなんて一日もあれば作れるから、本当にそう思うなら作って実験してみようよ。
そうすることで自分の愚かな間違いにちゃんと気が付けるよ。
2011/12/03(土) 19:04:11.19
昔、「ハノイ圧縮」ってネタがあったけど、これって辞典型の究極と言える。
ところが、このハノイ圧縮で、世界中のデータを圧縮していくと、
たちまち圧縮できなくなっていき、かえってサイズが増えることになる。

ちょっと試算してみるとわかるけど、
データ圧縮が圧縮となる世界って、非常に狭いんだよね。
ハノイ圧縮で圧縮できている範囲だけ利用するとしても、
結局それは、現在の他のデータ圧縮法よりは多少マシかなぁ程度。

ハノイ圧縮とLZ78を比べると面白いかもしれない、程度。
799デフォルトの名無しさん
垢版 |
2011/12/03(土) 20:28:46.35
>>796


圧縮アルゴリズム構築時に既知のデータと、圧縮時に未知のデータと分けて考える必要があるね。
ちなみに非可逆ね。

アルゴリズム構築時にハッシュテーブル作っておいて、様々な未知データに対してハッシュ値計算してハッシュテーブルを引く。
ハッシュテーブルにハッシュ値がなかったら、圧縮画像＝真っ黒画⇒像残差デカイってこと。
残差小さくしつつ圧縮率上げるんだから、非可逆の圧縮アルゴリズム考えてる人たちは、この間を責めてるわけだよな。

COS関数という既知の基底以外でも、ウェーブレットみたいに基底も学習しておけば、圧縮率上がるケースも当然あるだろうね。
800デフォルトの名無しさん
垢版 |
2011/12/03(土) 20:31:16.19
ちなみに、8x8の画像だったら64次元の基底があれば、任意の画像を線形和で表せるけど、
基底を10000万個用意しておいても良いわけだ。
圧縮したい画像の枚数が多ければ、10000万個基底用意しておいたとしても、勝てる場合がありそう。
2011/12/03(土) 20:49:07.46
>>800
ちなみに、10000次元の係数の大半がゼロになるように、L1正則化でもかけて、基底学習できればよさげだな。馬鹿馬鹿いってるやついるけど、血の巡り悪そうだな。
802デフォルトの名無しさん
垢版 |
2011/12/03(土) 21:55:07.14
>>797
隣り合うピクセルの色が近いからCOSで基底変換すると、高周波数成分が0になっるって気付いた奴がいるわけだよね。
そいつは、何枚かの画像（学習データ）を観察して、それに気付いたわけだ。
そして、未知の画像に対しても、同様の統計的性質があるに違いないと思った。これが暗にあるわけだな。


>>796
ちゃんと辞書のサイズZって書いてあるだろ。
ハッシュの先に格納されてるデータがあって、そこのサイズも考慮すれば、それって圧縮できてないよね。
2011/12/03(土) 22:49:37.03
このデータがこのシステムでこれだけのサイズになりましたっていう実測値だしてくれよ
2011/12/03(土) 23:10:54.75
WikipediaデータすべてがLinuxで1MBになった。
2011/12/03(土) 23:20:20.81
話にならんな
2011/12/03(土) 23:24:13.18
>>805
bzip2を知らんのか。
2011/12/03(土) 23:58:56.90
話にならんって言ってんだ
流れを読めよ
2011/12/04(日) 00:04:18.76
>>807
お前Linuxのインストールで躓いたくちだろ。
2011/12/04(日) 00:07:16.85
流れが読めない…
2011/12/04(日) 00:17:57.42
今のLinuxのインストールにどうやって躓く要素があるんだ？
2011/12/04(日) 00:19:41.82
Linuxができないのに圧縮を語るとは世も末。
2011/12/04(日) 00:24:16.25
LHA、ZIP、GZIPをはじめとする圧縮ユーティリティーの大部分はLinuxで開発された。
まずLinuxの勉強からやり直せ。
2011/12/04(日) 00:25:10.02
Linuxは俺が教えた
814デフォルトの名無しさん
垢版 |
2011/12/04(日) 00:28:07.22
これからはLinuxの時代
2011/12/04(日) 00:56:55.25
>>812
えっ
2011/12/04(日) 00:58:14.31
>>786の要望に応えられる圧縮をLinuxで作ってくれよ。
2011/12/04(日) 00:59:28.04
>>815
お前は圧縮ユーティリティーがCUIとして作られたことも知らないのか。
2011/12/04(日) 00:59:33.37
bzip2を知らんのか。
2011/12/04(日) 01:00:20.11
馬鹿には無理
2011/12/04(日) 01:00:53.14
CUI=Linuxだ(ｷﾘｯ)
2011/12/04(日) 01:03:49.60
>>816
それは車輪の再発明と言って優秀なリソースを分散させる結果となる。
2011/12/04(日) 01:07:07.61
できないんならひっこんでろ。
2011/12/04(日) 01:09:20.06
>>822
bzip2を知らんのか。
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況