圧縮・復元 相談室

[1 デフォルトの名無しさん NG NG]

アルゴリズムは別スレで

[101 デフォルトの名無しさん NG NG]

？

[102 山崎渉 NG NG]

（＾＾）

[103 デフォルトの名無しさん NG NG]

さーど じゃなくて さんど だろ。

[104 山崎渉 NG NG]

（＾＾）

[105 デフォルトの名無しさん NG NG]

データ圧縮について勉強したいのですが
どんな本を読めばよいのかわかりません。
わかる方がいれば教えてください。

[106 デフォルトの名無しさん NG NG]

>>105
データ圧縮ハンドブック
http://www.pearsoned.co.jp/washo/prog/wa_pro30-j.html

[107 105 NG NG]

不可逆な圧縮で、情報源が時間とともにゆっくりと変化していくものを
想定しています。
ちなみに今は、「情報と符号化の数理」という本を読んでいます。

[108 デフォルトの名無しさん NG NG]

「文書データ圧縮アルゴリズム入門」(CQ出版社)の復刊きぼんぬ！
漏れは大学の図書館で借りたこの本のおかげで圧縮にはまった。

[109 デフォルトの名無しさん NG NG]

このサイトはいいね
http://www.ingnet.or.jp/~kojif/mu/comp/

[110 デフォルトの名無しさん NG NG]

>ちなみに今は、「情報と符号化の数理」という本を読んでいます。
それを読めば十分というか
それより高度な内容の本はない。

[111 デフォルトの名無しさん NG NG]

>>107
培風館の他の書籍で、たとえば
現代シャノン理論、植松友彦著
情報源符号化・無歪みデータ圧縮、情報理論とその応用学会編
情報理論における情報スペクトル的方法、韓太舜著
情報理論、橋本猛著
などを読むとよいだろう。

[112 山崎渉 NG NG]

（＾＾）

[113 デフォルトの名無しさん NG NG]

lzopはディレクトリ情報もてないの？

[114 デフォルトの名無しさん NG NG]

外人さんは凄いな。
どう圧縮したらLet It Be（レットイットビー）がレルピーになるのか小一時間・・・。
聞いた奴もレルピーと聞いてLet It Beと復元する能力に小一時間・・・。

[115 デフォルトの名無しさん NG NG]

>114

おまえはいいことにきがついた。
それが人間のもってる辞書圧縮機能というやつだよ

[116 デフォルトの名無しさん NG NG]

>>115
熟達すると、文脈だけで次に言いたいことがわかってしまう。
これを阿吽とか、ツーカーの仲とかいう。アイコンタクトもそれに入るかな。

あとは、反射神経、夢、なども人間に組み込まれた圧縮機能といえよう！

[117 デフォルトの名無しさん NG NG]

プッ

[118 デフォルトの名無しさん NG NG]

>117

ちんこ

[119 デフォルトの名無しさん NG NG]

□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□
□□□□□□□□■■□□□□□□□□□□□□□□□□□■■□□□□□
□□□■■■■■■■■■■■■■□□□□□□□□□□□■■■■□□□
□□■■■□□□□□□□□□□□□□□□□□□□□□□■■□□□□□
□□■□■■■■■■■■□□■□□□□■□□□■■■■■■■■■■■
□□■□□□□■■□■■□■■□□□□■□□■■■□■□□□□□■■
□□■□■■■■□□□■■□□■□□■■■□■□□□■□□□□□□□
□□■□□■■□□□□□■■■■□□□■□□■□■■■■■■■■□□
□□■□■■■■■■■■■■■□□□□■■■■□□□■□□□□□□□
□□■■■□□■■□■□□□■■□■■■□□■□□□■■□□□■■□
□□■■■■■■■■■■■■■■■□■□□□■□□□□■■■■■□□
□□■□□□□■■□■□□□□□□□□□□□■□■□■■□■■□■□
□■■□□□□■■□■■□□□□□□□□□■□□■□■■□■■□■□
□■□□□□■■□□□■■□□■■□□□■■□□■■■■□■■■■□
■■□□□■■□□□□■■■■■■□□□■□□□□□■■□■■□□□
□□□■■■□□□□□□□■■■□□□□□□□■■■■■■■■■■■
□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□□

[120 デフォルトの名無しさん NG NG]

ttp://www.geocities.co.jp/Playtown-Denei/1184/satoimo/

他のスレにこんなのあったぞ

