圧縮・復元 相談室

■ このスレッドは過去ログ倉庫に格納されています
1デフォルトの名無しさん
垢版 |
NGNG
アルゴリズムは別スレで
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を知らんのか。
2011/12/04(日) 01:11:00.95
できてないじゃん。
2011/12/04(日) 01:13:36.24
最近ム板に変なのが住み着いて、ほとんどのスレが機能しなくなってるのは
なにか対策を考えて欲しい。
もう2chでは無理かね。
2011/12/04(日) 01:13:58.37
>>817
＞LHAは、奥村晴彦が開発したアルゴリズムをもとに、吉崎栄泰がMS-DOS向けに開発したもので、1988年にパソコン通信で初公開された。
ttp://ja.wikipedia.org/wiki/LHA
2011/12/04(日) 01:16:49.73
フォントですか？
2011/12/04(日) 03:17:42.97
>>800
だから、やってみろよ。自分が馬鹿だったってわかるから。
2011/12/04(日) 03:29:31.18
>>802
全然違うよ。
JPEGのエンコーダを書いたこともなく、ろくに理解もしないで何言っているの？
統計的性質なんて関係ないから。

＞ちゃんと辞書のサイズZって書いてあるだろ。

共有しているなら、辞書がネットワーク上にあったっていいだろ。
ローカルストレージに限定する理由はない。

＞ハッシュの先に格納されてるデータがあって、そこのサイズも考慮すれば、それって圧縮できてないよね。

本当に馬鹿だな。
ネットワーク全体で冗長度が下がっていれば、それは圧縮と同じなんだよ。
ハッシュは、辞書の符号化に相当する。
830デフォルトの名無しさん
垢版 |
2011/12/04(日) 06:10:22.03
>>829

>統計的性質なんて関係ないから。
JPEGエンコーダってDCTしてハフマン符号化じゃねーのかよ。
統計的性質使って圧縮してんだろ、馬鹿か？
全然違うって、何が違うか指摘しろよ。議論の基本を知らないのか？

