圧縮・復元 相談室

■ このスレッドは過去ログ倉庫に格納されています
1デフォルトの名無しさん
垢版 |
NGNG
アルゴリズムは別スレで
2005/06/26(日) 17:41:04
>418 >419
線形計画法のカーマーカー法じゃないの？
>カーマーカー特許とソフトウェア―数学は特許になるか 中公新書
>ttp://www.amazon.co.jp/exec/obidos/ASIN/412101278X/249-7663900-1232317
元々の圧縮アルゴリズムはともかく、○○＋ハッシュとかいうのになってくるとどんどん納得できなく
なっていくんだが。
422419
垢版 |
2005/06/26(日) 20:43:13
>421
すまんこった、カーマーカー法が最初の特許アルゴリズムだった。
ほら吹いてしまいました。ごめんさない。
423デフォルトの名無しさん
垢版 |
2005/07/01(金) 09:17:37
Info-ZIP社のZIP32.DLLって商用で使用するにはライセンスがいるのでしょうか？
UNZIP32はいるみたいなのですが。HP読んでもわからない･･･
2005/07/02(土) 03:14:07
zip32.dllは知らんが、zlibならいらないはず。
425413
垢版 |
2005/07/02(土) 07:57:25
>>414
どの/coffですか?
mlなら/coffつけてますが?>>407
2005/10/12(水) 02:59:27
hosyu
427デフォルトの名無しさん
垢版 |
2005/10/25(火) 10:46:17
質問です。
DEFLATE圧縮では元データはバイトごとに圧縮されるのですか？
それとも6ビットや5ビットなどビット単位ですか？
RFCと一緒にzlibやgzipのソースを読んでいるのですが
自分の読解力ではわかりません。
2005/10/25(火) 11:33:32
バイト単位
429427
垢版 |
2005/10/25(火) 11:37:52
>>428
バイト単位ですか。ありがとうございます。
その線で読んでみます。
2005/10/25(火) 11:44:07
ソース読んで理解できないなら>>298
431427
垢版 |
2005/10/25(火) 12:56:37
>>430
やっぱりその本を買った方がよさそうですね。
今から買ってきます。
2005/10/30(日) 11:38:36
書庫が１バイト足りずに破損している場合、末尾に00を付加するという話を聞いたんですがどうやって付加するんでしょうか？
調べようと思ったんですが検索ワードが思いつかない…
2005/10/30(日) 14:54:09
>432
君が何を聞きたいかが理解できない。
とりあえず付加するのは誰？
特定のソフトの話か、特定のファイル形式の話？
2005/10/30(日) 18:22:37
>>433
漏れの予想では、ファイルの末尾に00を付加させるのに、
どんな関数orAPIをコールすれば良いか判らない

そういうレベルの質問だと思う
2005/11/01(火) 00:17:17
板違いの予感。まさかnarがどうとかって話じゃないだろうな。

1 バイトのファイルを作っておいて copy /b とか cat とか、
そんなスキルもないならバイナリエディタ。