[121 デフォルトの名無しさん NG NG]

>>120
どーせなら4/1になってから披露すれば良かったのに。

[122 デフォルトの名無しさん NG NG]

>>121
どっかのスレに作者らしき奴が居たような気がする。

[123 デフォルトの名無しさん NG NG]

zipとgzip(zlib)ってアルゴリズムの組み合わせは一緒なんですか？
それでZipのアルゴリズムは”lz77->ハフマン”で正しいの？
するとどこらへんがzipとlhaは違うの？

[124 デフォルトの名無しさん NG NG]

タフマソ

[125 デフォルトの名無しさん NG NG]

>>123
gzip, lha のアルゴリズム的な違いはほとんどないです。
したがって、圧縮率もほぼ同等です。
ツールとしては、単体で圧縮しかできない(gzip)のか、
書庫化できる(LHA)のか、で大きく違うわけで。

[126 山崎渉 NG NG]

（＾＾）

[127 山崎渉 NG NG]

　　 ∧＿∧
　　（　　＾＾ ）＜ ぬるぽ（＾＾）

[128 デフォルトの名無しさん NG NG]

RARの圧縮アルゴリズムって
何使ってるんでしょう？

[129 デフォルトの名無しさん NG NG]

ここで聞かずに作者に聞け

[130 山崎渉 NG NG]

━―━―━―━―━―━―━―━―━[JR山崎駅（＾＾）]━―━―━―━―━―━―━―━―━―

[131 山崎渉 NG NG]

　　　 　∧＿∧
ﾋﾟｭ.ｰ　(　　＾＾ ） ＜これからも僕を応援して下さいね（＾＾）。
　　＝〔~∪￣￣〕
　　＝ ◎――◎ 　　　　　　　　　　　　　　　　　　　　　山崎渉

[132 デフォルトの名無しさん NG NG]

ﾎｫｰｼｭ！

[133 デフォルトの名無しさん NG NG]

それよりGIFはタダで使えるようになったのか？

[134 デフォルトの名無しさん NG NG]

日本では来年の6/19に特許が切れるらしいが。

[135 デフォルトの名無しさん NG NG]

「GIFの特許切れでPNGあぼーん」なんてほざいてるﾔｼ、ほんっと何もわかってないよな。

[136 山崎 渉 NG NG]

　__∧＿∧_
　|（　　＾＾ ）|　＜寝るぽ（＾＾）
　|＼⌒⌒⌒＼
　＼ |⌒⌒⌒~|　　　　　　　　　山崎渉
　　 ~￣￣￣￣

[137 山崎 渉 NG NG]

　__∧＿∧_
　|（　　＾＾ ）|　＜寝るぽ（＾＾）
　|＼⌒⌒⌒＼
　＼ |⌒⌒⌒~|　　　　　　　　　山崎渉
　　 ~￣￣￣￣

[138 山崎 渉 NG NG]

（＾＾）

[139 山崎 渉 NG NG]

　　　 (⌒V⌒)
　　　│ ＾ ＾ │＜これからも僕を応援して下さいね（＾＾）。
　　⊂|　　　　|つ
　　　（＿）（＿）　　　　　　　　　　　　　　　　　　　　　　山崎パン

[140 NG NG]

みなさん、統合アーカイバプロジェクトのライブラリを使ってますか？

[141 １４０ NG NG]

誰もいらっしゃいませんか？

[142 １４０ NG NG]

各APIの関数名が統一されていないので、ダイナミックリンクが大変ですよね。
何故こんな仕様になっているんでしょうか？
　　　　unlha32.dll は Unlha、UnlhaOpenArchive、UnlhaCloseArchive、etc
　　　　unzip32.dll は UnZip、UnZipOpenArchive、UnZipCloseArchive、etc
　　　　ungca32.dll は UnGCA、UnGCAOpenArchive、UnGCACloseArchive、etc
　　　　tar32.dll は Tar、TarOpenArchive、TarCloseArchive、etc
　　　　（他にも色々）
これ、使いにくいですよね。

私は、こうやって解決（？）したんですが、皆さんはどうなさってますか？
　　　　std::string api = "Unlha";
　　　　unlha 　　　　= ( UNLHA 　　　　　)GetProcAddress( dll, ( api + "" 　　　　　　　　).c_str() );
　　　　openarchive = ( OPENARCHIVE )GetProcAddress( dll, ( api + "OpenArchive" ).c_str() );
　　　　......

（せっかくの統合アーカイバなのですから、スタティックリンクは勿体無いと思います）



更に、Unlha(...)、UnZip(...)、Tar(...)などのコマンドラインｵﾌﾟｼｮﾝの不統一が使いにくいなあと思います
unlha32.dll なら　　 x filename directory
unzip32.dll なら　　 -x filename directory
tar32.dll なら　　　 -x filename -o directory

これまた使いにくい。
こちらは解決が面倒で未だに手をつけていません。help me

[143 デフォルトの名無しさん NG NG]

それはもう、どーしようもない。カタチは統合になっただけで結局は別モノって感じ。
それなりに便利なんで感謝してますけど。
一応そこら辺の改善を含み、使いやすいアーカイバ関連のライブラリを作る
プロジェクトが興ったみたいだけど、まだモノは出来てない。どうなるのかな

[144 １４０ NG NG]

お返事ありがとう
完全に汎用的に使えるラッパクラス/アプリケーションを制作中です

ini ファイルで dll ごとに設定を与えようと考えています。
（　各dll のパス、API接頭語、各コマンドラインオプション、などなど　）

クラス構成はこうなる予定です
　　CDLL　　　　　dll ダイナミック・リンクをラップしたクラス
　　CArchiver　　CommonArchiverLibraryProject のAPIをラップしたクラス
　　　　　　　　　　 Unlha(...)、Tar(...)などの違いを吸収します

CDLLのラッピングは一応完成。
CArchiverはラッピングのみ完成。次はコマンドラインオプション吸収を実装予定。
（その前に、ini ファイル用のクラスを作る予定）

面倒ですね。
Noah に丸投げしたほうが良いかもしれませんね。




> 一応そこら辺の改善を含み、使いやすいアーカイバ関連のライブラリを作る
> プロジェクトが興ったみたいだけど、まだモノは出来てない。どうなるのかな

とても気になります。
メーリングリスト内で興ったのでしょうか？

[145 デフォルトの名無しさん NG NG]

>>144
これかと
ttp://pc2.2ch.net/test/read.cgi/software/1046607695/

あと、解凍のみならともかく圧縮まで扱うなら、iniに設定を持たせるのは
無謀かと。

・SFX作成（書庫→SFX化と直接SFX化の二通りある)
・暗号化、ソリッド、分割などのオプション機能
・tgz/tbzなど、圧縮時に拡張子が変わる時はどうするか
・ファイルリスト仕様の微妙な違い

