最強の圧縮アルゴリズムを語ろう
レス数が950を超えています。1000を超えると書き込みができなくなります。
0001デフォルトの名無しさん
2006/04/26(水) 11:57:532bitがいい成績だったら2bitをひとかたまりにして
2ブロック、3ブロック、5ブロックで頻度をとる。
これを繰り返す。
0002デフォルトの名無しさん
2006/04/26(水) 11:59:11ラ ン レ ン グ ス 圧 縮 法 最 強
VB厨にもマジ簡単だからおすすめ
0003デフォルトの名無しさん
2006/04/26(水) 12:00:330004デフォルトの名無しさん
2006/04/26(水) 12:07:190005>>1 ハフマン・LZ77から勉強してこい
2006/04/26(水) 12:10:20r;ァ'N;:::::::::::::,ィ/ >::::::::::ヽ
. 〃 ヽル1'´ ∠:::::::::::::::::i
i′ ___, - ,. = -一  ̄l:::::::::::::::l
. ! , -==、´r' l::::::/,ニ.ヽ
l _,, -‐''二ゝ l::::l f゙ヽ |、 ここはお前の日記帳じゃねえんだ
レー-- 、ヽヾニ-ァ,ニ;=、_ !:::l ) } ト
ヾ¨'7"ry、` ー゙='ニ,,,` }::ヽ(ノ 「ハレ晴レユカイ」でも聞いてろ
:ーゝヽ、 !´ " ̄ 'l,;;;;,,,.、 ,i:::::::ミ
::::::::::::::::ヽ.-‐ ト、 r'_{ __)`ニゝ、 ,,iリ::::::::ミ
::::::::::::::::::::Vi/l:::V'´;ッ`ニ´ー-ッ-,、:::::`"::::::::::::::;゙ , な!
:::::::::::::::::::::::::N. ゙、::::ヾ,.`二ニ´∠,,.i::::::::::::::::::::///
:::::::::::::::::::::::::::::l ヽ;:::::::::::::::::::::::::::::::::::::::::::/ /
::::::::::::::::::::::::::::::! :|.\;::::::::::::::::::::::::::::::/ /
■5/10発売 涼宮ハルヒの憂鬱ED 「ハレ晴レユカイ」
http://www.youtube.com/watch?v=zuQiovLQc_s&search=haruhi
0006デフォルトの名無しさん
2006/04/26(水) 12:14:58俺が考えたのは2ビット(1ビットずらしも考える)、
3ビット(1ビット、2ビットずらしも考える)単位で出現頻度を調べて
頻度の高い単語を一纏めにしようというわけだ。
0007デフォルトの名無しさん
2006/04/26(水) 12:21:39プログラム作ってからこい
0008デフォルトの名無しさん
2006/04/26(水) 12:30:550009デフォルトの名無しさん
2006/04/26(水) 12:36:552×2 , 2×3 , 2×2×2で実現されるからだ。
たとえば英語(ASCIIコード)ならば
2ビット→2ブロック→2ブロックがいい頻度を出すだろう。
0010デフォルトの名無しさん
2006/04/26(水) 12:38:20纏めたはいいけど、複合化するときはどうするの。
0011デフォルトの名無しさん
2006/04/26(水) 12:39:352,3,5,7ブロックずつで統計を取る。
最後は、既存の圧縮プログラムで圧縮するんだ。
0012デフォルトの名無しさん
2006/04/26(水) 12:41:35単語辞書を圧縮したもののはじめに記録する。
0013デフォルトの名無しさん
2006/04/26(水) 12:43:04単なる糞コテなのかよ!それは
0014デフォルトの名無しさん
2006/04/26(水) 12:47:57a=1101と置換すれば
(1101)011(1101)(1101)01(1101) = a011aa01aとなり簡単になる。
こういう事をやりたいんだ。
0015デフォルトの名無しさん
2006/04/26(水) 12:49:020016デフォルトの名無しさん
2006/04/26(水) 12:50:10その辺はなんとか考えよう。
0017デフォルトの名無しさん
2006/04/26(水) 12:51:430018デフォルトの名無しさん
2006/04/26(水) 12:58:15しかし単語の抽出法は工夫の余地があるはずだ!
0019デフォルトの名無しさん
2006/04/26(水) 12:59:380020デフォルトの名無しさん
2006/04/26(水) 13:02:33頻出単語を少ないbitで表現できれば文字列長が小さくなるだろが!
0021デフォルトの名無しさん
2006/04/26(水) 13:03:480022デフォルトの名無しさん
2006/04/26(水) 13:11:50しかし、他人を納得させるには、「実物」を見せないとだめだ。
それをしない限り、オナニーと呼ばれても仕方ないぞ。
0023デフォルトの名無しさん
2006/04/26(水) 13:36:57一般的にはどのようなアルゴリズムがあるんだ。知ってるか?
0024デフォルトの名無しさん
2006/04/26(水) 13:56:400025デフォルトの名無しさん
2006/04/26(水) 14:03:26検索エンジンとか宇宙人語とか暗号解読とかに役立ちそうだな。
0026デフォルトの名無しさん
2006/04/26(水) 17:27:16が与えられたときに
a=1101010111001010101
とすれば
1101010111001010101 → a
と簡略化される
0027デフォルトの名無しさん
2006/04/26(水) 19:22:230028デフォルトの名無しさん
2006/04/26(水) 20:22:37bit単位の(汎用的な)圧縮アルゴリズムに限界があるのは明らかなんだから。
0029デフォルトの名無しさん
2006/04/26(水) 20:25:16そしたら辞書に本体が必要じゃないか。あまりに大きくしすぎても駄目だと言うことだな。
最低2回は繰り返さないと。
0030デフォルトの名無しさん
2006/04/26(水) 20:28:060031デフォルトの名無しさん
2006/04/26(水) 20:38:41パソコンが2進数にもとずくんだからそれは無理だ。
現在での最強は?
0032デフォルトの名無しさん
2006/04/26(水) 20:46:390033デフォルトの名無しさん
2006/04/26(水) 20:48:040034デフォルトの名無しさん
2006/04/26(水) 20:52:130035デフォルトの名無しさん
2006/04/26(水) 20:54:46じゃぁその文字列aそのものはどうやって保存するんだい?
0036デフォルトの名無しさん
2006/04/26(水) 20:59:43初に単語数を16bitで記録する。次に単語長を16bitで記録する。
次に単語を記録する。以下、単語数になるまで繰り返し。
0037デフォルトの名無しさん
2006/04/26(水) 21:03:15単語長 x=5 単語 y=11000
単語長 x'=2 単語 y'=01
単語長 x"=6 単語 y"=101011
zxyx'y'x"y"(圧縮データ)
003837
2006/04/26(水) 21:08:040039デフォルトの名無しさん
2006/04/26(水) 21:08:23それって最初のデータ13bit(2バイト以下)だよね。
明らかに増えてない?
004037
2006/04/26(水) 21:10:170041デフォルトの名無しさん
2006/04/26(水) 21:11:26004237
2006/04/26(水) 21:11:54004337
2006/04/26(水) 21:12:40没に10メガとかでもいいけど。
0044デフォルトの名無しさん
2006/04/26(水) 21:14:28それ以前に最適な辞書を作るアルゴリズムをどうやって作るのかと。
0045デフォルトの名無しさん
2006/04/26(水) 21:23:24「最適な辞書を作るアルゴリズム」を作るアルゴリズムを作れば?
0046デフォルトの名無しさん
2006/04/26(水) 21:30:39頑張って!
影から応援するから
0047デフォルトの名無しさん
2006/04/26(水) 21:46:24少なくとも単語は2bit以上だから2bitから調査しようぜ。
それで00がかなり多いとなったら次に0がくる確率がかなり多いとかなって。
0048デフォルトの名無しさん
2006/04/26(水) 21:48:370049デフォルトの名無しさん
2006/04/26(水) 22:01:47途中の01や111をどう扱うかによって変わるかと。
0050デフォルトの名無しさん
2006/04/26(水) 22:03:58どうやって作るの?
まさかとは思うが、それを作るために作るためのアルゴリズムをつくろうとか言い出す始末じゃ困るぞ。
0051デフォルトの名無しさん
2006/04/26(水) 22:18:22「どんなサイズのファイルでも50%に圧縮するアルゴリズムを考え付いた」といって
投資を集めていたやつがいたそうだ。しかもそのアルゴリズムは可逆なのだそうだ。
この詐欺師の事件の顛末、誰か知らないか?
0052デフォルトの名無しさん
2006/04/26(水) 22:58:37まず、詳しい圧縮・伸張方法を説明して、且つその方法が圧縮率や処理速度の点で良い結果を出せそうだ、ということをきっちり説明してくれ。
0053デフォルトの名無しさん
2006/04/27(木) 00:30:1710%じゃなかったっけ?
そういえばどうなったんだろうな。
0054デフォルトの名無しさん
2006/04/27(木) 01:12:42辞書部分 + 圧縮部分のサイズがもっとも小さくなるような
アルゴリズムをおまいらが開発するすれ。
0055デフォルトの名無しさん
2006/04/27(木) 01:47:10そう思ってた時期が僕にもありました
0056デフォルトの名無しさん
2006/04/27(木) 01:53:480057デフォルトの名無しさん
2006/04/27(木) 02:01:050058デフォルトの名無しさん
2006/04/27(木) 02:14:250059デフォルトの名無しさん
2006/04/27(木) 02:16:40物理ノイズも50%に圧縮するってか。
そりゃ騙されたほうが阿呆ですなあ。
0060デフォルトの名無しさん
2006/04/27(木) 02:40:562ブロック限定で辞書作るアルゴリズムだな。
任意のブロックで単語を見つけ出せればいいんだが。
0061デフォルトの名無しさん
2006/04/27(木) 06:27:03扱う方法などについて詳しく載っているサイトってありますか?
ググろうとしても「zip 仕様」とか「zip ソース」だとかで検索してもぜんぜんわからんとです・・・
0062デフォルトの名無しさん
2006/04/27(木) 06:39:13DLLをつかう。
http://www.csdinc.co.jp/archiver/lib/main.html
0063デフォルトの名無しさん
2006/04/27(木) 06:42:35手法について調べたいんだけど俺のぐぐりかたがヘタクソでみつからない、ていうお話です
0064デフォルトの名無しさん
2006/04/27(木) 06:47:37DLL作成をぐぐる。
0065デフォルトの名無しさん
2006/04/27(木) 06:49:280066デフォルトの名無しさん
2006/04/27(木) 06:54:47>>65 ええ、そんなかんじです
0067デフォルトの名無しさん
2006/04/27(木) 07:10:390068デフォルトの名無しさん
2006/04/27(木) 14:06:110069デフォルトの名無しさん
2006/04/27(木) 15:42:59かぶらせない方策を考えてない中学生。(発想力が)
>>61
pkzipとかで日本語以外もぐぐりゃいいんじゃないかな。
0070デフォルトの名無しさん
2006/04/27(木) 16:14:04なんだと。そんなことは簡単なことだ。
算術圧縮とか、ハフマンのやり方にならえばいいんだ。
ようするに2とおりの表し方がないようにすればいい。
0071デフォルトの名無しさん
2006/04/27(木) 16:49:24君らこの辺とかちゃんと読んでる?
↓
http://homepage3.nifty.com/DO/algorithm.htm の人のWX法。
ビット単位でやるとかなりコストかかりそうだけど、速度的なチューニングを
考えなければほぼそのまま適用できるでそ。
0072デフォルトの名無しさん
2006/04/27(木) 19:29:34>>18でちゃんと触れられてるぞ。
おまえこそちゃんと読めよw
0073デフォルトの名無しさん
2006/04/27(木) 20:06:17ipa でやってた↑のアルゴリズムとか読んでるのって話だよ。
誰一人読んでるようには見えないぞ。
0074デフォルトの名無しさん
2006/04/27(木) 20:39:00> 誰一人読んでるようには見えないぞ。
人が読んでいる間にそういうこと言うかね
0075デフォルトの名無しさん
2006/04/28(金) 10:39:43(1) 一語ずつ削る
11001110
1001110
001110
01110
1110
110
10
(2)ソートする
001110
01110
(10)
(10)01110
(110)
(110)01110
1110
単語(10)(110)(11)が出現していることが判明する。
0076デフォルトの名無しさん
2006/04/28(金) 10:41:320077デフォルトの名無しさん
2006/04/28(金) 10:43:3916bit(16語)まででいいか。
0078デフォルトの名無しさん
2006/04/28(金) 10:50:08しかし今おもったんだがソートする必要はない気がする。
なぜならば11001110が与えられたとき
(単語は2から4bitのまでだと仮定する)
配列を用意して3=(11)番目、7=(110)番目、12=(1100)番目の配列に1を足す。
次に2=(10)番目、4=(100)番目、5=(1001)番目の配列に1を足す
とやればいいんだ。
0079デフォルトの名無しさん
2006/04/28(金) 10:51:350080デフォルトの名無しさん
2006/04/28(金) 10:54:19単語が長いほど出現比率は下がるが。
長い方を採用するか、短くて量で勝負かだ。
0081デフォルトの名無しさん
2006/04/28(金) 10:57:320001と001と01が同じ配列に収められてしまう。
空を0、0を1、1を2に変換して記録しよう。
0082デフォルトの名無しさん
2006/04/28(金) 11:04:013の17乗は約2^27だから17bitまでの単語は登録できるな。
0083デフォルトの名無しさん
2006/04/28(金) 11:08:39到底zipやrarに太刀打ちできないからw
0084デフォルトの名無しさん
2006/04/28(金) 12:24:2871 のURLの人は、単語の前後の文字のエントロピを見て単語候補を絞り込んでる。
( 0110110 の中の "11" のように)前後が何時も同じときには「単語らしさ」を下げる、と。
0085デフォルトの名無しさん
2006/04/28(金) 13:49:06テキストならば8bit×5語=40bit、16bit×5語=80bitくらいだろう。
バイナリなら20bit程度なんだろうか。
この程度なら82の様にハッシュが使える。
0086デフォルトの名無しさん
2006/04/28(金) 14:06:04前提条件を明確にせず、延々と馬鹿を晒し続ける奴ばっかりなのは何故なんだ?
0087デフォルトの名無しさん
2006/04/28(金) 14:15:13戦う前から尻尾を振るのが負け犬。
戦って負けてキャンと鳴いてからが勝負さ
0088デフォルトの名無しさん
2006/04/28(金) 14:35:410089デフォルトの名無しさん
2006/04/28(金) 14:48:03発表する場もないし、ひとりでひっそりと使ってる。時間軸圧縮も作って、やっぱり動画プログラムでこっそり使ってる。
0090デフォルトの名無しさん
2006/04/28(金) 15:10:24最強の称号を手に出来るのは
汎用性のある可逆圧縮だ!
データ種類なんて関係ない。
どうせZIPやLHAより小さくなるって言ってもたかが知れてるんだし
互換性・普及度が大事だと思うけどな
0092デフォルトの名無しさん
2006/04/28(金) 15:53:47ttp://thcomp.org/~pen/pfyp/thcomp/THcomp_log.txt
0093デフォルトの名無しさん
2006/04/28(金) 16:01:43出た!THcomp!この手のスレには必ず出てくるな。
0094デフォルトの名無しさん
2006/04/28(金) 16:06:580095デフォルトの名無しさん
2006/04/28(金) 16:12:39たとえば
http://www.google.co.jp/maps?f=q&hl=ja&t=k&om=1&ll=34.944347,134.427681&spn=0.085131,0.113297
0096デフォルトの名無しさん
2006/04/28(金) 16:16:25だからTHcompだってば。
そろそろ8バイトくらい行ってるかなw
0097デフォルトの名無しさん
2006/04/28(金) 17:45:25その数は、有限だが計算機により計算する事が出来ない。
しかし、私達はその数を単に一文字で表現する事が出来る。 Ω と
0098デフォルトの名無しさん
2006/04/28(金) 18:45:580099デフォルトの名無しさん
2006/04/28(金) 23:51:3816bitだと16語どころか半角で2語しか入らないような。
0100デフォルトの名無しさん
2006/04/29(土) 03:39:310101デフォルトの名無しさん
2006/04/29(土) 03:41:030102デフォルトの名無しさん
2006/04/29(土) 03:42:560103デフォルトの名無しさん
2006/04/29(土) 13:46:400104デフォルトの名無しさん
2006/04/29(土) 17:31:220105デフォルトの名無しさん
2006/04/29(土) 17:53:060106デフォルトの名無しさん
2006/04/29(土) 18:05:160107デフォルトの名無しさん
2006/04/29(土) 20:46:380108デフォルトの名無しさん
2006/04/29(土) 20:47:28キセノンって何
0109デフォルトの名無しさん
2006/04/29(土) 20:50:402進数で16bitまでの単語の頻度を調べる。
5bitの単語が100回現れるとする。その単語を1bitに変換出来たとすると
500bitを100bitに縮められる。400bit分小さくできた。
同じようにすべての単語についてなんbit縮められるか調べる。
もっとも縮められる単語を2とおく。
すると10121102221021などとなる。
今度は3進数で頻度を調べる。縮められなくなるまで繰り返す。
誰が実装してくれるヤシいない?
0110デフォルトの名無しさん
2006/04/29(土) 20:52:29それは2進数に直した時にファイルサイズが膨れそう。
0111デフォルトの名無しさん
2006/04/29(土) 21:01:51それ以前に最初同一データに対して13万通り以上も調べるとなると相当時間がかかる。
あと、縮められなくなるって言うのは同一パターンがまったく含まれない時だけで、
n進数のnにあたる部分が随分大きい時になると思うのだが。
縮める前の文字列を格納するとなると色々附属情報が着いて来てややこしくなるので、
2進数→3進数→4進数→4進数を展開して2進数
という手順を一セットにしてファイルに書き出すのが妥当かと。
・・・と書いているうちに作りたくなったり。
0112デフォルトの名無しさん
2006/04/29(土) 21:10:0878-82を参考にしてくだされ。ハッシュを使うと簡単かと。
0113111
2006/04/29(土) 22:08:10あとは3進数を圧縮して4進数にするのと、4進数を2進数に展開して、そいつを8こ組み合わせてファイルに書き出す。
思ったより面倒^^;
0114・∀・)っ-○●◎
2006/04/29(土) 22:10:260116デフラグさん ◆WaDYW8eWxU
2006/04/29(土) 22:16:02/[_]ヽ
| |
234→うがざざすだでななにににののほよわわんん倒単圧数数数的簡進進進
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
0117111
2006/04/29(土) 22:19:272進数の検索をテストしているのだが、とてもじゃないが16ビットまで調べると時間食いすぎで効率悪い。
コードが悪いのかとも思うが。
備考
8ビットまで→約3分
16ビットまで→約42分
CPU:ペンティアム4 3.0GHz
0118111
2006/04/29(土) 22:24:390119復号してミナー(1/2) ◆fBLOhapji6
2006/04/29(土) 23:01:10m~}]:rtwdycl|EIJkDByL>EQ={Bu~B<j7CzVX&b%3RO6#t*\HQZqzC)Z3B,7R!!p
l`]xx]f~4\FwfyD\:mr];Ne=m2081?ERp0`TLwYHpzH):yKRhrrs\V%N|h'IV3Do
S|'!%Q'Z!S`q458DrvG5&PLds<9Ml9pxdejH|-\wuFD~SK?`\P~=ep+ij^aNgT7v
woYyYZ+R^\_k&7~<$HEDe?O>Fd~ey:nw{J>|M-f}:T>I@{ZK^O`f:5+\Rlu5~U?\
~Swl#^m?8cmvx2t@{3ldz6D|w#yqn=[pwY&}~UC}3Iu~6bS\31kz%*z#o:?dsJqi
u{Yr=/}){uXu`xiYd>L\Wo3}45fKF]mNP9"u?^sD|`Xq2hyv*Q7\{Zk~xeegkd}c
>~[yN,#fj=*`@5m9yel?b|^Gh/fuO1d}5~~SpWp"+w*VDS@n<ib@:~;}h[VQW0Bd
;yaGS7\^4<qkkx|e.@kloEd-lC@D9fvakkAucOt558+x~L:rkdSs\8\}nPS{sn_b
_]l@~y_J-3>#X({^1[9ox<"3u<|eL/(j&dRl^2~ixGwz#O|?m.d5fz\`uZ1\4q=)
c25My|[f7y1{]>FUF9R=~]Kv..rO~TYt3Dw]Zc},}zZm|x{_$=Feo55(D}61Wm-s
FYQp`E^]b~~to.IObF.QQC~A3xZEsDb;|x^]&y=i.~`JVx/xI~rathp|&xnLw@:0
u:LR*f/6_7^E/L5paC}uyJoUM"i7~VbWwFGN]gKJcWyCH!K}vt}/39Lm.ysW}LNN
q[w+4]j[*o`eU!j:2h[0|zF}k^_~r|/W/"}N(YUvnA{_vPj[V\W3:z~YMk;]X]~:
{=HW+g~f5TVmhd,mIjbk\ZP`u~ik{e^ZaQdog}l8~Us%?<T~cm|nJk'@dE!ot_XK
}vz#l\~U[X{EkUkM~xEb(v{>KY'0VHen\a8~Poz~q~^^w&nGr?-<\gx0kIX&5%~R
TC(\f<<ADM]TucX%C*h~u]g^u\bY6iip|`h[qVKVs|TuCD^SN(kFn[%?{]Wwkp6^
[~Hsua3A1Uuen|-;7n,~p<&HF_vy;+x.D:8'ouudz~9;9df5+qw},Agv<]f36]ZZ
N2Yrhmv?6|L1x^&x'mtTk|2J%tyh_b@#uvW`'P~P~A}+N8#Fx~2QxHVj3lP\|JnT
xgj^i[6{0`=Z4vwWitY&k\bKaN^UL1}/o~2StK?sG~)zjX5g;8fy7(RT`UtxU`Y|
0120復号してミナー(2/2) ◆fBLOhapji6
2006/04/29(土) 23:02:34Tu~@53t6"k:OK&zQTFgLPqZnNhL[G@dKIRzw-1"k~!uw8u9J!\k~~RCG%mcHb1cy
g2J}Vq;nVn=yU|2WOOQz}L*8@n5+9pfWGYr-\lNOF|8IEqe>~o\pz5-|f|c+:C2&
D3Fw|ty]D\]Fc~(lSV}Q$8@|2@]*V_H~P|M=mdS|#A'5)QAdE#B*^~k]%'p[fvu3
N+"jr+}l]G8Ss?n<5!}tuI=uhhnf|6#{M7|k6^N=V?T7<{,"(s;'Sw+iD3Cd/ms8
(3~NO~yvwamsveg_[-^yr=8?URHIsc]Ri8.tYj`q.}`'|<zaM~d[0b3>o-I{{bc]
G9}te,Tqwe*xr-VBKlPv]Y%N}JDD'//J`3_tf~Hv3]q;~qjJ!>u~zc$tt7ZdyE\V
A}R~UyThXw^g~u2t#X,%>b}Pm[sB+N{r>*RE2|_cv,xA1Zs?8v_=0*{'R9v<[fII
.43~[?vZRUX`d;YSz0'y}}q9bx?2st`44`-*{0+Ur&rkb3oU}*\(,xyM={cZ$~$a
VwL*ahfhGe/s}1EwrtjW3"|g*[^0S):iu[;^Q1L;ka?[vY^J};*hIM5x$MO-pAj^
@AEr6BR**<=,Cz}n&<v~bWQARQ{h@[ljUht-lk~y}Q9qmSu~zSPC/>6yBggo(1:~
~4XsRGnf:h:Ka.R|fVx{zpWiq@eV~d2h^x,ZV|fJW^TGm7q|Ua{%*Pz6{NoY7\-L
[n21;r0G&UMxgFs.-mPd.g|<O<wRv+9OhfDAR`9lS*|o~BI{1N={3miyj~lAweiE
7BX%Zshu8Z2=7t;#`:kuTI-zS,Dahyv_gDy=Ke?QBy?mK-<kx>jfVJ}mkd~mxJu~
VL9Tv^j~C|a@sg!!!
0121ヒント ◆fBLOhapji6
2006/04/29(土) 23:04:54・元はbzip2で圧縮したファイル
・圧縮と言うよりは符号化だな
・デフラグさん上等
0122デフォルトの名無しさん
2006/04/29(土) 23:06:53ここは最強の圧縮のアルゴリズムについて話し合う場であり、少なくとも私は暗号化のアルゴリズムについて話し合うつもりはありません。
0124デフォルトの名無しさん
2006/04/30(日) 00:17:442進→3進変換でさらにしゃれにならん時間かかりそうだし
2進用の辞書、3進用の辞書、4進用の辞書て具合に辞書だらけになって
あまり縮まなそうだな
ところでこのスレの圧縮アルゴリズムってユニバーサル符号化の方だよな?
0125111
2006/04/30(日) 01:18:58えぇ。もう16bitまで調べてたらしゃれにもならない時間がかかりましたよ。
10キロバイト引っ掻き回して1時間半くらいでしたかねぇ。
0126124
2006/04/30(日) 01:55:39ていうか2進だけ考えれば可変語長のHuffman符号化じゃんか
となると3進以上に変換するのは無意味だな。
たぶん2進→3進の時点で符号表の分だけサイズ増える
おとなしく算術符号なりRange Coderなり使え
0127124
2006/04/30(日) 02:07:30上にも書いたが>>111のやってることは可変語長のHuffman符号化と変わらん
2進の時点でエントロピー程度まで縮まるので3進以降は全く意味がない
可変語長だからユニバーサル符号化+エントロピー符号化と同程度まで
縮まる可能性はあるが時間がかかりすぎる上に動的符号化に対応できそうにないから
bzip2とか7zipより縮まるとは思えない
0128デフォルトの名無しさん
2006/04/30(日) 03:49:38http://ja.wikipedia.org/wiki/BPE
0129デフォルトの名無しさん
2006/04/30(日) 03:52:48一回目の圧縮で辞書に登録するのは最も縮まる2進数1語のみだよ。
0130デフォルトの名無しさん
2006/04/30(日) 04:01:57次に3進数のビット列で最も縮まる単語が10101(2が出てこない!)
だっとするとこれを3進数として辞書に登録しなければならず
回数を重ねるごとに辞書長は長くなる。
n : 繰り返した回数。
n | (n+1)進数の単語 | n進数の単語 | ・・ | 2進数の単語 | (n+2)進数による圧縮データ
0131デフォルトの名無しさん
2006/04/30(日) 04:59:14例えば、00000だと統計的には単語00が4回出てくるが、実際圧縮してみると
220や022になる。重複している部分があるため2つしか出てこない。
0132デフォルトの名無しさん
2006/04/30(日) 06:02:1216bitなのはハッシュテーブルにそのまま登録できるからという理由なんです。
10Kバイト=80000語だとその16倍(単語長)くらいの繰り返しで回数求められないですか。
2バイトの配列を(3の16乗)個用意しておけばbit列をそのままハッシュとして登録できる。
0133デフォルトの名無しさん
2006/04/30(日) 12:40:08って軽く30MB超えるんだけど
0134デフォルトの名無しさん
2006/04/30(日) 15:15:2841メガくらいか。
0135111
2006/04/30(日) 17:29:16開発停止しまつ。
0136デフォルトの名無しさん
2006/04/30(日) 17:52:31減るまで繰り返すんだから。
0137デフォルトの名無しさん
2006/04/30(日) 17:57:43どんなに続けようが増えるだけのこともある。
0138デフォルトの名無しさん
2006/04/30(日) 18:01:05圧縮の定義から。
0139デフォルトの名無しさん
2006/04/30(日) 18:19:00非圧縮にした所でやはりヘッダをつけざるを得ないし。
0140デフォルトの名無しさん
2006/05/01(月) 04:30:23圧縮ファイルの書式のことではないんだよ。>>109で縮まらなくなるまで
続けるといってるだろ。一回目で縮まらなければ何もしないんだよ。
0141デフォルトの名無しさん
2006/05/02(火) 00:15:04解凍ソフトと圧縮ソフトで同じテーブルを参照してればよい希ガス
と、暗号素人の俺が言ってみる。
0142111
2006/05/02(火) 01:38:47辞書を外部に持ったらデータファイル1バイトにでも圧縮できるさ。
じゃぁその外部辞書ファイルはどうやって圧縮するのかって言う話。
そして、同じテーブルを参照する必要があるなら別なテーブルも勿論あるわけで。
そのアドレスを圧縮後のデータファイルの内容にするとしたら、勿論アドレスが重なってはいけない(同じアドレスで違うデータが取り出せてはいけない)為、
ファイルの内容と同じになってしまう。
と言う事はヘッダとかが付く分重くなって終了。
とファイル暗号化ソフトを作った事がある俺が言ってみる。
0143デフォルトの名無しさん
2006/05/02(火) 03:53:16そういうコンセプトの圧縮アルゴリズムはすでにある。
辞書が固定でしかも巨大になってしまうので汎用的ではないが、かなりの高圧縮率を期待できる。
0144デフォルトの名無しさん
2006/05/02(火) 16:57:100145デフォルトの名無しさん
2006/05/02(火) 18:59:100146デフォルトの名無しさん
2006/05/02(火) 19:23:430147デフォルトの名無しさん
2006/05/02(火) 22:26:530148デフォルトの名無しさん
2006/05/02(火) 23:19:47>辞書を外部に持ったらデータファイル1バイトにでも圧縮できるさ。
うん?汎用性なくしてどうすんの?
>じゃぁその外部辞書ファイルはどうやって圧縮するのかって言う話。
する必要ないんじゃないの?
ちょっと思いつきで言いますよ。
例えば8bitで区切って見ていったときに、一度も出てこない数があったらそれを記録。
1ビットずつ2個書いて16ビットにして一致する部分を探し、見つけたら8bitに置換する。
複数あったらそれの分圧縮になる。
とかどうですか?
0149デフォルトの名無しさん
2006/05/02(火) 23:25:39これじゃあ漏れには理解できない。1ビットずつ2個書いたら普通2ビット。
0150デフォルトの名無しさん
2006/05/03(水) 00:55:1811001100にするってことですよ。
0151デフォルトの名無しさん
2006/05/03(水) 02:24:18それって劣化BPEじゃね?
0152デフォルトの名無しさん
2006/05/03(水) 16:51:461.輝度の情報を、基色と、それとの誤差に分解。
2.基色をランレングスとかで記録。
手動でシミュレートしてみましたが、どうやってみても圧縮前より容量が大きくなります。
本当にありがとうございました。
0153デフォルトの名無しさん
2006/05/03(水) 17:34:17そのツールを公開すれば神になれる。
0154152
2006/05/03(水) 17:44:25じゃあ拡張子をjpgにすれば金がワンサカ・・・。
0155デフォルトの名無しさん
2006/05/03(水) 17:58:160156デフォルトの名無しさん
2006/05/03(水) 19:02:22セキュリティ上のニーズがあるかも知れんな。
大きいものは小さく、小さいものは大きく。
すべてのファイルを10MBにするとか。
0157デフォルトの名無しさん
2006/05/03(水) 19:33:470158デフォルトの名無しさん
2006/05/03(水) 21:38:520159デフォルトの名無しさん
2006/05/03(水) 22:24:480160デフォルトの名無しさん
2006/05/03(水) 22:58:26俺が言った「辞書」って言うのは、元ファイルとまったく同等の物。
だから辞書一つにつき2つのファイルを1バイトに圧縮する事ができるが、辞書そのものがなければ復元不可。
0161デフォルトの名無しさん
2006/05/03(水) 23:26:37つまりTHCompもどきだな
0162デフォルトの名無しさん
2006/05/04(木) 00:02:13>>160
だから、汎用性なくしてどうすんの?
分かってて聞いてるのよ。
0163デフォルトの名無しさん
2006/05/04(木) 09:08:37thcompって、確か圧縮する(そもそも圧縮しないが)ファイルを削除→そのファイルを復元するとかいうネタがあったよね。
0164デフォルトの名無しさん
2006/05/04(木) 11:43:57・DOSの隠しファイルとして、
・WindowsNT系に存在するストリーム機能を利用して、
・数十〜250バイトのファイル内容を、ファイル名にすることで、
見た目のファイルサイズを0にするジョークプログラムがあったと思う
thcompは、アルカイックレコードを参照する >>142 みたいな話
だが、アルカイックレコードを参照するためのポインタが、
結局は元のファイルサイズ(あるいはエントロピーやレート)と同程度になるのは明らか
0165デフォルトの名無しさん
2006/05/04(木) 11:52:34そのデータを以下に示します。デコードはマウスでクリックするだけ!
"http://www.digitalpad.co.jp/~takechin/archives/susie347b.lzh"
0166デフォルトの名無しさん
2006/05/04(木) 12:20:511、どんなプログラムを使っても圧縮出来ない10Mバイトのデータを作成する それより短いコードのプログラムを作成せよ
0167デフォルトの名無しさん
2006/05/04(木) 12:22:54入力は行ってはいけない。 たとえば外部から乱数等の入力を行ってはいけない。
擬似乱数を発生させてもかまわまい。
0168デフォルトの名無しさん
2006/05/04(木) 16:08:540169デフォルトの名無しさん
2006/05/04(木) 16:29:42『構う』の受動態『かまわ』に、否定『まい』を付けた語句。
0170デフォルトの名無しさん
2006/05/04(木) 16:36:28後方分岐しか出来ないシンプルな命令体系のCPUをエミュレートするプログラムを作る
そのメモリ空間を擬似乱数により埋めておき、先頭より実行、
未定義命令を実行すれば終了とする。
ランダムに生成したプログラムは時々無限ループに陥り、永遠に未定義命令を実行しない事がありえるだろう。
後方分岐しか出来ないので、停止が判ったコードはそれ以後のメモリは何でもよい
よって、先頭より順に全ての組み合わせを生成するコードを書き
順に停止するかどうか調べてゆけば、停止するかどうあの確率を求める事が出来る。
確率は当然0より大きく1より小さいので
小数点以下をバイナリで順に出力させる。
このバイナリは圧縮出来るか?
0171デフォルトの名無しさん
2006/05/04(木) 16:47:09だからってC++のコードをbfに変換するヤツなんか作るなよ。
0172デフォルトの名無しさん
2006/05/04(木) 19:04:58読んだ雑誌の受け売りしかできんバカは黙ってろよ。
0173デフォルトの名無しさん
2006/05/11(木) 13:57:040174デフォルトの名無しさん
2006/05/11(木) 19:56:59aggwwwwwwwwwwwwwwwwwwwwwwwwwww
ワロタwwww
0175デフラグさん ◆WaDYW8eWxU
2006/05/11(木) 21:15:39/[_]
| |
aggw{31}タロ
0176デフォルトの名無しさん
2006/05/11(木) 21:28:450177デフォルトの名無しさん
2006/05/11(木) 21:31:59ワが消えてるよ
0178デフォルトの名無しさん
2006/05/11(木) 21:41:300179デフォルトの名無しさん
2006/05/11(木) 21:45:550180デフォルトの名無しさん
2006/05/11(木) 23:47:580181デフォルトの名無しさん
2006/05/12(金) 21:44:43不可{逆圧縮}
このように、装飾する区切りが違います。
0182デフォルトの名無しさん
2006/05/12(金) 21:45:130183デフォルトの名無しさん
2006/05/13(土) 00:35:000184デフォルトの名無しさん
2006/05/13(土) 20:05:44逆 に 不可 はつかんよ。
0185デフォルトの名無しさん
2006/05/13(土) 23:44:27じゃぁ所謂「出来なくはない」の類の[否定+逆]の文って一体?
0186185
2006/05/13(土) 23:46:010187デフォルトの名無しさん
2006/05/14(日) 00:04:09逆圧縮
ってナニ?
0188デフォルトの名無しさん
2006/05/14(日) 00:33:43そっちじゃなくて、
不可罰 罰する
不可能 能う
不可解 解する
不可侵 侵す
不可逆 逆?
という話。つまり言葉としておかしい。
0189デフォルトの名無しさん
2006/05/14(日) 03:53:490190デフォルトの名無しさん
2006/05/14(日) 04:00:030191デフォルトの名無しさん
2006/05/14(日) 04:04:070192デフォルトの名無しさん
2006/05/14(日) 09:41:05> かぎゃく 0 【可逆】
>
> 元に戻り得ること。
> ⇔不可逆
> 可逆圧縮 【かぎゃくあっしゅく】
>
> 〔lossless(data)compression〕
> 完全復元を前提とした手順で,データを圧縮する方式。アーカイバーなどで用いられる。ロスレス圧縮。
> →圧縮
> →非可逆圧縮
> →アーカイバー
どうしろと
0193デフォルトの名無しさん
2006/05/14(日) 16:50:09頭悪すぎ
0194デフォルトの名無しさん
2006/05/15(月) 09:09:01「可逆」というのが熟女
0195デフォルトの名無しさん
2006/05/15(月) 09:41:02おまえはどうなの?
0196デフォルトの名無しさん
2006/05/15(月) 09:43:530197デフォルトの名無しさん
2006/05/15(月) 09:48:260198デフォルトの名無しさん
2006/05/15(月) 12:51:300199デフォルトの名無しさん
2006/05/15(月) 12:58:31のが最強だろ。
0200デフォルトの名無しさん
2006/05/15(月) 22:18:130201デフォルトの名無しさん
2006/05/16(火) 05:47:320202デフォルトの名無しさん
2006/05/16(火) 20:39:55それじゃ「圧縮」ではなく「消滅」か「無視」の類。
0203デフラグさん ◆mRgSYalFkQ
2006/05/16(火) 21:55:27[゚д゚]ゝ デフラグツイデニアッシュクシマシタ
/[_]
| |
"{2}({53}){53}+{2},{5}-{2}.{6}/{112}0{252}1{179}2{123}3{63}4{72}5{116}6{94}7{36}8{39}9{37}:{107}=>{47}?AB{4}C{3}D{4}E{
2}HKMNOP{2}S{2}T{2}U{2}VW{4}Y[{57}]{57}a{59}b{10}c{7}d{4}e{56}f{2}g{60}h{6}i{14}j{3}k{3}l{4}m{4}n{4}o{10}p{9}r{3}s{57}t
{13}u{2}vw{4}xz{|{2}}~ュッアイカク{2}シ{3}タ{3}ツテ{2}トニハフホマラロ{2}ワ{2}ン゙{6}゚{2}、{33}。{53},・{7}:{109}?{9}!{3}_ゝ々ー{31}
〜({5}){5}〔〕{{2}}{2}「{7}」{7}『{3}』{3}【{3}】{3}+{3}◆→{4}⇔1{3}Mw{32}ぁあ{12}い{43}う{20}え{7}お{4}か{34}が{28}き{11}
ぎ{3}く{13}け{9}こ{7}ごさ{57}ざし{77}じ{5}す{39}ずせ{4}そ{17}た{25}だ{20}ち{2}っ{24}つ{11}て{36}で{22}と{28}ど{12}な{32}
に{37}ね{2}の{103}は{31}ば{6}ひべ{2}ま{20}み{5}め{3}も{16}ゃ{7}や{5}ゅゆよ{18}ら{11}り{21}る{52}れ{16}ろ{11}わ{6}を{
40}ん{60}ァ{12}ア{7}ィイ{29}ウエ{2}ォ{50}カ{8}キク{8}グ{7}コ{7}ゴ{2}サ{6}シ{2}ジス{5}ズ{8}セタ{7}ダッ{7}ツ{5}テデ{57}ト{5
9}ド{7}ナ{3}ニ{2}ネバ{11}ピ{2}フ{64}ブ{3}プ{7}ポマミ{2}ム{9}メ{2}モ{2}ヤュ{3}ョラ{8}リ{9}ル{72}レ{7}ロ{11}ワン{7}д悪圧{
28}以{3}謂違一{4}隠永円遠俺下{2}化何{2}可{26}火{2}課{2}画{3}解{3}開外拡確{3}割{4}完換間陥基{2}岐{2}機気記輝
擬{2}義{2}逆{23}求級強局金{3}句区空繰系{2}結月{7}見元{6}言{4}限{2}後{3}語{5}誤公功構稿{53}考行{5}合頃今差
最{3}在作{5}削雑参{2}使{2}子思{3}止{3}視誌事{3}似{2}時示辞{3}式実{3}弱{2}取手{4}受{2}修終十{2}重{2}縮{28}熟{3}
出{7}順{5}所書{4}女除小{4}消{2}照{2}称上場情飾{2}色{2}侵{2}神人水{12}数{5}性成{6}正生{3}績切先{2}前{55}然全{2
}素組相装像{2}足存体{2}態大{4}題{2}只単短知張調停{3}定{6}提程訂的点度{4}土{4}投{53}当{3}等{2}頭{3}動{2}同{2}
得読内日{60}入{2}寧能{4}売発罰{2}判汎否{3}非{6}頻{2}不{15}付部復{3}物分{8}文{2}聞{3}並変返補報宝{2}方{3}法{2
}萌本埋未{2}無{52}名{105}命{3}明滅木{19}黙目戻容{2}用{3}葉{2}来{6}乱{3}利率{2}了量力{3}類{2}令{3}劣録話{2}
0204デフォルトの名無しさん
2006/05/16(火) 22:27:26実はかなり適当?
0205デフォルトの名無しさん
2006/05/17(水) 03:44:22単に出現回数を数えただけじゃないか?しかも、不正確に
0206デフォルトの名無しさん
2006/05/17(水) 21:43:010207デフォルトの名無しさん
2006/05/18(木) 18:55:190208デフォルトの名無しさん
2006/05/18(木) 19:06:33「曖昧」と言うものはなかなか難しい。
0209デフォルトの名無しさん
2006/05/19(金) 14:10:01じゃあ漏れは0バイトに。
0210デフォルトの名無しさん
2006/05/19(金) 14:19:59不正確なら簡単だ
0211デフォルトの名無しさん
2006/05/19(金) 18:09:23ところが、情報理論的に不正確さも決められているので、
闇雲に情報を削除していけばよいということでもない。
0212デフォルトの名無しさん
2006/05/19(金) 18:52:01消去じゃん。
0213デフォルトの名無しさん
2006/05/22(月) 02:22:26画像の可逆圧縮とか、個人で作ってる形式多くて楽しかった。
PNGしょぼいよ!!とか、PIC2つえええとか、TLG6すげえなにこれ!とか
0214デフォルトの名無しさん
2006/05/22(月) 14:05:38文字を書いた人間の、その文に対応したニューラルネットワークの結びを記録、されば読む人間にとっても、その結びから一瞬で意味を理解する事が出来る。
150年ぐらい後の話だけどね。なんじゃこれは、SFか。
0215デフォルトの名無しさん
2006/05/22(月) 17:58:530216デフォルトの名無しさん
2006/05/22(月) 19:07:35記録する情報は、記録者の脳内ニューロンの繋がり(語句)を集めたもの(文章)だからだ。
0217デフォルトの名無しさん
2006/05/22(月) 19:11:35ASCII文字のうち有効文字は7750文字ちょっとで、12ビットあれば十分保存可能だから
保存に16ビット使う全角文字は4ビット落ちるし、保存に8ビットしか使わない半角文字の場合は
特殊な開始コードとかを使って無圧縮にする。
誰か作ってくれ。
0218デフォルトの名無しさん
2006/05/22(月) 19:12:060219デフォルトの名無しさん
2006/05/22(月) 21:07:26その「特殊な開始コード」に必要なビットが、バカにならんのよ。
無圧縮部分に圧縮されていない印を付けると言うことは、その部分で
データが膨らんでいると言うことだから。
0220デフォルトの名無しさん
2006/05/22(月) 21:25:38ASCII文書で有効文字が7750とか、もう言ってる事がめちゃくちゃ。
人格も発言内容も否定したくは無いが、会話の土台を築くために
まずは "ASCII CODE"とかの意味を調べてくれ。
0221デフォルトの名無しさん
2006/05/22(月) 22:29:46ってそういうことを言いたかったんじゃないのか。
0222デフォルトの名無しさん
2006/05/22(月) 22:38:31アホは黙ってろ
0223デフォルトの名無しさん
2006/05/22(月) 22:54:01言いたいことの意味はわかるが「会話」じゃなくて「対話」な、
この場合。
0224デフォルトの名無しさん
2006/05/22(月) 23:26:02脳内定義持ち出してまで
なにを必死になってるんだろう。
とりあえず辞書引け。
0225デフォルトの名無しさん
2006/05/23(火) 00:22:40画像を眺めながらオナニーをしてデータによって握りの圧力や刺激点を変える。
解凍するときは目を閉じて暗号化時と同じ手法でチンコをこすると画像がまぶたの裏に!
0226デフォルトの名無しさん
2006/05/23(火) 00:41:59これで5%くらいまで非可逆圧縮できますよ
0227デフォルトの名無しさん
2006/05/26(金) 07:18:06それ、すこしでも「つぼ」間違えたらぜんぜん違うファイルにならないか?
つか保守&アゲ
0228デフォルトの名無しさん
2006/05/26(金) 09:35:520229デフォルトの名無しさん
2006/05/26(金) 16:59:36http://news18.2ch.net/test/read.cgi/bizplus/1148626281/
0230デフォルトの名無しさん
2006/05/26(金) 20:07:33写真とかだとさ、大体色の同じような場所は固まってるよね。
だからこの圧縮方法結構使えるんじゃね?
0231デフォルトの名無しさん
2006/05/26(金) 20:43:170232デフォルトの名無しさん
2006/05/27(土) 00:40:30場合によってはERIやJPEG2000が上の場合もあるけど。
画像で圧縮率がいいのはTLG6かな。
場合によってはERIやJPEG2000が上の場合もあるけど。
89 E6 91 9C 82 C5 88 B3 8F 6B 97 A6 82 AA 82 A2
82 A2 82 CC 82 CD 54 4C 47 36 82 A9 82 C8 81 42
0D 0A 8F EA 8D 87 82 C9 82 E6 82 C1 82 C4 82 CD
45 52 49 82 E2 4A 50 45 47 32 30 30 30 82 AA 8F
E3 82 CC 8F EA 8D 87 82 E0 82 A0 82 E9 82 AF 82
C7 81 42 0D 0A
というバイト列を 16(任意だけど固定) づつまとめて
0234デフォルトの名無しさん
2006/05/27(土) 09:14:27E6 11100110
91 10010001
9C 10011100
82 10000010
C5 11000101
88 10001000
B3 10110011
8F 10001111
6B 01101011
97 10010111
A6 10100110
82 10000010
AA 10101010
82 10000010
A2 10100010
縦と横を並べ替えて
11111111 10111111
01000100 01000000
01000001 01010101
00110001 00100000
10010010 11000100
01010100 10110000
01001001 11111111
10100101 11100000
としてから圧縮を始めると圧縮率が上がるような気がするけど気のせい?
0235デフォルトの名無しさん
2006/05/27(土) 14:49:20文字が全部全角文字なら圧縮率が上がる可能性は十分考えられる。
半角文字列ならあんまり変わんないと思う。
0236デフォルトの名無しさん
2006/05/27(土) 15:06:21最上位ビットに規則性が生まれることに違いはないから改善するんでね?
0237デフォルトの名無しさん
2006/05/27(土) 15:15:280238デフォルトの名無しさん
2006/05/27(土) 17:04:31を、16づつまとめるのはめんどくさいから、全部一気に縦横並べ替えたやつを作った
何もしてないやつとZIP圧縮で比べた。データは日本国憲法
21,684 原文
8,243 普通にZIP
19,187 並べ替えてZIP
上位ビットの部分は、偏るけど、それ以外の部分はほとんどホワイトノイズ。
0239デフォルトの名無しさん
2006/05/27(土) 17:32:17一意性がなくなって、ある時は「日本」だったのにいきなり「某国」とか。
ビット単位で変換したんなら符号化もビット単位で見ていかないと圧縮できないよ。
ま、そのモデル化が効くデータも中にはあるかもね。
画像くらいしか思いつかんが。
0240デフォルトの名無しさん
2006/05/27(土) 17:41:57やっぱり圧縮率下がるよなぁ
0241デフォルトの名無しさん
2006/05/27(土) 18:51:540242デフォルトの名無しさん
2006/05/27(土) 18:54:07たとえば、ログをメモリに格納する時とか
LANなどでデータを送る際に圧縮しておくるとか
組み込み系ですから、圧縮率も重要ですが、なによりも速度重視のアルゴリズムを
考える必要があるのでしょうかね?
0243デフォルトの名無しさん
2006/05/27(土) 19:11:07並び順が変わるだけで大して違わないんじゃね?
16バイトで割り切れないサイズの時の処理とかめんどくさいし
0244デフォルトの名無しさん
2006/05/27(土) 19:18:01ハードウェア圧縮なら普通にすると思う
0245デフォルトの名無しさん
2006/05/27(土) 20:12:34ZIP以外の形式でも調査キボン
lzhとかcabとかrarとかtarとかoarとか。
0246デフォルトの名無しさん
2006/05/27(土) 20:21:01偶数バイト目だけとったものと奇数バイト目だけとったものを
別々に圧縮して連結してみたらどうなるかなぁ
0247デフォルトの名無しさん
2006/05/27(土) 21:27:20やってみれ
0248デフォルトの名無しさん
2006/05/27(土) 22:54:42テキストだろうが音だろうが画像だろうが、所詮0と1のデータですよね?
そういう観点で圧縮アルゴリズムを考えた場合、なにか最適なアルゴリズムって
ありますか?
0249デフォルトの名無しさん
2006/05/27(土) 23:37:210250デフォルトの名無しさん
2006/05/27(土) 23:43:56魔法斧で瞬殺しやがったwwww
0251デフォルトの名無しさん
2006/05/27(土) 23:44:290252デフォルトの名無しさん
2006/05/28(日) 00:06:44それを討論中
0253デフォルトの名無しさん
2006/05/28(日) 00:30:47ありません。
特定のタイプに強いアルゴリズムは作れるけど、
そのアルゴリズムは他のタイプには弱くなる。
アルゴリズムを切り替えれば良いと思うかも知れないけど、
全てのタイプに対応した全てのアルゴリズムを用意したとき、
どのアルゴリズムを使ったかの情報がファイル情報と等しくなる。
結局一般的な(と思われる)情報源に強いものを選ぶしかない。
で、LZとかBWTとかPPMに落ち着く。
0254デフォルトの名無しさん
2006/05/28(日) 10:24:31あるよ。任意のサーバーにファイルをうpしてURLを晒せばいいのさ
0255デフォルトの名無しさん
2006/05/28(日) 10:27:280256デフォルトの名無しさん
NGNG大容量の辞書を持つ必要はない
あと圧縮時間は掛かっても問題ないと思う
展開時間が通常とそれほど変わらないのであれば配布側が使うメリットは充分にある
0257デフォルトの名無しさん
2006/05/28(日) 19:39:14バイナリデータに特化した圧縮アルゴリズムを考えればいいのでしょうか?
あと、自分で考えたとしても、特許とか絡むと使えないんですよね?
0258デフォルトの名無しさん
2006/05/28(日) 19:41:32処理しないと、いけないですよね?
ということは、組み込み系でソフトウェア圧縮はむかない?
実装している人がいましたら、どのような用途で使ってますか?
そもそも、ここにファームウェア開発の人がいるかわかりませんが
0259デフォルトの名無しさん
2006/05/28(日) 19:54:160260デフォルトの名無しさん
2006/05/28(日) 20:09:17メモリの中身が判らないのに向いてるも何もあったもんじゃない。
そもそもメモリとファイルで違いなんかないだろ。
テキストとか画像とか音楽とかなんかの設定値とか、
それぞれ性質が全然違う。
こういう場合は素直にハフマンが良い。
0261デフォルトの名無しさん
2006/05/28(日) 23:54:18>バイナリデータに特化した圧縮アルゴリズムを考えればいいのでしょうか?
PC で扱えるデータは「全て」」バイナリデータですよ。
>>258
CPUのスペックもデータの帯域もわからないのに、向くも向かないも・・・
圧縮はそもそも用途が少ないような。
展開の方は結構ソフトウェア実装も多いみたいだけど。
0262デフォルトの名無しさん
2006/05/29(月) 19:53:12忘れた。
0263デフォルトの名無しさん
2006/05/30(火) 20:53:240264デフォルトの名無しさん
2006/05/31(水) 01:21:55「aaaaababababcabc」
↓
a:aaaaabbbbb
b:aaacc
c:a
↓
「aaaaabbbbbaaacca」
↓MTF
「a0000b0000100c01」
↓適当にエントロピー圧縮。
(゚д゚)ウマー
0265デフォルトの名無しさん
2006/06/03(土) 14:13:130266デフォルトの名無しさん
2006/06/05(月) 05:39:33モデムのデータ圧縮
0267デフォルトの名無しさん
2006/06/09(金) 04:39:23モレ昔ハフマン圧縮勉強した直後の頃に似たようなこと考えたことあった。
最終的には、ファイルを"0"(0x30)と"1"(0x31)に変換してから普通に辞書圧縮したら論理的に近似可能だということに気付いた。
で詳細は忘れたが、実際にやってみて(´・ω・`)ショボーンだった記憶がある。
FAが出たなら知りたひ・・・
0268デフォルトの名無しさん
2006/06/09(金) 08:47:12一般に辞書との一致で置き換えるアルゴリズムは圧縮率が悪い。
何故か?
今、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ずつ無駄を増やしているということになる。
じゃあどうすればいいのか?
書くのが疲れたので終わり。ごめん。
0269デフォルトの名無しさん
2006/06/09(金) 22:29:04圧縮率がよいアルゴリズム?
それとも同じ圧縮率でも高速なアルゴリズム?
それとも実装が簡単でそこそこ高速かつ圧縮率のよいアルゴリズム?
あと、特許とかあるからわからんけど、そういうものにかからないで
なるべく速いアルゴリズムといったらなんでしょうか?
やはり、特許がきになる・・・
0270デフォルトの名無しさん
2006/06/09(金) 23:41:22>>111が圧縮率の悪さに唖然として開発停止して以来誰も作り出すような発言や完成したような発言はしていないように思うがどうか。
>>269
スレタイから察するに3つそれぞれの意味での「最強」なのでしょう。
0271デフォルトの名無しさん
2006/06/10(土) 03:34:17何が最強かも定義がわからんし。
0272デフォルトの名無しさん
2006/06/22(木) 21:08:18ですが教えてもらえないでしょうか?
zipファイルのパスワードを解析したいのですが
そういったことは出来るのでしょうか?
0273デフォルトの名無しさん
2006/06/22(木) 23:54:56このスレッドはプログラム板にあるわけだが、
プログラム板(作る人が技術的な話をするとこ)ではなくて、
ソフトウェア板(使う人がいろいろな話をするとこ)のスレッド一覧を、
適当な単語でページ内検索しなさい。
「教えて」とか「質問」とか検索するといいよ。
0274デフォルトの名無しさん
2006/06/23(金) 01:01:16他のスレを探してみます。
スレタイからして実際にしようとした人とか
詳しい人が多そうとか思っちゃいました。
0275デフォルトの名無しさん
2006/06/23(金) 01:05:230276デフォルトの名無しさん
2006/06/26(月) 12:01:570277デフォルトの名無しさん
2006/06/27(火) 06:50:5766 名前:名無しでいいとも![sage] 投稿日:2006/06/27(火) 06:47:46.25 ID:3HXDRC1i
zicoって何かの圧縮形式みたいじゃね?
というわけで、ここでなんか圧縮形式が完成したらジーコ形式って名前にすることに決定。
0278デフォルトの名無しさん
2006/06/27(火) 07:28:48むしろ元サイズより増えるくらいでいいんじゃね?
0279デフォルトの名無しさん
2006/07/01(土) 12:02:560280デフォルトの名無しさん
2006/07/03(月) 06:25:400281デフォルトの名無しさん
2006/07/09(日) 03:19:12まぁ、どんなファイルに対してもサイズを縮めることができるような可逆圧縮は存在しないからなぁ。
0282デフォルトの名無しさん
2006/07/09(日) 16:54:180283デフォルトの名無しさん
2006/07/10(月) 08:55:58究極的には圧縮はただの変換(写像)だから、
「元のサイズ+適用したかしないかの1bit」が最小の期待値になる。
0284デフォルトの名無しさん
2006/07/10(月) 23:24:00無圧縮圧縮を思い出した。
0285デフォルトの名無しさん
2006/07/26(水) 09:52:030286デフォルトの名無しさん
2006/09/04(月) 22:09:100287デフォルトの名無しさん
2006/09/30(土) 17:21:290288デフォルトの名無しさん
2006/10/09(月) 17:34:23何を使って作ったらいいのかわからん
0289デフォルトの名無しさん
2006/10/09(月) 17:52:550290デフォルトの名無しさん
2006/10/09(月) 18:45:00その発想は無かったわ。
0291デフォルトの名無しさん
2006/10/09(月) 19:03:060292デフォルトの名無しさん
2006/10/09(月) 19:06:54そしてコロンブスに卵で殴り殺されるんだ。
0293デフォルトの名無しさん
2006/10/09(月) 20:15:26未開拓な分野もあるぞ
0294デフォルトの名無しさん
2006/10/09(月) 21:38:11apache/firefoxで使えるようになるのはいつー?
0295デフォルトの名無しさん
2006/10/11(水) 11:48:181. 16進ダンプを画面表示する。
2. 全て暗記する。
3. 何かのキーワードでそれを思い出せるようにする。
4. 別のコンピュータの前に座る。
5. キーワードを思い出す。
6. 全て打ち込む。
このようにすることにより何Gバイトのデータであったとしても
キーワードの長さに圧縮することがfhdsfdsjfけおwlw
0296デフォルトの名無しさん
2006/10/11(水) 12:29:200297デフォルトの名無しさん
2006/10/11(水) 13:22:13πを何千桁も覚える人がいるんだからいつかそのうちできるようになるさ。
なんだったら事前に bzip2 圧縮して小さくしておけばf;ぇkwlけ2いfそb
0298デフォルトの名無しさん
2006/10/11(水) 13:39:40π は 10 桁。
http://www.f7.dion.ne.jp/~moorend/news/2005020901.html
0299デフォルトの名無しさん
2006/10/12(木) 22:38:29人間という外部記憶装置に保存するわけですな
0300デフォルトの名無しさん
2006/10/12(木) 22:53:090301デフォルトの名無しさん
2006/10/13(金) 03:54:09オルゴールと同じ原理だ。
0302デフォルトの名無しさん
2006/10/13(金) 04:01:140303デフォルトの名無しさん
2006/10/13(金) 05:39:490304デフォルトの名無しさん
2006/10/13(金) 05:51:0324(または23)ビットにまでビット幅を圧縮してみて下さい。
intの値をfloatの仮数に埋め込みます。
0305デフォルトの名無しさん
2006/10/13(金) 12:54:04それ何の意味があるの?
#そもそも無理だし。
0306デフォルトの名無しさん
2006/10/13(金) 14:12:4432bitが特定(や有限・決まっている)の値なら簡単なんだけどね。
0307デフォルトの名無しさん
2006/10/13(金) 16:38:420308デフォルトの名無しさん
2006/10/13(金) 17:03:47機械や生き物が破壊されてしまうようなシステムを構築すれば良い。
表現できないものは無かったことにするという圧縮方法。
上位8ビットの違いによる差異を認識できるものを全て破壊する
という方法もある。
誰にも違いがわからなければロスレスであるという手法。
0309デフォルトの名無しさん
2006/10/13(金) 17:19:37xが32ビット整数だとして、C言語で書くと
x = (x >> 8) & 0x00ffffff;
但し不可逆。
全ての取りうる値での可逆圧縮は不可能。
0310デフォルトの名無しさん
2006/10/14(土) 01:13:45y=x & 0x00FFFFFF
これで x の8ビットを違うアルゴリズム処理すれば良さそう。
当然可逆圧縮・復元できないと意味ないけど、
残り8ビットは256通りだから、そんなに不可能ってほどでもない。
0311デフォルトの名無しさん
2006/10/14(土) 01:31:40詰めかえるだけなら圧縮とは言わないが。
前提が無いと、できるともできないともいえない。
0312デフォルトの名無しさん
2006/10/14(土) 01:44:38>詰めかえるだけなら圧縮とは言わないが。
コラ!
ウソ言っちゃいかんにょ。
0313デフォルトの名無しさん
2006/10/14(土) 04:35:39いわねーよ
0314デフォルトの名無しさん
2006/10/14(土) 22:56:30置き換えで圧縮する、固定長符号化もたまには思い出してください(つД・)
0315デフォルトの名無しさん
2006/10/14(土) 22:57:340316デフォルトの名無しさん
2006/10/15(日) 02:35:52任意の固定長符号で置き換えるなんて話お前しかしてねーよ
0317デフォルトの名無しさん
2006/10/15(日) 09:22:11int32の情報ををfloatの仮数に埋め込むというのは一例です。
intで表現される色情報 a|r|g|b を24bit構造体 struct Enc_T {char val[3];}に
埋め込むとか考えると、やる気出ますか?
もっと簡単な問題だと、32bitを31bitに圧縮してください。
圧縮率は (31/32)*100パーセントになります。
8bitを7bitでもいいけど。
0318デフォルトの名無しさん
2006/10/15(日) 10:46:59話が摩り替わってるじゃん。
int32bitをfloat32bitの仮数部に入れるって話は消費情報量を削減できてないだろ。
単に有効情報量が減るだけじゃん。
0319デフォルトの名無しさん
2006/10/15(日) 10:52:00>>304によると32ビット情報を24ビット(23ビット)に圧縮してからだと思うが
もしかして、float f=3.14f; int j=(int)f と勘違いしてないか?
0320デフォルトの名無しさん
2006/10/15(日) 10:59:120321デフォルトの名無しさん
2006/10/15(日) 11:17:35なんと言うのか、話が逸れてるんだよな…
32ビットのマスに入れるかどうかじゃなくて、
圧縮する方法・アルゴリズムが重要なんじゃないのか
その使い方や用途は君が関知する問題じゃないだろ?
0322デフォルトの名無しさん
2006/10/15(日) 11:51:100323デフォルトの名無しさん
2006/10/15(日) 12:19:030324デフォルトの名無しさん
2006/10/15(日) 12:49:060325デフォルトの名無しさん
2006/10/15(日) 13:44:4532bitを24bitに圧縮も考え次第で出来るだろ。
アルゴリズムというのは、そういうのじゃないのか?
ところで、無理とか不可能とか何を根拠に言ってるんだろう。
0326デフォルトの名無しさん
2006/10/15(日) 15:47:13議論は無理。問題の説明が足りなさ過ぎる。
勝手に考えると、
元が解らなくなっている可能性があってもいいなら
aだけ捨てたら?と思ってしまうが。
32bitを31bitにしたかったら、どこか1bit捨てたら?
0327デフォルトの名無しさん
2006/10/15(日) 16:42:580328デフォルトの名無しさん
2006/10/15(日) 17:07:08これじゃ優秀な奴は誰も来ないぞ。
ところで「とられない」ってどこの言葉だ?
0329デフォルトの名無しさん
2006/10/15(日) 17:11:210330デフォルトの名無しさん
2006/10/15(日) 17:33:09おまえはエスパーのようだが、どこの惑星から来た?
0331デフォルトの名無しさん
2006/10/15(日) 18:11:16すでに切れた特許なら再び取られることは無いだろうな
0332デフォルトの名無しさん
2006/10/15(日) 20:36:32> ところで、無理とか不可能とか何を根拠に言ってるんだろう。
情報量を考えれば自明だからちゃんと勉強しろ。
圧縮後のデータは最大で24MBの情報量しか持ち得ないのに、
それを伸長するのにどうやったら任意の32MBデータが出現しうるんだよ。
まあ、
> 32MBを24MBに圧縮できる(アルゴリズムがある)のだから
というところから、圧縮を魔法かなにかと勘違いしてるのは分かるが。
0333デフォルトの名無しさん
2006/10/15(日) 20:47:45「32Mを24Mに圧縮できる」というのは結果論であって
そのアルゴリズムで常に24Mに収まるという事ではない。
32Mのデータを24Mに圧縮できる「可能性」があるというだけで
32Mを24Mに確実に圧縮できるアルゴリズムというわけではなく
最悪の場合32Mのデータは32Mの容量を必要とする。
もしもどんなデータでも確実に32M→24Mに圧縮できるとしたら
その24Mのデータも確実に18Mになるわけで、そうやって圧縮していけば
データは無限に小さく圧縮できるはずだが、そうはならないよな?
32Mが24Mに圧縮できるのは、32Mのデータの中に冗長な情報が含まれているからで
結局は平均情報量に近づく事はできてもそれ以下になる事はない。
そして完全にランダムな32bitのデータは
冗長な情報が全く含まれていない32bitのデータという意味
(もし出現パターンがあるならそれも情報と考えられる)なので
ランダム32bitデータを24bitにするには8bit捨てるしかない。
0334デフォルトの名無しさん
2006/10/15(日) 23:16:38それを何度か繰り返し使えば世の中のすべての情報は 24bit にまで圧縮できることになるな。
0335デフォルトの名無しさん
2006/10/15(日) 23:32:29[ヽ□
| |
□□□□□□□□□□□□□□□□□□□□□□□□□
[゚д゚]
[ヽ日
| |
日日日日日日日日日日日日日
[゚д゚]
[ヽ品
| |
品品品品品品品品
[゚д゚]
[ヽ昌
| |
昌昌昌昌
ヽ[゚д゚]ノ
[_]
| |
晶晶
0336デフォルトの名無しさん
2006/10/15(日) 23:38:120337デフォルトの名無しさん
2006/10/16(月) 00:58:09データの最後のbitが0だったらそのbitを削るんだ。
1だったらそのまま。
これで1/2の確立でどんなデータ、
ランダムなデータでも1bit削れるよ!
同じ感じで後ろ(先頭でもいいけど)1byteが0x00なら削って、
0x00以外ならそのまま。
1/256の確立で1byte圧縮できるよ!
0338デフォルトの名無しさん
2006/10/16(月) 01:09:42削るのはいいんだがどうやって復元するつもりだ?
0339337じゃないけど
2006/10/16(月) 01:18:14駄目なら最後に0をくっつける。
これでどんなデータでも復元できるよ。
1byteのも同じ感じで、エラーが出なければOK。
駄目なら最後に1byte分の0x00をくっつける。
付けても付けなくても同じ結果を得られる場合もあると思うが
そのときはどっちでもいいんだよ!
0340デフォルトの名無しさん
2006/10/16(月) 01:21:460341デフォルトの名無しさん
2006/10/16(月) 01:31:11その方法だとエラー検査のための仕組みを別に用意しなければいけなくて、
それを厳密に行うためには圧縮前のデータと同じだけの容量が必要になる。
0342デフォルトの名無しさん
2006/10/16(月) 02:56:15そしたらそのマシンは捨ててしまう
これで圧縮が出来た
後でそのデータが必要になったら、フィルムを現像して思い出に浸ろう
写真の裏にマシン名も書いておくと良いな
0343デフォルトの名無しさん
2006/10/16(月) 14:08:00それを何度か繰り返し使えば世の中のすべての情報は 1bit にまで圧縮できることになるな。
0344デフォルトの名無しさん
2006/10/16(月) 15:12:08つまり全ての情報は同じって事。あなたとわたしも全く同じ。
0345デフォルトの名無しさん
2006/10/16(月) 15:14:410346デフォルトの名無しさん
2006/10/16(月) 15:23:250347デフォルトの名無しさん
2006/10/16(月) 15:48:030348デフォルトの名無しさん
2006/10/16(月) 20:29:500349デフォルトの名無しさん
2006/10/17(火) 00:52:06待て、1bitなんだから0か1で全ての情報は二つに分けられることに
0350デフォルトの名無しさん
2006/10/17(火) 01:06:390351デフォルトの名無しさん
2006/10/17(火) 12:21:41完全平衡状態に至って熱的死を迎えるか、
再度収縮して次のビッグ・バンが起きるか、
の2つってことか。
0352デフォルトの名無しさん
2006/10/17(火) 13:27:410353デフォルトの名無しさん
2006/10/17(火) 14:34:140354デフォルトの名無しさん
2006/10/17(火) 15:18:400355デフォルトの名無しさん
2006/10/18(水) 00:53:480356デフォルトの名無しさん
2006/10/18(水) 03:02:37おまいの脳細胞
0357デフォルトの名無しさん
2006/10/18(水) 03:17:57素子2単位で1bit分の情報を記録するようにすればいいだけじゃまいか
0358デフォルトの名無しさん
2006/10/18(水) 05:39:051.5TBで作れるようになるまで待てと言ってるのか?
0359デフォルトの名無しさん
2006/10/18(水) 11:00:01もう解決してるんだけど、つまんない話ばっかりでお前らには教えてやんない。
>>335,>>337は少し面白かったけど、まだまだ。
0360デフォルトの名無しさん
2006/10/18(水) 12:46:530361デフォルトの名無しさん
2006/10/19(木) 21:29:22それってどんなの? オレ的には、
1つのアルゴリズムで結果を帰還させて
圧縮できなくなるまで繰り返すようなのが
美しいと思うのだけど。
0362デフォルトの名無しさん
2006/10/19(木) 21:33:470363デフォルトの名無しさん
2006/10/19(木) 21:39:44だから、それって具体的にどうやるわけ?
0364デフォルトの名無しさん
2006/10/19(木) 22:34:01362と363が俺の言いたかったことを言い尽くしていたことに感動した。
0365デフォルトの名無しさん
2006/10/19(木) 23:15:050366361
2006/10/19(木) 23:32:27ただなんとなく美しい気がしたので。
自分では無理な気がしています。
具体的に無理な理由を説明できるならお願いしたいのですが・・
逆に出来るよ!というのであればなおさらお願いしますー
0367デフォルトの名無しさん
2006/10/19(木) 23:52:18その性質をもつ自明な圧縮の例
圧縮 f (x) とは
x == 0 のとき 0
x > 0 のとき x-1
何度か繰り返せば、どんな数も 0 に圧縮できる。
0368デフォルトの名無しさん
2006/10/19(木) 23:59:570369デフォルトの名無しさん
2006/10/20(金) 00:07:52>復元は何になるの?
何度繰り返したかを覚えておいて逆関数(1足す)をその回数繰り返せばよい。
0370デフォルトの名無しさん
2006/10/20(金) 01:26:570371デフォルトの名無しさん
2006/10/20(金) 02:28:420372デフォルトの名無しさん
2006/10/20(金) 06:39:02なに食わせてもソコソコ縮んで程ほどの圧縮解凍速度
そういうのが良いアルゴリズム。
さらに実装したときに悪意のあるデータによって
セキュリティが脅かされるような不具合が生じない事や
暗号化などまで考慮されていると最高
0373デフォルトの名無しさん
2006/10/20(金) 09:34:25その回数はどこで覚えておくの?
0374369
2006/10/20(金) 09:56:10「繰り返し適用して・・・」という手法をとる以上、圧縮後のデータとは別の
どこかに記録するより他ないんじゃないかな。人間が覚えておく等。
0375デフォルトの名無しさん
2006/10/20(金) 11:48:41そのアルゴリズムは結構出尽くしているかも…
視点を変えてみると面白い!
0376デフォルトの名無しさん
2006/10/20(金) 18:33:360377デフォルトの名無しさん
2006/10/20(金) 19:29:240378361
2006/10/21(土) 22:32:18なんてないよね。きっと。
圧縮ってデータの傾向を利用して可能性を省くことだから、
圧縮後のデータは傾向が消えてるだろうし。
2つのアルゴリズムで交互に通せばいいのか?
でもさまざまな傾向に対応できるように
いろいろなアルゴリズムを用意して・・・とやると
>>362ですよね
結局は>>372に落ち着くと・・・。
>>367
基本の形、ということでしょうか。
圧縮できるところは圧縮して、出来ないところはそのまま。
繰り返すたびにデータが変化していって、だんだん圧縮できなくなる。
そんなイメージ?
0379デフォルトの名無しさん
2006/10/22(日) 00:27:040380デフォルトの名無しさん
2006/10/22(日) 13:53:49何を言ってるんだ、こいつは。
0381デフォルトの名無しさん
2006/10/22(日) 16:42:451001010110101、というのを、a・sinA+b・cosB+…+n・sinN、みたいな、合成波形としてとらえて行く。
圧縮・展開時には、フーリエ変換を使用する。
パラメータとして、a、A、b、B、…、n、N、だけを設定してやればよく、効率の良い圧縮となる。
とかは、既出?
0382デフォルトの名無しさん
2006/10/22(日) 18:39:45もうすこし具体的に書かないと言いたいことが見えてこないから、
既出かどうかは分からない。
0383デフォルトの名無しさん
2006/10/22(日) 18:49:020384デフォルトの名無しさん
2006/10/22(日) 18:56:40一時話題になった、可逆で1/100に圧縮できるというアルゴリズムが
そんな方法だった。
もちろん、一斉に「ダウト!」を喰らってたがw
0385デフォルトの名無しさん
2006/10/22(日) 19:32:480386デフォルトの名無しさん
2006/10/22(日) 19:38:45別物になっちゃうのはアウトだな。
スーパーマン使えねえ。
0387デフォルトの名無しさん
2006/10/22(日) 19:44:37だからどうしてなったのか不明だな
0388デフォルトの名無しさん
2006/10/22(日) 20:17:570389361
2006/10/22(日) 20:44:43「都合が良い」の度合いの問題ですよ〜
実用していて発生するデータの内で。
そりゃ作ろうと思えばいくらでも作れますから。
やっぱいくら考えても
1つのアルゴリズムで繰り返して使う・・・なんて思いつきませんわぁ
処理時間は処理回数と比例するだろうから
組み合わせを全て試して最適解を出すようなタイプかなぁ
とは なんとなく思いますが。経験上
コテハンは最後にしときます
0390デフォルトの名無しさん
2006/10/22(日) 20:49:590391デフォルトの名無しさん
2006/10/22(日) 22:10:420392デフォルトの名無しさん
2006/10/22(日) 23:31:150393デフォルトの名無しさん
2006/10/22(日) 23:38:27なんで?
0394デフォルトの名無しさん
2006/10/22(日) 23:43:180395デフォルトの名無しさん
2006/10/24(火) 21:20:41Cマガジン
圧縮アルゴリズム
が
あんま余計なこと書いてなくてよい。
0396デフォルトの名無しさん
2006/10/30(月) 15:35:26最強のアルゴリズムであって、1つのアルゴリズムだけですべてを適用させる
汎用のアルゴリズムなどあるわけないだろ。wwwwwwwwwwwww
0397デフォルトの名無しさん
2006/10/30(月) 19:59:090398デフォルトの名無しさん
2006/10/31(火) 11:43:020399デフォルトの名無しさん
2006/10/31(火) 16:26:51>そしてこれらの選択肢は全て結果が等しい、つまり等価なわけだ。
>同じ結果に対して別の選択肢が存在するという事は、
>それはつまり冗長だということになる。
詳しい理論や真偽の程はともかく、感覚的に納得の行く説明�dクス
>>270モレにもそのように思える。
しかしそれはモレの頭が悪い所為かも知れないと思って聞いてみた。
0400デフォルトの名無しさん
2006/11/02(木) 13:19:10zip32.dllはdeflateだけじゃないの?
0401デフォルトの名無しさん
2006/11/06(月) 01:12:51圧縮アルゴリズムは
アルゴリズムの説明は確かにいいかもだけど
プログラムについての説明がない、ソースコードのリストがあるだけ
0402デフォルトの名無しさん
2006/11/06(月) 01:34:370403デフォルトの名無しさん
2006/11/06(月) 01:41:220404デフォルトの名無しさん
2006/11/06(月) 15:11:057z で -tgzip -mx=9 オプション指定すると、もっと圧縮された .gz
形式がでるよ。
0405デフォルトの名無しさん
2006/11/06(月) 18:38:210406デフォルトの名無しさん
2006/11/06(月) 20:02:010407デフォルトの名無しさん
2006/11/07(火) 13:41:460408デフォルトの名無しさん
2006/11/11(土) 00:11:080409デフォルトの名無しさん
2006/11/30(木) 12:59:35>>1エントロピーと言う言葉をぐぐってからこないと
大恥かくことになるよ
もうおそかったらごめん
0410デフォルトの名無しさん
2006/12/01(金) 13:56:450411デフォルトの名無しさん
2006/12/01(金) 17:55:250412デフォルトの名無しさん
2006/12/02(土) 00:59:32伸張出来ません
0413デフォルトの名無しさん
2006/12/03(日) 01:11:57しかし、ふにゃふにゃになり硬くなることはありません。
0414デフォルトの名無しさん
2006/12/03(日) 19:24:361kぐらいのファイルに保存することができる。
0415デフォルトの名無しさん
2006/12/06(水) 17:00:19p2pのって、どういう意味だ? ファイルが分割されてあちこちのサーバにあるとか?
0416デフォルトの名無しさん
2006/12/07(木) 11:33:090417デフォルトの名無しさん
2006/12/16(土) 02:31:58テキストファイルではなく、プログラム形式のバイナリファイルを
圧縮及び解凍する目的で利用するなら、どのような圧縮解凍アルゴリズムが
適しているでしょうか?
現状の候補はLZSSです。
また採用する条件は以下です。
・解凍スピードが著しく遅くないこと。
・WEB上でC言語のプログラムソースサンプルが公開されていること。
他に思いつくのはここでもでてくる以下のものたちです。
ハフマン
LZ
BPE
アドバイスお願い致します。
0418デフォルトの名無しさん
2006/12/16(土) 06:28:48既存の自爆形式で何か不満でも?
0419デフォルトの名無しさん
2006/12/16(土) 15:08:320420デフォルトの名無しさん
2006/12/20(水) 20:57:34例えば、あえてテキスト用途の圧縮方式を使ってもいいんだ!という意気込みがないとねぇ。
0421デフォルトの名無しさん
2006/12/20(水) 22:01:20テキストの圧縮を考えると、日本語と
欧米では事情が違うよなぁ。
UNICODEなんか、漢字がばらばらに
なってるから、圧縮難しそうと思う。
0422デフォルトの名無しさん
2006/12/22(金) 08:54:020423デフォルトの名無しさん
2006/12/25(月) 14:28:59変換すれば良いんではないか?
0424デフォルトの名無しさん
2006/12/28(木) 01:04:08素人考えスマソ
0425デフォルトの名無しさん
2006/12/28(木) 01:12:08まさにその考えで実装されたのが、FAXで使用される modified Huffman
(実態は連長圧縮に近い)
より数学的に 0/1 の列を置き換えるのが、数え上げ法と Elias 符号
0426デフォルトの名無しさん
2006/12/28(木) 01:56:17イラストロジックの様に黒の数だけを記録して白の数を完全に無くしてしまえば
データにもよるけれどかなり削れるんじゃないかなぁ、と
イラストロジック自体絶対に解けるものじゃないのが難点ですが
解凍時間に制限がなければ何時かは解凍できるんじゃ・・・という希望
0427デフォルトの名無しさん
2006/12/28(木) 08:23:31適当なイラストロジックで必要なビット数計ってごらん。大した圧縮率にならないから。
0428デフォルトの名無しさん
2006/12/28(木) 08:28:52>イラストロジックの様に黒の数だけを記録して白の数を完全に無くしてしまえば
イラストロジックは横だけでなく、縦方向の情報もあるので、そもそも倍になっている。
縦横の情報より、黒白にすれば一次元で表され効率がいい。
0429デフォルトの名無しさん
2006/12/28(木) 13:32:13>>26
それはTHcompのアルゴリズムじゃないか?
>>29
Web上に辞書を置けば解決。
っていうか、既にアップデートした段階で圧縮されているともいえる。
つまり俺らは既に最強の圧縮アルゴリズムを意識することなく使っている?
0430デフォルトの名無しさん
2006/12/28(木) 22:03:33物怖じせず、正直に言うと、
バカじゃないの?
0431デフォルトの名無しさん
2006/12/28(木) 22:39:01情報の本質を理解している者ならばなおのこと。
0432デフォルトの名無しさん
2006/12/29(金) 00:24:56黒だけとかにすると、場合によっては解凍不能になるのは別に置いといて、
何ビット単位で並べるかによって圧縮率は異なるから(確率的に。なぜなら圧縮するデータが異なるため。)
いかに(時間的に)効率よく圧縮できるか、又いかに圧縮率を高められるかにおいてかなり疑問なのだが。
0433暇人13世 ◆tAo.kQ2STk
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の数を記録する。
解凍は、逆の計算を行えば出来るはず。
実装面倒なので誰かテスト頼む。つーか既にあったら教えてくれ。名前。
0434デフォルトの名無しさん
2006/12/29(金) 01:41:49MTF/UTC/ORTの族に近いと思う。いわゆる順列符号とか再帰時間符号。
ローテート回数が再帰時間に相当するようだから、当たらずといえども遠からずかと。
あと、0/1列上だと、数え上げ符号や算術符号が存在しているので、
少なくともこれらより優れていそうなものじゃないと。
0435暇人13世 ◆tAo.kQ2STk
2006/12/29(金) 01:52:14それと、iの値を記録せずに前回のiとの差分を記録した方が記録効率がいいことが分かった。
後ひとつは、出力結果をさらにハフマンとかで圧縮しないとファイルがでかい。
(ただし0と1の比がかなり偏っているので再圧縮は効率が高そう)
>>434
情報thx。調べてみる。
0437デフォルトの名無しさん
2007/01/09(火) 22:31:210438デフォルトの名無しさん
2007/01/13(土) 18:59:19Aが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とかでないと駄目ぽなのか
0439デフォルトの名無しさん
2007/01/13(土) 19:05:530440デフォルトの名無しさん
2007/01/14(日) 00:52:13確かに最近の OutlookExpress は最適化を行うと
dbx ファイルがごみ箱にもコピーされるようになったね。
0441デフォルトの名無しさん
2007/01/28(日) 19:42:260442デフォルトの名無しさん
2007/02/03(土) 13:13:52WEB上で公開されているものであれば良いです。
■条件
LZSS法、ハフマン符号化以外
(すでに所有しているため)
ハフマン符号化よりも伸張のスピードが速いもの。
圧縮時のスピードは問いません。
伸張が早ければそれでよいです。
>>441さんのLZOはよさそうですが、
プログラムソースを見つけることができませんでした。
よろしくお願い致します。
0443デフォルトの名無しさん
2007/02/03(土) 13:21:550444デフォルトの名無しさん
2007/02/03(土) 15:12:300445デフォルトの名無しさん
2007/02/03(土) 15:18:41BPEでいいじゃん。
0446デフォルトの名無しさん
2007/02/03(土) 15:20:31調べる能力もないのかおまいは。
ぐぐったら一番上に出てきたぞ。
0447デフォルトの名無しさん
2007/02/04(日) 02:13:33つかLZOもLZ77だし。
LZ77はただのメモリコピーだから一番速い。
ハフマンはやり方次第で表引きに出来るからこれも相当速い。
>>442
という訳で、その条件を満たすものはないよ。残念ながら。
まだ遅いと感じてるなら実装が悪いだけ。
0448デフォルトの名無しさん
2007/02/04(日) 03:35:56残念ながらここの住民のほとんどは、高等な数学を扱えるほど頭がよくありません。
マルチエンコードみたいな技術の動きを読み取るほどの視野も持ち合わせていません。
まあ書き込みをざっとみればわかるだろ。
0449デフォルトの名無しさん
2007/02/04(日) 05:11:54ハフマンよりレンジコーダーのほうが速くね?
0450デフォルトの名無しさん
2007/02/04(日) 06:33:23いや、ハフマンの方が2,3倍速い。
Athlon64 X2 2.0GHzのマシンでRam Disk上で計測した場合、
ハフマン 60-80MB/s
レンジ 20-30MB/s
こんな感じ。
どっちもcで書いて結構チューニングしてる。
ファイルのi/oも含んでるから、
圧縮率の分だけ気持ちレンジコーダの方が有利かな。
LZとかなしで純粋に1byteずつ符号化した場合ね。
あ、上の数字は復号だよ。
符号化も同じようなもんだけど。
0451デフォルトの名無しさん
2007/02/04(日) 09:39:05自分から答えを教えるってことしないよな。
他人の非難は出来るけど、その実、自分で答えを
導き出せない、レベルの低い奴なのだろうか?
まぁ、2ch見てる程度の人間だから仕方がないかも。
他人の非難しかしない奴より、なんでもいいから、
自分の意見を述べる奴の方がましってのは、
どこにあっても同じだと思う。
0452デフォルトの名無しさん
2007/02/04(日) 09:56:47こんな過疎スレで誰に言ってるのかよく分からんが。
0453デフォルトの名無しさん
2007/02/04(日) 10:05:330454デフォルトの名無しさん
2007/02/04(日) 12:25:59どこを縦読み?
0455デフォルトの名無しさん
2007/02/04(日) 14:05:56ハフマンのが速いって怪しいな。もしかして静的ハフマンか?
動的なら木の操作が入る分、ハフマンの方が不利だろ。
SSE2を使って最適化したレンジコーダがハフマンに劣ることってありえない。
一度チューニングしたそのコードを書いてみ。
0456デフォルトの名無しさん
2007/02/05(月) 02:09:260457デフォルトの名無しさん
2007/02/05(月) 05:23:19怪しいと言われても実測値だからねぇ。
もしかしなくても静的ハフマンだよ。
動的ハフマンなんて普通使わないでしょ。
木も使わないよ。
SSEは使ったことないから比較出来ないです。ごめん。
アセンブラあまり使えないし。
ただレンジコーダはSIMD化出来る部分が少ないはずなんだよね。
1bitにつき必ず一回は整数の乗算か除算が必要だしね。
ハフマンはシフトと表引きだけで済むからずっと速いはずなんだけど。
気になるなら実験してみて下さいな。
>450で出した数字より遅いなら最適化が十分でないですよ。
ただのハフマンならzip(deflate)やcab(lzx)と同じ位の速度がでるはず。
0458デフォルトの名無しさん
2007/02/05(月) 10:26:28実測値が怪しいんじゃなくて、君の最適化が怪しいって事。
実測値でしか語らず、理論値で説明できないのは、どうして速いかという検証が君ができていないってことだ。
静的ハフマンならテーブル引き+ストリーム出力でほぼ最速になるのは当たり前。
で、レンジコーダの方だが、こっちも静的でいいなら、少ない乗算でできる。テーブル引きとそうかわらん。
SSE2なら乗算平均1clock以下で演算できるから、ほとんど変わらない。
1bitにつきというが、一体どんなレンジコードなんだ?そんな馬鹿なことは普通はしない。
PPMとかのソース見たことないんじゃないの?
静的では若干ハフマンが有利な程度でほとんど変わらんし、
動的ではレンジコーダの方が圧倒的に上。
0459デフォルトの名無しさん
2007/02/05(月) 13:52:03458さんのレンジコーダはそんなに速いの?
とりあえずハフマンは静的でレンジコーダは動的でいいよね?
最初からそのつもりで書いてたんだけど。
動的ハフマンとか静的レンジコーダってあまり見ないし。
正直SSE2はよく分からんのだけど(もうSSE4まで出てるんだっけ?)、
例えばアルファベットサイズが256ならシンボル確定するのに
8bit分の8回バイナリサーチするよね?
ここの部分が一番時間がかかってるはずなんだけど、
ここってそんなに速く出来るの?
いきなりPPMとか言われたりして、
どうも話がかみ合ってない感じなんだけど、
実験用のバイナリどこかに上げようか?
0460デフォルトの名無しさん
2007/02/05(月) 14:03:56>とりあえずハフマンは静的でレンジコーダは動的でいいよね?
ダメだろ。条件をどちらかに揃えないで比較するのはおかしい。
0461デフォルトの名無しさん
2007/02/05(月) 14:07:42>いきなりPPMとか言われたりして、
最強の圧縮アルゴリズムを語るこのスレなら、知っていて当然の基礎知識。
>実験用のバイナリどこかに上げようか?
バイナリじゃなくて、問題箇所のソースを上げてくれ。
0462デフォルトの名無しさん
2007/02/05(月) 14:14:12エンコードするのに、バイナリサーチする馬鹿は普通いない。
それとも「圧縮」の話から、「展開」の話に摩り替えてるの?
0463デフォルトの名無しさん
2007/02/05(月) 14:20:29悪い俺が馬鹿だった。アンカーたどったら元は伸張の話みたいだ。orz
0464デフォルトの名無しさん
2007/02/05(月) 14:22:15おかしいといっても実際動的ハフマンとか静的レンジコーダって殆ど使われてないし。
それにハフマンも動的と静的じゃ殆ど別のアルゴリズムと言って良いくらい違いがあるんだけど。
自分が言ってたのは一般的に使われてる静的ハフマンと動的レンジコーダなんだよ。
事実上この2つ以外を使うことってないと思うんだけど。
動的か静的かで条件を揃えるのって実用上無意味な比較なんじゃないのかな。
>>461
いやPPMは知ってるけどハフマンとかレンジコーダの話をしてていきなり
>PPMとかのソース見たことないんじゃないの?
とか言われても困っちゃうんだけど。
ソースは上げられません。ごめん。
>>462
自分が書いたのは
>>447,450,457,459で
>>442からの流れでデコードの話をしてるんだよ。
別に摩り替えてないと思うんだけど。
なんでそんなに攻撃的なのか分かりません。
もう少し落ち着いて話をしませんか?
0465デフォルトの名無しさん
2007/02/05(月) 14:50:31>おかしいといっても実際動的ハフマンとか静的レンジコーダって殆ど使われてないし。
動的ハフマンがあまり使われないのは、速度の劣化に対する圧縮率の向上があまりないから。
レンジコードだと動的にしても、あまり速度が遅くならず、圧縮率の向上が見られるから、動的で使うことが多いだけ。
>自分が言ってたのは一般的に使われてる静的ハフマンと動的レンジコーダなんだよ。
でも速度比較するなら、どっちも静的にすればいい。その程度のこともできないの?
理解せずにレンジコーダをつかっているとしか思えん。
>ソースは上げられません。ごめん。
なぜ?ビルドできなくてもいいし、部分的にでも上げる事が出来ない理由があるの?
0466デフォルトの名無しさん
2007/02/05(月) 14:52:53>事実上この2つ以外を使うことってないと思うんだけど。
そんなのアプリの用途の問題であって、アルゴリズムの比較とは何の関係もない。
実際、静的算術圧縮を使う事だって普通にある。
>動的か静的かで条件を揃えるのって実用上無意味な比較なんじゃないのかな。
無意味じゃないよ。条件そろえないほうが無意味。
0467デフォルトの名無しさん
2007/02/05(月) 14:56:18>>PPMとかのソース見たことないんじゃないの?
>とか言われても困っちゃうんだけど。
PPMのレンジコーダのコードは優秀。
0468デフォルトの名無しさん
2007/02/05(月) 15:00:54やっぱり話がかみ合ってないんだよなぁ。
ソース上げろと言われてもその前にあなたが出してくださいよ、
という話になってしまうし。
私がヘボグラマーでレンジコーダの方が速いということで終了しましょう。
バイナリのアップは止めておきます。
0469デフォルトの名無しさん
2007/02/05(月) 15:03:31どのPPM?
Dmitry Shkarin?
0470お呼びじゃない?
2007/02/05(月) 15:07:120471デフォルトの名無しさん
2007/02/05(月) 15:08:15アルゴリズムの実行効率の優劣を論じてるんじゃなくて、
>ハフマン符号化よりも伸張のスピードが速いもの。
>圧縮時のスピードは問いません。
>伸張が早ければそれでよいです。
って話じゃなかったっけ。
>>45が勘違いしてエンコードの話始めてから話が変になったが。
0472デフォルトの名無しさん
2007/02/05(月) 15:58:28>なんか妙に絡まれてるけどなんでだろう?
静的と動的という、機能的に違うもので無意味な比較をしているから。
圧縮率無視すれば、ハフマンより速いレンジコーダだって書ける。
0473デフォルトの名無しさん
2007/02/05(月) 16:04:17そんなに違わなくね?
圧縮展開って意味なら大差ないような。
ストリームに対応出来るかどうかとか?
0474デフォルトの名無しさん
2007/02/05(月) 16:11:49全然違う。
静的なら頻度表が必要。動的なら不要。
出現確率の変化に動的なら対処できるが、静的では不可能。
0475デフォルトの名無しさん
2007/02/05(月) 16:17:25ブロックに分割したらダメなのか?
0476デフォルトの名無しさん
2007/02/05(月) 16:18:23それって単に多少の圧縮率の話ですよね。
それで「全然違う」かどうかは入力の性質次第かと思うが。
「機能的に違う」「全然違う」と言えるような差異としては
>ストリームに対応出来るかどうかとか?
の方が適切なんじゃない?
0477デフォルトの名無しさん
2007/02/05(月) 16:21:05そんなに違いがあるとも思えないけどな。
0478デフォルトの名無しさん
2007/02/05(月) 16:32:25静的も動的も、ストリームに対応するかしないかはどっちも一緒。
どっちもたいていブロックに分割した上で、対応する。
0479デフォルトの名無しさん
2007/02/05(月) 16:33:370480デフォルトの名無しさん
2007/02/05(月) 16:37:22違うよ。
動的か静的かは、確率変動に対応できるかどうかという違いがある。
静的は展開が速いが無駄なデータが多くなるし、圧縮時は無駄なリードが発生する。
0481デフォルトの名無しさん
2007/02/05(月) 16:44:28それって結局圧縮率の問題じゃね?
出現確率の変化の仕方次第じゃ動的な方が圧縮率悪かったりするよ?
それに動的だと出現しないシンボルが無駄になるんだよな。
エスケープ使うとますます遅くなるしな。
0482デフォルトの名無しさん
2007/02/05(月) 17:03:35圧縮率無視するなら、そもそも圧縮なんかしないでいいだろ。
圧縮率が上がればその分読み込みも速くなるから無視は出来ないと思うが。
動的が圧縮率悪くなるわけではない。実装がタコだとそうなるけど。
理論値では動的のほうが必ず上になる。出現しないシンボルは、静的のテーブルの分で相殺できる。
静的に適したデータなら、動的が無駄に遅くなるという点は同意だが。
0483デフォルトの名無しさん
2007/02/05(月) 17:26:15>圧縮率無視するなら、そもそも圧縮なんかしないでいいだろ。
べつにそんな事言ってないぞ。
ていうか圧縮率の問題は比較する上で静的動的と本質的に関係なくね?
>動的が圧縮率悪くなるわけではない。実装がタコだとそうなるけど。
いんや実装の問題じゃないよ。
どんな実装をしても変化を捉えられないケースは必ずある。
>理論値では動的のほうが必ず上になる。
逆じゃね?
動的だと任意の位置のシンボルの出現確率はそれまでの文脈から決定されるわけだから、
どのシンボルも常に確からしい確率を与えられるとは限らないでしょ。
静的だと区間における出現確率をあらかじめ調査するから、
その区間に限っては任意のシンボルは必ず確からしい確率が与えられるはず。
頻度表の分動的より悪くなることが多いと思うけど。
>出現しないシンボルは、静的のテーブルの分で相殺できる。
出来るとは限らないでしょ。
テーブルのサイズは決まってないわけだし。
作り方次第じゃ数バイトで済んだりするよ。
0484デフォルトの名無しさん
2007/02/05(月) 17:36:19>ていうか圧縮率の問題は比較する上で静的動的と本質的に関係なくね?
関係あるよ。これは確率論だから。
>どんな実装をしても変化を捉えられないケースは必ずある。
その場合は静的と同じに出来る。動的の下限が静的なんだが。
>動的だと任意の位置のシンボルの出現確率はそれまでの文脈から決定されるわけだから、
>どのシンボルも常に確からしい確率を与えられるとは限らないでしょ。
>静的だと区間における出現確率をあらかじめ調査するから、
ここまでは正解。
>その区間に限っては任意のシンボルは必ず確からしい確率が与えられるはず。
ここが間違い。
例えば、区間内に「AAAA...AAAABBBB....BBBB」というデータが与えられた場合、
静的だとA、Bの確率が0.5になる。
シャッフルしたらエントロピーが上がり、情報量が下がることはわかると思うが、
静的では圧縮率に変化が起こらないことから、そういった要素を無視しているのはわかるよな?
>作り方次第じゃ数バイトで済んだりするよ。
数バイトで済む場合、動的のほうの無駄も、同程度以下で済ますことが出来る。
情報量の計算すればわかることだが。
0485デフォルトの名無しさん
2007/02/05(月) 17:56:05>ここが間違い。
>例えば、区間内に「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にはならない。
理論的には静的な方が良くなるのは分かるよね?
動的符号化は常に被符号語が未知であるが故に確からしい確率を与えることが出来ない。
>シャッフルしたらエントロピーが上がり、情報量が下がることはわかると思うが、
???
エントロピーが上がって、情報量が上がるの間違いだよね?
文脈次第では?
0486デフォルトの名無しさん
2007/02/05(月) 18:10:00>ん?その区間の確率は理論上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値のモデルで検証してみることだ。
区間内に出現確率の変化がある場合、動的のほうが必ず良くなるから。
そして変化が無い場合でも、動的でも静的と同レベルに抑える方法があることがわかる。
>エントロピーが上がって、情報量が上がるの間違いだよね?
エントロピーが上がる=情報量が下がるだよ。
シャッフルしたら情報量が下がるのがわからん?
0487デフォルトの名無しさん
2007/02/05(月) 18:15:11静的
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
0488デフォルトの名無しさん
2007/02/05(月) 18:18:07頻度テーブルの情報量を加えてごらん。
0489デフォルトの名無しさん
2007/02/05(月) 18:23:20>>その変化の仕方はタコなアルゴリズム。
どんな入力に対しても対応できる方法は存在しないよ。
>>高圧縮のアルゴリズムはすべて動的になっていることからもわかるはずだが。
残念。
それらは一般的な情報源に対して高圧縮率なだけ。
例えばPAQやPPM*よりLZが倍近く高圧縮になるケースが実在する。
0490デフォルトの名無しさん
2007/02/05(月) 18:25:19>それらは一般的な情報源に対して高圧縮率なだけ。
>例えばPAQやPPM*よりLZが倍近く高圧縮になるケースが実在する。
だから、それは特殊な場合だろ。平均的には論理的に動的のほうが上というのがわからんの?
0491デフォルトの名無しさん
2007/02/05(月) 18:27:021bitでイイ?
0492デフォルトの名無しさん
2007/02/05(月) 18:29:06どうやって表現するんだ?AAAAとAAABとAABBとABBBとBBBBが区別できないといけないだろ。
0493デフォルトの名無しさん
2007/02/05(月) 18:33:53WEB上で公開されているものであれば良いです。
■条件
LZSS法、ハフマン符号化以外
(すでに所有しているため)
ハフマン符号化よりも伸張のスピードが速いもの。
圧縮時のスピードは問いません。
伸張が早ければそれでよいです。
0494デフォルトの名無しさん
2007/02/05(月) 18:33:58てことは少なくとも頻度表を除けば平均的な
区間圧縮率は静的な方が上なんだよ。
で、これにテーブルをどうするかって位の差なんだよなこれがさ。
最初から辞書として持っててもいいわけだ。
実際PAQとかDurilcaとかはテーブル持ってんだよね。
0495デフォルトの名無しさん
2007/02/05(月) 18:42:03>だからよ、テーブルは任意サイズでもいいわけよ。
誰もそれを否定していないが?
情報量から限界があるから、無駄をなくすことができるだけで、下限は情報量によって決る。
>てことは少なくとも頻度表を除けば平均的な
>区間圧縮率は静的な方が上なんだよ。
必要な頻度表を除けばというのはインチキだな。
最悪時の動的のロスもその程度だから、必要な頻度表を含めば動的も静的もほとんど変わらない。
しかし、区間中に確率の差がある場合、動的の方が理論的には良くなる。
>最初から辞書として持っててもいいわけだ。
持っててもいいが、持っていなくてもいい。
0496デフォルトの名無しさん
2007/02/05(月) 18:49:29ランレングス
0497デフォルトの名無しさん
2007/02/05(月) 19:03:14その時点で決められないんだよな。
>最悪時の動的のロスもその程度だから、必要な頻度表を含めば動的も静的もほとんど変わらない。
なら動的の方が良いとは限らないのでは?
>しかし、区間中に確率の差がある場合、動的の方が理論的には良くなる。
なぜ?
入力に対してどんなに対応を切り替えようが
動的である限り常に最悪のパターンは存在する。
どんなBitのパターンであっても同じだよ?
つまりどんな入力に対しても頻度表を除けば常に静的な方が圧縮率は上。
動的符号化は常に被符号語が未知であるが故に確からしい確率を与えることが出来ない。
最適な確率・符号長を与えられない時点で平均的には必ず静的より悪くなる。
その上でこれに加える頻度表は任意でいい訳よ。
どんな形で頻度表が作られるかは不明。サイズも不明。
だから動的が理論的に必ず良いというのはおかしいのさ。
そもそも頻度表が加わるから大きくなると言ってるけど
どんな形で頻度表を持たせるかは言及してないでしょ。
0498デフォルトの名無しさん
2007/02/05(月) 19:08:53>つまりどんな入力に対しても頻度表を除けば常に静的な方が圧縮率は上。
馬鹿。
0499デフォルトの名無しさん
2007/02/05(月) 19:11:32馬鹿はないだろ馬鹿は。
でも間違ってないだろ?
0500デフォルトの名無しさん
2007/02/05(月) 19:13:40シャノンの情報理論も間違ってることになるんじゃ?
0501デフォルトの名無しさん
2007/02/05(月) 19:15:21>動的符号化は常に被符号語が未知であるが故に確からしい確率を与えることが出来ない。
>最適な確率・符号長を与えられない時点で平均的には必ず静的より悪くなる。
間違い。
静的は全体で確率を求めるため、局所的な確率を効率よく求めることが出来ない。
最適な確率・符号長を与えられない時点で平均的には必ず動的より悪くなる。
静的なアルゴリズムを選択する場合でも、
ブロックにわけることで、擬似的に動的っぽい効果は得られるが。
0502デフォルトの名無しさん
2007/02/05(月) 19:19:43どんな入力に対しても最適にする事は出来ないんだよ?
実装の問題とかじゃなくてさ。
0503デフォルトの名無しさん
2007/02/05(月) 19:21:46>局所的な確率はどうやって求めんのよ?
ベイズ推定
0504デフォルトの名無しさん
2007/02/05(月) 19:22:42これを動的符号化で期待値求めてみてよ。
0505デフォルトの名無しさん
2007/02/05(月) 19:26:07A=aが1000個の固まり
B=bが1000個の固まり
に展開して、aとbで符号化してみたらどう?
0506デフォルトの名無しさん
2007/02/05(月) 19:28:11何やったって既知である静的符号化より区間平均が悪くなるのに。
特殊な情報源に強くする事は出来ても全般は無理よ。
0507デフォルトの名無しさん
2007/02/05(月) 19:37:17母数を大きく取るのね。
500/1000
501/1001
502/1002
500/1003
0.062499813247569977380545675660332
大きくとるほどに変化に強くなる。
0508デフォルトの名無しさん
2007/02/05(月) 19:54:14動的な符号化ってのはさ大体の場合、頻度の累計値が決まってんのよ。
で、一定期間(1bit毎でも)で頻度表を更新するんだけど、
これのおかげで静的で言うところの区間が可変になるんだな。
だからシンボルが連続したりすると圧縮率が良くなるんだ。
で、シンボルがランダムだと悪くなったりするんだ。
テキストとか所謂圧縮しやすい情報源だと偏りがあるから良く効くんだよ。
で、ランダムだと全然ダメだったりするんだ。
で、あらゆる全てのビットパターン(未知の情報源)をトータルすると
結局、静的符号化が上回るんだよ。
0509デフォルトの名無しさん
2007/02/05(月) 23:05:45>で、あらゆる全てのビットパターン(未知の情報源)をトータルすると
やっぱりお前は馬鹿だな。
全ビットのパターンをトータルするなら圧縮しない方が一番いい。そんなこともわからないのかよ…。
0510デフォルトの名無しさん
2007/02/05(月) 23:12:32理論値を語ってるんじゃなかったんか。
0511デフォルトの名無しさん
2007/02/05(月) 23:14:22じゃあ、君の考えだとPPM法を静的にした方が圧縮率が上がるということ?
そんなことやる奴なんていないと思うが。
0512デフォルトの名無しさん
2007/02/05(月) 23:15:54全パターンなら、理論値だろうと実測値だろうと一緒だろ。圧縮しないのが最強だ。
0513デフォルトの名無しさん
2007/02/05(月) 23:26:12頻度表を除けば理論上はそうなるよ。
まあ当たり前なんだけどさ。
頻度表をどうするかはまた別の話。
durilcaとかは自前でテキスト用に辞書をもってたりする。
実用上はもちろん頻度表は動的に作ることになるだろうけどね。
>>512
理論的に必ず動的が上だって言うからそれは違うだろって話をしてたんだよ。
究極的には圧縮しないのが最強なのは全くもってその通り。
可逆圧縮はただの変換なんだから、
どんなアルゴリズムを用いたとしても、
入力サイズ+圧縮したかしないかの1bitが最小の期待値になる。
n通りのビットパターンはn通りのビットパターンでしか表現できない。
0514デフォルトの名無しさん
2007/02/05(月) 23:47:50おかしいだろという話なんだよ。
実際存在しうるデータってのはランダムの方が圧倒的に多いんだよ。
>>511
abcabcabcab
ときてabの次に何が来るか考えたら分かるよ。
cが来るだろうなと思って実際にcがきたとしても、
動的符号化はc以外の文字にも常に確率を割り当てなきゃならない。
既知であれば必ず最適な符号長が割り当てられる。
0515デフォルトの名無しさん
2007/02/06(火) 00:17:03>実際存在しうるデータってのはランダムの方が圧倒的に多いんだよ。
馬鹿だなー。実在するデータは、ランダムの方が少ないから、圧縮アルゴリズムが有効なんだよ。
0516デフォルトの名無しさん
2007/02/06(火) 00:19:38何度も言うが、頻度表除いたらダメだろ。情報が頻度表に移動しているだけなんだから。
根本的に情報理論がわかってないんとちゃう?
0517デフォルトの名無しさん
2007/02/06(火) 00:30:46>動的符号化はc以外の文字にも常に確率を割り当てなきゃならない。
>既知であれば必ず最適な符号長が割り当てられる。
それが違うんだな。既知であるためには、先行して情報が与えられている必要がある。
その情報の量と、動的の場合に確率を割り当てる量というのは、実は同じ。
しかし静的の場合、局所確率に適応できないため、原理的に最適な符号を割り当てることが出来ない。
圧縮率がシャッフルさせても変化しないというのは、
文字の前後との相関性の情報量を利用できていないということに他ならない。
圧縮というのは、出現の偏りによって圧縮するのであって、単なる出現確率だけよりも、
時系列情報(既出文字との相関性)の偏りを利用できた方が、一般的に圧縮率は向上する。
0518デフォルトの名無しさん
2007/02/06(火) 00:32:21有効じゃないなんて誰も言ってないだろ。
理論的に話してるんだから考えうるデータは全部考慮しなきゃならんだろ。
>>516
>何度も言うが、頻度表除いたらダメだろ。情報が頻度表に移動しているだけなんだから。
それはそう。
だが動的にすれば常に理論上圧縮率が良くなるのは違うだろ?
頻度表をどう持たせてどう使うかはまた別の話。
そもそも動的にしたことで偏った情報源で圧縮率が良くなるのを
理論値だなんて言うからおかしくなるんだよ。
0519デフォルトの名無しさん
2007/02/06(火) 00:36:57トレードオフなんだよ。
圧縮率が良くなった時だけ見てるからそうなるんだよ。
よーく考えてみてよ。
理論上の話なんだから。
0520デフォルトの名無しさん
2007/02/06(火) 00:37:18>だが動的にすれば常に理論上圧縮率が良くなるのは違うだろ?
理論上、実際に使うデータでは平均的に圧縮率が向上する。
なお、現実と一致しないような理論は理論ではなく空論。
>頻度表をどう持たせてどう使うかはまた別の話。
動的だってそれ専用の表に符号を追い出すことは出来る。
そんなもの切り離して考える方がどうかしている。
>そもそも動的にしたことで偏った情報源で圧縮率が良くなるのを
動的にしたことで偏るんじゃなくて、偏りが抽出できるだけ。
始めから偏ったデータを使っているから圧縮アルゴリズムに意味が出てくるの。
0521デフォルトの名無しさん
2007/02/06(火) 00:38:22理論上というのは、ランダムとか全パターンのことじゃないぞ。
根本的に何か勘違いしていると思われ。
0522デフォルトの名無しさん
2007/02/06(火) 00:42:58なぁ、おかしくないか?
ワーストケースを考慮しないのが理論的なのか?
圧縮しやすいデータを対象にして話すのは結構だけど、
だったら理論て言葉はなしにするべきだろ。
実際tar化されたファイルとかで圧縮・非圧縮のが混ざってたりして
動的が不利になるケースとかもあるんだよ?
0523デフォルトの名無しさん
2007/02/06(火) 00:44:150524デフォルトの名無しさん
2007/02/06(火) 00:44:55じゃあ理論上てのはどんなのだよ。
人それぞれ対象が違ったらそれこそ話が合わないじゃないか。
0525デフォルトの名無しさん
2007/02/06(火) 00:48:35究極的にはそれはその通り。
だが符号表を除けば除いた残りの部分は必ず動的より良くなる。
当たり前すぎる。
動的が常に理論的に上ってのは間違い。
0526デフォルトの名無しさん
2007/02/06(火) 00:49:13圧縮しやすいではなく、圧縮可能なデータ。いろいろな偏りが含まれていることが前提になる。
程度の差は様々でいいが、出現確率に差があり、相関性にも差があるのが、現実のデータ。
そういう差がないなら、それはただの乱数列であって、圧縮アルゴリズムを適用する対象外だ。
乱数であることを検出したら、圧縮しないで転送すればいいだけ。
動的でも静的でもいいが、不利になったりするのは、実装上の問題であって、情報の理論的な問題ではない。
0527デフォルトの名無しさん
2007/02/06(火) 00:49:530528デフォルトの名無しさん
2007/02/06(火) 00:51:21>だが符号表を除けば除いた残りの部分は必ず動的より良くなる。
除けばなんて話はしていない。合わせたら動的の方が良くなる。
静的で頻度表に全部符号を置けば、良くなるどころか0ビットに圧縮可能だが、そんなものは圧縮とは言わない。アホ過ぎる。
0529デフォルトの名無しさん
2007/02/06(火) 00:52:28そういうこと。その中で、動的は時系列情報を利用できる。
0530デフォルトの名無しさん
2007/02/06(火) 00:54:03>圧縮しやすいではなく、圧縮可能なデータ。いろいろな偏りが含まれていることが前提になる。
圧縮可能かどうかはアルゴリズム次第なんだって。
そんな前提条件があるなら先に言ってくれよ。
>そういう差がないなら、それはただの乱数列であって、圧縮アルゴリズムを適用する対象外だ。
じゃあ理論値て言葉はなしにしてくれよ。
0531デフォルトの名無しさん
2007/02/06(火) 00:55:44時系列情報て、それは結局ワーストケースとのトレードオフなんだって。
0532デフォルトの名無しさん
2007/02/06(火) 00:56:20理論値は理論値。確率や相関性を分散とかを適当に設定すればいいのであって。
全パターンというのは、そもそも圧縮を考える上で無意味なこと。
0533デフォルトの名無しさん
2007/02/06(火) 00:58:10そんなことを言うなら、頻度表もワーストケースとのトレードオフだ。バカバカしい。
0534デフォルトの名無しさん
2007/02/06(火) 00:58:52理論値てのは普通全部含めるだろ?
いい加減理論値って言葉はやめなよ。
特定の場合のみなら理論とはかけ離れてる。
0535デフォルトの名無しさん
2007/02/06(火) 01:01:29バカバカしい、って理論の話じゃなかった訳?
あなたの理論は特定のアルゴリズムで圧縮できる
特定のファイルにのみ適用されるの?
0536デフォルトの名無しさん
2007/02/06(火) 01:06:48>理論値てのは普通全部含めるだろ?
含めないよ。偏りがないなら圧縮できないで終了だから。
n次相関がどれだけとか、分散がどれだけとか、偏りがあることが前提になる。
0537デフォルトの名無しさん
2007/02/06(火) 01:11:08特定のアルゴリズムというわけではないよ。
現実のデータというのは、高次相関性があるわけ。
どんなアルゴリズムもその相関性を利用して圧縮を行う。
全次元で相関性が0なら、完全な乱数列であり、圧縮理論の対象外になる。
多かれ少なかれ、相関性があることが前提になる。
そして、その相関性を高次まで多く利用できるアルゴリズムが圧縮率が上がるということなの。
0538デフォルトの名無しさん
2007/02/06(火) 01:13:09とりあえず前提条件も話さずに特定の場合のみ取り出して
「理論上は…」ってのだけは止めるべきだと思うよ。
0539デフォルトの名無しさん
2007/02/06(火) 01:18:31理論上は静的の方が冗長な情報が含まれるから劣るんだよ。
シャッフルしたときとの差の情報が使われていないからね。
ただ、現実には理論値が出せないことがあるから、静的な方がいいこともあるだけ。
「情報量」で考えられないやつにはわからないかもしれんが。
0540デフォルトの名無しさん
2007/02/06(火) 01:20:18無限にアルゴリズムが存在する中では高次相関とかは無意味なんだって。
完全な乱数列かどうかなんて判定は出来ないんだから。
全次元の判定なんて不可能でしょ。
というか理論と言う時点で全ての情報源は等価である事が前提だと思うんだけど。
0541デフォルトの名無しさん
2007/02/06(火) 01:29:29>全次元の判定なんて不可能でしょ。
だから、どれだけの次元を利用できるかということになる。
静的なら最低の相関性だけしか使わないが、
それ以上の相関性を利用できれば理論上、圧縮率が上がるのは当たり前なんだよ。
>というか理論と言う時点で全ての情報源は等価である事が前提だと思うんだけど。
そんなんだったら、確率論も、情報理論もいらんがな。
これらは何らかの偏りがあることでしか意味がないから。
0542デフォルトの名無しさん
2007/02/06(火) 01:32:05後だしの前提条件を踏まえる限りは概ね正しいと思うよ。
ただし議論するときは前提条件はきちんと提示するべきだね。
0543デフォルトの名無しさん
2007/02/06(火) 01:37:52全パターンなんて基地外じみた条件こそ後出しだろ。
まともな情報理論で語るなら、そんなわかりきったことを持ち出して議論を無意味にしたりはしないのが普通。
0544デフォルトの名無しさん
2007/02/06(火) 11:42:470545デフォルトの名無しさん
2007/02/06(火) 12:39:190546デフォルトの名無しさん
2007/02/06(火) 16:58:04エルゴード情報源くらいを仮定してみては?
0547デフォルトの名無しさん
2007/02/06(火) 23:20:22理想論の放棄=客観的なアルゴリズム比較の放棄
と同等だわな。
0548デフォルトの名無しさん
2007/02/06(火) 23:23:28同意。
現代の圧縮アルゴリズム論は、もう情報源の設定が必須だな。
なんでも使える汎用アルゴリズムなんて、曖昧で議論も検証も不毛になりがち。
0549デフォルトの名無しさん
2007/02/07(水) 08:42:10"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
0550デフォルトの名無しさん
2007/02/07(水) 08:43:0919 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
0551デフォルトの名無しさん
2007/02/07(水) 08:44:06I=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
…どうでしょう?
0552デフォルトの名無しさん
2007/02/07(水) 09:00:010553デフォルトの名無しさん
2007/02/07(水) 09:15:44ア、ナルほど。
1のIMや3のM■はもっと後にコード化されるみたいですね。
もう一度やってみます。
0554デフォルトの名無しさん
2007/02/07(水) 09:36:590 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
0555デフォルトの名無しさん
2007/02/07(水) 09:37:45I=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
…合ってますか?
0556549
2007/02/07(水) 11:28:47ではなくて
"IN■ULM■UM■ULM■UND■UM■ULM■HERUM"
↑
でした。
しかもノートに答えが載ってました、はははは。(^^ゞ
…吊ってきます。
0557デフォルトの名無しさん
2007/03/21(水) 06:13:42すでに圧縮書庫の数は大量に存在するわけだし、類似点も沢山見つかっている
頻度の高いものは共通の辞書としてあらかじめ持っておけばば数には入らず
辞書の部分だけデータは縮小されるはずだ。
共通辞書を参照するには1つの系統の辞書だとインデックスが大きくなるので
個別の特徴によって辞書の総数を減らした多段の辞書も用意しておくべき。
圧縮できない決まったパターンがある場合、それ自身(生)を持っているほうが
明らかに有用だろう。
0558デフォルトの名無しさん
2007/03/21(水) 07:09:13特定用途に絞るならそれでいいと思うけどね。
0559デフォルトの名無しさん
2007/03/29(木) 19:08:450560デフォルトの名無しさん
2007/03/31(土) 22:44:28>>548
0561デフォルトの名無しさん
2007/03/31(土) 23:04:45固定化されたデータ列A(たとえば、ttp://f55.aaa.livedoor.jp/~vipper/vipmemorialthread/
にHTML化されているデータを下から順に50個くっつけた奴とか)に対して
データ列B=圧縮されたデータ列A+圧縮に使用したバイナリデータ(実行ファイル、辞書、etc.)
となるデータ列Bを生成する時、データ列Bが(Byte単位で)最も軽くなるような圧縮ソフトを作りあって競う とか。
「圧縮に使用したバイナリデータ」は原則、実行可能状態の時のサイズで。(zipとかupxfとかを許可するかどうかは誰かが決めてくれ。lzhはだめだろ。)
あと、「圧縮されたデータ列AはURLです」とか無しな。ローカルでクローズドなコンピュータ単体で、データ列Aが復元できなきゃ話にならん。ネットに接続は問題外で。
0562561
2007/03/31(土) 23:15:30解凍に必要なバイナリデータもデータ列Bに含める。
(「辞書なんて解凍側持ち、データ列Aは1byteに圧縮プギャー」とか乱立しても面白くないため)
ソースコードの添付は義務ではないものとする。
(そんなに欲しけりゃ逆汗して手に入れるだろ。)
0563デフォルトの名無しさん
2007/03/31(土) 23:28:550564デフォルトの名無しさん
2007/04/01(日) 11:52:53京都
0565デフォルトの名無しさん
2007/04/01(日) 14:41:210566デフォルトの名無しさん
2007/04/01(日) 18:15:070567デフォルトの名無しさん
2007/04/01(日) 19:55:16そしてサイト巡ってもう少し勉強しろ。(日本語のはまともなのがないぞ)
というか簡単なのでいいからまともに動くプログラム一から書いてみろ。
そんでもって適当なファイルでベンチマークとってみろ。
calgaryとかcanterburyのコーパスでかまわん。
「使える」アルゴリズムを造るのが如何に大変か分かるぞ。
0568デフォルトの名無しさん
2007/04/02(月) 00:14:53まず、特定のバイト列をとても効率よく圧縮できるアルゴリズムを作って、
それを改良していけば「最強の圧縮アルゴリズム」の仕様・実装について深く語り合えるかなと。
0569568@途中で送信しちまった
2007/04/02(月) 00:15:45まず、特定のバイト列をとても効率よく圧縮できるアルゴリズムを作って、
それを改良していけば「最強の圧縮アルゴリズム」の仕様・実装について深く語り合えるかなと。
そう思うのだがどうだろう?
0570デフォルトの名無しさん
2007/04/02(月) 03:20:25圧縮率だけでよければ、最強の圧縮は作れるにょ。
そんなのは40年前から知られているにょ。
今も昔も圧縮の研究は、
圧縮率をなるべく落さずに高速なアルゴリズムを作ることだにょ。
確率論とか情報理論はどうでもいいにょ。
確率論とか情報理論を知らない奴はもっとどうでもいいにょ。
0571デフォルトの名無しさん
2007/04/02(月) 03:31:520572デフォルトの名無しさん
2007/04/02(月) 03:33:22そう一瞬思ってしまった・・・不覚orz
0573デフォルトの名無しさん
2007/04/02(月) 03:36:41にしても、まず圧縮率優先だろう。
アルゴリズムの計算速度の最適化ならあとからいくらでもやりようがあるが
その圧縮率が糞なら言う事ない。
0574デフォルトの名無しさん
2007/04/05(木) 12:24:01リアルタイムエンコーディングが必要な場面では
速度重視のアルゴリズムも必要だと思うけどなぁ。
0575デフォルトの名無しさん
2007/04/09(月) 21:31:390576デフォルトの名無しさん
2007/04/10(火) 00:34:290577デフォルトの名無しさん
2007/04/10(火) 08:04:26mp3 や jpeg など 不可逆圧縮 と呼ばれるのはそうだね。
0578デフォルトの名無しさん
2007/04/10(火) 08:33:58ファイルのプロパティ見ればサイズが変わってるのが人間にもわかっちゃうよ
0579デフォルトの名無しさん
2007/04/10(火) 08:47:360580デフォルトの名無しさん
2007/04/12(木) 15:46:35逆に考えれば
認識できない人間を量産すればいい
0581デフォルトの名無しさん
2007/04/13(金) 08:18:190582デフォルトの名無しさん
2007/06/17(日) 12:20:260583デフォルトの名無しさん
2007/07/05(木) 11:12:510584デフォルトの名無しさん
2007/07/05(木) 21:06:43しかし、この定理に関して、私は真に驚くべき判例を見つけたが、この余白はそれを書くには狭すぎる。
そこで、私の発見した圧縮方法でこの長大な論文を圧縮してここに記す。
0
Q.E.D.
0585デフォルトの名無しさん
2007/07/05(木) 22:10:17存在はするが、母数が大きくなればそのようなビット列が現れる確率は0に収束すると考えることもできるのだ
いや、そんな気がするだけで深くは考えていないので証明は勘弁するのだ
0586デフォルトの名無しさん
2007/07/06(金) 00:40:040587デフォルトの名無しさん
2007/07/06(金) 12:34:510588デフォルトの名無しさん
2007/07/06(金) 12:51:27厳密な乱数ってのは、今までの数列から未来を予測できない。そして特定のパターン性もない。
データの圧縮ってのはデータの特徴からして、冗長な部分があるから可能なんだよ。
乱数で生成したバイト列を圧縮してみ?マジで圧縮率悪いから。
君の主張は圧縮できるほど冗長性の高いビット列が多数派ということになるが、
存在しうるバイト列のうち、冗長性の高いものは少数派だぜ。
ただ、俺らが普段使っているデータってのは意味を持つからな。だからこそ冗長性が高い。
だからこそ圧縮できるってわけだ。
0589デフォルトの名無しさん
2007/07/06(金) 13:45:050590デフォルトの名無しさん
2007/07/06(金) 22:02:59人間の目に触れる機会があるものはむしろ代数的数の方が多いとか、そんな感じか。
どんな感じだ。
0591588
2007/07/06(金) 23:11:59そんな感じだと思っていい。
俺たちが欲しがるデータってのは何らかの規則性をもったデータがほとんどだから圧縮できる。
だが、世の中に存在しうるデータの中からすればそれは激レアなんだよ。
ほとんどのパターンは単なるノイズ。
サルにキーボード叩かせて偶然シェークスピアの名作ができる可能性を考えてみろ。
神職人が苦労して意味のあるデータを紡いでるんだよ。
圧縮ってのは等価交換なんだよ。
何かを縮める代わりに何かを増やしてるんだ。
俺たちは、自分たちが使う種類のデータが縮んで、
俺たちにとってどうでもいいデータは縮まない方法を使っているんだ。
代償になっている部分、つまり圧縮しないほうがサイズ小さいよってデータは必ずある。
0592デフォルトの名無しさん
2007/07/07(土) 09:20:55人間の視覚が代数的なものしか認識出来ないってことでは?
0593デフォルトの名無しさん
2007/07/10(火) 23:23:540594デフォルトの名無しさん
2007/07/10(火) 23:44:34駄目なやつだけ実圧縮すればいいだろう
0595デフォルトの名無しさん
2007/07/10(火) 23:46:060596デフォルトの名無しさん
2007/07/11(水) 00:10:260597デフォルトの名無しさん
2007/07/11(水) 01:28:34親しい間での「あれとって」「はいよ」ってのも圧縮技術だよね。
前後の文脈と状況とで「予測の枝狩り」をした上で、さらに
お互いが脳内に保持している辞書情報を使って「解凍」している。
結局、そのときの会話以上の情報をお互いがすでに保有しているから
解凍できるのであって、圧縮というよりは通信速度の向上の話に
なっていく気もするけど、これは大容量時代を迎えた今のPC事情なら
積極的に活用していくべきだよね。
究極の圧縮言語を操るフランドルはかわいいよという話なんだけど
0598デフォルトの名無しさん
2007/07/11(水) 05:58:07例えば、一単語3バイト( 2の24乗個 )で表せるとすれば
this is a pen は、元々は、1バイト×13語 で13バイトだが
単語帳を使えば、3バイト×4単語 12バイトだ (たいして変わらんな)
日本語なら、
私はペンが大好きです は、2バイト×10語で20バイトだが
私 は ペン が 大好き です 3バイト×6単語 で18バイトだ
こっちも大して変わらんな
2語以上の頻出語のみ辞書を使うか 辞書使用ははじめの一ビットで判定して
私 は 【ペン】 が 【大好き】 【です】 括弧の部分のみ辞書(一単語2バイトとする)を使うと
17bit × 6 で102bitだ ほぼ13バイトだな
0599デフォルトの名無しさん
2007/07/11(水) 06:04:37いいんだ
これってまだ誰も実用していないだろ 作ってみるかな
0600デフォルトの名無しさん
2007/07/11(水) 06:14:02this is a pen は、 17 + 9 + 9 + 17 約12.5バイトだな
0601デフォルトの名無しさん
2007/07/11(水) 06:20:47_ (m) _ピコーン
|ミ|
/ `´ \
('A`) 「辞書を使って辞書をあssy(ry」
ノヽノヽ
くく
0602デフォルトの名無しさん
2007/07/11(水) 06:22:290603デフォルトの名無しさん
2007/07/11(水) 06:27:25そのあと通常圧縮をする
辞書がなければはじめから通常圧縮
0604デフォルトの名無しさん
2007/07/11(水) 08:32:560605デフォルトの名無しさん
2007/07/11(水) 08:43:26圧縮後 ふっくらブラジャー愛のあと
考察 人間の記憶の仕方は不思議だ
0606デフォルトの名無しさん
2007/07/11(水) 09:05:110607デフォルトの名無しさん
2007/07/11(水) 09:17:59無意味な文字8つを、何らか意味のある情景ひとつに置き換えている
0608デフォルトの名無しさん
2007/07/11(水) 09:25:40ビット単位で調べて、頻出ビット列の統計を取るんだ
そして、算術圧縮の要領で、ビット割り当てを行う
(辞書を作るときにアルゴリズムを使って割り当ててもその辞書と特許は関係ないはずだ)
そして、通常圧縮だ
0609デフォルトの名無しさん
2007/07/11(水) 12:15:37算術圧縮の意味わかってないしw
0610デフォルトの名無しさん
2007/07/11(水) 13:02:16そうだよ JPEGのビット列を調べるんだよ
種類別によって11100111がよく出てくるとか判別できるだろ
そしたらもっとも全体長が短くなるようにビットを割り当てる
0611デフォルトの名無しさん
2007/07/11(水) 13:18:00ヘッダぐらいは圧縮できるがそれは既存のアルゴリズムで十分小さくさくなる
だいたい変換後のビット列を確定するのを遅延して圧縮率高めるのが算術圧縮だろ
算術圧縮で静的な辞書つくるとかいってる時点でかなり間抜け
0612デフォルトの名無しさん
2007/07/11(水) 13:19:190613デフォルトの名無しさん
2007/07/11(水) 13:48:430614デフォルトの名無しさん
2007/07/11(水) 14:13:51>jpeg共通の特徴とか特にないの、既に圧縮されてるんだから
あるよ。
嘘だと思うなら、NASAのサイトから大き目で冗長度の高いJPGを落としてきて、
それを7zとかdgcで圧縮してごらん。ヘッダレベルでない圧縮がかかることがわかるから。
>>613
>jpgが可逆にもっと小さくなるなら、それは画像フォーマットとして使ったほうが合理的だ
可逆で小さくなるが、可搬性が失われるので利用されないだけ。
JPEG2000でも使えば良い。
0615デフォルトの名無しさん
2007/07/11(水) 14:43:280616デフォルトの名無しさん
2007/07/11(水) 14:51:37俺が書いているのは、jpeg共通の特徴であって、
jpeg共通に出てくる特徴的なビット列ではないのだが。
で、圧縮できることも示したのだから、やってみればいい。
0617デフォルトの名無しさん
2007/07/11(水) 15:05:25趣味で選んだ、このサイトの大股開きの女の子の画像がいくつまで縮められるか勝負しようぜ!
以下の画像を使用することにする
圧縮と復元ルーチンのC++のコード、合計のファイルサイズを出してくれ
http://aerobimania.ixo.jp/gymnastics3/gym3/image/202_010f.jpg
http://aerobimania.ixo.jp/gymnastics3/gym3/image/202_0110.jpg
http://aerobimania.ixo.jp/gymnastics3/gym3/image/202_0107.jpg
http://aerobimania.ixo.jp/gymnastics3/gym3/image/202_010b.jpg
http://aerobimania.ixo.jp/gymnastics3/gym3/image/202_011f.jpg
0618デフォルトの名無しさん
2007/07/11(水) 15:45:480619デフォルトの名無しさん
2007/07/11(水) 15:46:48「そうか。ふふん」
0620デフォルトの名無しさん
2007/07/11(水) 16:12:25jpegがさらに圧縮できるのは"個々"の冗長性を利用してる圧縮してるんだよ
jpeg共通の特徴なんてないの。"共通"だとか"辞書"だとか根本的に間違っるだろ
0621デフォルトの名無しさん
2007/07/11(水) 16:14:250622デフォルトの名無しさん
2007/07/11(水) 17:22:19>jpegがさらに圧縮できるのは"個々"の冗長性を利用してる圧縮してるんだよ
だから俺はそれを言っているのだが。
>jpeg共通の特徴なんてないの。"共通"だとか"辞書"だとか根本的に間違っるだろ
俺はそんな主張はしていない。俺が>>614で書いたことは、
JPEGの符号化は最適ではなく(算術圧縮でもない)、値が偏る傾向があるので、
それを「jpeg共通の特徴」としているだけ。
0623デフォルトの名無しさん
2007/07/11(水) 17:57:52他人にレス付けるときは、ちょっと前も読んで文脈を掴みましょう。
0624デフォルトの名無しさん
2007/07/11(水) 18:57:27ふが
0625デフォルトの名無しさん
2007/07/11(水) 19:07:54>>614で新しい話を始めたわけじゃないだろ。
そんなのわかってる。
文脈掴めというのなら、お前が先に掴んでやれよ。馬鹿が。
俺は608の言いたいことはわかったぞ。
0626デフォルトの名無しさん
2007/07/11(水) 20:20:10ストーリーが超圧縮されたドラマを見るんだ
0627デフォルトの名無しさん
2007/07/11(水) 20:32:26おかしな理論ぶちまけるヤツが出てくるんだがなんでなんだろうな。
jpegはDCTしてハフマンかけるからjpeg特有のビット列なんてのは
基本的に出てこないはずなんだが。
jpegが再圧縮で縮んだのならDCT後の冗長性をハフマン符号で
処理し切れなかっただけだろう。
可変長で符号化されたデータなんだから固定長でモデル化する
アルゴリズム(現存するやつほぼ全て)は効かないに決まってるんだ。
0628デフォルトの名無しさん
2007/07/11(水) 20:45:19普通に圧縮率下がってただけじゃね?
毎度毎度パッツンパッツンに圧縮かけてらんないよ
0629デフォルトの名無しさん
2007/07/11(水) 20:48:19>jpegはDCTしてハフマンかけるからjpeg特有のビット列なんてのは
>基本的に出てこないはずなんだが。
DCT後のハフマン符号がある種の傾向を持つから、元の発言者は、
それをjpeg特有のビット列と言いたいんだろ。
それぐらい理解してやれよ馬鹿。
>jpegが再圧縮で縮んだのならDCT後の冗長性をハフマン符号で
>処理し切れなかっただけだろう。
だからそんなことはわかりきっているんだってば。
>可変長で符号化されたデータなんだから固定長でモデル化する
>アルゴリズム(現存するやつほぼ全て)は効かないに決まってるんだ。
7zやdgcで5%程度縮むから、効かないわけではないし、
その効率を上げるために、元の発言者は、ビット単位を考えてるんだろ。
それぐらい理解してやれよ馬鹿。
0630デフォルトの名無しさん
2007/07/11(水) 20:58:37623じゃないけど(俺=609,611,620)
・例えば、htmlなら、いったんhtml辞書で縮めてからテキスト辞書で縮める
↓
・exe、text(日本語、英語、ドイツ語など)、html、jpegなどを
ビット単位で調べて、頻出ビット列の統計を取るんだ
そして、算術圧縮の要領で、ビット割り当てを行う
(辞書を作るときにアルゴリズムを使って割り当ててもその辞書と特許は関係ないはずだ)
↓
・種類別によって11100111がよく出てくるとか判別できるだろ
って流れだぜ。
jpegという種類によくでるビット列があって、jpeg辞書がつくれると思ってるんだぜ。
ファイル別に圧縮するのは当然可能だけど、jpeg辞書はつくれんだろ。
HTML引合いにだすくらいでやめときゃいいのに、厨まるだしじゃん。
0631デフォルトの名無しさん
2007/07/11(水) 21:10:390632デフォルトの名無しさん
2007/07/11(水) 22:20:21もう少し圧縮が効く
jpegtranとか、ハフマンテーブルを最適化してjpeg化できるプログラムもあるが、
たいていは圧縮にかかる時間と圧縮率を天秤にかけて、妥協してる
zipやrarにある「速度重視」オプションで圧縮してるようなもno
そういうの基準にしてもしょうがない
0633デフォルトの名無しさん
2007/07/11(水) 22:46:20>jpegという種類によくでるビット列があって
実際あるぞ。ハフマン符号化で圧縮しているものの癖が出るから。
0634デフォルトの名無しさん
2007/07/11(水) 23:05:16>jpeg辞書がつくれると
ちょっと意味が違うけど、エロ方面では基礎実験が進んでいる。
手持ちの画像のハッシュを集めてデータベース化し
効率よく蒐集を行うプロジェクトがある。
0635デフォルトの名無しさん
2007/07/12(木) 01:49:00そういう観点「所詮0と1のデータ」=デジタルデータであるという観点であれば、
最適な圧縮方法はあるでしょう。
そうじゃない観点=アナログデータとして扱うってことだから、これは難しいよね。
0636デフォルトの名無しさん
2007/07/12(木) 02:49:15ImageDatabaseでしょ?
あれはちょっとぜんぜん違うような
0637デフォルトの名無しさん
2007/07/12(木) 03:15:38あると言い張るならそのバイト列を示してくださいな
ヘッダを読みとばしてハフマン符号化されてる部分の統計とる
そのくらいのスクリプト位書けるでしょ?
統計的に厳密でなくても、風景人物CG等ゴチャマゼ
サイズ、jpeg圧縮率バラバラでサンプル数1万もあれば納得しますよ
0638デフォルトの名無しさん
2007/07/12(木) 10:08:16>あると言い張るならそのバイト列を示してくださいな
誰もバイト列なんて言ってないが?馬鹿じゃないのか。
それに何でお前の為にそこまでやってやらないといけないんだ?
別に論争しているわけでも論破しているわけでもないぞ。
納得できないならしなくていい。説得する気もない。
ただ、いろいろな圧縮アルゴリズムを作り、検証してきた中で
知っている情報を提供しているだけだ。
いろいろな可能性を考え、創造しようとしている奴の出鼻を挫くような奴は最低だと思う。
0639デフォルトの名無しさん
2007/07/12(木) 10:23:56そのくらい自分でやれよ・・・
反論するなら自分で検証しろよ
0640デフォルトの名無しさん
2007/07/12(木) 10:36:42証明できないなら間違ってるって認めろよ
プログラム作れてっていったってK&Rの練習問題レベル
決して無理なこと要求してるわけじゃない
言い訳ばっかりでつまんない奴だ
064110ビットの出現率を求める
2007/07/12(木) 10:42:40#include <fstream>
#include <string>
#include <vector>
#include <dir.h>
#define N 4096
using namespace std;
struct sortyou { int sum; int num;};
int comp(const void *p0, const void *q0){
struct sortyou *p = (struct sortyou *)p0;
struct sortyou *q = (struct sortyou *)q0;
if (p->sum > q->sum) return -1;
else if (p->sum < q->sum) return 1;else return 0;}
main(){
struct ffblk Fd;char tp[N];unsigned int i,n,b;
sortyou x[1024];
for(i=0;i<1024;i++){x[i].sum=0;x[i].num=i;}
findfirst("*", &Fd, 55);
do {
if((Fd.ff_attrib & FA_DIREC) != FA_DIREC){
fstream fp(Fd.ff_name,ios::in | ios::binary );if(!fp)return 0;
fp.read(tp,N);n=fp.gcount();
b=tp[0]+(tp[1]&3);x[b].sum++;
while(!fp.eof()){
for(i=10;i<8*n;i++){ b=((b<<1)&1023) + ((tp[i/8]>>(i%8))&1);x[b].sum++;}
fp.read(tp,N);n=fp.gcount();}
fp.close();}}while(!findnext(&Fd));findclose(&Fd);
qsort(x, 1024, sizeof(struct sortyou), comp);
for(i=0;i<1024;i++)cout << "bit列"<<x[i].num<<" 回数"<<x[i].sum<<endl;}
0642641
2007/07/12(木) 10:44:060643デフォルトの名無しさん
2007/07/12(木) 10:47:17間違っていなければ、jpgでやってみると0000000000( =0 )の出現率がかなり高い
0644デフォルトの名無しさん
2007/07/12(木) 10:54:32>証明できないなら間違ってるって認めろよ
もう無茶苦茶だな。
証明できない=間違っている
ではないだろ。
お前が勝手に間違っていると思うなり、証明するなり好きにすればいい。
>プログラム作れてっていったってK&Rの練習問題レベル
>決して無理なこと要求してるわけじゃない
なら、お前がやれよ。
0645641
2007/07/12(木) 10:55:390646デフォルトの名無しさん
2007/07/12(木) 10:58:40そもそも、このツールで0.1%の偏りとか検出できるの?
0.1%といっても、1MB中の1000BYTEに相当するから、統計的にはかなりのものになるが。
0647デフォルトの名無しさん
2007/07/12(木) 11:02:26例えば、ファイルの内容が
111010101111000001010101010101010101010101111001
で4bitの統計を取る場合は、
(1110)=7、 (1101)=11、 ・・をカウントしていくわけ
0648デフォルトの名無しさん
2007/07/12(木) 11:03:410649デフォルトの名無しさん
2007/07/12(木) 11:05:54それは質問の答えになっていない。
聞いているのは、検出できるのか、できないのかだ。
0650デフォルトの名無しさん
2007/07/12(木) 11:07:370000000000の出現率は2位以下の倍以上だ
0651デフォルトの名無しさん
2007/07/12(木) 11:09:07「全パターンの出現率の偏り」だが、意味がわからないですか?
0652デフォルトの名無しさん
2007/07/12(木) 11:12:36のだと前者の方が高圧縮かな?
0653デフォルトの名無しさん
2007/07/12(木) 11:17:190654デフォルトの名無しさん
2007/07/12(木) 11:36:56今度は3進数で一番縮むやつを3で置き換えれば良いと思うんだが>>1と同じだが
0655Nビットの統計を取る
2007/07/12(木) 11:53:42#include <fstream>
#include <dir.h>
#define N 4096
#define M 5
using namespace std;
struct sortyou { int sum; int num;};
int comp(const void *p0, const void *q0){
struct sortyou *p = (struct sortyou *)p0;
struct sortyou *q = (struct sortyou *)q0;
if (p->sum > q->sum) return -1;
else if (p->sum < q->sum) return 1;else return 0;}
main(){
struct ffblk Fd;char tp[N];unsigned int i,n,b=0,MM=1;
MM=MM<<M;cout <<MM<<endl;
sortyou *x= new sortyou[MM];
for(i=0;i<MM;i++){x[i].sum=0;x[i].num=i;}
findfirst("*", &Fd, 55);
do {
if((Fd.ff_attrib & FA_DIREC) != FA_DIREC){
fstream fp(Fd.ff_name,ios::in | ios::binary );if(!fp)return 0;
fp.read(tp,N);n=fp.gcount();
for(i=0;i<M/8;i++)b+=(tp[i]<<(i*8));
b+=tp[M/8]&((1<<(M%8))-1);x[b].sum++;
while(!fp.eof()){
for(i=10;i<8*n;i++){ b=((b<<1)&(MM-1)) + ((tp[i/8]>>(i%8))&1);x[b].sum++;}
fp.read(tp,N);n=fp.gcount();}
fp.close();}}while(!findnext(&Fd));findclose(&Fd);
qsort(x, MM, sizeof(struct sortyou), comp);
for(i=0;i<MM;i++)cout << "bit列"<<x[i].num<<" 回数"<<x[i].sum<<endl;}
0656デフォルトの名無しさん
2007/07/12(木) 11:55:150657改良版
2007/07/12(木) 12:07:27#include <fstream>
#include <dir.h>
#define N 4096
#define M 5
using namespace std;
struct sortyou { int sum; int num;};
int comp(const void *p0, const void *q0){
struct sortyou *p = (struct sortyou *)p0;
struct sortyou *q = (struct sortyou *)q0;
if (p->sum > q->sum) return -1;
else if (p->sum < q->sum) return 1;else return 0;}
char* bit(int x){char i,*c=new char[M+1];c[M]='\0';
for(i=0;i<M;i++)c[M-1-i]=((x>>i)&1)+'0';return c;}
main(){
struct ffblk Fd;char tp[N];unsigned int i,n,b=0,MM=1;MM=MM<<M;
sortyou *x= new sortyou[MM];for(i=0;i<MM;i++){x[i].sum=0;x[i].num=i;}
findfirst("*", &Fd, 55);
do { if((Fd.ff_attrib & FA_DIREC) != FA_DIREC){
fstream fp(Fd.ff_name,ios::in | ios::binary );if(!fp)return 0;
fp.read(tp,N);n=fp.gcount();
for(i=0;i<M/8;i++)b+=(tp[i]<<(i*8));b+=tp[M/8]&((1<<(M%8))-1);x[b].sum++;
while(!fp.eof()){
for(i=10;i<8*n;i++){ b=((b<<1)&(MM-1)) + ((tp[i/8]>>(i%8))&1);x[b].sum++;}
fp.read(tp,N);n=fp.gcount();}
fp.close();}}while(!findnext(&Fd));findclose(&Fd);
qsort(x, MM, sizeof(struct sortyou), comp);
for(i=0;i<MM;i++)cout << "bit列"<<bit(x[i].num) <<" 回数"<<x[i].sum<<endl;}
0658デフォルトの名無しさん
2007/07/12(木) 12:47:500659こんどは動くだろう
2007/07/12(木) 13:47:14#include <fstream>
#include <io.h>
#define N 4096
#define M 10
using namespace std;
struct sortyou { unsigned int sum; unsigned int num;};
int comp(const void *p0, const void *q0){
struct sortyou *p = (struct sortyou *)p0;
struct sortyou *q = (struct sortyou *)q0;
if (p->sum > q->sum) return -1;
else if (p->sum < q->sum) return 1;else return 0;}
char* bit(unsigned int x){char i,*c=new char[M+1];c[M]='\0';
for(i=0;i<M;i++)c[M-1-i]=((x>>i)&1)+'0';return c;}
main(){ struct _finddata_t Fd;long hF;
char tp[N];unsigned int i,n,b=0,MM=1;MM=MM<<M;
sortyou *x= new sortyou[MM];for(i=0;i<MM;i++){x[i].sum=0;x[i].num=i;}
hF=_findfirst("*", &Fd);
for(;;){
if(((Fd.attrib & _A_SUBDIR) == _A_SUBDIR) || Fd.size<500){_findnext(hF,&Fd);continue;}
fstream fp(Fd.name,ios::in | ios::binary );if(!fp)return 0;
fp.read(tp,N);n=fp.gcount();
for(i=0;i<M/8;i++)b+=(tp[i]<<(i*8));b+=tp[M/8]&((1<<(M%8))-1);x[b].sum++;
while(n>0){
for(i=10;i<8*n;i++){b=((b<<1)&(MM-1)) + ((tp[i/8]>>(i%8))&1);x[b].sum++;}
fp.read(tp,N);n=fp.gcount();}
fp.close();if(_findnext(hF,&Fd))break;}_findclose(hF);
qsort(x, MM, sizeof(struct sortyou), comp);
for(i=0;i<MM;i++)cout << "bit列"<<bit(x[i].num) <<" 回数"<<x[i].sum<<endl;}
0660嵐じゃないけど・・間違えた こっちで
2007/07/12(木) 14:07:23#include <fstream>
#include <io.h>
#define N 4096
#define M 5
using namespace std;
struct sortyou { unsigned int sum; unsigned int num;};
int comp(const void *p0, const void *q0){
struct sortyou *p = (struct sortyou *)p0;
struct sortyou *q = (struct sortyou *)q0;
if (p->sum > q->sum) return -1;
else if (p->sum < q->sum) return 1;else return 0;}
char* bit(unsigned int x){char i,*c=new char[M+1];c[M]='\0';
for(i=0;i<M;i++)c[M-1-i]=((x>>i)&1)+'0';return c;}
main(){struct _finddata_t Fd;long hF;
char tp[N];unsigned int i,n,b=0,MM=1;MM=MM<<M;
sortyou *x= new sortyou[MM];for(i=0;i<MM;i++){x[i].sum=0;x[i].num=i;}
hF=_findfirst("*", &Fd);for(;;) {
if(((Fd.attrib & _A_SUBDIR) == _A_SUBDIR) || Fd.size<500) {
if(_findnext(hF,&Fd))break; else continue; }
fstream fp(Fd.name,ios::in | ios::binary );if(!fp)return 0;
fp.read(tp,N);n=fp.gcount();
for(i=0;i<M/8;i++)b+=(tp[i]<<(i*8));b+=tp[M/8]&((1<<(M%8))-1);x[b].sum++;
cout<<"read..."<<Fd.name<<"\n";while(n>0){
for(i=10;i<8*n;i++){b=((b<<1)&(MM-1)) + ((tp[i/8]>>(i%8))&1);x[b].sum++;}
fp.read(tp,N);n=fp.gcount();}
fp.close();if(_findnext(hF,&Fd))break;}
_findclose(hF);qsort(x, MM, sizeof(struct sortyou), comp);
for(i=0;i<MM;i++)cout << "bit列"<<bit(x[i].num) <<" 回数"<<x[i].sum<<endl;}
0661デフォルトの名無しさん
2007/07/12(木) 14:26:327行スレで圧縮してきてくれないか
0662デフォルトの名無しさん
2007/07/12(木) 14:31:310663デフォルトの名無しさん
2007/07/12(木) 14:37:2515桁の統計
これに基づいて最適なビット割り当てを作ってくれ
0664デフォルトの名無しさん
2007/07/12(木) 16:13:37無圧縮と同じくらい負荷が軽いならアリかも知れんが。
再圧縮かけるより別のアルゴリズムで圧縮した方が縮むぞ。
0665デフォルトの名無しさん
2007/07/12(木) 16:15:01そういうことだな
しかし、textやexeは工夫する余地は多分にある
0666デフォルトの名無しさん
2007/07/12(木) 16:18:23しかし最強の可逆圧縮をするにはjpegもやらないとな
0667デフォルトの名無しさん
2007/07/12(木) 16:19:20それは別の人が高速化を考えればいい
効率と高速化、どっちも煮詰まってからが本当の勝負だろ
0668デフォルトの名無しさん
2007/07/12(木) 16:36:050669デフォルトの名無しさん
2007/07/12(木) 16:38:250670デフォルトの名無しさん
2007/07/12(木) 18:20:490671書き込みブラウザ
2007/07/12(木) 19:27:070672デフォルトの名無しさん
2007/07/12(木) 20:32:30[JPEG写真のみ26MB]
bit列000000000000000 回数223127
bit列111111100000000 回数109291
bit列111111110000000 回数109270
bit列111111111000000 回数59070
bit列111111000000001 回数58252
bit列111111000000000 回数56119
bit列011111111000000 回数54578
bit列000000010000000 回数41782
…(ry
ぱっとみ数%程度の圧縮にしかならん。その分次の段の圧縮率が下がるんだし
何もしないで、そのまま7Zにでも通したほうがいい
0673デフォルトの名無しさん
2007/07/12(木) 20:38:46>ぱっとみ数%程度の圧縮にしかならん。その分次の段の圧縮率が下がるんだし
まあ、そうだが、わずかでも、特徴があるのと、圧縮できることは証明されたな。
誰も大幅に圧縮率が上がるなんていってないし。
0674デフォルトの名無しさん
2007/07/12(木) 21:37:26んなこたない。
a.jpg 92329b →a.jpg.zip 92437b(非圧縮)→ a.jpg.zip.7z 89987b
a.jpg 92329b →a.jpg.zip 90232b(最高圧縮)→ a.jpg.zip.7z 91526b
つまり、圧縮を2度やるより何もしないほうがいい。
前段の圧縮される分<後段の圧縮量を下げる分
ということになったら前段は圧縮とはいえない。
0が並んでるところは、まさに後段で圧縮される予定の部分と思われ、
数%なら"辞書"が外に出せるメリットより、2重圧縮のデメリットが
勝ってしまう可能性大。ほぼ無意味なことが証明されたと思うが
0675バグ修正 16桁以上も計算可
2007/07/12(木) 22:45:29#include <fstream>
#include <io.h>
#define N 16384
#define M 18
using namespace std;
struct sortyou { unsigned int sum; unsigned int num;};
int comp(const void *p0, const void *q0){
struct sortyou *p = (struct sortyou *)p0;struct sortyou *q = (struct sortyou *)q0;
if (p->sum > q->sum) return -1;else if (p->sum < q->sum) return 1;else return 0;}
char* bit(unsigned int x){char i,*c=new char[M+1];c[M]='\0';
for(i=0;i<M;i++)c[M-1-i]=((x>>i)&1)+'0';return c;}
main(){struct _finddata_t Fd;long hF;
char tp[N];unsigned int i,n,b=0,MM=1;MM=MM<<M;
sortyou *x= new sortyou[MM<<1];
for(i=0;i<MM;i++){x[i].sum=0;x[i].num=i;}
hF=_findfirst("*", &Fd);for(;;) {
if(((Fd.attrib & _A_SUBDIR) == _A_SUBDIR) || Fd.size<500) {
if(_findnext(hF,&Fd))break; else continue; }
fstream fp(Fd.name,ios::in | ios::binary );if(!fp)return 0;
fp.read(tp,N);n=fp.gcount();
for(i=0;i<M/8;i++)b+=(((unsigned char)tp[i])<<(i*8));
b+=(((unsigned char)tp[M/8])&((1<<(M%8))-1));x[b].sum++;
cout<<"read..."<<Fd.name<<"\n";while(n>0){
for(i=10;i<8*n;i++){b=((b<<1)&(MM-1)) + ((tp[i/8]>>(i%8))&1);x[b].sum++;}
fp.read(tp,N);n=fp.gcount();}
fp.close();if(_findnext(hF,&Fd))break;}
_findclose(hF);qsort(x, MM, sizeof(struct sortyou), comp);
for(i=0;i<MM;i++)cout << "bit列"<<bit(x[i].num) <<" 回数"<<x[i].sum<<endl;}
0676デフォルトの名無しさん
2007/07/12(木) 23:07:53長くて読む気しないので7行で頼む
0677ちょっと短くなった
2007/07/12(木) 23:43:59#include <io.h>
#include <algorithm>
#include <vector>
#define M 5
using namespace std;
struct sy { unsigned int sum; unsigned int num;};
bool comp(const sy& l, const sy& r){ return l.sum > r.sum;}
char* bit(unsigned int );
main(){
struct _finddata_t Fd; long hF;
char tp[16384];unsigned int i,n,b=0,N=1;N=N<<M;vector<sy> x;
for(i=0;i<N;i++){sy y;y.sum=0;y.num=i;x.push_back(y);}
hF=_findfirst("*", &Fd);for(;;) {
if(((Fd.attrib & _A_SUBDIR) == _A_SUBDIR) || Fd.size<500){
if(_findnext(hF,&Fd))break;else continue;}
fstream fp(Fd.name,ios::in | ios::binary );if(!fp)return 0;
fp.read(tp,16384);n=fp.gcount();
for(i=0;i<M/8;i++)b+=(((unsigned char)tp[i])<<(i*8));
b+=(((unsigned char)tp[M/8])&((1<<(M%8))-1));x[b].sum++;
cout<<"read..."<<Fd.name<<"\n";while(n>0){
for(i=10;i<8*n;i++){b=((b<<1)&(N-1))+((tp[i/8]>>(i%8))&1);x[b].sum++;}
fp.read(tp,16384);n=fp.gcount();}
fp.close();if(_findnext(hF,&Fd))break;}
_findclose(hF);
sort(x.begin(),x.end(),comp);
for(i=0;i<N;i++)cout << "bit列"<<bit(x[i].num) <<" 回数"<<x[i].sum<<endl;}
char* bit(unsigned int x){char i,*c=new char[M+1];c[M]='\0';for(i=0;i<M;i++)c[M-1-i]=((x>>i)&1)+'0';return c;}
0678もっと短くなった
2007/07/13(金) 00:08:29#include <io.h>
#include <algorithm>
#include <vector>
#define M 10
using namespace std;
struct sy { unsigned int s; unsigned int n;};
bool comp(const sy& l, const sy& r){return l.s > r.s;}
char* bit(unsigned int );
main(){
struct _finddata_t Fd; long hF;
char tp[16384];unsigned int i,n,b=0,N=1;N=N<<M;vector<sy> x;
for(i=0;i<N;i++){sy y;y.s=0;y.n=i;x.push_back(y);}
hF=_findfirst("*", &Fd);for(;;){
if(((Fd.attrib>>4)&1)==1||Fd.size<500){
if(_findnext(hF,&Fd))break;else continue;}
fstream fp(Fd.name,ios::in | ios::binary );if(!fp)return 0;
cout<<"read..."<<Fd.name<<"\n";for(;;){
fp.read(tp,16384);n=fp.gcount();if(n<1)break;
for(i=0;i<8*n;i++){b=((b<<1)&(N-1))+((tp[i/8]>>(i%8))&1);x[b].s++;}}
fp.close();if(_findnext(hF,&Fd))break;}
_findclose(hF);sort(x.begin(),x.end(),comp);
for(i=0;i<N;i++)cout << "bit列"<<bit(x[i].n) <<" 回数"<<x[i].s<<endl;}
char* bit(unsigned int x){char i,*c=new char[M+1];c[M]='\0';
for(i=0;i<M;i++)c[M-1-i]=((x>>i)&1)+'0';return c;}
0679デフォルトの名無しさん
2007/07/13(金) 10:00:53>a.jpg 92329b →a.jpg.zip 92437b(非圧縮)→ a.jpg.zip.7z 89987b
誰もzipで圧縮するなんて話はしてないし、
jpegが7zで圧縮できると証明できているじゃん。
jpegに冗長性があるわけだし、ビット列に特徴があるのも証明されたことになるよ。
圧縮率は微々たるものだが、間違ってはいなかったってことだ。
0680デフォルトの名無しさん
2007/07/13(金) 10:15:430681デフォルトの名無しさん
2007/07/13(金) 11:01:20だから逆にJPEGのハフマン符号(とランレングス圧縮)だけ展開して、
高圧縮でやりなおすのが直感的には正しいと思う
0682デフォルトの名無しさん
2007/07/13(金) 11:18:25それは正しいとかどうかでは無いね。
それをやったら、jpegの圧縮ではなく、別の画像圧縮形式の提案になる。
一連の話はjpegをさらに圧縮できるかどうかだし、特徴のあるビット列があるかどうか論点だった。
結論としては、圧縮率は微々たる物だが、特徴のあるビット列が存在することは証明された。
0683デフォルトの名無しさん
2007/07/13(金) 11:28:247z のレンジコーダ部分、 zipのハフマン部分だけで圧縮してて
両方とも lz部分は役に立ってない可能性がある。
んで、lz部分が役に立ってるなら特徴のあるビットデータがあると言えるかもしれんが
ハフマンとかレンジコーダで圧縮してる場合はデータに偏りがある(例えば00やFFが多い)ぐらいしか言えない。
経験的に、あまり圧縮できないファイルではlzが役に立ってない事が多い。
0684デフォルトの名無しさん
2007/07/13(金) 11:42:31>jpgをzipで圧縮可能 or jpgを7zで圧縮可能≠特徴のあるビット列が存在する
誰も圧縮可能だからという理由で、ビット列があるとは主張していないよ。
「特徴のあるビット列」はツールを実行することで証明されただけ。
結論としては、圧縮率は微々たる物だが、特徴のあるビット列が存在することは証明された。
0685デフォルトの名無しさん
2007/07/13(金) 11:44:490686デフォルトの名無しさん
2007/07/13(金) 11:48:360687デフォルトの名無しさん
2007/07/13(金) 11:52:28ん? あぁ、すまん。議論見てなかった。
ビット列に いくらかの特徴はあるのかもしれんが、
頑張ってjpg専用辞書作るに値するような特徴だとは思えないけど。
ちなみに、jpg専用辞書作ったらzipや7zに比べて大幅な圧縮率の改善を期待できると思う?
0688デフォルトの名無しさん
2007/07/13(金) 11:56:33同一ファイルでなくても、複数ファイルにわたって同一の部分ビット列が存在することはさらに多い
データの保安性とのトレードオフがあるだろうけど、こういうの数を減らすことができたら効率良いよね
最近どこかで聞いた話だけど
0689デフォルトの名無しさん
2007/07/13(金) 12:08:280690デフォルトの名無しさん
2007/07/13(金) 16:43:29状況を限定すれば効果があるかもしれない
特定のジャンルの画像で辞書が似てるものをひとまとめにして
専用の辞書を作りそれを配布することで画像そのものの
ファイルサイズは小さく出来るかもしれない。
というわけでこのスレを借りて、フランドルの画像を集めるところから
はじめてみよう
0691デフォルトの名無しさん
2007/07/14(土) 09:47:39ハフマンの圧縮率下げてスピード優先にしてるんだから、
圧縮する余地が残っているのは自明なんだと思ってたが
0692デフォルトの名無しさん
2007/07/14(土) 10:03:03どうやってるのかね
(C++読めんのよ・・・)
0693デフォルトの名無しさん
2007/07/14(土) 22:06:10その上で圧縮率最高とかのときの話になってるのだと思ったけど。
ところでフランドル画像はまだ?
0694デフォルトの名無しさん
2007/07/14(土) 22:47:01ここで特徴が〜とかいってる人。
それを分かった上で〜とかいってるのって正直電波としか思えない。
なんつーかアルゴリズムを変えて圧縮を繰り返せば
限りなくエントロピーに近づけるとか考えてそうな感じ。
頼むからもっと勉強してくれよ。
0695デフォルトの名無しさん
2007/07/14(土) 22:59:27究極の圧縮ソフトということにしたらよかったのに
0696デフォルトの名無しさん
2007/07/14(土) 23:06:20八百屋でケチな主婦が30分くらいかけて野菜を1円単位で値切って
買ってきてこんなに安くなった!みたいな。
でも隣町のスーパーでもっと安く売ってたみたいな。
いや個人的にはたまには八百屋助けてやれよとか思わないでもないけど
まあ世の中合理化の時代だし競争力がないもんが淘汰されるのは仕方ないかなぁ。
潰れてビルが建ったほうが実は世のためなのかもしれないとか考えるんだけど
それってやっぱ冷たい都会の人の考えなのかとか。
でも土地持ちだったら実はウハウハだったかもしれなくて同情の余地はないのかも
とか思うんだけどそんなプライベートなことは分かんないし、
見た目にはやっぱ大変そうに見えたりもするんだけどまあやっぱ他人事だから
仕方ないんだろうなぁとか思ったりするよね。
そんな感じ。
0697デフォルトの名無しさん
2007/07/14(土) 23:29:39うだうだ値切ってる時間あったら他の仕事して儲けろ
0698デフォルトの名無しさん
2007/07/14(土) 23:49:12その考えも大事だけど、実務ではなく研究が目的なら
値切りの真理を最後まで追究するのがサイエンティスト道
0699デフォルトの名無しさん
2007/07/15(日) 00:27:15それを他人が勝手にやってくれると期待して理屈だけ語ってるのでなければ。
他人のやる事に否定的なコメントをつけるのは、時間の無駄を心配する卒塔婆心か
否定する事で自分を優位と思い込みたい虚栄心か、そのいずれかだろう。
あまりクドクド否定する、それも出来るか出来ないか研究してる相手に、
数%で得か損かのような話をしてもしょうがあるまい。
0700デフォルトの名無しさん
2007/07/15(日) 00:32:210701デフォルトの名無しさん
2007/07/16(月) 11:49:500702デフォルトの名無しさん
2007/07/16(月) 23:17:220703デフォルトの名無しさん
2007/07/17(火) 01:04:020704デフォルトの名無しさん
2007/07/17(火) 01:16:51検証用のツール用意されたら
捨て台詞吐いて逃げた
0705デフォルトの名無しさん
2007/07/17(火) 02:04:080706デフォルトの名無しさん
2007/08/15(水) 02:09:19KGBとかGCAとかバカみたいに遅いしマジ最悪
並の圧縮率で超高速なアーカイバが最強でしょ
0707デフォルトの名無しさん
2007/08/15(水) 03:46:50宇宙からの通報とか。
0708デフォルトの名無しさん
2007/08/15(水) 22:22:46という題名のWebページを先日見つけた
0709デフォルトの名無しさん
2007/08/16(木) 23:48:090710デフォルトの名無しさん
2007/08/17(金) 00:53:59火星いったやつも 10Kbps とかだろ
圧縮技術が無いと宇宙じゃどうにもなんないな
0711デフォルトの名無しさん
2007/08/17(金) 01:37:460712デフォルトの名無しさん
2007/08/17(金) 01:51:530713デフォルトの名無しさん
2007/08/17(金) 02:48:56http://pc11.2ch.net/test/read.cgi/desktop/1109102136/l50
0714デフォルトの名無しさん
2007/08/17(金) 07:56:000715デフォルトの名無しさん
2007/08/17(金) 17:13:22MTFの文字列をつかっての大まかな方法はわかったのですが、
これをバイナリで実行する場合、実際のデータと辞書内のインデックスを見分けるにはどうしたらいいのでしょうか?
初めは1バイト単位でやろうと思ってたのですが、これ自体が間違っているのでしょうか?
0716デフォルトの名無しさん
2007/08/17(金) 20:16:46最近、職場で「出戻り寄生派遣」という言葉が囁かれています。
派遣契約を切られたにもかかわらず「次の派遣先でも切られてしまって生活できません」
などと 言って泣き落としで現場マネージャーにすら一切話がないまま再派遣契約した人のことです。
今月初め、半年前に切った派遣が出社してきてマネージャーも含めみんなびっくりしました。
影でコソコソ偉い人に泣きついて再契約したそうです。同じ部署の人には黙って・・・
そんなことまでして自宅の近くの派遣先にこだわって人間として恥ずかしくないのですか。
仕事に必要な技術がなく勉強する気もないのを逆手にとって
「私のような人の視点で仕事をすることも大切だと思います」と挨拶された時には
みんな凍りついていました。派遣でスキルアップとか言ってる癖に以前と同じように
技術を勉強する気はなく「それは私の仕事ではありません」の一点張り、
派遣で収入アップとか言ってる癖に時給は前回と同じで喜んで再契約。
結局、なんの努力もせずに派遣で安直に収入を得たいだけじゃないですか。
身分不相応な商品のローンを払うために派遣だと当然足りない収入は親にも寄生して、
いつ切られるんじゃないかとビクビクしながら人事権のある人間とだけ仲良くし、
契約終了を通知されれば泣き落とし。悲惨な人生ですね。
氏んだほうがいいんじゃないですか。
0717デフォルトの名無しさん
2007/08/17(金) 20:20:07区別の必要がなくなる。ただBLOCK SORTINGと組み合わせないで
MTF単体でつかうとLZ系よりかなり圧縮率悪いから実用的じゃない
0718デフォルトの名無しさん
2007/08/17(金) 22:07:25新しいデータが出る度に追加するんじゃなくて、初めから全てセットしておくんですね。
やっと実際に使えるようになりそうです。
BWTの方は比較的楽に理解できたのですが、MTFはどうしても分からなかったので…
BWTのみにしようかと諦めていたので助かりました。
ありがとうございました。
0719デフォルトの名無しさん
2007/08/18(土) 06:38:50MTFは実装は簡単だけど圧縮率も速度もそれほど良くないから注意な。
0720デフォルトの名無しさん
2007/08/19(日) 12:13:280721デフォルトの名無しさん
2007/08/23(木) 19:50:340722デフォルトの名無しさん
2007/08/23(木) 19:58:46超大雑把に言えばそう。
0723デフォルトの名無しさん
2007/08/23(木) 20:39:000724デフォルトの名無しさん
2007/08/23(木) 21:07:510725デフォルトの名無しさん
2007/08/29(水) 00:35:030726画像処理の510
2007/08/31(金) 16:19:39http://pc11.2ch.net/test/read.cgi/tech/1183910525/510
よろしくお願いします。
0727デフォルトの名無しさん
2007/08/31(金) 17:08:39こっちもスレ違いだ。そんなの最強でもなんでもない。圧縮復元相談スレにしてくれ。
0728デフォルトの名無しさん
2007/09/01(土) 04:52:06シャノンの理論の限界を超えることはできないんだよね?
0729デフォルトの名無しさん
2007/09/01(土) 13:37:51最強とは適材適所に特化したアルゴリズムであり汎用ではない。
1万種類の目的別素材があれば、それら全てに特化したアルゴリズムが
1万種類必要になるということだ。圧縮する素材より複雑で、データ量が
肥大しているものこそ圧縮率は高い。
決まった仕組や特徴に対して汎用の圧縮をするのは高圧縮としては無駄の
域になるんじゃないか?
0730デフォルトの名無しさん
2007/09/01(土) 13:59:46アカシックレコードを内蔵していれば、どんなファイルも100バイト程度に圧縮できる。
0731デフォルトの名無しさん
2007/09/01(土) 14:11:240732デフォルトの名無しさん
2007/09/01(土) 15:43:09無理無理
アカシックレコードがあったとして、
そのインデックスが何バイトになると思ってるんだよ
ちなみに円周率のランダムに並ぶ数字を使って圧縮するのも同じ
0733デフォルトの名無しさん
2007/09/01(土) 20:32:59だから100バイト程度あれば充分だろ。
人類が作れるファイルの数を計算してみろ。
0734デフォルトの名無しさん
2007/09/01(土) 20:35:59つまりいずれは 8の100乗バイト をインデックスだけで消費しちゃうよね
という話じゃね?
0735デフォルトの名無しさん
2007/09/01(土) 20:57:200736デフォルトの名無しさん
2007/09/01(土) 21:46:01完全なスライド辞書圧縮とか?
0737デフォルトの名無しさん
2007/09/01(土) 21:48:16lzxかな。そこまで圧縮率良い訳では無いけど。
あとはtek系はどうなんだろ…。
0738デフォルトの名無しさん
2007/09/01(土) 22:01:330739デフォルトの名無しさん
2007/09/02(日) 05:12:01でかい辞書をどこかに置いておいて個々の圧縮ファイルがそれを参照するやつ。
0740デフォルトの名無しさん
2007/09/02(日) 05:17:280741デフォルトの名無しさん
2007/09/02(日) 06:25:460742デフォルトの名無しさん
2007/09/03(月) 13:59:03winnyのアーキテクチャ利用して、圧縮解凍ソフトって作れないんだろうか
0743デフォルトの名無しさん
2007/09/04(火) 11:10:520744デフォルトの名無しさん
2007/09/04(火) 11:19:350745デフォルトの名無しさん
2007/10/14(日) 05:34:240746デフォルトの名無しさん
2007/10/14(日) 16:45:000747デフォルトの名無しさん
2007/10/14(日) 17:14:370748デフォルトの名無しさん
2007/10/17(水) 07:53:24問題は使われている技術が応用可能かどうかだ
0749デフォルトの名無しさん
2007/10/22(月) 10:40:21よ書いてみる
0750デフォルトの名無しさん
2007/10/28(日) 04:55:190751デフォルトの名無しさん
2007/10/28(日) 09:08:33>>742
0752デフォルトの名無しさん
2007/10/28(日) 09:10:31winnyや、shareの場合、ダウンロードされたときにしか、拡散しない(アップロードしない)はずだから、
圧縮しようとした時に、ローカルにキャッシュが生成されるだけで、
圧縮にはならない。
圧縮時に、強制的に、他のp2pクライアントにアップロードする必要がある
0753デフォルトの名無しさん
2007/10/30(火) 01:17:03アップロードすればいいんじゃない?
0754デフォルトの名無しさん
2007/11/01(木) 21:35:300755デフォルトの名無しさん
2007/11/03(土) 12:00:56自分のPCさえ、容量が少なくなればそれでいい
0756デフォルトの名無しさん
2007/11/03(土) 12:51:29http://pc11.2ch.net/test/read.cgi/tech/1191860116/38
0757デフォルトの名無しさん
2007/11/03(土) 22:52:250758デフォルトの名無しさん
2007/11/04(日) 01:50:07gqSCsYLGgvCBSSANCg0KiX6O/JemgsaCooKkiWmLdoLJkbGC
rY+skJQgDQozLjE0MTU5MjaBYyANCg0KgrGC6oLMj6yQlJNf
keY5MzI5OTI0MYyFltqCqYLnkOaC8ILdgsSC2YK1gqIgDQqB
YzA3MjE0NTQ1MjU1MjA4NzcxMzYzNzUxNTaBYyANCo3Fj4mC
zDiVto6agsmShZbagr6BQiANCoK7gqQiMDcyMTQ1NDUigsaC
zYF1g0mDaYNqgVuCtYKxgrWCsYF2gsyCsYLGgqCC6YFCIA0K
DQqCsYLqgs2Cx4KkgqKCpIKxgsaCvoFIIA0KkF+CzYnkgViC
yYm9gvCRaYKmguaCpILGgrWCxIKigumC8YK+gWMgDQqI6pHM
gUGJvYLwgseCpI1sgqaC6oLOgWMgDQoNCg0KDQoNCoLIgUGC
yILxgr6CwYLEgVuBSYFJIA0KgUCBX4FAgUCBQIFAgUCBQIFA
gUCBXoFAgUAgDQqBQIFAgUCBQIO2g7aDtiANCg==
0759デフォルトの名無しさん
2007/11/04(日) 16:42:04オナニーってでるぜ
0760デフォルトの名無しさん
2007/11/04(日) 19:22:270761デフォルトの名無しさん
2007/12/08(土) 12:29:06多いと思うんだよね・・・
リビングストン大佐がアーカードだったりするのもその一つかと。
作品単体で観ても確かに普通に面白いんだけど、それを踏まえないと
もったいない気がする。キスの天ぷらをポン酢で食べちゃうような感じ。
0762デフォルトの名無しさん
2007/12/15(土) 18:47:440763デフォルトの名無しさん
2007/12/15(土) 21:21:07http://internet.watch.impress.co.jp/cda/news/2007/09/25/16977.html
これはかなり参考になる
0764デフォルトの名無しさん
2007/12/15(土) 22:35:47こういうの分からないっていう人はIQ低いと思う。
0765デフォルトの名無しさん
2007/12/15(土) 23:56:23とっかかりになる知識があればいいけどね
kskとか知ってればgkbrとか応用できるけど
0766デフォルトの名無しさん
2007/12/16(日) 00:07:05wktkかmjkあたりだと思ってた
0767デフォルトの名無しさん
2007/12/16(日) 00:12:05もっとも非可逆になるかも知れんが。
0768デフォルトの名無しさん
2007/12/16(日) 00:37:590769デフォルトの名無しさん
2007/12/16(日) 00:44:260770デフォルトの名無しさん
2007/12/16(日) 18:10:31IQ高い人はgkbrをゴキブリとも読めたりする。
0771デフォルトの名無しさん
2007/12/16(日) 20:24:16"g"一文字で5通り、"gkbr"なら、5x5x5x5=625通り。
"gkbr"を「ごきぶり」と読めるのと同じぐらい、「画家ぶる」と読んでもおかしくない。
0772デフォルトの名無しさん
2007/12/16(日) 20:58:060773デフォルトの名無しさん
2007/12/16(日) 21:26:43不可逆圧縮と見てもいいけど。
そういう意味から言えばハッシュ==不可逆圧縮なのかもしれんな。
0774デフォルトの名無しさん
2007/12/16(日) 22:04:33母音が全部消えるなら 後家いびり でもok。
0775デフォルトの名無しさん
2007/12/16(日) 22:56:39なに言ってるんだ。
文脈的にゴキブリじゃ意味が通らないことぐらいは分かるだろ。
文法的にも、文章の一番最後に置いて「ケリを付ける」用法の単語なんだから
「ガクブル」だと類推できそなもんだが。
まあ、前提として「ガクブル」の単語と用法を理解してないとダメだけどな。
0776デフォルトの名無しさん
2007/12/17(月) 15:44:38覗いてる掲示板の傾向とか、そっち方面からの類推で。
0777デフォルトの名無しさん
2007/12/17(月) 21:10:51モノの括り方が必要だと思うな。
0778デフォルトの名無しさん
2007/12/17(月) 23:05:05がヒトラーだったりするわけだろ。
0779デフォルトの名無しさん
2007/12/17(月) 23:08:020780デフォルトの名無しさん
2007/12/17(月) 23:15:15品行方正なら本を焼いたり人を焼いたりはしないけどね
0781デフォルトの名無しさん
2007/12/17(月) 23:19:20新しいのは難しいんでないの?
0782デフォルトの名無しさん
2007/12/17(月) 23:24:44・順次
・反復
・分岐
のことかとオモタ俺
たしかに全てはこの応用なんだが
0783デフォルトの名無しさん
2007/12/18(火) 11:34:100784デフォルトの名無しさん
2007/12/18(火) 12:08:190785デフォルトの名無しさん
2007/12/20(木) 16:41:25名古屋駅近辺でお話しましょう
0786デフォルトの名無しさん
2007/12/21(金) 18:03:560787デフォルトの名無しさん
2007/12/23(日) 03:59:30http://www.c10n.info/archives/720
0788デフォルトの名無しさん
2007/12/23(日) 21:11:37ttp://slashdot.jp/~tt/journal/425221
256MBも食う糞アルゴリズムは要らない
0789デフォルトの名無しさん
2007/12/23(日) 23:28:06手元でコンパイルして試したけど全然使わんぞ
1.5MBぐらい、算術符号使うと1/3ぐらいになる
0790デフォルトの名無しさん
2007/12/23(日) 23:30:260791デフォルトの名無しさん
2007/12/25(火) 16:15:420792デフォルトの名無しさん
2007/12/26(水) 00:43:54パテントフリーとかを考えてる人にとっては嬉しいのでは?
256MBってのはhttp://cs.fit.edu/~mmahoney/compression/にあるPAQの事だと思うが、
記事自体とはあまり関係ない
0793デフォルトの名無しさん
2008/01/02(水) 16:51:57直感で言うが、and,notの他に、回転演算(ローテートって言うんか?)が必要じゃないかと
シフト演算は回転演算とandがあれば十分実装できるけど、andとnotじゃ足し算も難しい気が
0794デフォルトの名無しさん
2008/01/02(水) 19:01:490795デフォルトの名無しさん
2008/01/02(水) 21:42:36ド・モルガンの法則って小学校か中学校か高校か大学で習わなかったか?
andとnotがあればorも作れるし、and,or,notがあれば加算器も作れる。
0796デフォルトの名無しさん
2008/01/03(木) 00:41:510797デフォルトの名無しさん
2008/01/03(木) 00:48:050798デフォルトの名無しさん
2008/01/03(木) 00:56:170799デフォルトの名無しさん
2008/01/03(木) 07:46:010800デフォルトの名無しさん
2008/01/03(木) 07:56:120801793
2008/01/08(火) 00:55:03いや、ドモルガンなら分かるが、随分習う時期に幅があるな。
試しにand、or、notだけで加算機を作ってみてくれないか。頼むから。
C言語で宜しく。
どれもこれも他のbitに影響されない演算だから、それらのみを組み合わせても
足し算に必要な繰り上がりが出来ない気がするんだが。
0802デフォルトの名無しさん
2008/01/08(火) 01:06:450803デフォルトの名無しさん
2008/01/08(火) 01:19:57これか?
ttp://jp.youtube.com/watch?v=XICtHIuZ1u4
0804デフォルトの名無しさん
2008/01/08(火) 01:23:260805デフォルトの名無しさん
2008/01/08(火) 01:57:42単純に、あるビットからのキャリを次のビットに加算するだけだが。
擬似コードだがこんな感じで。
bit xor(bit a, bit b) {return a & ~ b | ~ a & b;} // xorの実装((a and (not b)) or ((not a) and b))
c:0 = a:0 & b:0;
na:0 = xor(a:0, b:0);
c:1 = a:1 & b:1 | a:1 & c:0 | b:1 & c:0;
na:1 = xor(xor(a:1, b:1), c:0);
c:2 = a:2 & b:2 | a:2 & c:1 | b:2 & c:1;
na:2 = xor(xor(a:2, b:2), c:1);
...
あとは必要なだけ並べればいい。
0806デフォルトの名無しさん
2008/01/08(火) 02:47:39数式より回路図の方が見やすいだろう。
ttp://ja.wikipedia.org/wiki/%E5%8A%A0%E7%AE%97%E5%99%A8
俺は加算器とフリップフロップを知ったときは、仕組みの単純さと
論理の美しさに感動したな。
794が言うように、NANDがあれば何でもできる。
0807デフォルトの名無しさん
2008/01/08(火) 03:19:21一方を複数組み合わせてANDもORも作れるから。
スレ違いついでに、命令セットは1種類でおkな話
http://en.wikipedia.org/wiki/One_instruction_set_computer
0808デフォルトの名無しさん
2008/01/08(火) 03:27:240809デフォルトの名無しさん
2008/01/11(金) 20:31:450810デフォルトの名無しさん
2008/01/11(金) 20:34:28>スレ違いついでに、命令セットは1種類でおkな話
>ttp://en.wikipedia.org/wiki/One_instruction_set_computer
↓こいつがその実装例だよな
ttp://www.amazon.co.jp/products/dp/4839909865
インストラクションに別名付いてるけど実質1セット
0811デフォルトの名無しさん
2008/01/11(金) 21:07:50シフト、ローテートは物理的に配線をずらして繋げばおk、ゲートは不要。
念のため。
0813デフォルトの名無しさん
2008/01/18(金) 19:40:18定数シフトはね
0814デフォルトの名無しさん
2008/01/18(金) 21:09:34繰り返しやセレクタは、また別の話だろうな。
0815デフォルトの名無しさん
2008/02/03(日) 22:20:52バレルシフタってあるんですけど。
0816デフォルトの名無しさん
2008/02/03(日) 23:40:17>>814
バレルシフタは結局はnビットシフタとセレクタだ。
0817デフォルトの名無しさん
2008/02/17(日) 13:53:36無数の対象に無数の最強アルゴリズムが存在する。
つまり最強になれる対象が一つもないアルゴリズムは糞ということだ。
0818デフォルトの名無しさん
2008/02/17(日) 14:07:39たとえば全てに対して2位を取れたらそれはすばらしい物だと思わないか?
0819デフォルトの名無しさん
2008/02/17(日) 14:16:44評価基準を変えればどんなものであっても一位になれる
極論でいうと「xxx に対する圧縮率が xx% に一番近くなるアルゴリズム」
0820デフォルトの名無しさん
2008/02/18(月) 20:26:49一般的に、単一ファイルを圧縮してまとめるよりも
全ファイルをまとめて圧縮する方が、辞書が共通化できたりして圧縮率が良い。
.cabや.tar.gz、solidな.rarなど。
操作性は悪くなるけど。
ということは、同じ複数ファイル一括であっても、
似たようなファイルを優先して近辺に圧縮すれば
さらに僅かに圧縮率が向上するのではなかろうか。
asciiテキストとSJISテキストとバイナリとか。
あるいは、辞書だけでなくハフマン符号もタイプ別に持ったりとか。
アルゴリズムとは関係ないけど。
0821デフォルトの名無しさん
2008/02/18(月) 20:43:52離れてても十分有効なこともある
0822デフォルトの名無しさん
2008/02/18(月) 21:11:09これはまだ誰もやってないと思うよ 作ってみれば
0823デフォルトの名無しさん
2008/02/18(月) 21:13:23たとえばS-JISでもHTMLやC++やXMLとかまた別の分類があるし言語の分類もあるしどのくらい分類するのが良いのかある
でももっとも減らせる所を減らすべき
たとえばexeとかDLLとかもともとサイズが大きいやつ テキストは1M以上は少ない
0824デフォルトの名無しさん
2008/02/18(月) 21:20:16dgcaがやってるらしい
0825デフォルトの名無しさん
2008/02/18(月) 21:27:46辞書を用意しようとすると始めに分類しないといけない
類似度を測るにはベクトル空間モデルがいいと思うよ
ttp://ja.wikipedia.org/wiki/%E3%83%99%E3%82%AF%E3%83%88%E3%83%AB%E7%A9%BA%E9%96%93%E3%83%A2%E3%83%87%E3%83%AB
0826デフォルトの名無しさん
2008/02/18(月) 21:59:57何Kバイトずつに区切るとか、ブロックソーディングのあとにどのような圧縮するかで変わるし
0827デフォルトの名無しさん
2008/02/18(月) 22:31:26コードはともかく、リソースは、文字かその他かという分類もあるし。
ただ、こちらは外部から見て文字か画像か等を判別するのは無理かな。
0828デフォルトの名無しさん
2008/02/18(月) 22:59:580829デフォルトの名無しさん
2008/02/19(火) 09:59:50最高ではないだろうし、最高だとは誰も思ってないよ。
ただ、言えることは、まだ誰もやってないことではなく、
誰もがやったようなありふれたことだってこと。
正直、あまりにも時代遅れ。まあ、自分でいろいろやってみることには価値があるけどね。
0830デフォルトの名無しさん
2008/02/20(水) 16:05:49cab、7zipあたりもやってるみたい
同じファイルばっかりだと異様にちぢむし
0831デフォルトの名無しさん
2008/02/28(木) 01:51:08#include <iostream>
#include <string>
#include <set>
using namespace std;
class gou{
public: string str; int num;
gou(string a, int b){str=a; num=b;}
bool operator<(const gou& a)const{return str<a.str;}};
main(){
int sz=10000,n;
string a(sz,'\0');
for(n=0;n<sz;n++)a[n]=rand()&255;
multiset<gou> s;
for(n=0;n<sz;n++){ s.insert(gou(a,n)); a=a.substr(1)+a[0];}
multiset<gou>::iterator p;
for(p= s.begin(); p!=s.end(); p++ )
printf("元の位置=%6d ソート後の末尾= %3d\n",p->num,(unsigned char)p->str[sz-1]);
}
0832デフォルトの名無しさん
2008/02/29(金) 15:47:530833デフォルトの名無しさん
2008/03/01(土) 22:04:10a(n) < a(n+1)である番号に対して、それをファイルnへ書き出す
ファイルnごとにそれをソートする
未ソートなのはa(n) < a(n+1)とa(n) = a(n+1)だ
初めにソートした結果から、その一つ前が先頭より大きいものは
自然並べればソートできている あとは連続する部分だがそれは簡単
0834デフォルトの名無しさん
2008/03/01(土) 22:05:090835デフォルトの名無しさん
2008/03/02(日) 14:47:21ttp://homepage3.nifty.com/wpage/index.html
0836デフォルトの名無しさん
2008/03/02(日) 21:03:24Home pageの主?情報交換しよう 10Gでもまとめてしたい
0837デフォルトの名無しさん
2008/03/04(火) 16:45:300838デフォルトの名無しさん
2008/03/04(火) 20:42:27走査→差分→連長→MTF→符号化
0839デフォルトの名無しさん
2008/03/04(火) 20:50:19ああびっくらこいただ
0840デフォルトの名無しさん
2008/03/04(火) 21:23:30圧縮に使えることがわかってきた
詳しくは次週
0841デフォルトの名無しさん
2008/03/04(火) 21:26:36記憶整理機構が圧縮アルゴリズムになるって話?
0842デフォルトの名無しさん
2008/03/05(水) 13:51:100843デフォルトの名無しさん
2008/03/05(水) 16:08:55たまにサバンな人が無劣化保存を実現しているが
0844デフォルトの名無しさん
2008/03/11(火) 10:39:05だれか一緒に研究しましょう
http://scholar.google.com/scholar?num=100&hl=ja&ie=sjis&oe=sjis&newwindow=1&q=fm-index
0845デフォルトの名無しさん
2008/03/11(火) 11:42:30パソコンで、合計10Gのファイル達を検索できるようにしたい
元のファイルを復元出来てindexが必要ないのはブロックソーティングだが
実用的でないのが欠点 何とかならないものか
0846デフォルトの名無しさん
2008/03/11(火) 12:13:460847デフォルトの名無しさん
2008/03/11(火) 16:22:54圧縮して連結するんじゃダメなのかね
0848デフォルトの名無しさん
2008/03/11(火) 20:31:18あと分割するとサーチに時間がかかってしまいます
0849デフォルトの名無しさん
2008/03/11(火) 23:41:25ブロックソーティングや、算術圧縮や、ハフマンは1語か2語の関係しか考えない
例えば1〜4語までの関係を取り扱った方が性能良いはず
0850デフォルトの名無しさん
2008/03/12(水) 09:20:36その根拠は?
PPMで次元を上げるとかえって性能が落ちるのは知ってるよな?
0851デフォルトの名無しさん
2008/03/12(水) 11:12:51上の方針はあきらめましたよ 単語の出現確率でビット数を割り当てた場合、
全文検索しようとすると1bit単位でブロックソートしなくてはいけなくなります
でも圧縮率は上がると思います
算術圧縮は文字の前後の関係を考慮せず、
ブロックソーティングでは2バイトの関係だけです
日本語や英語などは2バイト以上の単語が多くあるため効果があると思います
0852デフォルトの名無しさん
2008/03/12(水) 11:21:16>全文検索しようとすると1bit単位でブロックソートしなくてはいけなくなります
ブロックソート理解していないのね。
何bit単位でもブロックソートの結果は同じ。
>でも圧縮率は上がると思います
だから根拠は?
>算術圧縮は文字の前後の関係を考慮せず、
そんなの後段のエントロピー符号化でモデルと関係ない。ハフマンより上なのは常識。
>ブロックソーティングでは2バイトの関係だけです
間違い。PPMの無限大次元と同じ。
0853デフォルトの名無しさん
2008/03/12(水) 11:45:36サイズが100Mだとして100M単位でブロックソーティングしたら変化無しです
あとブロックソーティングは前(後ろ)に何があるのかしか考慮しませんよ
たとえば、THという2語が多く出現すればソート語にT(またはH)が連続しますが
そのあとにEが多く出現しても、少なかったとしてもTの連続する個数には影響を及ぼしません
0854デフォルトの名無しさん
2008/03/12(水) 11:46:53まあ単語レベルで分割してBWTをかければ単語間の繋がりを利用できて、
しかもインデックスのBit数を減らせるのでいいかもしれない。
が、単語間の相関性てのは相当な量を読み込まないと見えてこない。
人間の様に何十年もかけてサンプルを得ているわけじゃないから。
>ブロックソーティングや、算術圧縮や、ハフマンは1語か2語の関係しか考えない
そんなことはない。もっと勉強しろ。
>>850
それは極端な話。
PPM(というか圧縮全般)のサンプル(情報源)として英文がよく使われて、
英語の平均単語長が5くらいだったので結果としてPPMのOrderは5位で頭打ちで、
それ以上は無駄(むしろ悪いこともある)とされたから。
実際は最適なOrderは文脈に依存する。
上手いOrder FallモデルがあればPPM*は十分な性能を発揮する。
メモリさえ許せば。
0855デフォルトの名無しさん
2008/03/12(水) 11:50:17ハフマンや算術圧縮では全記号が等確率に出現するので圧縮はほとんどしません
しかし、A=abcdefgという単語を作ればAAAAになります
0856デフォルトの名無しさん
2008/03/12(水) 12:00:19そりゃモデル化の問題だ。
7byteで一単語(つまりアルファベットサイズ56bit)とすれば
エントロピー符号(算術符号・ハフマン符号)でも結局同じになる。
この単語長を可変にして単語を辞書番号に変換したのがLZ符号。
0857デフォルトの名無しさん
2008/03/12(水) 12:03:48そんな事は無いですよ
A=abcdefgがかなり多く出現したとしても
通常の文書ではほかに単独でa,b,c,d,e,f,,gは現れますから
1byte単位であつかうしか無くなります
0858デフォルトの名無しさん
2008/03/12(水) 12:08:32だからそれはモデル化の問題なの。
abcdefgもaもbもcも一単語として扱えば同じ。
エントロピー符号はシンボル単位だから
シンボルがどうなっているかはモデルとは無関係。
0859デフォルトの名無しさん
2008/03/12(水) 12:09:290860デフォルトの名無しさん
2008/03/12(水) 12:11:11もっと勉強してくれ。
0861デフォルトの名無しさん
2008/03/12(水) 12:11:53ブロックソーティングは2語の関係しか考慮しないというのは間違っていないと思いますが
0862デフォルトの名無しさん
2008/03/12(水) 12:13:407byte(56bit)単位で扱える日本語や英語の文書は無いと思いますよ
モデルの話をしています
0863デフォルトの名無しさん
2008/03/12(水) 12:14:00影響する。
しないと思い込んでいるのは、THだけ考えているから。
SHとか入ってくると状況が変わってくる。
0864デフォルトの名無しさん
2008/03/12(水) 12:14:57BWTはただの変換でエントロピー符号とは全然性質が違うということ
を理解してほしい。
BWTが2語しか考慮しないのは確実に間違っている。
0865デフォルトの名無しさん
2008/03/12(水) 12:15:39間違い。
0866デフォルトの名無しさん
2008/03/12(水) 12:16:31THとSHが隣接しているか、していないかはソートに影響を及ぼさないと思いますが
0867デフォルトの名無しさん
2008/03/12(水) 12:19:41だから、単語をどうやって分けるかは算術符合だのハフマンだのとは
別の問題なの。
0868デフォルトの名無しさん
2008/03/12(水) 12:21:36隣接しているなんて書いてないが。
ブロックに含まれるかどうかが問題なんだってば。
0869デフォルトの名無しさん
2008/03/12(水) 12:23:080870デフォルトの名無しさん
2008/03/12(水) 12:25:22単語(一語)はすでに分けられているとして話してます 例えば日本語や英語です
>>868
文書に含まれているかどうかだけならば出現頻度に影響しますが
2語や3語や4語のつながりとは関係ないことになります
0871デフォルトの名無しさん
2008/03/12(水) 12:31:41設定を後から付け加えても駄目だよ。
俺はここで終わりにする。
IDないから分からんかも知れんが
>>854,856,858,860,864,867,869
は俺。
0872デフォルトの名無しさん
2008/03/12(水) 12:33:21関係があるから、BWTしたものがより圧縮しやすくなるんだってば。
2語の関係だけと思うなら、PPMのそれと比較してみろよ。
PPMとBWTの違いは、時系列情報があるかないかの違いしかない。
処理方法は全く違うが、本質的には同じものなんだってば。
0873デフォルトの名無しさん
2008/03/12(水) 12:45:41http://www.ipa.go.jp/NBP/14nendo/14youth/mdata/2-8.htm
WX法は現在の圧縮アルゴリズムの中心であるLZ法とは違い
全体のデータ構造を調べて単語を抽出するので単語抽出の妥当性がよくなる.
また,高圧縮率を誇るブロックソート法と比べても
「単語間の距離」 「単語長と出現数の関係」
「単語が出現する範囲 」といった情報を利用できる点で,WX法は優れている.
0874デフォルトの名無しさん
2008/03/12(水) 12:47:14「単語間の距離」 「単語長と出現数の関係」「単語が出現する範囲 」
という情報を利用していないと言うことだ
0875デフォルトの名無しさん
2008/03/12(水) 12:57:25BWTは、「単語間の距離」は利用していないが、結果的に、隣接しているか否かの情報は利用している。
0876デフォルトの名無しさん
2008/03/12(水) 12:58:39初めに言ったとおりだ
0877デフォルトの名無しさん
2008/03/12(水) 13:01:180878デフォルトの名無しさん
2008/03/12(水) 13:02:34だから、それが間違い。
0879デフォルトの名無しさん
2008/03/12(水) 13:03:290880デフォルトの名無しさん
2008/03/12(水) 13:06:32BWTは2語の関係だけでなく、 ブロックサイズ分の文字の長さの関係が反映されている。
だからこそ、その当時、BWTが注目されたわけなんだが。
0881デフォルトの名無しさん
2008/03/12(水) 13:14:47XとY 、 YとZはつながっていますが、ソートしてしまえば
それらは別々の位置へ移動してしまいます
XY*********YZ********
というデータをソートしても同じ結果です
だから3語の関係は無くなってしまいます
0882デフォルトの名無しさん
2008/03/12(水) 13:38:00>というデータをソートしても同じ結果です
これが間違い。
0883デフォルトの名無しさん
2008/03/12(水) 13:43:15******XYZ*****
の巡回データは、
YZ***********X
Z***********XY
になる
XY*****YZ*****
の巡回データは、
Y*****YZ*****X
Z*****XY*****Y
になる
これをソートして末尾のデータを出力すれば同じだよ
0884デフォルトの名無しさん
2008/03/12(水) 13:49:53ということは3語目も結果に影響するな 間違えていたよ スマソ
0885デフォルトの名無しさん
2008/03/12(水) 13:51:13わかりやすい例で書くなら、
AAAXYZAAAXYZAAAAAAAAAYY
と
AAAXYAAAYZAAAXYAAAYZAAA
は全然異なってくる
0886デフォルトの名無しさん
2008/03/12(水) 14:13:17単語抽出が価値あると思ったがそうなるとやる意味がないといえる
ということはzipやPPMに圧縮率で劣る点はないって事か?
1語目の影響が完全に2語目を上回っているところが少し弱点にはなり得えそうだが・・そんなことはないか?
T*Eに対して*に入る語を予測しようとするとき、TとEの2語に影響されるが
ブロックソーティングでは価値に対する重みがないか
0887デフォルトの名無しさん
2008/03/12(水) 14:18:35文中にXYZが多くあればソート後、YZ…Xが大量にできる
XYとYZが個別にある場合は、Y…Xが大量にできる
しかしYで始まる巡回文字列はいっぱいあるので
末尾のX自体は飛び飛びにしか並ばない
YZで始まる巡回文字列はあまりないからXが結構並ぶ
つまりあなたの勘違い
0888デフォルトの名無しさん
2008/03/12(水) 14:27:14通常のやつでは、△○○○としたとき
○○○から△を予測することに等しいといえるが
後方ソートでは、○○○△に対して前方から最後の1語を予測するのと同じ
こっちの方が予測が成り立ちやすいか?
0889デフォルトの名無しさん
2008/03/12(水) 14:53:51どうせBZIP2の人が既に試してるだろうけど
0890デフォルトの名無しさん
2008/03/12(水) 15:00:32やってみればわかるが、どちらにしてもほとんど変わらん。
0891デフォルトの名無しさん
2008/03/12(水) 17:24:560892デフォルトの名無しさん
2008/03/12(水) 19:44:24Efferosだっけ?女性の研究者が関係論文を出している。日本の有村氏とかも。
ブロックソーティングの理論解析は10年〜5年前にほぼ終わってる。
以下亀レス。
>>850
PPMの次元を上げると性能が落ちるのは、モデル化の方法が最適ではなかったから。
これは、PPMZあたりでも語られている。日本だと横尾氏あたりか。
0893デフォルトの名無しさん
2008/03/12(水) 21:54:520894デフォルトの名無しさん
2008/03/12(水) 22:10:50手段の一つに過ぎないはずだが
0895デフォルトの名無しさん
2008/03/12(水) 22:22:19このへん参照してみて
http://www.google.com/search?q=%22fm-index%22+ferragina
0896デフォルトの名無しさん
2008/03/13(木) 08:46:472バイトが一致したときに置き換えると間違えることがあります 1バイト文字が混在しているためだと思います
どのようにして正確に変換出来ますか
例えば・・・
�瓔鴾戌リ�^�u�~�������拐蹄ゥ�キ����
朗隆塚晴猪益神祥福靖精羽諸都飯飼
0897デフォルトの名無しさん
2008/03/13(木) 08:59:18変換の仕方は他所で聞くべき。
つか文字コード変えたら不可逆になる場合も出てくると思うが。
変換前の情報も残すのか?
それを承知の上ならマッピングの都合でs-jisよりeucの方が圧縮しやすいぞ。
0898デフォルトの名無しさん
2008/03/13(木) 09:05:34英数字、記号は半角、カタカナは全角に統一して不可逆で格納します
これは検索とサイズに有効です
0899デフォルトの名無しさん
2008/03/13(木) 09:16:38といわれてもな…
ここんとこよく現れてるブロックソートの人だよね?
ここで聞くよりとりあえずググる。
http://www.google.com/search?hl=ja&q=s-jis+%E5%88%A4%E5%AE%9A&lr=
不可逆でいいならs-jisより内部でアルゴリズムに合わせて
全部マップし直した方がさらに速く圧縮も効くと思うぞ。
0900デフォルトの名無しさん
2008/03/13(木) 09:21:15情報サンクス eucに統一することにしました
カタカナを信頼性あるソフトで変換しておけば
2バイトの一致を調べるだけで置き間違いが起こらないと思います
0901デフォルトの名無しさん
2008/03/13(木) 12:18:00隔離スレとしてちゃんと機能してるな
0902デフォルトの名無しさん
2008/03/16(日) 05:41:42Ko & Alulu法を実装したいのですが、概要はわかるのですができあがりまで遠いです
解説かコードありませんか
0903902
2008/03/16(日) 05:59:050904デフォルトの名無しさん
2008/03/16(日) 14:06:41abcde
ades
abc
adc
多分木に格納して順に呼び出せばソート出来そうなんですけど
どのように実装すれば良いと思いますか?数ギガのデータだとメモリに入りきるのか不明です
0905デフォルトの名無しさん
2008/03/16(日) 14:45:000906デフォルトの名無しさん
2008/03/16(日) 15:02:07x[n]< x[n+1] となるn番目の文字をTypeAといい、TypeAでないものをTypeBと言います。
先頭がTypeAで残りがTypeBで構成される文字列全てをソートしたい
最速でソートするにはどうすればいいか?というものです
>>905
ファイルへのアクセスがタイムロスになると思うのですが、なるべくランダムアクセスを減らして
一度に読み込んだ方が良いと思いますが・・どのようにしたらいいでしょうか?
重複は削除します
0907デフォルトの名無しさん
2008/03/16(日) 16:13:1810Gのブロックなんてソートはできても解凍でないって
ブロックサイズが大きくなる程
指数関数的に解凍が遅くなるってわかってるよね?
ましてメモリに全部載らないものどうやって解凍するの?
0908デフォルトの名無しさん
2008/03/16(日) 16:24:57高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」
このWTを利用することで、近年提案されている圧縮全文索引(Compressed Suffix Arrays、FM-index、wavelet treeなど)やsuccinct data structure(括弧木など)を実現することができます。
http://codezine.jp/a/article/aid/261.aspx?p=1
0909デフォルトの名無しさん
2008/03/16(日) 16:30:53メモリは使わずに済みますが、WTの索引と、圧縮元のデータにランダムアクセスする必要があるため
10ギガの8bitずつのランダムアクセスにかかる時間程度かかります 計算時間はほとんど無くランダムアクセスだけの時間だけと思います
WTの構築にすこし時間がかかりますが
0910デフォルトの名無しさん
2008/03/16(日) 16:50:57HDDへのアクセスを極力減らしたいなら、マージ法を改良していくしかなさそうだね。
代わりに計算量が増えるけど。
0911デフォルトの名無しさん
2008/03/16(日) 16:51:30これを使えば、>>906の部分列のソートだけで実質的にブロックソートが完了出来ます
とても長い列をソートしなくて済みます (もともとは10Gサイズの列でした)
>>908のwavelet treeを使えば、ブロックソートされたデータの全文検索や、
任意の文書をそのサイズに応じた時間で復元出来ます
圧縮と全文検索を実現したいと思います
0912デフォルトの名無しさん
2008/03/16(日) 17:23:45ここだけで特別に教えます 語の頻度を調べて高頻度順に番号を付け替えます
すると例えば
a ・・・・ t
a ・・・・ t
a ・・・・ t
x ・・・・ t
x ・・・・ t
x ・・・・ t
というデータがあったときaからxの間には別のソートされた列が入りtの連続が分断されてしまいますが、
a ・・・・ t
a ・・・・ t
a ・・・・ t
b ・・・・ t
b ・・・・ t
b ・・・・ t
ならばtが連続する可能性が出てきます aとbの区切りに終わりがtで無いデータが入ったら駄目ですが。。。
でも可能性として少し連続が増えそうです より増やせそうなテクニックはありますか
0913デフォルトの名無しさん
2008/03/16(日) 18:06:50たいして効果ないw
未発表なんじゃなくて意味ないから誰も言わないだけ。
0914デフォルトの名無しさん
2008/03/17(月) 00:36:27> これ使えばすべてをメモリ上にのせて操作する必要ないです
いやHDにランダムアクセスなんて選択肢はないんだって。爆遅だから。
> 任意の文書をそのサイズに応じた時間で復元出来ます
初めから文書単位で圧縮しとけば修正のたびに10Gも圧縮し直さないで済む
0915デフォルトの名無しさん
2008/03/17(月) 00:46:15ファイルを跨ってwavelet tree作っとけば全文検索できる
全体を一個に圧縮する意味はほとんどないと思うよ
0916デフォルトの名無しさん
2008/03/17(月) 02:24:220917デフォルトの名無しさん
2008/03/17(月) 02:43:34俺天才じゃね?
0918デフォルトの名無しさん
2008/03/17(月) 02:46:09キーワードの周囲の文200文字だけとかなら200回だけのアクセスです
一瞬です あと全データを復元することはまれです
ソート済みのデータが一定以上の大きさになったらひとまとめにして
小さい(100M以下とか)ならば復元してから追加すればいいかと思います
検索対象が増えますが
0919デフォルトの名無しさん
2008/03/17(月) 02:47:34ブロックソートすることによって全文検索が可能になるんですよ
0920デフォルトの名無しさん
2008/03/17(月) 08:24:16まず、3桁以下の場合、256*256*256個のビット配列のビットを立てます
4桁の場合は、ハッシュを使ってバッファに蓄えておきます 一杯になっなら4桁をHDDをビット配列と見なして書き出します
5桁以上のものは、そのままHDDに書き出しておいてあとで普通にソートをします
あとは順番に呼び込めばソート出来ます これで4桁以下の文字はソートせずに済みます
0921デフォルトの名無しさん
2008/03/19(水) 22:46:180922デフォルトの名無しさん
2008/03/23(日) 04:16:270923デフォルトの名無しさん
2008/03/23(日) 09:35:380924デフォルトの名無しさん
2008/03/23(日) 09:49:16主語による。
0925デフォルトの名無しさん
2008/04/16(水) 20:03:520926デフォルトの名無しさん
2008/04/19(土) 09:10:340927デフォルトの名無しさん
2008/04/19(土) 22:52:050928デフォルトの名無しさん
2008/04/20(日) 13:22:110929デフォルトの名無しさん
2008/04/21(月) 22:00:26・おまいの圧縮アルゴリズムの特許で大儲け
・現行全ての圧縮アルゴリズムの特許が切れてフリーに
・おまいが壺サイズに圧縮されてから千の風に伸長される
の何れの幸福のことですか?
0930デフォルトの名無しさん
2008/04/29(火) 21:54:420931デフォルトの名無しさん
2008/05/01(木) 18:54:41とんでもない圧縮率が実現できそうだが、時間もとんでもなくかかりそうだ。
0932デフォルトの名無しさん
2008/05/01(木) 19:33:350933デフォルトの名無しさん
2008/05/01(木) 23:34:060934デフォルトの名無しさん
2008/05/02(金) 10:57:04概要とURLが貼ってあれば転送量は減る可能性が高い
0935デフォルトの名無しさん
2008/05/02(金) 11:06:250936デフォルトの名無しさん
2008/05/02(金) 12:11:06板ごととかカテゴリごとに辞書を作ったらよさげ?
0937デフォルトの名無しさん
2008/05/07(水) 11:23:53ほとんどのデータを可逆圧縮で40%以下に
出来るソフトって需要あります?
その、売れるんでしょうか?
40%くらいでは需要は無いでしょうか?
0938デフォルトの名無しさん
2008/05/07(水) 11:39:06MP3とかJPGとかPNGとかも40%になるなら需要あるはず
0939デフォルトの名無しさん
2008/05/07(水) 11:48:02どんなzipを食わせても平均して40%以下に圧縮できるなら、ぜひ買わせてもらおう。
0940デフォルトの名無しさん
2008/05/07(水) 11:49:33レスありがとうございます。
プログラムのことはあまり詳しくないので
がんばって、プログラムに取り組んで行きたい
と思います。
0941デフォルトの名無しさん
2008/05/07(水) 18:01:050942デフォルトの名無しさん
2008/05/07(水) 18:43:220943デフォルトの名無しさん
2008/05/07(水) 18:49:570944デフォルトの名無しさん
2008/05/07(水) 18:51:18出来たら、一億の金を出しても良いぞ
0945デフォルトの名無しさん
2008/05/07(水) 18:52:030946デフォルトの名無しさん
2008/05/07(水) 19:00:39可逆で?
0947デフォルトの名無しさん
2008/05/07(水) 20:28:32いかなるデータも40%以下に可逆圧縮できるとすると
繰り返し圧縮すればデータ量は限りなくゼロに近づく
ありえない。あの特殊なヘルメットを自作するなんて
特定データに特化した圧縮ならば可能かもしれない
0948デフォルトの名無しさん
2008/05/07(水) 20:32:430949デフォルトの名無しさん
2008/05/07(水) 20:47:59多段、再度圧縮も出来ます。
プログラムの勉強をしながら作るので
時間は掛かると思いますが、今年中には
出来ると思いますので気長に待っていて下さいね。
0950デフォルトの名無しさん
2008/05/07(水) 20:48:19次スレはこちら
http://bubble6.2ch.net/test/read.cgi/cafe50/1141039267/
0951デフォルトの名無しさん
2008/05/07(水) 20:49:40こちらへどぞー
http://etc7.2ch.net/denpa/
0952デフォルトの名無しさん
2008/05/17(土) 23:01:02あんまりなので、まじめにお話しすると。
あるファイルを元の情報に復元できる形で圧縮する(可逆圧縮)場合、どのような圧縮手段を尽くしても、
ある一定のサイズより小さく圧縮することはできません。
(シャノン, 1948)
多重に圧縮しても、ある限界より小さくできないのです。
もしできたとすれば、それは非可逆なものになるでしょうね。
私としては、コルモゴルフが気になって仕方がないのですが、無関係かもしれませんね。
0953デフォルトの名無しさん
2008/05/18(日) 12:18:45データを出力する機械語の最適化まで必要になるから
もはや領域が違うな。
つうかコロモゴロフ複雑性ってデータ圧縮に関しては
「ある一部のデータは圧縮できて、のこりは圧縮できない」
っていう結論が出てくるだけだぞ。
バイナリで表現可能なあらゆる情報のうち、
人間にとって意味を感じさせる情報が極端に偏っているからこそ「圧縮」できるんだ。
数学的にはほとんど全ての(無限)データ列はアルゴリズム化できない。
0954952
2008/05/24(土) 17:21:22なるほど、もやもやがすっきりしました。
無論、正確な証明を追って納得したわけではないのでアレですが、まあ私のようなものにその必要はありますまい。
ありがとうございました。
0955デフォルトの名無しさん
2008/05/28(水) 04:59:280956デフォルトの名無しさん
2008/06/01(日) 01:13:38禿しく乙
0957デフォルトの名無しさん
2008/06/06(金) 09:46:050958デフォルトの名無しさん
2008/06/07(土) 13:05:13将来的に圧縮アルゴリズムを使ったり応用できる職につきたいんだがどんな仕事があるだろうか?
ソフトウェア開発しか思いつかないぜ。
データ圧縮がなんていう分野なのかも分からないんだ…
0959デフォルトの名無しさん
2008/06/07(土) 13:08:080960デフォルトの名無しさん
2008/06/07(土) 22:15:30だいたい、圧縮アルゴリズムやプログラムなんかほとんど無料で使える物だし、金儲けにするのは難しいよね。
変換コンテンツ系(パケッ得とか)も圧縮技術使ってるんだろうけど求人少なそうだしなー
0961デフォルトの名無しさん
2008/06/07(土) 22:16:43sage
0962デフォルトの名無しさん
2008/06/07(土) 22:26:01OSS系の会社は?
0963デフォルトの名無しさん
2008/06/08(日) 02:17:06そのなかの数人がOSSに専念してるだけだろw
0964デフォルトの名無しさん
2008/06/08(日) 03:52:040965デフォルトの名無しさん
2008/06/10(火) 21:26:30金儲けできるつったら動画圧縮ぐらいかね?
基幹特許取って一攫千金してやる、ぐらいの勢いは必要だろうけど。
0966デフォルトの名無しさん
2008/06/11(水) 01:26:30偉そうにしてんじゃねーよ。
0967デフォルトの名無しさん
2008/06/11(水) 03:06:06もっと偉そうにしなくても
0968デフォルトの名無しさん
2008/06/11(水) 03:28:31それが10分の1とか100分の1とかに圧縮出来たら金になる罠
0969デフォルトの名無しさん
2008/06/11(水) 09:52:13その程度なら既にできているよ。
その程度のことも知らないようでは、金になるような仕事は無理だろ。
0970デフォルトの名無しさん
2008/06/11(水) 09:54:090971デフォルトの名無しさん
2008/06/11(水) 10:28:19どう理解していないの?
動画圧縮の1/200なんて珍しくもないんだけど。
その圧縮したものをさらに1/100だったら、そんな話をしている方が異常。
金になる以前に原理的に不可能。
0972デフォルトの名無しさん
2008/06/11(水) 12:51:58金なんて払ったこと無いが
0973デフォルトの名無しさん
2008/06/11(水) 13:24:45圧縮(前後のフレームはたいていは似たようが画像になるので差分情報のみ記録など)
+
バイナリデータとしての圧縮(ZipやLzhみたいな圧縮)
がされてるから、
うーん。これ以上、更に驚異的な圧縮をするのは大変。
原理的に不可能なのかは証明されてるのか知らんけどさ。
0974デフォルトの名無しさん
2008/06/11(水) 13:56:23再生時に、レンダンリング生成した画像と通常のフレームを合成表示するとか、
天才の発想があれば、可能かも知れん。
0975デフォルトの名無しさん
2008/06/11(水) 14:06:24それに近いことはMPEG4に取り入れられている。(スプライト符号化)
ほとんど利用されていないけどね。
0976デフォルトの名無しさん
2008/06/11(水) 14:21:27つまりそういうこと。
「そんな話」であることが理解できないのが馬鹿。
0977デフォルトの名無しさん
2008/06/11(水) 15:31:35スルーできないお前も馬鹿
0978デフォルトの名無しさん
2008/06/11(水) 16:00:48急に天啓でも得たのかな。
0979デフォルトの名無しさん
2008/06/11(水) 21:04:08>金になる以前に原理的に不可能。
そう思っていた時期が私にもありました
0980デフォルトの名無しさん
2008/06/11(水) 21:23:18{
return 0;
}
0981デフォルトの名無しさん
2008/06/11(水) 23:42:09だれかプログラムかいてください
0982デフォルトの名無しさん
2008/06/11(水) 23:50:51レス数が950を超えています。1000を超えると書き込みができなくなります。