ってところだったりして。
2005/11/01(火) 02:01:51
narってなにさ？
2005/11/04(金) 11:05:22
もしかして null ?
2005/11/04(金) 11:16:46
ナルほど
2005/11/04(金) 20:13:26
>>438
誰がうま(ry

>>432, >>435
出てきて釈明しる！
440435
垢版 |
2005/11/04(金) 22:15:29
済まん、あっさりスルーされると思ってた。
「伺か」が使うアーカイブ(実態はzip)の拡張子。
公開終了したアーカイブをWebArchiveから拾ってくるって話。
まあ、オタネタだ。
441435
垢版 |
2005/11/04(金) 22:26:30
補足。
WevArchiveにはファイル末尾の0を切り捨ててしまうというバグ(?)がある。
そのためせっかく昔のアーカイブを見つけてもzipが解凍できないことがある。
末尾に0を付加してやると正常に解凍できるようになる。
というのがこちらで想定した問題のバックグラウンド。
442432
垢版 |
2005/11/04(金) 22:31:07
自己解決したから書き込まなかったんだけど、WebArchiveのzipファイルで〜て事が聞きたかった。
narは良く分からなかったけど、435が書いてくれたからまぁ良いかと思ってた
オレのせいで微妙な話が続いて悪かったです
2005/11/12(土) 12:52:07
zlibの使い方を詳しく丁寧に説明してる日本語サイトを教えてください。
あと、gzip（と可能ならzipも）の中のファイル名を解凍せずに知りたいんですが、できませんか？
2005/11/12(土) 18:30:27
zlib.hの英語を読むのが一番確実だと思うけど。
別に読みにくくは無いし、そんなに長くもないし。
gzio.cも。
2005/11/17(木) 22:59:07
>>443
ヘッダにテキストで書いてあるけど。
2005/11/17(木) 23:36:52
>>445
日本語って言ってるだろうが、馬鹿
2005/11/18(金) 00:43:37
日本語なかったっけ？　どっかでzlib.hのコメント日本語訳みたことがあるんだけどどこだったか…
2005/11/18(金) 15:11:28
>>446
日本語読めないのに日本語要求してたんですね。
# 単に駄々をこねてみたかっただけかな? :-P
449443
垢版 |
2005/11/18(金) 23:21:09
ありがとうございました。
日本語訳はこれですね。
ttp://www.sra.co.jp/people/m-kasahr/zlib/zlib-1.1.4-ja.h
2005/12/25(日) 22:34:49
zlib の deflate　を利用して
自前でzipファイルを作るプログラムを作ろうと思います。
とりあえず、ここの仕様書を見たのですが、
http://www.pkware.com/business_and_developers/developer/popups/appnote.txt

extra fieldの意味がよくわからないです。
私の場合は、この部分は出力しなくて良いのでしょうか？
451デフォルトの名無しさん
垢版 |
2005/12/26(月) 16:51:16
あげます
2005/12/26(月) 23:35:03
遠慮なく頂きます
453デフォルトの名無しさん
垢版 |
2006/02/09(木) 06:24:45
前スレ

圧縮アルゴリズム考えたんですが
http://pc8.2ch.net/test/read.cgi/tech/1041803200/


テンプレは >>1-3 あたりには無い。
454デフォルトの名無しさん
垢版 |
2006/02/10(金) 23:16:40
乗っ取るの？
455デフォルトの名無しさん
垢版 |
2006/02/26(日) 18:38:09
圧縮アルゴリズム2
http://pc8.2ch.net/test/read.cgi/tech/1140946646/
2006/02/27(月) 10:56:10
圧縮アルゴリズム考えたんですが

まずデータの中にフラグの立ったビットがいくつか数えます。
そしてデータは0と1を並べ変えたものと考えます。
あとはそれを使って先頭ビットから1なら
(そこから先のビット数)Ｃ(そこから先の立ちビット数)
を計算して足していきます。
つまり圧縮するデータを0と1の並べ替えとしたときに、
それらを辞書順に並べて上から何番目かを数えるということをします。

例)8ビット中3ビット立ってるとして
10001100
最初1なので
7Ｃ2
を計算。0は読み飛ばし次の1でも
3Ｃ1
を計算。これ以上は変わらないので終わり。
で、上の二つを足す
7*6/2*1+3/1=24
あとはこの数と圧縮前のファイルサイズと立ちビットの数だけ出力すれば復元可能。