>共有しているなら、辞書がネットワーク上にあったっていいだろ。
>ネットワーク全体で冗長度が下がっていれば、それは圧縮と同じなんだよ。
ならハッシュ値計算してデータをひっぱってくるシステムも、圧縮できているわけだな。
今現在ある全ての画像を一箇所に溜めて、未来に撮影される画像もそこに含まれていれば、圧縮できていると言えるだろうな。
とりあえず、学習データで圧縮アルゴリズム作って、検証用のデータで精度を測るって、基本は理解してるか？
2011/12/04(日) 08:54:51.86
↑
こいつ最高にアホ(AAry
832デフォルトの名無しさん
垢版 |
2011/12/04(日) 09:36:28.61
とりあえず、ハッシュマップの話は飽きたよ。
100枚画像があって、20枚重複してて、実質80枚分のデータだったら、サイズ0.8倍になるのね。

DCTとハッシュマップの間を責めれば圧縮率あがるだろってことでしょ？
2011/12/04(日) 12:21:13.24
>>830
初心者はWindowsでも使ってろ。
2011/12/04(日) 17:45:11.22
>>830
＞JPEGエンコーダってDCTしてハフマン符号化じゃねーのかよ。

そうだよ。で、君はJPEGエンコーダぐらい書いたことあるんだよね？
俺はちゃんと0から自作したことあるよ。

＞統計的性質使って圧縮してんだろ、馬鹿か？

どこが？
DCTは統計とは関係がないし、ハフマン符号は対象データの中での出現頻度であって、
先の様々な画像の統計的性質とは無関係だよ。
量子化テーブルをどういうものにするかは、ある統計的な性質と関係あるが、
それは画像の統計的性質じゃなくて、人間が見たときに許容できる誤差としての統計的性質。

＞全然違うって、何が違うか指摘しろよ。議論の基本を知らないのか？

こんな枯れた技術は議論する価値もないだろ。
調べればわかるし、わからないような馬鹿や、調べることもできないような馬鹿はここに来るな。

最低限、自分のアイデアを自作してみてからここに来い。
その上で、わからないことがあれば、俺様が教えてやる。
2011/12/04(日) 17:46:44.08
webp っていいの？
持ってる jpeg ファイル全部 webp 化して
元の画像捨てても平気？
2011/12/04(日) 18:12:14.39
>>835
お前が今後使うブラウザやビュアが対応しているならいいんじゃね
可逆モードもあるしな。
2011/12/04(日) 18:16:28.65
>>834
＞DCTは統計とは関係がないし、ハフマン符号は対象データの中での出現頻度であって、
＞先の様々な画像の統計的性質とは無関係だよ。
ん？関係あるよね？
なんでDCTで直行変換かますと、多くの軸の係数が0になるの？
近くのピクセルの色が似てるからだよね。
こーいうのを、人は統計的性質と呼ぶのでは？

＞それは画像の統計的性質じゃなくて、人間が見たときに許容できる誤差としての統計的性質。
人の見が感じる違いと2乗誤差は違うから、そこを責めてる話もあるけど。
そこに拘らなければ、まぁ2乗誤差だろうな。
DCT後の軸の係数が小さいところを0に打ち切るだけ。

上の議論は、COS以外の基底を使って、より少ない非ゼロの軸で、2乗誤差を小さくすることが出来ないかって話じゃね？
後ろのハフマン符号化には触れてない。
2011/12/04(日) 18:20:06.53
>>837
まず、答えろよ。
君はJPEGエンコーダぐらい書いたことあるの？ないの？どっち？
お前のレベルに合わせて教えてあげるから。
2011/12/04(日) 18:24:29.29
>>837
＞なんでDCTで直行変換かますと、多くの軸の係数が0になるの？

ならないよ。

＞DCT後の軸の係数が小さいところを0に打ち切るだけ。

違うよ。

量子化テーブルをなんで使うのかわかってる？
2011/12/04(日) 18:29:21.23
>>839

0になるというか、係数が小さくなるってことな。
それで量子化テーブルの数値がきまってんだろ。馬鹿か？
2011/12/04(日) 18:34:19.38
>>840
小さくならないよ。小さくするために量子化テーブルを使うの。
馬鹿なことを書いて恥をかく前に、JPEGエンコーダぐらい自作しろよ。
基本部分は一日あればできるし、理解も深まるから、こんなスレに書き込んでいるよりずっといいぞ。

それができないような馬鹿なら、この世界に首を突っ込まない方がいい。
2011/12/04(日) 18:37:49.68
>>841
http://ja.wikipedia.org/wiki/%E9%9B%A2%E6%95%A3%E3%82%B3%E3%82%B5%E3%82%A4%E3%83%B3%E5%A4%89%E6%8F%9B
ほら、Wikipediaにのってるよ。
右の画像のDCTみてね！
2011/12/04(日) 18:44:10.50
さらにいうと、どんな画像食わせても、高周波数成分は小さくなる。
この大きさに合わせて量子化テーブルの値が決まってるわけだな。

おまえ、作ったことあんじゃねーの？理解せずにコード書き写しただけ？
2011/12/04(日) 18:51:27.51
>>842
だから何？実際の数値見たことないの？
量子化テーブルが周波数によって数値が違う意味わかってる？
2011/12/04(日) 18:55:04.30
>>843
＞この大きさに合わせて量子化テーブルの値が決まってるわけだな。

違うよ。
実際には、高周波成分に大きな値が来ることが多々ある。
低周波の値より、高周波の値の方が無視できるから、量子化テーブルの係数が大きくなるの。
低周波は数値が小さくても無視しない方がいいから、テーブルの係数が小さい。
2011/12/04(日) 18:55:58.56
>>844
大体、低周波数が大きくならないなら、DCTする意味ねーだろ。
ひとつおりこうさんになったな。
2011/12/04(日) 18:57:19.48
>>845
そう。
多々ある。その頻度と、各基底が人の目に影響を与える比率で、係数が決まっている。
2011/12/04(日) 18:57:47.70
>>843
作ったことあるも何も、仕事でやってて、それで飯食っている。
2011/12/04(日) 19:03:34.67
>>846
＞大体、低周波数が大きくならないなら、DCTする意味ねーだろ。

JPEGにおいてDCTは高周波成分と低周波成分を分ける意味しかない。
つまり、どの情報を捨てるかというフィルタ(後段の量子化テーブル)を使って、圧縮率を上げている。
(他にも色情報を落とすとかもあるが)
変換誤差があるものの、DCT自体はnear可逆変換なので、それだけでは圧縮にならない。
2011/12/04(日) 19:17:15.10
>>849
そんなはずはない。
色んなソフトで使われてる係数は、「頻度の逆数ｘ視覚への影響」で決まってるはずだぞ。
つまり、基底組み替えた結果、スペクトルに偏りがあるってのは重要なんだよ。

どっかに、量子化係数の決め方の解説があったが、見つからんな。
2011/12/04(日) 19:21:25.29
この話って、そもそも基本なはずだが。

つーか仕事でやってんのに、こーいうの理解してないの？
流石に周波数分離するだけってのはないだろ。
音の圧縮だって同じじゃん。
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況