など、仕様が異なるところがかなりあるので設定がかなり膨れ上がりそう。

[146 デフォルトの名無しさん NG NG]

ファイルを圧縮するプログラムを作りたいのですが、まずなにからはじめたらいいのでしょうか

[147 デフォルトの名無しさん NG NG]

>>146
まずは、ファイルをコピーするプログラムを作る。
このときに、ファイルの入出力などの取り扱いについて学ぶ。

次に、圧縮のアルゴリズムなどについて学ぶ。
それから、上記のコピープログラムに、圧縮と展開を組み込む。

[148 デフォルトの名無しさん NG NG]

>>146
データ圧縮ハンドブックを買ってくる。
ソースを(コピペじゃなくて自分でキーボード叩いて)全部うつす。
コンパイルして遊ぶ。

[149 デフォルトの名無しさん NG NG]

SPECintベンチマークにcompressが含まれてて、これはとっても
並列化しにくいんですけれども、gzipなら割と簡単に並列化できるんじゃ
ないかと思いました。

　i)１ブロック読んで、中の部分文字列をハッシュ表に登録
　ii)ブロック内の各位置からの最長一致を求める。
　iii)エントロピー符号化

という順でやれば、各ステップは並列にできるのじゃないでしょうか。
gzipだと、エントロピー符号化もブロックごとの静的ハフマンだし…
ただ、ii)では無駄な位置に対しても投機的に最長一致を探すことになりますが。
並列化できないのは、ビット列の出力ですが、この時間は大きくないでしょうし。

[150 デフォルトの名無しさん NG NG]

>>149
i) と ii) を分ける理由が分からん。
ハッシュ関数換えるってんなら話は別だが。

[151 デフォルトの名無しさん NG NG]

>>150
並列化したら、
後に出てきた部分文字列の方を先に処理することもありえますから、
その際に、前に出てきた文字列が未登録だと
うまく圧縮できません（逐次処理と結果が変わります）。