こいつはすげぇやとｵﾓて作ったら799バイトのデータを50分かけて圧縮して何番目のデータかの数値だけで2972バイト悔いました。
Ｃ(コンビネーション)て恐ろしいな
2006/02/28(火) 00:49:54
俺を圧縮してみろ！！
2006/02/28(火) 09:12:37
>>456
Lynch-Davisson 符号とか数え上げ符号を調べてみて
459デフォルトの名無しさん
垢版 |
2006/02/28(火) 10:27:28
圧縮にはならないって事か？調べたけどあまり無くて分からなかった
2006/02/28(火) 16:19:05
10年くらい前、bzip で使われている
ブロックソートが何故圧縮にいいのか証明されていない、
と聞いた気がするんだけど、今はもう証明されているの？
2006/03/01(水) 03:29:22
( >>460 http://www.google.com/search?q=BWT+MTF&lr= )
2006/03/01(水) 03:52:31
>>460
有村　とか　Effros の論文読んでみて
2006/03/01(水) 04:02:46
>>456 >>459
Schalkwijk の数え上げ符号

長さ n のバイナリ文字列中に 1 の個数が w 個あるものを考える
このとき、インデクス i

　　i = Σj=1,n x[j] n-j C w[j]

を用いて1対1に対応付けすることができる。ただし、w[j] = Σi=j, n x[i]

符号化は、まず、1 の個数 w を ceil(log n) ビットの2進数で出力する
次に、インデクス i を ceil(log k C w) ビットの2進数で出力する
なお、ceil() は切り上げ

この符号化は、1記号あたりエントロピーまで漸近的に圧縮可能
2006/03/01(水) 14:26:02
>>463ごめん後半からわかんなかった…

ところでJAVAでLZWとLZ77とHUFFMANとDEFLATEを説明サイト見ながら自分なりの解釈で作ったんだけど
76Kbのビットマップをデフレで圧縮したら44Kbになったのね。
で、7zのZIPで圧縮したら37Kbになったのよ。
これって何がいけないの？Lhacaも7zより圧縮率悪いけど
どういう工夫すれば縮むようになるん？

教えてエロい人！
465デフォルトの名無しさん
垢版 |
2006/03/02(木) 18:09:48
AGE
466デフォルトの名無しさん
垢版 |
2006/03/02(木) 23:20:46
ハフマン圧縮について教えてください。

よくあるのは、出現率の低いものを２個取り出して、その和をつくり、さらに残ったなかから一番出現率が小さいものをとりだし、
これと、先ほどの和の結果との和をとり・・・
という説明です。

でもなんか要するに出現数のおおい順にソートして（出現ゼロ回のものは無視する）
A,D,B,C,・・・みたいに配列に入れます。
そして順に、1,10,110,1110,11110・・・
と符号をふればいいだけのように思えてしまいます。
なぜ小さいものを取り出して和を作り、さらに小さいのと和をつくり・・みたいなことをする必要があるのでしょうか？
467デフォルトの名無しさん
垢版 |
2006/03/02(木) 23:35:09
最初俺もそう思ったけど、ちょっと考えたらそれじゃ意味ないことに気づいたんだよ
なんでかって？忘れたなぁ…
2006/03/03(金) 00:01:40
>>466
それは unary 符号（単進符号、一進符号）というもの

符号が最適になるには条件というものがあって、
unary の場合、記号の出現確率が 1/2, 1/4, 1/8, ... となる場合にのみ最適な符号を構成できる
一方、Huffmanはどんな出現確率の記号群に対してでも最適な符号を構成できる
469466
垢版 |
2006/03/03(金) 00:41:32
なるほど。よくわからないけど間違っていたことだけはわかりましたｗ
ありがとうございます！！！！！！！！！
470デフォルトの名無しさん
垢版 |
2006/03/04(土) 00:41:35
JAVAでLZWとLZ77とHUFFMANとDEFLATEを説明サイト
教えてくれ俺もみたい
471デフォルトの名無しさん
垢版 |
2006/03/04(土) 10:02:12
データ圧縮法概説
というところ。その名の通り原理や概念を解説しているだけでJAVAどころか
プログラミングにすらふれていない。
でも説明は分かりやすいからJAVAでも作れた。
472デフォルトの名無しさん
垢版 |
2006/03/04(土) 21:26:39
データ圧縮法概説
ないよ
どうすればいいの？
2006/03/04(土) 21:37:29
Internet Archive
2006/03/04(土) 21:39:06
つーか、ちょっとリンクを追いかけていけば生きてるサイトにたどり着いたぞ
2006/03/04(土) 21:54:37
どうやっておいかけるの？
476デフォルトの名無しさん
垢版 |
2006/03/04(土) 23:53:49
我楽多頓陳館で検索。
管理人は一人で何役もこなすアニメ好きの54歳
世露死苦!!
477デフォルトの名無しさん
垢版 |
2006/03/05(日) 14:04:16
見つかった？
2006/03/05(日) 19:46:29
今zip圧縮のサンプル作ってる
2006/03/05(日) 20:51:59
それはzlibとか使って？それとも圧縮部も自作？
自作だったら性能を上げる工夫とか教えてほしいです。
2006/03/06(月) 00:58:20
圧縮部分も自作です。組み込みに乗せるから
パフォーマンスそこそこでだいたい2kから10ｋいないの
zlibを作成しようとしてます。なので性能よりもマシン語
の吐かせた内容をコンパクトにすることに命をかけています。
私も工夫とかよく解らない部分が多いため、IEEEの論文などをいくつか入手し
勉強をしているところです。アルゴリズム的に速度を上げる方法と
コーディングレベルで最適化する方法2つの視点で最適化について
考えていますがまだ道のりは厳しいです
2006/03/06(月) 01:23:44
特許まわりはどうなのかしら?
482デフォルトの名無しさん
垢版 |
2006/03/06(月) 13:05:55
現在猿でも分かるC言語講座をみながらJAVAでブロックソートとMTFとレンジコード制作二日目。
Cはよく分からんがブロックソートの符号化とMTFの符号化･復号化が完成
ブロックソートの復号がうまく行かない…
483デフォルトの名無しさん
垢版 |
2006/03/07(火) 01:43:41
Huffman圧縮で質問です。
記号が一回しか登場せず、２分木が１つも作成できないような場合、
その記号にはどんな符号を割り当てるのですか？
484デフォルトの名無しさん
垢版 |
2006/03/07(火) 06:59:12
多分最初に出現する記号の種類の数もカウントしてるんだろ？
俺はその値が1になる場合は2にしてもう一文字あると仮定して
やってる。その文字は何でもいいが大抵は0x0だな
2006/03/07(火) 08:28:48
>>483
「記号が1種類しかない」フラグを作って、記号を記録しとく。
「記号がいくつ現れたか」も記録しとけば、記号は全部空ビット列に変換で良い。
2006/03/07(火) 21:31:22
ありがとうございます。
>>484
なるほど。それならアルゴリズムに大幅な変更はいらないですね。
>>485
そうですね。Huffmanにこだわらずにってことですね。

今からどっちにするか迷います。ありがとうございました。
2006/03/08(水) 00:50:18
動的ハフマンって実装自体は特許事項に
抵触技術内容含まれてないですよね？
488デフォルトの名無しさん
垢版 |
2006/03/08(水) 07:25:58
大丈夫でしょ。やり方にもよるかもしれないけど、まあ普通に作れば無問題
2006/03/08(水) 22:54:08
動画配信のMPEG４とかH264ってのは適合型ハフマンで送るのですか？
もしそうならパケロスしても大丈夫な理由を教えてください。
490デフォルトの名無しさん
垢版 |
2006/03/14(火) 19:13:07
やっとJAVAでブロックソートとMTFとRLE7とレンジ圧縮(圧縮だけ)
ができた。でもサイトにあるほどの圧縮率が出ないwwwww
なんで…orz
2006/03/14(火) 19:38:26
>>490
どこのサイトかしらないけど、結果だけ載せている場合は、かなり細かいチューニングや、
アルゴリズム改良が加えられていることが多い。

ソース・実行プログラムもあるなら、圧縮結果をバイナリ比較するとか、
サイトのプログラムによる出力を自作プログラムで展開させてみるとか（あるいはその逆）、
圧縮結果のバイナリそのものの解析をしてみたらどうだろう。
492デフォルトの名無しさん
垢版 |
2006/03/14(火) 21:50:38
猿でも分かるプログラミング講座とかいうとこだったはず
Cのソースがあったから移植してみたブロックソートは間違いないからなぁ…
まあいろいろ結果を調べてみる
2006/03/15(水) 12:29:54
>>492
Cのソースプログラムが公開されているので、
1ステップずつ動作を追っていけばいいのではないか

途中の変数の状態を確認したり、演算結果に差異がないかを調べたり
2006/03/15(水) 19:31:53
いい忘れてたけどCのコンパイラとか持ってないんだ。
落とさなきゃだめかな？
2006/03/15(水) 22:51:59
今や、GCCコンパイラだけでなくMSコンパイラも無料。
「資金がない」で逃げる行為はもはや言い訳にならなくなった。
496デフォルトの名無しさん
垢版 |
2006/03/16(木) 07:09:38
重いの入れたくない。はあり？
2006/03/16(木) 15:00:59
なし、軽いの入れればいい
498デフォルトの名無しさん
垢版 |
2006/03/16(木) 16:44:24
sumという38000byte位のファイルを圧縮した結果250byte位劣って13Kb程になった。
実はヘッダなどの付加のしかたが微妙に違うのだがそれだけで
こんなに差が出るもんかな？ちなみに
BlockSort->MTF->ZLE+RLE7->RCA
って感じで4段階で圧縮してます。ヘッダ情報はどれもこっちの方が少ないのに…
2006/03/16(木) 19:09:09
>>498
アルゴリズムや定数も同じで、各段階でのヘッダも小さいのに
出来上がりファイルが大きいのなら何かバグってるんでしょうね。
2006/03/16(木) 21:24:35
>>499え!?マジで？℃チクショウーーーーーーーーー!!!!!
501デフォルトの名無しさん
垢版 |
2006/03/18(土) 08:49:04
困憊羅が雨後かねぇwwwwwwwww!!!!!!
502デフォルトの名無しさん
垢版 |
2006/03/18(土) 11:09:59
2chの圧縮ダットを解凍するにあたって資料が欲しいのですが、どこか頼みます。
2006/03/18(土) 18:35:48
TextSS　の64bit化おながいします

もしくは64bitにネイティブ対応した置換ソフトないですか？
504デフォルトの名無しさん
垢版 |
2006/03/19(日) 19:48:35
新しい圧縮アルゴリズム考えようぜ!!
2006/03/19(日) 20:22:48
>>504は>>1も読めないのか
506デフォルトの名無しさん
垢版 |
2006/03/19(日) 20:51:34
だってアルゴリズムスレ無いしここの再利用で十分だろ？
2chの無駄も減って一石二鳥だね
2006/03/19(日) 23:20:14
昨日、カミさんに怒られてrar圧縮されたさ
めっちゃ苦しかった
508デフォルトの名無しさん
垢版 |
2006/03/20(月) 08:55:07
KWSK!!!!
509デフォルトの名無しさん
垢版 |
2006/03/20(月) 22:28:21
へいっ!!!ついにやったぜ
JAVAにブロックソートとMTFとZLE7と適応型RANGEを移植完了!!ながかった〜
圧縮率は7z>BZIP2≒俺の>ZIPという感じ
これからは圧縮されたデータをさらに圧縮できるようにする変換でも考えるﾉｼ
2006/03/28(火) 22:15:14
ZIP圧縮について質問です。

zip32.dllに圧縮したいフォルダパスを-rオプションで渡した場合
zip内に格納されたファイルがドライブTOPからのフルパスで格納されてしまいます。

指定したフォルダ以下のみを格納するにはどうすれば、よいのでしょうか？
2006/03/29(水) 01:03:46
SetCurrentDirectoryしてから、相対パスで指定すればいいんじゃね？
512510
垢版 |
2006/03/29(水) 02:44:16
511>

無事にできました(^-^;
ありがとう
2006/04/22(土) 06:43:41
正確には圧縮アーカイブではないですが、ISOイメージファイルのフォーマットが書いてある場所を探しているのですが、いいのはないですか？ とりあえず日本語のは見つかりませんでした。イメージファイルでないISO-9660自体の解説はあるのですが・・・
514デフォルトの名無しさん
垢版 |
2006/04/23(日) 19:25:43
商用フリーな圧縮解凍ライブラリってありません？
利用はWindowsです。
2006/04/23(日) 21:59:31
http://cise.edu.mie-u.ac.jp/~okumura/compression/zlib.html
ここのサンプルcomptest.cで解凍しようとしても、エラー起こして解凍できないんだが、できます？
516515
垢版 |
2006/04/24(月) 11:44:22
これで圧縮したのはこれで解凍できるな。
しかし、他で圧縮したのはこれで解凍できないし、これで圧縮したのは他で解凍できない。
ヘッダー？　ヘッダーの処理はzlibはしてくれないんですか？　初期化時にヘッダー付きを渡すとポインターとカウンターが変わるかもしれないと説明には書いてあるが、実際変わらない。　
2006/04/25(火) 00:08:09
zlibはdeflate処理をしてくれるだけでZIPファイルフォーマットの解釈はやりませんよ。
その辺は自作汁。

この辺の本を読んでみるとよし…と思う
http://www.amazon.co.jp/exec/obidos/ASIN/4797324287/
2006/04/27(木) 18:33:29
zlibを使ってデータの伸張をやろうとしてて

byte *src // 圧縮されたデータ
int len // src の長さ
byte *dst // 解凍されたデータの格納先

dst = malloc(5 * len * sizeof(src));
decompress(dst, src, len); // src を展開して dst に格納
// 適当な処理
free(dst);

みたいなことをやろうかなと考えているんですが、dstで確保したメモリが足りなかったときのことを
考えるとこれじゃあマズいでしょうし、あらかじめ必要なメモリの計算は解凍処理をしないと
分からないようだしでちょっと困っています。
皆さんならどうしますか？
2006/04/27(木) 21:25:40
圧縮も自前なら圧縮データとは別に（先頭につけるとかして）、
圧縮前のデータのサイズも持っておく。
2006/04/27(木) 22:28:48
ちなみにsizeof(src)は4バイトだろ。
■ このスレッドは過去ログ倉庫に格納されています
5ちゃんねるの広告が気に入らない場合は、こちらをクリックしてください。
ニューススポーツなんでも実況