[152 デフォルトの名無しさん NG NG]

PPMやべー
PPMに惚れそう

[153 デフォルトの名無しさん NG NG]

その高速性はあたかも弾丸のようだ。

[154 デフォルトの名無しさん NG NG]

>>152
もう惚れ済みですが何か？
7-zip [ ttp://7-zip.org/ ] とか、
ppmd(1) [ ttp://packages.debian.org/unstable/utils/ppmd.html ] とか。

[155 デフォルトの名無しさん NG NG]

zip や lha　とかってbitごとに辞書化してるんですか？
それともbyteごとなんでしょうか。
よく見る解説ページでは"aaabcccddddff"とかって
アルファベットだったりと概念的なものばかりでよくわからんのですが…

[156 デフォルトの名無しさん NG NG]

>>155
一般に圧縮ではバイト（あるいはそれ以上の大きさ)が用いられる。
あと、圧縮の説明にアルファベットがよく使われるのは”見える”からだと思われ。

[157 155 NG NG]

なるほどー。
じゃあ何を判断にくぎってるんですか？たとえば
125 124 209 300 125 124 200 111
とかって画像データ があったとすると
125 124　が2つ
209　　　　が1つ
300　　　　が1つ
200 が１つ
111　　　　が１つ

ってのと
125 124 20　が2つ
9 300　　　 　が1つ
0 111

[158 155 NG NG]

(失礼しました。続きを)

125 124 20　が2つ
9 300　　　 　が1つ
0 111　　　　　が1つ
の二通りにできますよね。じっさいのところどうやってるんでしょうか？

[159 デフォルトの名無しさん NG NG]

>>158
その違いが辞書の違い、すなわち、手法の違い。
LZ'77, LZ'78 くらいでよいから、参考書で勉強すべし。

[160 155 NG NG]

なるほど。もちっと本読んで勉強します。
ありがとうございました

[161 デフォルトの名無しさん NG NG]

LZSSのソース（作者が使用してもよいと言ってる物）欲しいんですがどこにありますか？
へたれなのでアルゴリズムﾊﾟｸﾘたいのですが。

[162 デフォルトの名無しさん NG NG]

>>161
おまいは奥村先生の「最新アルゴリズム事典」を枕にして勉強しる。

[163 デフォルトの名無しさん NG NG]

>>161
おまいは奥村先生に足を向けて寝ていはいけない。
http://www.matsusaka-u.ac.jp/%7Eokumura/algo/

[164 デフォルトの名無しさん NG NG]

>>162-163
奥村先生のソースコードは落としましたがあれは本当にLZSSの基本実装みたいな形ですよね？
だもんで速度的にちょっといけてないかなーとへたれ心に思ってみてり。
因みにツリーを使わずハッシュを使うと特許に触れるんでしたっけ？

[165 デフォルトの名無しさん NG NG]

>>164
LHA, gzip はハッシュを使って実装されている。

つーか、へたれを自称する人は基本をおろそかにしてはいけない。
とりあえず、LHA か gzip のソースを読んでみてわからなかったら、
素直に奥村先生を拝むこと。

[166 デフォルトの名無しさん NG NG]

>>161
これはどうだ？
http://www.ingnet.or.jp/~kojif/mu/comp/

[167 161 NG NG]

>>164
へたれだからこそｺﾋﾟﾍﾟなんだよ!
ハッシュ化するのは問題ないんですね。少し勉強して奥村先生コードに手を加えるか…。

>>166
確か最初に落としたけど研究目的以外はx(ﾒｯ)なんすﾖ。

[168 デフォルトの名無しさん NG NG]

>>164
LZSS系列だとツリー使っても特許の地雷だらけなのよね。
ハッシュ使っても地雷だらけ、ってのは変わらんけど。

[169 デフォルトの名無しさん NG NG]

>>168
特許の有効期限、いつになったら切れるんだ？

[170 デフォルトの名無しさん NG NG]

特許発効から20年ほど

[171 デフォルトの名無しさん NG NG]

MACのsit形式の仕様書はいつになったら公開されるんですか
不便でしようがありませんよ！

どこかに解析資料とかないでしょうか

[172 デフォルトの名無しさん NG NG]

>>171
こんなのとか。
ttp://www.stuffit.com/win/sdk/index.html

[173 デフォルトの名無しさん NG NG]

>20年ほど

長いよねぇ

[174 デフォルトの名無しさん NG NG]

>>172
ありがとう

登録制なのか…やだなぁ

[175 デフォルトの名無しさん NG NG]

ttp://www.cmagazine.jp/books/assyuku/index.html

この本とかはどうだろ？

[176 Ｃ+++ NG NG]

>>10
　激しくﾜﾛﾀ（笑）。

[177 デフォルトの名無しさん NG NG]

>>171
ttp://www.speakeasy.org/~russotto/arseniccomp.html

[178 デフォルトの名無しさん NG NG]

圧縮といえば、2年くらい前にすげー大ボラ吹いた奴が
海外にいなかったっけ？

[179 デフォルトの名無しさん NG NG]

>>178
1/100に圧縮できるってヤツか?

[180 デフォルトの名無しさん NG NG]

あげ

[181 デフォルトの名無しさん NG NG]

おまえらエントロピーくらいわかってるよな？

[182 デフォルトの名無しさん NG NG]

圧縮・燃焼について語れ

[183 デフォルトの名無しさん NG NG]

ロータリーエンジンはすごいって事話す事になったんですか？

[184 デフォルトの名無しさん NG NG]

ロリータエンジン

[185 デフォルトの名無しさん NG NG]

LZ系で小さいやつ
(コードサイズが小さくて、
符号化・復号化だけで余計な機能がなく、
復号が速いやつ)
ない？
アプリにこっそり組み込んで使いたいんだが。

[186 デフォルトの名無しさん NG NG]

>>178-179
ZeoSyncｷﾀｰｗ
懐かしいな。

[187 デフォルトの名無しさん NG NG]

>>185
奥村LZSSでもつかっとけ

[188 デフォルトの名無しさん NG NG]

THCompが最強

[189 デフォルトの名無しさん NG NG]

>>185
MS-COMPRESSを呼び出すのが簡単かつ確実

[190 デフォルトの名無しさん NG NG]

>>189
WinでもAIXでも使えるのをおながいします。

[191 185 NG NG]

昔の7行スレのやつ使うことにしました。
ちょっと遅いけどすげー小さいので。
ちなみに190は偽物です。

[192 デフォルトの名無しさん NG NG]

む、7行であったのか

[193 デフォルトの名無しさん NG NG]

>>192
7行のだと、Huffman, rangecoder, LZ77系, RLEなら、
それぞれ2つ以上の実装が出ていたはず。
LZ78とかBPEとかもあった。

[194 デフォルトの名無しさん NG NG]

>>192
これかな？
http://www.isl.cs.gunma-u.ac.jp/~shingo/make/7line/7line.html

[195 デフォルトの名無しさん NG NG]

違う

[196 デフォルトの名無しさん NG NG]

数MのXMLを短時間で圧縮解凍したいんですが、圧縮率とパフォーマンスのバランス
の取れた圧縮アルゴリズムってなんでしょう？

XML → 無駄なコード削除 → ブロックソーティング → MFT → ランレングス

　でやってみたんですが、圧縮率は満足なもののブロックソーティングが遅すぎて
使えませんでした。もちろん、高速化は可能だと思うのですが…

[197 デフォルトの名無しさん NG NG]

>>196
まずbzip2で試してみて、それでも遅ければブロックソートは向いてない、
十分な速度ならブロックソートの高速化が甘いかと。

ブロックソートの高速化についてはこちらなど
M.Hiroi's Home Page　ttp://www.geocities.co.jp/SiliconValley-Oakland/1680/
white page　ttp://homepage3.nifty.com/wpage/

[198 じんばん NG NG]

すいません、javaで圧縮・解凍プログラムの作成を試みているのですが、
どこか良いサイトあれば教えてください。
jarでなくてgzipの話です、念のため。

[199 デフォルトの名無しさん NG NG]

そういったアルゴリズム関連の場合、
いきなりJavaソースを探すのではなく、
C/C++をJavaに翻訳することを薦める。

[200 じんばん NG NG]

>199
javaには、圧縮関連のインタフェースが提供されているはずなのですが。。
圧縮クラスだとか圧縮メソッドのような。。

[201 デフォルトの名無しさん NG NG]

>>198

> 標準的な ZIP ファイル形式および ＧＺＩＰ ファイル形式を読み取ったり、書き出したりするためのクラスを提供します。

http://java.sun.com/j2se/1.4/ja/docs/ja/api/java/util/zip/package-summary.html