最強の圧縮アルゴリズムを語ろう

2bit , 3bit , 5bit ずつに頻度を取る。
2bitがいい成績だったら2bitをひとかたまりにして
2ブロック、3ブロック、5ブロックで頻度をとる。
これを繰り返す。

　　　　ラ　　ン　　レ　　ン　　グ　　ス　　圧　　縮　　法　　最　　強


　VB厨にもマジ簡単だからおすすめ

アカデミックにでおｋ

圧縮率が最強なのを語ろう

>>1
　　　　　　r;ｧ'N;:::::::::::::,ｨ／　　　　　 >::::::::::ヽ
.　　　 　 〃　　ヽﾙ1'´　　　 　 　 ∠:::::::::::::::::i
　　 　 　 i′　　___,　-　,. = -一　 ￣ｌ:::::::::::::::ｌ
.　　　　　 ! , -＝=､´r'　　　　　　　 　 l::::::/,ﾆ.ヽ
　　　　　　ｌ　　　　　　　　_,, -‐''二ゝ　 ｌ::::l fﾞヽ |、 ここはお前の日記帳じゃねえんだ
　　　 　 　 ﾚー-- ､ヽヾﾆ-ｧ,ﾆ;＝、_　　 !:::l ） } ト
　　　　　　 ヾ¨'７"ry､｀ 　 ｰﾞ='ニ,,,｀　 　 }::ヽ(ノ 　「ハレ晴レユカイ」でも聞いてろ
:ｰゝヽ､ 　 　 !´ "￣ 'l,;;;;,,,.、　　　　　　　,i:::::::ﾐ
::::::::::::::::ヽ.-‐ ﾄ、　r'_{　　 __)｀ニゝ、　 ,,iﾘ::::::::ﾐ 　　　
::::::::::::::::::::Vi／l:::V'´;ｯ`ﾆ´ｰ-ｯ-,､:::::`"::::::::::::::;ﾞ　, 　な！
:::::::::::::::::::::::::N. ﾞ､::::ヾ,.｀二ﾆ´∠,,.i::::::::::::::::::::/／／
:::::::::::::::::::::::::::::l　ヽ;:::::::::::::::::::::::::::::::::::::::::::／　／
::::::::::::::::::::::::::::::!　:|.＼;::::::::::::::::::::::::::::::／　／

■5/10発売　涼宮ハルヒの憂鬱ED　「ハレ晴レユカイ」
http://www.youtube.com/watch?v=zuQiovLQc_s&search=haruhi

ハフマン、LZぐらい知ってるよ
俺が考えたのは2ビット(1ビットずらしも考える)、
3ビット(1ビット、2ビットずらしも考える)単位で出現頻度を調べて
頻度の高い単語を一纏めにしようというわけだ。

無理だって
プログラム作ってからこい

TeXでペーパー作成してから来い

4bit , 6bit , 8bitは統計をとらなくてよい。
2×2　,　2×3　,　2×2×2で実現されるからだ。
たとえば英語(ASCIIコード)ならば
2ビット→2ブロック→2ブロックがいい頻度を出すだろう。

ひとまとめって、どこに纏めるつもり？
纏めたはいいけど、複合化するときはどうするの。

頻度の高いブロックが出続ける間は
2,3,5,7ブロックずつで統計を取る。
最後は、既存の圧縮プログラムで圧縮するんだ。

>>10
単語辞書を圧縮したもののはじめに記録する。

おーい早くキンタマーセマティカ君出て来いよ！
単なる糞コテなのかよ！それは

たとえば110101111011101011101が与えられたとしよう。
a=1101と置換すれば

(1101)011(1101)(1101)01(1101) = a011aa01aとなり簡単になる。
こういう事をやりたいんだ。

中学生だろお前

どの区切りで一単語と見なすかで全体の文字列長が変わってしまうが
その辺はなんとか考えよう。

ハフマンもLZも名前だけしか知らん様子ですね。

一般的にはword extraction(wx法)というやつなのだがな。
しかし単語の抽出法は工夫の余地があるはずだ！

また数学的に無理だと証明されている事をこねくり回す基地外か

どこに無理だと証明されているんだよ。
頻出単語を少ないbitで表現できれば文字列長が小さくなるだろが！

動くプログラムを実際に作ってうｐしてからこいや>>1

「考える」だけなら誰でも出来るんだよ。「考える」だけならな。

しかし、他人を納得させるには、「実物」を見せないとだめだ。
それをしない限り、オナニーと呼ばれても仕方ないぞ。

この場合おもに単語抽出方法を考えればいいわけだ。辞書を使わずに。
一般的にはどのようなアルゴリズムがあるんだ。知ってるか？

人こないな〜

高圧縮な単語抽出アルゴリズムが開発できれば
検索エンジンとか宇宙人語とか暗号解読とかに役立ちそうだな。

1101010111001010101
が与えられたときに
a=1101010111001010101
とすれば
1101010111001010101　→　a
と簡略化される

bzip2最強

いまのところ、量子圧縮がいちばん有望じゃない？
bit単位の(汎用的な)圧縮アルゴリズムに限界があるのは明らかなんだから。

>>26
そしたら辞書に本体が必要じゃないか。あまりに大きくしすぎても駄目だと言うことだな。
最低2回は繰り返さないと。

算術圧縮

>>28
パソコンが2進数にもとずくんだからそれは無理だ。
現在での最強は？

何でも量子と言えば何とかなると思ったら大間違いだ！

漁師コンピューティング

圧縮しなくても武豊より身長低いのに。

>>14
じゃぁその文字列aそのものはどうやって保存するんだい？

>>35
初に単語数を16bitで記録する。次に単語長を16bitで記録する。
次に単語を記録する。以下、単語数になるまで繰り返し。

単語数　z=3
単語長　x=5 単語　y=11000
単語長　x'=2 単語　y'=01
単語長　x"=6 単語　y"=101011

zxyx'y'x"y"(圧縮データ)

この様に文字列長を縮めてから通常の圧縮ルーチンを起動するんだ。

>>37
それって最初のデータ13bit（2バイト以下）だよね。
明らかに増えてない？

元のデータが1ギガとかだと辞書はたいしたサイズではない

元のデータがギガ単位にならなければ圧縮率が高まらないアルゴリズムってどうなんだろ。

あとどの単語に何ビット割り当てるという情報もいるな。

>>41
没に10メガとかでもいいけど。

>>14,>>35-42
それ以前に最適な辞書を作るアルゴリズムをどうやって作るのかと。

talk:>>44
「最適な辞書を作るアルゴリズム」を作るアルゴリズムを作れば？

>>45
頑張って！
影から応援するから

同じ単語でもどこで切り出すかで長さが変わるんだよな。
少なくとも単語は2bit以上だから2bitから調査しようぜ。
それで00がかなり多いとなったら次に0がくる確率がかなり多いとかなって。

0001001110000だと単語00の出現回数はいくつにしたらいいんだ？

>>48
途中の01や111をどう扱うかによって変わるかと。

talk:>>45
どうやって作るの？

まさかとは思うが、それを作るために作るためのアルゴリズムをつくろうとか言い出す始末じゃ困るぞ。

ちょっと前の話だが、いわゆるITバブルだったころ、
「どんなサイズのファイルでも50%に圧縮するアルゴリズムを考え付いた」といって
投資を集めていたやつがいたそうだ。しかもそのアルゴリズムは可逆なのだそうだ。

この詐欺師の事件の顛末、誰か知らないか？

>>1
まず、詳しい圧縮・伸張方法を説明して、且つその方法が圧縮率や処理速度の点で良い結果を出せそうだ、ということをきっちり説明してくれ。

>>51
10%じゃなかったっけ?
そういえばどうなったんだろうな。

どんなビット列、文字列に対しても
辞書部分 + 圧縮部分のサイズがもっとも小さくなるような
アルゴリズムをおまいらが開発するすれ。

圧縮ファイルをﾃｷｽﾄにしてそれを圧縮するを繰り返せばすげぇ圧縮できる。


そう思ってた時期が僕にもありました

ブロックソート＋BPEでいいんじゃね？

最強は非可逆だって

それハッシュ

>>51
物理ノイズも50%に圧縮するってか。
そりゃ騙されたほうが阿呆ですなあ。

BPE（Byte Pair Encoding；バイト対符号化）なんていうのがあるのか。
2ブロック限定で辞書作るアルゴリズムだな。
任意のブロックで単語を見つけ出せればいいんだが。

あんまり関係ない質問で恐縮なんですが、ZIPファイルとかLZHファイル等を
扱う方法などについて詳しく載っているサイトってありますか？

ググろうとしても「zip 仕様」とか「zip ソース」だとかで検索してもぜんぜんわからんとです・・・

>>61
ＤＬＬをつかう。
http://www.csdinc.co.jp/archiver/lib/main.html

>>62 ｽﾏﾝｽ、さすがにそれは知ってるけど、それと同じようなことを（自前で）実現するような
手法について調べたいんだけど俺のぐぐりかたがヘタクソでみつからない、ていうお話です

>>63
DLL作成をぐぐる。

標準の形式をしりたいということか。

>>64 うう・・・ぐぐってみたですがよくわからんですorz
>>65 ええ、そんなかんじです

http://www.iecapc.jp/06/diffusenew/guide/zip.html

夢を語り合うスレはここですか？

>37は単語と置き換える記号aを既存の記号と
かぶらせない方策を考えてない中学生。(発想力が)

>>61
pkzipとかで日本語以外もぐぐりゃいいんじゃないかな。

>>69
なんだと。そんなことは簡単なことだ。
算術圧縮とか、ハフマンのやり方にならえばいいんだ。
ようするに2とおりの表し方がないようにすればいい。

>>1-70
君らこの辺とかちゃんと読んでる？
　　↓
http://homepage3.nifty.com/DO/algorithm.htm　の人のWX法。

ビット単位でやるとかなりコストかかりそうだけど、速度的なチューニングを
考えなければほぼそのまま適用できるでそ。

>>71
>>18でちゃんと触れられてるぞ。
おまえこそちゃんと読めよｗ

いやだから一般的なwx法の話じゃなくて、
ipa でやってた↑のアルゴリズムとか読んでるのって話だよ。

誰一人読んでるようには見えないぞ。

>>73
> 誰一人読んでるようには見えないぞ。
人が読んでいる間にそういうこと言うかね

11001110の場合。

(1) 一語ずつ削る
11001110
1001110
001110
01110
1110
110
10
(2)ソートする
001110
01110
(10)
(10)01110
(110)
(110)01110
1110

単語(10)(110)(11)が出現していることが判明する。

a=110を単語として扱うのがいいな。

あまりに長い単語は出現しないだろうからソート対象にのは
16bit(16語)まででいいか。

>>71を読んでみたところこんな感じでやっている。
しかし今おもったんだがソートする必要はない気がする。
なぜならば11001110が与えられたとき
(単語は2から4bitのまでだと仮定する)
配列を用意して3=(11)番目、7=(110)番目、12=(1100)番目の配列に1を足す。
次に2=(10)番目、4=(100)番目、5=(1001)番目の配列に1を足す
とやればいいんだ。

これならソートは必要なくデータ長×最大単語長くらいの時間で頻度が調べられる。

しかし問題はより長い単語は少ない単語を含むという点だ。
単語が長いほど出現比率は下がるが。
長い方を採用するか、短くて量で勝負かだ。

まずった。
0001と001と01が同じ配列に収められてしまう。
空を0、0を1、1を2に変換して記録しよう。

2バイト長の配列を2^27個用意すると256Ｍバイト必要だ。
3の17乗は約2^27だから17bitまでの単語は登録できるな。

やってみろよｗｗ

到底zipやrarに太刀打ちできないからｗ

>>80
71 のURLの人は、単語の前後の文字のエントロピを見て単語候補を絞り込んでる。
( 0110110 の中の "11" のように)前後が何時も同じときには「単語らしさ」を下げる、と。

しかし実用的には単語長はいくつくらいになるんだろうか？
テキストならば8bit×5語=40bit、16bit×5語=80bitくらいだろう。
バイナリなら20bit程度なんだろうか。
この程度なら82の様にハッシュが使える。

そもそも対象のデータによって最適なアルゴリズムは異なるのに、
前提条件を明確にせず、延々と馬鹿を晒し続ける奴ばっかりなのは何故なんだ？

飛べない豚はただの豚。

戦う前から尻尾を振るのが負け犬。
戦って負けてキャンと鳴いてからが勝負さ

内容も理解せずに んなこと言われてもｗ

画像圧縮で振幅＋矩形ブロックで、そこそこの圧縮率と高速度のもの作って使ってる。
発表する場もないし、ひとりでひっそりと使ってる。時間軸圧縮も作って、やっぱり動画プログラムでこっそり使ってる。

>>86
最強の称号を手に出来るのは
汎用性のある可逆圧縮だ！
データ種類なんて関係ない。

机上の空論はいいから誰かGCA/DGCAよりイイの作って見たら？

どうせZIPやLHAより小さくなるって言ってもたかが知れてるんだし
互換性・普及度が大事だと思うけどな

THcompが最強だな。
ttp://thcomp.org/~pen/pfyp/thcomp/THcomp_log.txt

>>92
出た！THcomp！この手のスレには必ず出てくるな。

現在世界最強はどのアルゴリズム?

>>94 URLだろ
たとえば
http://www.google.co.jp/maps?f=q&hl=ja&t=k&om=1&ll=34.944347,134.427681&spn=0.085131,0.113297

>>94
だからTHcompだってば。
そろそろ8バイトくらい行ってるかなw

どんな計算機でも圧縮出来ない数がある。
その数は、有限だが計算機により計算する事が出来ない。
しかし、私達はその数を単に一文字で表現する事が出来る。　Ω　と

http://www.ice.nuie.nagoya-u.ac.jp/~h003149b/lang/p/notes/2003_12_04.html

>>77
16bitだと16語どころか半角で2語しか入らないような。

バイナリならそんなに16bitもあれば十分。

バイナリならそんなに16bitもあれば十分。

ぱくろな！

ぱくった　というより「引っ張った」という表現の方があってるｷｶﾞｽ。

希ガスと言えばヘリウム

ヘリウムは潤沢にある。尤も、太陽と言う名前で宇宙に転がっているので熱と質量をどうするかが問題だが。

俺はネオン派。

僕はキセノン派

>>107
キセノンって何

アルゴリズムを発見した。
2進数で16bitまでの単語の頻度を調べる。
5bitの単語が100回現れるとする。その単語を1bitに変換出来たとすると
500bitを100bitに縮められる。400bit分小さくできた。
同じようにすべての単語についてなんbit縮められるか調べる。
もっとも縮められる単語を2とおく。
すると10121102221021などとなる。

今度は3進数で頻度を調べる。縮められなくなるまで繰り返す。
誰が実装してくれるﾔｼいない?

>>109
それは2進数に直した時にファイルサイズが膨れそう。

>>110
それ以前に最初同一データに対して13万通り以上も調べるとなると相当時間がかかる。
あと、縮められなくなるって言うのは同一パターンがまったく含まれない時だけで、
n進数のnにあたる部分が随分大きい時になると思うのだが。

縮める前の文字列を格納するとなると色々附属情報が着いて来てややこしくなるので、
2進数→3進数→4進数→4進数を展開して2進数
という手順を一セットにしてファイルに書き出すのが妥当かと。

・・・と書いているうちに作りたくなったり。

>>111
78-82を参考にしてくだされ。ハッシュを使うと簡単かと。

とりあえず2進数を圧縮して3進数にするアルゴリズムは書けた。
あとは3進数を圧縮して4進数にするのと、4進数を2進数に展開して、そいつを8こ組み合わせてファイルに書き出す。
思ったより面倒＾＾；

2進数→4進数のほうが圧倒的に簡単なのになんでわざわざ3進数にすんだよｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ

>>114
そういう仕様。>>109のアイデアを実装しやすいように脳内変換して>>111（自身）が書いた通り。

　 [ﾟдﾟ]　ﾃﾞﾌﾗｸﾞｶﾞｶﾝﾘｮｳｼﾏｼﾀ
　/[＿]ヽ
　　|　|
234→うがざざすだでななにににののほよわわんん倒単圧数数数的簡進進進
ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ

talk:>>109
2進数の検索をテストしているのだが、とてもじゃないが16ビットまで調べると時間食いすぎで効率悪い。
コードが悪いのかとも思うが。

備考
8ビットまで→約3分
16ビットまで→約42分

CPU:ペンティアム4 3.0GHz

因みに検索のテスト対象はソースファイル(10139Byte)です。

9:q9)Foe0D~W4|IHgpAe7k^&EzD9x20~xa}e4QXf~}Ce_I$d^Ra#uz#px*A{}`3#
m~}]: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|

L8dTnQ.^vMK=wTSg3LLb~{$BMv85+tu+Q}N8?ViG@fBA\,S97!oYjistPx@7K*~`
Tu~@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!!!

・Range Coder
・元はbzip2で圧縮したファイル
・圧縮と言うよりは符号化だな
・デフラグさん上等

>>119-120
ここは最強の圧縮のアルゴリズムについて話し合う場であり、少なくとも私は暗号化のアルゴリズムについて話し合うつもりはありません。

>>121

　 [ ﾟдﾟ]y-一~~~~　ﾃﾞﾌﾗｸﾞ?　ﾊｧ?　ﾔﾙｷﾃﾞﾈｪﾖ
　ﾉ[ ﾍ ﾍ

bit単位でファイル全部なめるとしゃれにならん時間かかりそうだし
2進→3進変換でさらにしゃれにならん時間かかりそうだし
2進用の辞書、3進用の辞書、4進用の辞書て具合に辞書だらけになって
あまり縮まなそうだな

ところでこのスレの圧縮アルゴリズムってユニバーサル符号化の方だよな?

>>124
えぇ。もう16bitまで調べてたらしゃれにもならない時間がかかりましたよ。
10キロバイト引っ掻き回して1時間半くらいでしたかねぇ。

違うだろエントロピー符号化だよ、よく見ろ俺。
ていうか2進だけ考えれば可変語長のHuffman符号化じゃんか
となると3進以上に変換するのは無意味だな。
たぶん2進→3進の時点で符号表の分だけサイズ増える
おとなしく算術符号なりRange Coderなり使え

風呂入ってる間にレスついてたか
上にも書いたが>>111のやってることは可変語長のHuffman符号化と変わらん
2進の時点でエントロピー程度まで縮まるので3進以降は全く意味がない

可変語長だからユニバーサル符号化+エントロピー符号化と同程度まで
縮まる可能性はあるが時間がかかりすぎる上に動的符号化に対応できそうにないから
bzip2とか7zipより縮まるとは思えない

バイト対符号化より縮まるはずだ！

http://ja.wikipedia.org/wiki/BPE

>>124
一回目の圧縮で辞書に登録するのは最も縮まる2進数1語のみだよ。

はじめに最も縮まる単語が1101だったとして
次に3進数のビット列で最も縮まる単語が10101(2が出てこない!)
だっとするとこれを3進数として辞書に登録しなければならず
回数を重ねるごとに辞書長は長くなる。

n　:　繰り返した回数。

n　|　(n+1)進数の単語　|　n進数の単語　|　・・　|　2進数の単語　|　(n+2)進数による圧縮データ

単語の統計の取り方と単語の切り出し方などによって縮まる単語は変わってくる。
例えば、00000だと統計的には単語00が4回出てくるが、実際圧縮してみると
220や022になる。重複している部分があるため2つしか出てこない。

>>125
16bitなのはハッシュテーブルにそのまま登録できるからという理由なんです。
10Kバイト=80000語だとその16倍(単語長)くらいの繰り返しで回数求められないですか。

2バイトの配列を(3の16乗)個用意しておけばbit列をそのままハッシュとして登録できる。

　　2バイトの配列を(3の16乗)個用意しておけばbit列をそのままハッシュとして登録できる。
って軽く30MB超えるんだけど

>>133
41メガくらいか。

データサイズが圧縮前より増えた＾＾；


開発停止しまつ。

減ることはあっても増えることはないんだよ。
減るまで繰り返すんだから。

んなこたーない。
どんなに続けようが増えるだけのこともある。

一回目の圧縮で縮めなかったらそのままなんだよ。
圧縮の定義から。

全く縮まない完全にランダムなデータはヘッダやらテーブルやらがつく分増える罠。
非圧縮にした所でやはりヘッダをつけざるを得ないし。

>>139
圧縮ファイルの書式のことではないんだよ。>>109で縮まらなくなるまで
続けるといってるだろ。一回目で縮まらなければ何もしないんだよ。

辞書は外部に持てばいいんじゃないの？
解凍ソフトと圧縮ソフトで同じテーブルを参照してればよい希ガス

と、暗号素人の俺が言ってみる。

>>141
辞書を外部に持ったらデータファイル1バイトにでも圧縮できるさ。
じゃぁその外部辞書ファイルはどうやって圧縮するのかって言う話。

そして、同じテーブルを参照する必要があるなら別なテーブルも勿論あるわけで。
そのアドレスを圧縮後のデータファイルの内容にするとしたら、勿論アドレスが重なってはいけない（同じアドレスで違うデータが取り出せてはいけない）為、
ファイルの内容と同じになってしまう。
と言う事はヘッダとかが付く分重くなって終了。

とファイル暗号化ソフトを作った事がある俺が言ってみる。

>>141
そういうコンセプトの圧縮アルゴリズムはすでにある。
辞書が固定でしかも巨大になってしまうので汎用的ではないが、かなりの高圧縮率を期待できる。

あらゆる文章は 13 バイトに圧縮可能ってやつ?w

声自演も

符号化の基礎は別の所で勉強することを勧める

ここはDOSもばあああああああああああああああああ

>>142
>辞書を外部に持ったらデータファイル1バイトにでも圧縮できるさ。
うん？汎用性なくしてどうすんの？
>じゃぁその外部辞書ファイルはどうやって圧縮するのかって言う話。
する必要ないんじゃないの？

ちょっと思いつきで言いますよ。
例えば8bitで区切って見ていったときに、一度も出てこない数があったらそれを記録。
1ビットずつ2個書いて16ビットにして一致する部分を探し、見つけたら8bitに置換する。
複数あったらそれの分圧縮になる。

とかどうですか？

＞1ビットずつ2個書いて16ビットにして一致する部分を探し、見つけたら8bitに置換する。

これじゃあ漏れには理解できない。1ビットずつ2個書いたら普通2ビット。

1010を
11001100にするってことですよ。

>>148
それって劣化BPEじゃね？

素人考えだが、画像を圧縮するときの手法を思いついたので聞いてくらさい。
1.輝度の情報を、基色と、それとの誤差に分解。
2.基色をランレングスとかで記録。

手動でシミュレートしてみましたが、どうやってみても圧縮前より容量が大きくなります。
本当にありがとうございました。

画像データは1KB当り1円が相場。
そのツールを公開すれば神になれる。

な、なんだってー！
じゃあ拡張子をjpgにすれば金がワンサカ・・・。

ただし名画級だとな。

ファイルサイズを一定にするツールは
セキュリティ上のニーズがあるかも知れんな。
大きいものは小さく、小さいものは大きく。
すべてのファイルを10MBにするとか。

ファイル分割で十分な気もするが。

そういやあの頃はフロッピーサイズに分割するツール、重宝してたな。

今はDVDサイズに分割するツールが重宝してるお。

>>148
俺が言った「辞書」って言うのは、元ファイルとまったく同等の物。
だから辞書一つにつき2つのファイルを1バイトに圧縮する事ができるが、辞書そのものがなければ復元不可。

>>160
つまりTHCompもどきだな

148だけど
>>160
だから、汎用性なくしてどうすんの？
分かってて聞いてるのよ。

>>161
thcompって、確か圧縮する（そもそも圧縮しないが）ファイルを削除→そのファイルを復元するとかいうネタがあったよね。

>>163
・DOSの隠しファイルとして、
・WindowsNT系に存在するストリーム機能を利用して、
・数十〜250バイトのファイル内容を、ファイル名にすることで、

見た目のファイルサイズを0にするジョークプログラムがあったと思う

thcompは、アルカイックレコードを参照する >>142 みたいな話
だが、アルカイックレコードを参照するためのポインタが、
結局は元のファイルサイズ（あるいはエントロピーやレート）と同程度になるのは明らか

408kbのデータをたった60バイトに圧縮することに成功しました！
そのデータを以下に示します。デコードはマウスでクリックするだけ！



"http://www.digitalpad.co.jp/~takechin/archives/susie347b.lzh"

課題：　
１、どんなプログラムを使っても圧縮出来ない１0Ｍバイトのデータを作成する　それより短いコードのプログラムを作成せよ

課題の補足：
　入力は行ってはいけない。　たとえば外部から乱数等の入力を行ってはいけない。
　擬似乱数を発生させてもかまわまい。

かまわまい

【 かまわ - まい 】
『構う』の受動態『かまわ』に、否定『まい』を付けた語句。

手順：

後方分岐しか出来ないシンプルな命令体系のCPUをエミュレートするプログラムを作る
そのメモリ空間を擬似乱数により埋めておき、先頭より実行、
未定義命令を実行すれば終了とする。

ランダムに生成したプログラムは時々無限ループに陥り、永遠に未定義命令を実行しない事がありえるだろう。

後方分岐しか出来ないので、停止が判ったコードはそれ以後のメモリは何でもよい
よって、先頭より順に全ての組み合わせを生成するコードを書き
順に停止するかどうか調べてゆけば、停止するかどうあの確率を求める事が出来る。

確率は当然0より大きく１より小さいので
小数点以下をバイナリで順に出力させる。

このバイナリは圧縮出来るか？

brainfuckでjpeg並のやつ作ったら称えてやるよ。
だからってC++のコードをbfに変換するヤツなんか作るなよ。

>97=>166,167,170
読んだ雑誌の受け売りしかできんバカは黙ってろよ。

agg

>>173
aggｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
ﾜﾛﾀｗｗｗｗ

　 [ﾟдﾟ]ゝ　ﾃﾞﾌﾗｸﾞﾂｲﾃﾞﾆｱｯｼｭｸｼﾏｼﾀ
　/[＿]
　　|　|
aggｗ{31}ﾀﾛ

寧ろegg

>>175
ﾜが消えてるよ

不可逆圧縮なんで。

あれ？非可逆圧縮？不可逆圧縮？

文法的には非可逆圧縮が正しいけど、不可逆圧縮という言葉も割と使われているのでどちらもいいと思う。

非｛可逆圧縮｝
不可｛逆圧縮｝
このように、装飾する区切りが違います。

修飾だﾊﾞｶﾎﾞﾝﾄﾞ

「（非（可逆））圧縮」だろバカ。

>>181
逆 に 不可 はつかんよ。

>>184
じゃぁ所謂「出来なくはない」の類の[否定＋逆]の文って一体？

[可能＋否定＋逆]　に訂

>>181
逆圧縮
ってナニ？

>>185
そっちじゃなくて、
　不可罰　罰する
　不可能　能う
　不可解　解する
　不可侵　侵す
　不可逆　逆?
という話。つまり言葉としておかしい。

不可は圧縮にかかる、逆も圧縮にかかる

可逆は熟語。

不可は熟語。

gooに聞いてみた。

> かぎゃく 0 【可逆】
>
> 元に戻り得ること。
> ⇔不可逆

> 可逆圧縮 【かぎゃくあっしゅく】
>
> 〔lossless（data）compression〕
> 完全復元を前提とした手順で，データを圧縮する方式。アーカイバーなどで用いられる。ロスレス圧縮。
> →圧縮
> →非可逆圧縮
> →アーカイバー

どうしろと

何だこいつら
頭悪すぎ

不可逆・非可逆で一単語だろ。
「可逆」というのが熟女

>>193
おまえはどうなの？

そろそろ最弱の圧縮アルゴリズムでも語ろうか。

つ BASE64

それが圧縮アルゴリズムである限り、最弱は只のアーカイバだろ。

>>111,135
のが最強だろ。

萌え

>>1-200 は圧縮すると 0 bit になりました

>>201
それじゃ「圧縮」ではなく「消滅」か「無視」の類。

>>1-202

　 [ﾟдﾟ]ゝ　ﾃﾞﾌﾗｸﾞﾂｲﾃﾞﾆｱｯｼｭｸｼﾏｼﾀ
　/[＿]
　　|　|
"{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}⇔１{3}Ｍｗ{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}

>>203
実はかなり適当？

テキストの非可逆圧縮というか、情報縮約というか、
単に出現回数を数えただけじゃないか？しかも、不正確に

不可逆でいいんならいくらでも可能

非可逆でいいならどんなデータでも1バイトに圧縮（縮小）できるが。

>>205
「曖昧」と言うものはなかなか難しい。

>>207
じゃあ漏れは0バイトに。

>>208
不正確なら簡単だ

>>210
ところが、情報理論的に不正確さも決められているので、
闇雲に情報を削除していけばよいということでもない。

>>209
消去じゃん。

昔いろんな圧縮形式の圧縮率比べまくったなぁ。
画像の可逆圧縮とか、個人で作ってる形式多くて楽しかった。
ＰＮＧしょぼいよ！！とか、ＰＩＣ２つえええとか、ＴＬＧ６すげえなにこれ！とか

文章を圧縮するに当たって、文字情報を記録するんじゃなくて意味を記録すればよくね？
文字を書いた人間の、その文に対応したニューラルネットワークの結びを記録、されば読む人間にとっても、その結びから一瞬で意味を理解する事が出来る。
150年ぐらい後の話だけどね。なんじゃこれは、SFか。

意味を解釈するプログラムのサイズが馬鹿でかくなる

プログラムが意味を解釈する必要は無い。
記録する情報は、記録者の脳内ニューロンの繋がり（語句）を集めたもの（文章）だからだ。

暗号化の対象がASCII文章のみなら、考えたアルゴリズムあるよ。
ASCII文字のうち有効文字は7750文字ちょっとで、12ビットあれば十分保存可能だから
保存に16ビット使う全角文字は4ビット落ちるし、保存に8ビットしか使わない半角文字の場合は
特殊な開始コードとかを使って無圧縮にする。

誰か作ってくれ。

age

>>217
その「特殊な開始コード」に必要なビットが、バカにならんのよ。
無圧縮部分に圧縮されていない印を付けると言うことは、その部分で
データが膨らんでいると言うことだから。

>>217
ASCII文書で有効文字が7750とか、もう言ってる事がめちゃくちゃ。
人格も発言内容も否定したくは無いが、会話の土台を築くために
まずは "ASCII CODE"とかの意味を調べてくれ。

まあアルファベットと空白だけの文章なら一文字7bitでいけるけど、
ってそういうことを言いたかったんじゃないのか。

6bitでいけるわボケ
アホは黙ってろ

>>220
言いたいことの意味はわかるが「会話」じゃなくて「対話」な、
この場合。

>>223
脳内定義持ち出してまで
なにを必死になってるんだろう。
とりあえず辞書引け。

俺が実践している最強の画像圧縮アルゴリズム

画像を眺めながらオナニーをしてデータによって握りの圧力や刺激点を変える。
解凍するときは目を閉じて暗号化時と同じ手法でチンコをこすると画像がまぶたの裏に！

抜けない画像は削除
これで5%くらいまで非可逆圧縮できますよ

>>225
それ、すこしでも「つぼ」間違えたらぜんぜん違うファイルにならないか？

つか保守&アゲ

なんでも全部0xffに縮めて、相手が怒ってきたら謝ればいいんだよ。

【IT】米Microsoft、新画像フォーマット「Windows Media Photo」発表
http://news18.2ch.net/test/read.cgi/bizplus/1148626281/

>>152
写真とかだとさ、大体色の同じような場所は固まってるよね。
だからこの圧縮方法結構使えるんじゃね？

１ドット単位のチェック柄の画像（ディザとか）で死亡

画像で圧縮率がいいのはTLG6かな。
場合によってはERIやJPEG2000が上の場合もあるけど。

例えば、下の2行を圧縮するとき


画像で圧縮率がいいのは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(任意だけど固定) づつまとめて

89 10001001
E6 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

としてから圧縮を始めると圧縮率が上がるような気がするけど気のせい？

>>233-234
文字が全部全角文字なら圧縮率が上がる可能性は十分考えられる。
半角文字列ならあんまり変わんないと思う。

>>235
最上位ビットに規則性が生まれることに違いはないから改善するんでね?

普通にやるより 7/8になるという主張？

>>233-234
を、１６づつまとめるのはめんどくさいから、全部一気に縦横並べ替えたやつを作った
何もしてないやつとZIP圧縮で比べた。データは日本国憲法

21,684　原文
8,243　普通にZIP
19,187　並べ替えてZIP

上位ビットの部分は、偏るけど、それ以外の部分はほとんどホワイトノイズ。

そんなことしたらある文字が前後の状態で違う文字になっちゃう。
一意性がなくなって、ある時は「日本」だったのにいきなり「某国」とか。
ビット単位で変換したんなら符号化もビット単位で見ていかないと圧縮できないよ。

ま、そのモデル化が効くデータも中にはあるかもね。
画像くらいしか思いつかんが。

俺も手を動かしてたんだが>>238に先を越された
やっぱり圧縮率下がるよなぁ

16づつまとめるのがミソなんじゃないでしょうか？

誰か、組み込み系で圧縮アルゴリズム使ってる人いますか？
たとえば、ログをメモリに格納する時とか
LANなどでデータを送る際に圧縮しておくるとか
組み込み系ですから、圧縮率も重要ですが、なによりも速度重視のアルゴリズムを
考える必要があるのでしょうかね？

>>241
並び順が変わるだけで大して違わないんじゃね?
１６バイトで割り切れないサイズの時の処理とかめんどくさいし

>>242
ハードウェア圧縮なら普通にすると思う

>>238
ZIP以外の形式でも調査ｷﾎﾞﾝ

lzhとかcabとかrarとかtarとかoarとか。

ホワイトノイズになってしまうっていう点で思いついたんだが

偶数バイト目だけとったものと奇数バイト目だけとったものを
別々に圧縮して連結してみたらどうなるかなぁ

>>246
やってみれ

圧縮に関してはわからない素人ですが
テキストだろうが音だろうが画像だろうが、所詮0と1のデータですよね？

そういう観点で圧縮アルゴリズムを考えた場合、なにか最適なアルゴリズムって
ありますか？

ハフマン

愛しのドレッドゾンビたんｷﾀｺﾚ

魔法斧で瞬殺しやがったｗｗｗｗ

激しく誤爆すいません

>>248
それを討論中

>>248
ありません。

特定のタイプに強いアルゴリズムは作れるけど、
そのアルゴリズムは他のタイプには弱くなる。
アルゴリズムを切り替えれば良いと思うかも知れないけど、
全てのタイプに対応した全てのアルゴリズムを用意したとき、
どのアルゴリズムを使ったかの情報がファイル情報と等しくなる。
結局一般的な(と思われる)情報源に強いものを選ぶしかない。
で、LZとかBWTとかPPMに落ち着く。

>>248
あるよ。任意のサーバーにファイルをうpしてURLを晒せばいいのさ

ここで語る圧縮はやはり可逆なものに限られますか

辞書を毎回生成すれば
大容量の辞書を持つ必要はない

あと圧縮時間は掛かっても問題ないと思う
展開時間が通常とそれほど変わらないのであれば配布側が使うメリットは充分にある

メモリの中身を圧縮するという意味では、
バイナリデータに特化した圧縮アルゴリズムを考えればいいのでしょうか？

あと、自分で考えたとしても、特許とか絡むと使えないんですよね？

組み込み系で圧縮を考えると、最悪でも数ms、できればμsの時間で
処理しないと、いけないですよね？

ということは、組み込み系でソフトウェア圧縮はむかない？

実装している人がいましたら、どのような用途で使ってますか？
そもそも、ここにファームウェア開発の人がいるかわかりませんが

はてなマーク多いな

なんかずれてるな。
メモリの中身が判らないのに向いてるも何もあったもんじゃない。
そもそもメモリとファイルで違いなんかないだろ。

テキストとか画像とか音楽とかなんかの設定値とか、
それぞれ性質が全然違う。
こういう場合は素直にハフマンが良い。

>>257
＞バイナリデータに特化した圧縮アルゴリズムを考えればいいのでしょうか？
PC で扱えるデータは「全て」」バイナリデータですよ。

>>258
CPUのスペックもデータの帯域もわからないのに、向くも向かないも・・・
圧縮はそもそも用途が少ないような。
展開の方は結構ソフトウェア実装も多いみたいだけど。

LANコントローラあたりの設計だと、圧縮していたような・・・
忘れた。

ZigZagスキャンでもしとけよw

なつかしの540アルゴリズム

「aaaaababababcabc」
　↓
a:aaaaabbbbb
b:aaacc
c:a
　↓
「aaaaabbbbbaaacca」
　↓MTF
「a0000b0000100c01」
　↓適当にエントロピー圧縮。
（ﾟдﾟ）ｳﾏｰ

ホシュ

>>258
モデムのデータ圧縮

ところで、結局>>1のビット羅列による圧縮はＦＡ出たの？
ﾓﾚ昔ハフマン圧縮勉強した直後の頃に似たようなこと考えたことあった。
最終的には、ファイルを"0"(0x30)と"1"(0x31)に変換してから普通に辞書圧縮したら論理的に近似可能だということに気付いた。
で詳細は忘れたが、実際にやってみて（´･ω･`）ｼｮﾎﾞｰﾝだった記憶がある。

ＦＡが出たなら知りたひ・・・

FAという訳ではないんだが一応答えらしきものを示しておこうか。

一般に辞書との一致で置き換えるアルゴリズムは圧縮率が悪い。
何故か？
今、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ずつ無駄を増やしているということになる。

じゃあどうすればいいのか？
書くのが疲れたので終わり。ごめん。

ここでいう最強は
圧縮率がよいアルゴリズム？
それとも同じ圧縮率でも高速なアルゴリズム？
それとも実装が簡単でそこそこ高速かつ圧縮率のよいアルゴリズム？

あと、特許とかあるからわからんけど、そういうものにかからないで
なるべく速いアルゴリズムといったらなんでしょうか？

やはり、特許がきになる・・・

>>267
>>111が圧縮率の悪さに唖然として開発停止して以来誰も作り出すような発言や完成したような発言はしていないように思うがどうか。

>>269
スレタイから察するに3つそれぞれの意味での「最強」なのでしょう。

BlockSort+適応型符号化でいいような。
何が最強かも定義がわからんし。

スレ違いなのはわかっています。
ですが教えてもらえないでしょうか？

zipファイルのパスワードを解析したいのですが
そういったことは出来るのでしょうか？

>>272
このスレッドはプログラム板にあるわけだが、
プログラム板(作る人が技術的な話をするとこ)ではなくて、
ソフトウェア板(使う人がいろいろな話をするとこ)のスレッド一覧を、
適当な単語でページ内検索しなさい。
「教えて」とか「質問」とか検索するといいよ。

わかりました。
他のスレを探してみます。
スレタイからして実際にしようとした人とか
詳しい人が多そうとか思っちゃいました。

いやだから、鼬害だってばさ。

ネットにデータをうｐってハッシュ値をURLにすればよい

http://live23.2ch.net/test/read.cgi/livecx/1151356052/

66 名前：名無しでいいとも！[sage] 投稿日：2006/06/27(火) 06:47:46.25 ID:3HXDRC1i
　zicoって何かの圧縮形式みたいじゃね？

というわけで、ここでなんか圧縮形式が完成したらジーコ形式って名前にすることに決定。

間違っても最強にしちゃいかんな
むしろ元サイズより増えるくらいでいいんじゃね？

G Compression Archiverはどう？

鼬害だって言ってるだろ、池沼か？

>>278
まぁ、どんなファイルに対してもサイズを縮めることができるような可逆圧縮は存在しないからなぁ。

つまり、元サイズより大きくなるのが合理的だ、と？

そうだけど？
究極的には圧縮はただの変換(写像)だから、
「元のサイズ+適用したかしないかの1bit」が最小の期待値になる。

>>278
無圧縮圧縮を思い出した。

http://72.14.235.104/search?q=cache:z5jvOgJbrB0J:download.microsoft.com/download/1/6/a/16acc601-1b7a-42ad-8d4e-4f0aa156ec3e/WMPhotoSpec_v10.doc+WMPhotoSpec_v10.doc&hl=ja&gl=jp&ct=clnk&cd=1&client=firefox

保守

あげあげ

圧縮のアルゴリズムって特許とか色々ありすぎ。
何を使って作ったらいいのかわからん

誰も思いつかないような新しい方法を考えればいいんじゃね？

>>289
その発想は無かったわ。

もう、出尽くしてない？

いつの時代も雑魚はそう言う。
そしてコロンブスに卵で殴り殺されるんだ。

量子コンピュータやDNAコンピュータで使えるアルゴリズムという
未開拓な分野もあるぞ

paq8とかlzmaとかtek5辺りのハードウェアアクセラレータまだー?
apache/firefoxで使えるようになるのはいつー?

誰も思いついていないような新しい方法

1. 16進ダンプを画面表示する。
2. 全て暗記する。
3. 何かのキーワードでそれを思い出せるようにする。
4. 別のコンピュータの前に座る。
5. キーワードを思い出す。
6. 全て打ち込む。

このようにすることにより何Gバイトのデータであったとしても
キーワードの長さに圧縮することがfhdsfdsjfけおwlw

2. が無理だと思われ

>>296
πを何千桁も覚える人がいるんだからいつかそのうちできるようになるさ。
なんだったら事前に bzip2 圧縮して小さくしておけばf;ぇkwlけ２いfそb

>>297
π は 10 桁。
http://www.f7.dion.ne.jp/~moorend/news/2005020901.html

>>295
人間という外部記憶装置に保存するわけですな

それはしんどいですな

そうだ、紙に穴を開けて保存するのはどうだろう？
オルゴールと同じ原理だ。

鉛筆で書けば消せるし、また書けるよ！

もはや圧縮アルゴリズムではないなｗ

任意・ランダムで生成される32ビット情報を
24(または23）ビットにまでビット幅を圧縮してみて下さい。
intの値をfloatの仮数に埋め込みます。

>>304
それ何の意味があるの?
#そもそも無理だし。

意味があるかよりも、32bitを24bitに圧縮する方法ってことでしょ？
32bitが特定（や有限・決まっている）の値なら簡単なんだけどね。

いやだから、24ビットに圧縮しても32ビットの空間を消費するなら意味ないじゃん。

上位8ビットが非ゼロならば、情報源を含むその辺り（空間的に）の
機械や生き物が破壊されてしまうようなシステムを構築すれば良い。
表現できないものは無かったことにするという圧縮方法。

上位8ビットの違いによる差異を認識できるものを全て破壊する
という方法もある。
誰にも違いがわからなければロスレスであるという手法。

>>304
xが32ビット整数だとして、C言語で書くと
x = (x >> 8) & 0x00ffffff;
但し不可逆。

全ての取りうる値での可逆圧縮は不可能。

>>308-309
y=x & 0x00FFFFFF
これで x の8ビットを違うアルゴリズム処理すれば良さそう。
当然可逆圧縮・復元できないと意味ないけど、
残り8ビットは256通りだから、そんなに不可能ってほどでもない。

32*3 = 24*4
詰めかえるだけなら圧縮とは言わないが。
前提が無いと、できるともできないともいえない。

>>311

＞詰めかえるだけなら圧縮とは言わないが。

ｺﾗ！
ｳｿ言っちゃいかんにょ。

>>312
いわねーよ

>>313
置き換えで圧縮する、固定長符号化もたまには思い出してください(つД・)

符号化

>>314
任意の固定長符号で置き換えるなんて話お前しかしてねーよ

なんというか問題が難しかったようですね。
int32の情報ををfloatの仮数に埋め込むというのは一例です。
intで表現される色情報 a|r|g|b を24bit構造体 struct Enc_T {char val[3];}に
埋め込むとか考えると、やる気出ますか？

もっと簡単な問題だと、32bitを31bitに圧縮してください。
圧縮率は (31/32)*100パーセントになります。
8bitを7bitでもいいけど。

>>317
話が摩り替わってるじゃん。
int32bitをfloat32bitの仮数部に入れるって話は消費情報量を削減できてないだろ。
単に有効情報量が減るだけじゃん。

>>318
>>304によると32ビット情報を24ビット(23ビット）に圧縮してからだと思うが
もしかして、float f=3.14f; int j=(int)f と勘違いしてないか？

32ビットの情報を24ビットに圧縮しても、その情報を32ビットのマスに入れたんじゃ意味ないだろと言っている。

>>320
なんと言うのか、話が逸れてるんだよな…
32ビットのマスに入れるかどうかじゃなくて、
圧縮する方法・アルゴリズムが重要なんじゃないのか
その使い方や用途は君が関知する問題じゃないだろ？

ランダムな32ビット整数を24ビットに圧縮するという話についてなら、とっくに無理と言ってるが。

どうして？

32bitに圧縮しきれない可能性があるからじゃないか？

32MBを24MBに圧縮できる（アルゴリズムがある）のだから
32bitを24bitに圧縮も考え次第で出来るだろ。
アルゴリズムというのは、そういうのじゃないのか？
ところで、無理とか不可能とか何を根拠に言ってるんだろう。

みんな考えてる問題の定義と目的がバラバラのようだし、
議論は無理。問題の説明が足りなさ過ぎる。

勝手に考えると、
元が解らなくなっている可能性があってもいいなら
aだけ捨てたら？と思ってしまうが。
32bitを31bitにしたかったら、どこか1bit捨てたら？

圧縮のアルゴリズムで特許をとられないのって、何があるの？

このスレはレベル低いな。
これじゃ優秀な奴は誰も来ないぞ。

ところで「とられない」ってどこの言葉だ？

特許に引っかからないのは？って聞きたいんだろ？

>>329
おまえはエスパーのようだが、どこの惑星から来た？

>>327
すでに切れた特許なら再び取られることは無いだろうな

>>325
> ところで、無理とか不可能とか何を根拠に言ってるんだろう。
情報量を考えれば自明だからちゃんと勉強しろ。
圧縮後のデータは最大で24MBの情報量しか持ち得ないのに、
それを伸長するのにどうやったら任意の32MBデータが出現しうるんだよ。

まあ、
　> 32MBを24MBに圧縮できる（アルゴリズムがある）のだから
というところから、圧縮を魔法かなにかと勘違いしてるのは分かるが。

>>325
「32Mを24Mに圧縮できる」というのは結果論であって
そのアルゴリズムで常に24Mに収まるという事ではない。
32Mのデータを24Mに圧縮できる「可能性」があるというだけで
32Mを24Mに確実に圧縮できるアルゴリズムというわけではなく
最悪の場合32Mのデータは32Mの容量を必要とする。
もしもどんなデータでも確実に32M→24Mに圧縮できるとしたら
その24Mのデータも確実に18Mになるわけで、そうやって圧縮していけば
データは無限に小さく圧縮できるはずだが、そうはならないよな？
32Mが24Mに圧縮できるのは、32Mのデータの中に冗長な情報が含まれているからで
結局は平均情報量に近づく事はできてもそれ以下になる事はない。

そして完全にランダムな32bitのデータは
冗長な情報が全く含まれていない32bitのデータという意味
(もし出現パターンがあるならそれも情報と考えられる)なので
ランダム32bitデータを24bitにするには8bit捨てるしかない。

どんな 32bit のデータでも常に 24bit に圧縮できるアルゴリズムがあれば、
それを何度か繰り返し使えば世の中のすべての情報は 24bit にまで圧縮できることになるな。

　　　　　　　　　　[ﾟдﾟ]
　　　　　　　　　 　[ヽ□
　　　　　 　　　　　|　 |　
□□□□□□□□□□□□□□□□□□□□□□□□□

　　　　　　　　[ﾟдﾟ]
　　　　　　　 　[ヽ日
　 　　　　　　　|　 |　
日日日日日日日日日日日日日

　　　　　[ﾟдﾟ]
　　　　 　[ヽ品
　　　　　 |　 |　
品品品品品品品品

　　[ﾟдﾟ]
　 　[ヽ昌
　　 |　 |　
昌昌昌昌

ヽ[ﾟдﾟ]ノ
　 [＿]　
 　|　 |　
　晶晶

そこでTHCompですよ。

いまオレすごい圧縮を考えたんだ！
データの最後のbitが0だったらそのbitを削るんだ。
1だったらそのまま。
これで1/2の確立でどんなデータ、
ランダムなデータでも1bit削れるよ！
同じ感じで後ろ（先頭でもいいけど）1byteが0x00なら削って、
0x00以外ならそのまま。
1/256の確立で1byte圧縮できるよ！

>>337
削るのはいいんだがどうやって復元するつもりだ？

まずはそのまま、エラーが出なければOK。
駄目なら最後に0をくっつける。
これでどんなデータでも復元できるよ。
1byteのも同じ感じで、エラーが出なければOK。
駄目なら最後に1byte分の0x00をくっつける。

付けても付けなくても同じ結果を得られる場合もあると思うが
そのときはどっちでもいいんだよ！

運まかせ

>>339
その方法だとエラー検査のための仕組みを別に用意しなければいけなくて、
それを厳密に行うためには圧縮前のデータと同じだけの容量が必要になる。

必要な32bitデータの入ったマシンをカメラで撮るんだ
そしたらそのマシンは捨ててしまう
これで圧縮が出来た

後でそのデータが必要になったら、フィルムを現像して思い出に浸ろう
写真の裏にマシン名も書いておくと良いな

どんな 32bit のデータでも常に 1bit に圧縮できるアルゴリズムがあれば、
それを何度か繰り返し使えば世の中のすべての情報は 1bit にまで圧縮できることになるな。

>>343
つまり全ての情報は同じって事。あなたとわたしも全く同じ。

ここは哲学的なインターネットですね。

つまり、熱的終焉だな。

ここは物理学的なインターネットですよ

じゃあ俺は情緒的に

>>344
待て、1bitなんだから0か1で全ての情報は二つに分けられることに

Lz77

>>349
完全平衡状態に至って熱的死を迎えるか、
再度収縮して次のビッグ・バンが起きるか、
の2つってことか。

猫を殺したくなければそれ以上踏み込んじゃいかん

半分死んでいて半分生きている猫

轢かれて体半分潰れたが運悪く首は折れなかった みたいな感じか

0.5bitの情報を記録できる素子がほしい

>>355
おまいの脳細胞

>>355
素子2単位で1bit分の情報を記録するようにすればいいだけじゃまいか

それはつまり今の3.5in 750GBのハードディスクを作れる技術が
1.5TBで作れるようになるまで待てと言ってるのか？

なんだ、来ない間にずいぶんと白熱してたんだね。
もう解決してるんだけど、つまんない話ばっかりでお前らには教えてやんない。
>>335,>>337は少し面白かったけど、まだまだ。

みんなもホントは解決してるから大丈夫。

最強の圧縮アルゴリズムっていうけど、
それってどんなの？　オレ的には、
１つのアルゴリズムで結果を帰還させて
圧縮できなくなるまで繰り返すようなのが
美しいと思うのだけど。

俺的には傾向を見つけ出してそれに基づいて圧縮するのが美しいと思うけど

>>361
だから、それって具体的にどうやるわけ？

あまりのアホさに361をスルーしたが、
362と363が俺の言いたかったことを言い尽くしていたことに感動した。

>>361 感動した！！

具体的な方法については言及しないつもりでした。
ただなんとなく美しい気がしたので。
自分では無理な気がしています。
具体的に無理な理由を説明できるならお願いしたいのですが・・
逆に出来るよ！というのであればなおさらお願いしますー

>>361
その性質をもつ自明な圧縮の例

圧縮 f (x) とは
　x == 0 のとき 0
　x > 0 のとき x-1

何度か繰り返せば、どんな数も 0 に圧縮できる。

復元は何になるの？

「どんな数も」ってのは間違いか。入力は自然数限定ってことで。

＞復元は何になるの？
何度繰り返したかを覚えておいて逆関数（1足す)をその回数繰り返せばよい。

最強を語る前に最弱を語ろうではないか？

圧縮になってないのは自明だな。

どんな頑張っても圧縮率には限界があるんだから
なに食わせてもソコソコ縮んで程ほどの圧縮解凍速度
そういうのが良いアルゴリズム。
さらに実装したときに悪意のあるデータによって
セキュリティが脅かされるような不具合が生じない事や
暗号化などまで考慮されていると最高

>>369
その回数はどこで覚えておくの？

>>373
「繰り返し適用して・・・」という手法をとる以上、圧縮後のデータとは別の
どこかに記録するより他ないんじゃないかな。人間が覚えておく等。

>>362
そのアルゴリズムは結構出尽くしているかも…
視点を変えてみると面白い！

近似する式にするってのすごいよね。

どういうこと？

自分で圧縮したデータが、自分にとって都合のいいデータであること
なんてないよね。きっと。
圧縮ってデータの傾向を利用して可能性を省くことだから、
圧縮後のデータは傾向が消えてるだろうし。
２つのアルゴリズムで交互に通せばいいのか？
でもさまざまな傾向に対応できるように
いろいろなアルゴリズムを用意して・・・とやると
>>362ですよね
結局は>>372に落ち着くと・・・。

>>367
基本の形、ということでしょうか。
圧縮できるところは圧縮して、出来ないところはそのまま。
繰り返すたびにデータが変化していって、だんだん圧縮できなくなる。
そんなイメージ？

エントロピーが云々で何とかかんとか

もともと自分にとって都合のいいデータって絶対に存在しないでしょ？
何を言ってるんだ、こいつは。

>>30

1001010110101、というのを、a・sinA+b・cosB+…+n・sinN、みたいな、合成波形としてとらえて行く。
圧縮・展開時には、フーリエ変換を使用する。
パラメータとして、a、A、b、B、…、n、N、だけを設定してやればよく、効率の良い圧縮となる。

とかは、既出？

ずいぶん工学よりだけど、圧縮アルゴリズムなんてそんなもんだよ。
もうすこし具体的に書かないと言いたいことが見えてこないから、
既出かどうかは分からない。

少なくとも、非可逆圧縮には利用されているのは間違いなさそうな気がする

>>381

一時話題になった、可逆で1/100に圧縮できるというアルゴリズムが
そんな方法だった。

もちろん、一斉に「ダウト！」を喰らってたがｗ

データによっては十分可能だと思うが

スーパーマンが両手で炭の塊を圧縮したらダイヤモンドになってたが、
別物になっちゃうのはアウトだな。
スーパーマン使えねえ。

高温・高圧
だからどうしてなったのか不明だな

しかもカット済みのダイヤが出てきたもんな・・・

>>380
「都合が良い」の度合いの問題ですよ〜
実用していて発生するデータの内で。
そりゃ作ろうと思えばいくらでも作れますから。

やっぱいくら考えても
１つのアルゴリズムで繰り返して使う・・・なんて思いつきませんわぁ
処理時間は処理回数と比例するだろうから
組み合わせを全て試して最適解を出すようなタイプかなぁ
とは なんとなく思いますが。経験上

コテハンは最後にしときます

圧縮で良書がないね〜

圧縮でかよ！

>>287ぐらいまでの停滞っぷりが嘘のようだw

でも、本当に圧縮技術の良書ってないよね。
なんで？

論文嫁

>>390
Cマガジン
圧縮アルゴリズム

が
あんま余計なこと書いてなくてよい。

対象が何かを分析し、対象の種類と特徴によってアルゴリズムを可変させるのが
最強のアルゴリズムであって、１つのアルゴリズムだけですべてを適用させる
汎用のアルゴリズムなどあるわけないだろ。ｗｗｗｗｗｗｗｗｗｗｗｗｗ

新しいアルゴリズムは開発しないのか？

助けてアルゴマン！

>>268
＞そしてこれらの選択肢は全て結果が等しい、つまり等価なわけだ。
＞同じ結果に対して別の選択肢が存在するという事は、
＞それはつまり冗長だということになる。
詳しい理論や真偽の程はともかく、感覚的に納得の行く説明�dクス
>>270ﾓﾚにもそのように思える。
しかしそれはﾓﾚの頭が悪い所為かも知れないと思って聞いてみた。

zip32.dllとzlib使った自前のプログラムで比較したんだけど圧縮率に結構差がある。
zip32.dllはdeflateだけじゃないの？

>>395
圧縮アルゴリズムは
アルゴリズムの説明は確かにいいかもだけど
プログラムについての説明がない、ソースコードのリストがあるだけ

C言語の入門書でも読んでろ

そうしとくぜ

>>400
7z で -tgzip -mx=9 オプション指定すると、もっと圧縮された .gz
形式がでるよ。

アルゴリズムばかｗｗｗｗ

なに興奮してんの(^_^;

アルゴリズム体操

アルゴリラ？

>>26まで読んだ俺様が以降を読まずにレス

>>1エントロピーと言う言葉をぐぐってからこないと
大恥かくことになるよ
もうおそかったらごめん

ボクの部屋はエントロピーが増大する一方です。

ぼくのおちんこは(

CRCエラーです
伸張出来ません

伸ばすことに成功しました。
しかし、ふにゃふにゃになり硬くなることはありません。

p2pの圧縮ソフトはどうだろうか。
1kぐらいのファイルに保存することができる。

>>414
p2pのって、どういう意味だ? ファイルが分割されてあちこちのサーバにあるとか?

それって結局はthcompよね

質問させてください。

テキストファイルではなく、プログラム形式のバイナリファイルを
圧縮及び解凍する目的で利用するなら、どのような圧縮解凍アルゴリズムが
適しているでしょうか？

現状の候補はLZSSです。

また採用する条件は以下です。
・解凍スピードが著しく遅くないこと。
・WEB上でC言語のプログラムソースサンプルが公開されていること。

他に思いつくのはここでもでてくる以下のものたちです。
ハフマン
LZ
BPE

アドバイスお願い致します。

>>417
既存の自爆形式で何か不満でも?

upx

何でもいいんじゃないか？
例えば、あえてテキスト用途の圧縮方式を使ってもいいんだ！という意気込みがないとねぇ。

どうでもいいことかも知れないけど、
テキストの圧縮を考えると、日本語と
欧米では事情が違うよなぁ。
UNICODEなんか、漢字がばらばらに
なってるから、圧縮難しそうと思う。

感じがバラバラにならない文字コードに変換してから圧縮するんだ

というか、文字の意味なんかどうでもいいから圧縮に都合が良いように
変換すれば良いんではないか?

0を白、1を黒と見立ててイラストロジックにすればかなり圧縮されるのでは？
素人考えスマソ

>>424
まさにその考えで実装されたのが、FAXで使用される modified Huffman
（実態は連長圧縮に近い）

より数学的に 0/1 の列を置き換えるのが、数え上げ法と Elias 符号

modified Huffmanって白と黒の数を数えるんでしたよね？
イラストロジックの様に黒の数だけを記録して白の数を完全に無くしてしまえば
データにもよるけれどかなり削れるんじゃないかなぁ、と
イラストロジック自体絶対に解けるものじゃないのが難点ですが
解凍時間に制限がなければ何時かは解凍できるんじゃ・・・という希望

>>426
適当なイラストロジックで必要なビット数計ってごらん。大した圧縮率にならないから。

>>426
＞イラストロジックの様に黒の数だけを記録して白の数を完全に無くしてしまえば

イラストロジックは横だけでなく、縦方向の情報もあるので、そもそも倍になっている。
縦横の情報より、黒白にすれば一次元で表され効率がいい。

流れ読まずに書き込み
>>26
それはTHcompのアルゴリズムじゃないか？
>>29
Web上に辞書を置けば解決。
っていうか、既にアップデートした段階で圧縮されているともいえる。
つまり俺らは既に最強の圧縮アルゴリズムを意識することなく使っている？

>>429
物怖じせず、正直に言うと、

バカじゃないの？

暗黙の了解という言葉の意味を理解しているならば軽率な発言は出来ないはずだ。
情報の本質を理解している者ならばなおのこと。

>>426
黒だけとかにすると、場合によっては解凍不能になるのは別に置いといて、
何ビット単位で並べるかによって圧縮率は異なるから（確率的に。なぜなら圧縮するデータが異なるため。）
いかに（時間的に）効率よく圧縮できるか、又いかに圧縮率を高められるかにおいてかなり疑問なのだが。

思いついた。

まず配列に圧縮するデータを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の数を記録する。
解凍は、逆の計算を行えば出来るはず。


実装面倒なので誰かテスト頼む。つーか既にあったら教えてくれ。名前。

>>433
MTF/UTC/ORTの族に近いと思う。いわゆる順列符号とか再帰時間符号。
ローテート回数が再帰時間に相当するようだから、当たらずといえども遠からずかと。

あと、0/1列上だと、数え上げ符号や算術符号が存在しているので、
少なくともこれらより優れていそうなものじゃないと。

実装してみたらアルゴリズムが悪いのか相当遅かった。
それと、iの値を記録せずに前回のiとの差分を記録した方が記録効率がいいことが分かった。
後ひとつは、出力結果をさらにハフマンとかで圧縮しないとファイルがでかい。
（ただし0と1の比がかなり偏っているので再圧縮は効率が高そう）

>>434
情報thx。調べてみる。

>>433
iの値が0の連続の個数（のようなもの）、回した回数が1の連続の個数ってことで
たんなるランレングスのように思えるが・・・

torrentファイルを使う。

仮にﾃｷｽﾄﾌｧｲﾙだとして出現頻度が
Aが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とかでないと駄目ぽなのか

最強の圧縮はゴミ箱だ

うん。
確かに最近の OutlookExpress は最適化を行うと
dbx ファイルがごみ箱にもコピーされるようになったね。

展開の速さならLZO

以下の条件を満たすオープンソースの圧縮、伸張アルゴリズムはありませんか？
WEB上で公開されているものであれば良いです。

■条件
LZSS法、ハフマン符号化以外
（すでに所有しているため）

ハフマン符号化よりも伸張のスピードが速いもの。
圧縮時のスピードは問いません。
伸張が早ければそれでよいです。


>>441さんのLZOはよさそうですが、
プログラムソースを見つけることができませんでした。
よろしくお願い致します。

http://wiki.osask.jp/?tek1/comp

ウェーブレットとかの話はでないんだな

>>442
BPEでいいじゃん。

>>442
調べる能力もないのかおまいは。
ぐぐったら一番上に出てきたぞ。

実用レベルだとLZ77+ハフマンが一番速いよ。
つかLZOもLZ77だし。
LZ77はただのメモリコピーだから一番速い。
ハフマンはやり方次第で表引きに出来るからこれも相当速い。
>>442
という訳で、その条件を満たすものはないよ。残念ながら。
まだ遅いと感じてるなら実装が悪いだけ。

>>444
残念ながらここの住民のほとんどは、高等な数学を扱えるほど頭がよくありません。
マルチエンコードみたいな技術の動きを読み取るほどの視野も持ち合わせていません。

まあ書き込みをざっとみればわかるだろ。

>>447
ハフマンよりレンジコーダーのほうが速くね？

>>449
いや、ハフマンの方が2,3倍速い。
Athlon64 X2 2.0GHzのマシンでRam Disk上で計測した場合、
ハフマン 60-80MB/s
レンジ　 20-30MB/s
こんな感じ。
どっちもcで書いて結構チューニングしてる。
ファイルのi/oも含んでるから、
圧縮率の分だけ気持ちレンジコーダの方が有利かな。
LZとかなしで純粋に1byteずつ符号化した場合ね。
あ、上の数字は復号だよ。
符号化も同じようなもんだけど。

上からモノ言ってる奴って他のスレでもそうだが、
自分から答えを教えるってことしないよな。
他人の非難は出来るけど、その実、自分で答えを
導き出せない、レベルの低い奴なのだろうか？
まぁ、2ch見てる程度の人間だから仕方がないかも。
他人の非難しかしない奴より、なんでもいいから、
自分の意見を述べる奴の方がましってのは、
どこにあっても同じだと思う。

まあ、なんだ、落ち着けよ。
こんな過疎スレで誰に言ってるのかよく分からんが。

コピペだ反応すんな

>>451
どこを縦読み?

>>450
ハフマンのが速いって怪しいな。もしかして静的ハフマンか？
動的なら木の操作が入る分、ハフマンの方が不利だろ。
SSE2を使って最適化したレンジコーダがハフマンに劣ることってありえない。
一度チューニングしたそのコードを書いてみ。

0圧縮

>>455
怪しいと言われても実測値だからねぇ。
もしかしなくても静的ハフマンだよ。
動的ハフマンなんて普通使わないでしょ。
木も使わないよ。
SSEは使ったことないから比較出来ないです。ごめん。
アセンブラあまり使えないし。
ただレンジコーダはSIMD化出来る部分が少ないはずなんだよね。
1bitにつき必ず一回は整数の乗算か除算が必要だしね。
ハフマンはシフトと表引きだけで済むからずっと速いはずなんだけど。
気になるなら実験してみて下さいな。
>450で出した数字より遅いなら最適化が十分でないですよ。
ただのハフマンならzip(deflate)やcab(lzx)と同じ位の速度がでるはず。

>>457
実測値が怪しいんじゃなくて、君の最適化が怪しいって事。
実測値でしか語らず、理論値で説明できないのは、どうして速いかという検証が君ができていないってことだ。
静的ハフマンならテーブル引き＋ストリーム出力でほぼ最速になるのは当たり前。
で、レンジコーダの方だが、こっちも静的でいいなら、少ない乗算でできる。テーブル引きとそうかわらん。
SSE2なら乗算平均1clock以下で演算できるから、ほとんど変わらない。
1bitにつきというが、一体どんなレンジコードなんだ？そんな馬鹿なことは普通はしない。
PPMとかのソース見たことないんじゃないの？

静的では若干ハフマンが有利な程度でほとんど変わらんし、
動的ではレンジコーダの方が圧倒的に上。

>>458
458さんのレンジコーダはそんなに速いの？
とりあえずハフマンは静的でレンジコーダは動的でいいよね？
最初からそのつもりで書いてたんだけど。
動的ハフマンとか静的レンジコーダってあまり見ないし。

正直SSE2はよく分からんのだけど(もうSSE4まで出てるんだっけ？)、
例えばアルファベットサイズが256ならシンボル確定するのに
8bit分の8回バイナリサーチするよね？
ここの部分が一番時間がかかってるはずなんだけど、
ここってそんなに速く出来るの？

いきなりPPMとか言われたりして、
どうも話がかみ合ってない感じなんだけど、
実験用のバイナリどこかに上げようか？

>>459
＞とりあえずハフマンは静的でレンジコーダは動的でいいよね？

ダメだろ。条件をどちらかに揃えないで比較するのはおかしい。

>>459
＞いきなりPPMとか言われたりして、

最強の圧縮アルゴリズムを語るこのスレなら、知っていて当然の基礎知識。

＞実験用のバイナリどこかに上げようか？

バイナリじゃなくて、問題箇所のソースを上げてくれ。

>>459
エンコードするのに、バイナリサーチする馬鹿は普通いない。
それとも「圧縮」の話から、「展開」の話に摩り替えてるの？

>>462
悪い俺が馬鹿だった。アンカーたどったら元は伸張の話みたいだ。orz

>>460
おかしいといっても実際動的ハフマンとか静的レンジコーダって殆ど使われてないし。
それにハフマンも動的と静的じゃ殆ど別のアルゴリズムと言って良いくらい違いがあるんだけど。
自分が言ってたのは一般的に使われてる静的ハフマンと動的レンジコーダなんだよ。
事実上この2つ以外を使うことってないと思うんだけど。
動的か静的かで条件を揃えるのって実用上無意味な比較なんじゃないのかな。

>>461
いやPPMは知ってるけどハフマンとかレンジコーダの話をしてていきなり
>PPMとかのソース見たことないんじゃないの？
とか言われても困っちゃうんだけど。

ソースは上げられません。ごめん。

>>462
自分が書いたのは
>>447,450,457,459で
>>442からの流れでデコードの話をしてるんだよ。
別に摩り替えてないと思うんだけど。

なんでそんなに攻撃的なのか分かりません。
もう少し落ち着いて話をしませんか？

>>464
＞おかしいといっても実際動的ハフマンとか静的レンジコーダって殆ど使われてないし。

動的ハフマンがあまり使われないのは、速度の劣化に対する圧縮率の向上があまりないから。
レンジコードだと動的にしても、あまり速度が遅くならず、圧縮率の向上が見られるから、動的で使うことが多いだけ。

＞自分が言ってたのは一般的に使われてる静的ハフマンと動的レンジコーダなんだよ。

でも速度比較するなら、どっちも静的にすればいい。その程度のこともできないの？
理解せずにレンジコーダをつかっているとしか思えん。

＞ソースは上げられません。ごめん。

なぜ？ビルドできなくてもいいし、部分的にでも上げる事が出来ない理由があるの？

>>464
＞事実上この2つ以外を使うことってないと思うんだけど。

そんなのアプリの用途の問題であって、アルゴリズムの比較とは何の関係もない。
実際、静的算術圧縮を使う事だって普通にある。

＞動的か静的かで条件を揃えるのって実用上無意味な比較なんじゃないのかな。

無意味じゃないよ。条件そろえないほうが無意味。

>>464
＞>PPMとかのソース見たことないんじゃないの？
＞とか言われても困っちゃうんだけど。

PPMのレンジコーダのコードは優秀。

なんか妙に絡まれてるけどなんでだろう？
やっぱり話がかみ合ってないんだよなぁ。
ソース上げろと言われてもその前にあなたが出してくださいよ、
という話になってしまうし。
私がヘボグラマーでレンジコーダの方が速いということで終了しましょう。
バイナリのアップは止めておきます。

>>467
どのPPM？
Dmitry Shkarin？

PPMと聞くと、画像ファイルフォーマットか濃度かカントリーミュージックしか思い浮かばない漏れが来ましたよ。

>>465
アルゴリズムの実行効率の優劣を論じてるんじゃなくて、

＞ハフマン符号化よりも伸張のスピードが速いもの。
＞圧縮時のスピードは問いません。
＞伸張が早ければそれでよいです。

って話じゃなかったっけ。
>>45が勘違いしてエンコードの話始めてから話が変になったが。

>>468
＞なんか妙に絡まれてるけどなんでだろう？

静的と動的という、機能的に違うもので無意味な比較をしているから。
圧縮率無視すれば、ハフマンより速いレンジコーダだって書ける。

>>472
そんなに違わなくね？
圧縮展開って意味なら大差ないような。
ストリームに対応出来るかどうかとか？

>>473
全然違う。
静的なら頻度表が必要。動的なら不要。
出現確率の変化に動的なら対処できるが、静的では不可能。

>>474
ブロックに分割したらダメなのか？

>>474
それって単に多少の圧縮率の話ですよね。
それで「全然違う」かどうかは入力の性質次第かと思うが。

「機能的に違う」「全然違う」と言えるような差異としては
＞ストリームに対応出来るかどうかとか？
の方が適切なんじゃない？

まぁ、ストリームっても大概バッファリングするんだから
そんなに違いがあるとも思えないけどな。

>>476
静的も動的も、ストリームに対応するかしないかはどっちも一緒。
どっちもたいていブロックに分割した上で、対応する。

つまり動的か静的かはあまり意味がないってことか。

>>479
違うよ。
動的か静的かは、確率変動に対応できるかどうかという違いがある。
静的は展開が速いが無駄なデータが多くなるし、圧縮時は無駄なリードが発生する。

>>480
それって結局圧縮率の問題じゃね？
出現確率の変化の仕方次第じゃ動的な方が圧縮率悪かったりするよ？
それに動的だと出現しないシンボルが無駄になるんだよな。
エスケープ使うとますます遅くなるしな。

>>481
圧縮率無視するなら、そもそも圧縮なんかしないでいいだろ。
圧縮率が上がればその分読み込みも速くなるから無視は出来ないと思うが。
動的が圧縮率悪くなるわけではない。実装がタコだとそうなるけど。
理論値では動的のほうが必ず上になる。出現しないシンボルは、静的のテーブルの分で相殺できる。
静的に適したデータなら、動的が無駄に遅くなるという点は同意だが。

>>482
>圧縮率無視するなら、そもそも圧縮なんかしないでいいだろ。
べつにそんな事言ってないぞ。
ていうか圧縮率の問題は比較する上で静的動的と本質的に関係なくね？

>動的が圧縮率悪くなるわけではない。実装がタコだとそうなるけど。
いんや実装の問題じゃないよ。
どんな実装をしても変化を捉えられないケースは必ずある。

>理論値では動的のほうが必ず上になる。
逆じゃね？
動的だと任意の位置のシンボルの出現確率はそれまでの文脈から決定されるわけだから、
どのシンボルも常に確からしい確率を与えられるとは限らないでしょ。
静的だと区間における出現確率をあらかじめ調査するから、
その区間に限っては任意のシンボルは必ず確からしい確率が与えられるはず。
頻度表の分動的より悪くなることが多いと思うけど。

>出現しないシンボルは、静的のテーブルの分で相殺できる。
出来るとは限らないでしょ。
テーブルのサイズは決まってないわけだし。
作り方次第じゃ数バイトで済んだりするよ。

>>483
＞ていうか圧縮率の問題は比較する上で静的動的と本質的に関係なくね？

関係あるよ。これは確率論だから。

＞どんな実装をしても変化を捉えられないケースは必ずある。

その場合は静的と同じに出来る。動的の下限が静的なんだが。

＞動的だと任意の位置のシンボルの出現確率はそれまでの文脈から決定されるわけだから、
＞どのシンボルも常に確からしい確率を与えられるとは限らないでしょ。
＞静的だと区間における出現確率をあらかじめ調査するから、

ここまでは正解。

＞その区間に限っては任意のシンボルは必ず確からしい確率が与えられるはず。

ここが間違い。
例えば、区間内に「AAAA...AAAABBBB....BBBB」というデータが与えられた場合、
静的だとA、Bの確率が0.5になる。

シャッフルしたらエントロピーが上がり、情報量が下がることはわかると思うが、
静的では圧縮率に変化が起こらないことから、そういった要素を無視しているのはわかるよな？

＞作り方次第じゃ数バイトで済んだりするよ。

数バイトで済む場合、動的のほうの無駄も、同程度以下で済ますことが出来る。
情報量の計算すればわかることだが。

>>484
>ここが間違い。
>例えば、区間内に「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にはならない。
理論的には静的な方が良くなるのは分かるよね？

動的符号化は常に被符号語が未知であるが故に確からしい確率を与えることが出来ない。

>シャッフルしたらエントロピーが上がり、情報量が下がることはわかると思うが、
???
エントロピーが上がって、情報量が上がるの間違いだよね？
文脈次第では？

>>485
＞ん？その区間の確率は理論上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値のモデルで検証してみることだ。
区間内に出現確率の変化がある場合、動的のほうが必ず良くなるから。
そして変化が無い場合でも、動的でも静的と同レベルに抑える方法があることがわかる。

＞エントロピーが上がって、情報量が上がるの間違いだよね？

エントロピーが上がる＝情報量が下がるだよ。
シャッフルしたら情報量が下がるのがわからん？

「AAAB」
静的
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

>>487
頻度テーブルの情報量を加えてごらん。

>>とは限らない。もちろんその手の変化があるという意味では正解だが、
>>その変化の仕方はタコなアルゴリズム。
どんな入力に対しても対応できる方法は存在しないよ。

>>高圧縮のアルゴリズムはすべて動的になっていることからもわかるはずだが。
残念。
それらは一般的な情報源に対して高圧縮率なだけ。
例えばPAQやPPM*よりLZが倍近く高圧縮になるケースが実在する。

>>489
＞それらは一般的な情報源に対して高圧縮率なだけ。
＞例えばPAQやPPM*よりLZが倍近く高圧縮になるケースが実在する。

だから、それは特殊な場合だろ。平均的には論理的に動的のほうが上というのがわからんの？

>>488
1bitでイイ？

>>491
どうやって表現するんだ？AAAAとAAABとAABBとABBBとBBBBが区別できないといけないだろ。

以下の条件を満たすオープンソースの圧縮、伸張アルゴリズムはありませんか？
WEB上で公開されているものであれば良いです。

■条件
LZSS法、ハフマン符号化以外
（すでに所有しているため）

ハフマン符号化よりも伸張のスピードが速いもの。
圧縮時のスピードは問いません。
伸張が早ければそれでよいです。

だからよ、テーブルは任意サイズでもいいわけよ。
てことは少なくとも頻度表を除けば平均的な
区間圧縮率は静的な方が上なんだよ。
で、これにテーブルをどうするかって位の差なんだよなこれがさ。
最初から辞書として持っててもいいわけだ。
実際PAQとかDurilcaとかはテーブル持ってんだよね。

>>494
＞だからよ、テーブルは任意サイズでもいいわけよ。

誰もそれを否定していないが？
情報量から限界があるから、無駄をなくすことができるだけで、下限は情報量によって決る。

＞てことは少なくとも頻度表を除けば平均的な
＞区間圧縮率は静的な方が上なんだよ。

必要な頻度表を除けばというのはインチキだな。
最悪時の動的のロスもその程度だから、必要な頻度表を含めば動的も静的もほとんど変わらない。
しかし、区間中に確率の差がある場合、動的の方が理論的には良くなる。

＞最初から辞書として持っててもいいわけだ。

持っててもいいが、持っていなくてもいい。

>>493
ランレングス

だからさ頻度表は任意だから加えたらどっちが上かは
その時点で決められないんだよな。

>最悪時の動的のロスもその程度だから、必要な頻度表を含めば動的も静的もほとんど変わらない。
なら動的の方が良いとは限らないのでは？

>しかし、区間中に確率の差がある場合、動的の方が理論的には良くなる。
なぜ？
入力に対してどんなに対応を切り替えようが
動的である限り常に最悪のパターンは存在する。
どんなBitのパターンであっても同じだよ？
つまりどんな入力に対しても頻度表を除けば常に静的な方が圧縮率は上。
動的符号化は常に被符号語が未知であるが故に確からしい確率を与えることが出来ない。
最適な確率・符号長を与えられない時点で平均的には必ず静的より悪くなる。
その上でこれに加える頻度表は任意でいい訳よ。
どんな形で頻度表が作られるかは不明。サイズも不明。
だから動的が理論的に必ず良いというのはおかしいのさ。
そもそも頻度表が加わるから大きくなると言ってるけど
どんな形で頻度表を持たせるかは言及してないでしょ。

>>497
＞つまりどんな入力に対しても頻度表を除けば常に静的な方が圧縮率は上。

馬鹿。

>>498
馬鹿はないだろ馬鹿は。
でも間違ってないだろ？

いやでもこれが間違っているとなると
シャノンの情報理論も間違ってることになるんじゃ？

>>497
＞動的符号化は常に被符号語が未知であるが故に確からしい確率を与えることが出来ない。
＞最適な確率・符号長を与えられない時点で平均的には必ず静的より悪くなる。

間違い。
静的は全体で確率を求めるため、局所的な確率を効率よく求めることが出来ない。
最適な確率・符号長を与えられない時点で平均的には必ず動的より悪くなる。

静的なアルゴリズムを選択する場合でも、
ブロックにわけることで、擬似的に動的っぽい効果は得られるが。

局所的な確率はどうやって求めんのよ？
どんな入力に対しても最適にする事は出来ないんだよ？
実装の問題とかじゃなくてさ。

>>502
＞局所的な確率はどうやって求めんのよ？

ベイズ推定

AAAB,AABA,ABAA,BAAA
これを動的符号化で期待値求めてみてよ。

>>504
A=aが1000個の固まり
B=bが1000個の固まり
に展開して、aとbで符号化してみたらどう？

分かんないかなあ、次の文字が未知である以上
何やったって既知である静的符号化より区間平均が悪くなるのに。
特殊な情報源に強くする事は出来ても全般は無理よ。

>>505
母数を大きく取るのね。
500/1000
501/1001
502/1002
500/1003
0.062499813247569977380545675660332
大きくとるほどに変化に強くなる。

ああそうだ、動的の方が良くなるパターンに言及してなかったよ。
動的な符号化ってのはさ大体の場合、頻度の累計値が決まってんのよ。
で、一定期間(1bit毎でも)で頻度表を更新するんだけど、
これのおかげで静的で言うところの区間が可変になるんだな。
だからシンボルが連続したりすると圧縮率が良くなるんだ。
で、シンボルがランダムだと悪くなったりするんだ。
テキストとか所謂圧縮しやすい情報源だと偏りがあるから良く効くんだよ。
で、ランダムだと全然ダメだったりするんだ。
で、あらゆる全てのビットパターン(未知の情報源)をトータルすると
結局、静的符号化が上回るんだよ。

>>508
＞で、あらゆる全てのビットパターン(未知の情報源)をトータルすると

やっぱりお前は馬鹿だな。
全ビットのパターンをトータルするなら圧縮しない方が一番いい。そんなこともわからないのかよ…。

>>509
理論値を語ってるんじゃなかったんか。

>>506
じゃあ、君の考えだとPPM法を静的にした方が圧縮率が上がるということ？
そんなことやる奴なんていないと思うが。

>>510
全パターンなら、理論値だろうと実測値だろうと一緒だろ。圧縮しないのが最強だ。

>>511
頻度表を除けば理論上はそうなるよ。
まあ当たり前なんだけどさ。
頻度表をどうするかはまた別の話。
durilcaとかは自前でテキスト用に辞書をもってたりする。
実用上はもちろん頻度表は動的に作ることになるだろうけどね。

>>512
理論的に必ず動的が上だって言うからそれは違うだろって話をしてたんだよ。
究極的には圧縮しないのが最強なのは全くもってその通り。
可逆圧縮はただの変換なんだから、
どんなアルゴリズムを用いたとしても、
入力サイズ+圧縮したかしないかの1bitが最小の期待値になる。
n通りのビットパターンはn通りのビットパターンでしか表現できない。

理論的に語るなら得意な情報源のみ取り出して上だというのは
おかしいだろという話なんだよ。
実際存在しうるデータってのはランダムの方が圧倒的に多いんだよ。

>>511
abcabcabcab
ときてabの次に何が来るか考えたら分かるよ。
cが来るだろうなと思って実際にcがきたとしても、
動的符号化はc以外の文字にも常に確率を割り当てなきゃならない。
既知であれば必ず最適な符号長が割り当てられる。

>>514
＞実際存在しうるデータってのはランダムの方が圧倒的に多いんだよ。

馬鹿だなー。実在するデータは、ランダムの方が少ないから、圧縮アルゴリズムが有効なんだよ。

>>513
何度も言うが、頻度表除いたらダメだろ。情報が頻度表に移動しているだけなんだから。
根本的に情報理論がわかってないんとちゃう？

>>514
＞動的符号化はc以外の文字にも常に確率を割り当てなきゃならない。
＞既知であれば必ず最適な符号長が割り当てられる。

それが違うんだな。既知であるためには、先行して情報が与えられている必要がある。
その情報の量と、動的の場合に確率を割り当てる量というのは、実は同じ。
しかし静的の場合、局所確率に適応できないため、原理的に最適な符号を割り当てることが出来ない。

圧縮率がシャッフルさせても変化しないというのは、
文字の前後との相関性の情報量を利用できていないということに他ならない。
圧縮というのは、出現の偏りによって圧縮するのであって、単なる出現確率だけよりも、
時系列情報（既出文字との相関性）の偏りを利用できた方が、一般的に圧縮率は向上する。

>>515
有効じゃないなんて誰も言ってないだろ。
理論的に話してるんだから考えうるデータは全部考慮しなきゃならんだろ。

>>516
>何度も言うが、頻度表除いたらダメだろ。情報が頻度表に移動しているだけなんだから。
それはそう。
だが動的にすれば常に理論上圧縮率が良くなるのは違うだろ？
頻度表をどう持たせてどう使うかはまた別の話。
そもそも動的にしたことで偏った情報源で圧縮率が良くなるのを
理論値だなんて言うからおかしくなるんだよ。

局所的な確率が良くなっているのはワーストケースとの
トレードオフなんだよ。
圧縮率が良くなった時だけ見てるからそうなるんだよ。
よーく考えてみてよ。
理論上の話なんだから。

>>518
＞だが動的にすれば常に理論上圧縮率が良くなるのは違うだろ？

理論上、実際に使うデータでは平均的に圧縮率が向上する。
なお、現実と一致しないような理論は理論ではなく空論。

＞頻度表をどう持たせてどう使うかはまた別の話。

動的だってそれ専用の表に符号を追い出すことは出来る。
そんなもの切り離して考える方がどうかしている。

＞そもそも動的にしたことで偏った情報源で圧縮率が良くなるのを

動的にしたことで偏るんじゃなくて、偏りが抽出できるだけ。
始めから偏ったデータを使っているから圧縮アルゴリズムに意味が出てくるの。

>>519
理論上というのは、ランダムとか全パターンのことじゃないぞ。
根本的に何か勘違いしていると思われ。

>>520
なぁ、おかしくないか？
ワーストケースを考慮しないのが理論的なのか？
圧縮しやすいデータを対象にして話すのは結構だけど、
だったら理論て言葉はなしにするべきだろ。
実際tar化されたファイルとかで圧縮・非圧縮のが混ざってたりして
動的が不利になるケースとかもあるんだよ？

最適な予測で符号を求める方法も、あらかじめ符号をもつのも、情報量的には実は同じ。

>>521
じゃあ理論上てのはどんなのだよ。
人それぞれ対象が違ったらそれこそ話が合わないじゃないか。

>>523
究極的にはそれはその通り。
だが符号表を除けば除いた残りの部分は必ず動的より良くなる。
当たり前すぎる。
動的が常に理論的に上ってのは間違い。

>>522
圧縮しやすいではなく、圧縮可能なデータ。いろいろな偏りが含まれていることが前提になる。
程度の差は様々でいいが、出現確率に差があり、相関性にも差があるのが、現実のデータ。
そういう差がないなら、それはただの乱数列であって、圧縮アルゴリズムを適用する対象外だ。
乱数であることを検出したら、圧縮しないで転送すればいいだけ。

動的でも静的でもいいが、不利になったりするのは、実装上の問題であって、情報の理論的な問題ではない。

本来持っている情報量を下回る圧縮は出来ないってことだね。

>>525
＞だが符号表を除けば除いた残りの部分は必ず動的より良くなる。

除けばなんて話はしていない。合わせたら動的の方が良くなる。
静的で頻度表に全部符号を置けば、良くなるどころか０ビットに圧縮可能だが、そんなものは圧縮とは言わない。アホ過ぎる。

>>527
そういうこと。その中で、動的は時系列情報を利用できる。

>>526
>圧縮しやすいではなく、圧縮可能なデータ。いろいろな偏りが含まれていることが前提になる。
圧縮可能かどうかはアルゴリズム次第なんだって。
そんな前提条件があるなら先に言ってくれよ。

>そういう差がないなら、それはただの乱数列であって、圧縮アルゴリズムを適用する対象外だ。
じゃあ理論値て言葉はなしにしてくれよ。

>>529
時系列情報て、それは結局ワーストケースとのトレードオフなんだって。

>>530
理論値は理論値。確率や相関性を分散とかを適当に設定すればいいのであって。
全パターンというのは、そもそも圧縮を考える上で無意味なこと。

>>531
そんなことを言うなら、頻度表もワーストケースとのトレードオフだ。バカバカしい。

>>532
理論値てのは普通全部含めるだろ？
いい加減理論値って言葉はやめなよ。
特定の場合のみなら理論とはかけ離れてる。

>>533
バカバカしい、って理論の話じゃなかった訳？
あなたの理論は特定のアルゴリズムで圧縮できる
特定のファイルにのみ適用されるの？

>>534
＞理論値てのは普通全部含めるだろ？

含めないよ。偏りがないなら圧縮できないで終了だから。
n次相関がどれだけとか、分散がどれだけとか、偏りがあることが前提になる。

>>535
特定のアルゴリズムというわけではないよ。
現実のデータというのは、高次相関性があるわけ。
どんなアルゴリズムもその相関性を利用して圧縮を行う。
全次元で相関性が0なら、完全な乱数列であり、圧縮理論の対象外になる。
多かれ少なかれ、相関性があることが前提になる。
そして、その相関性を高次まで多く利用できるアルゴリズムが圧縮率が上がるということなの。

やっぱり根っこのところで考え方が違い過ぎて議論になってないね。
とりあえず前提条件も話さずに特定の場合のみ取り出して
「理論上は…」ってのだけは止めるべきだと思うよ。

>>538
理論上は静的の方が冗長な情報が含まれるから劣るんだよ。
シャッフルしたときとの差の情報が使われていないからね。
ただ、現実には理論値が出せないことがあるから、静的な方がいいこともあるだけ。
「情報量」で考えられないやつにはわからないかもしれんが。

>>537
無限にアルゴリズムが存在する中では高次相関とかは無意味なんだって。
完全な乱数列かどうかなんて判定は出来ないんだから。
全次元の判定なんて不可能でしょ。
というか理論と言う時点で全ての情報源は等価である事が前提だと思うんだけど。

>>540
＞全次元の判定なんて不可能でしょ。

だから、どれだけの次元を利用できるかということになる。
静的なら最低の相関性だけしか使わないが、
それ以上の相関性を利用できれば理論上、圧縮率が上がるのは当たり前なんだよ。

＞というか理論と言う時点で全ての情報源は等価である事が前提だと思うんだけど。

そんなんだったら、確率論も、情報理論もいらんがな。
これらは何らかの偏りがあることでしか意味がないから。

一応断っておくがあなたの主張については
後だしの前提条件を踏まえる限りは概ね正しいと思うよ。
ただし議論するときは前提条件はきちんと提示するべきだね。

>>542
全パターンなんて基地外じみた条件こそ後出しだろ。
まともな情報理論で語るなら、そんなわかりきったことを持ち出して議論を無意味にしたりはしないのが普通。

結局のとこ全パターン厨って何が言いたいの？

もう終わりにしろよ。

どうして情報源の設定をしないのだろうか。
エルゴード情報源くらいを仮定してみては？

>>541
理想論の放棄＝客観的なアルゴリズム比較の放棄
と同等だわな。

>>546
同意。
現代の圧縮アルゴリズム論は、もう情報源の設定が必須だな。

なんでも使える汎用アルゴリズムなんて、曖昧で議論も検証も不毛になりがち。

Lempel-Zivについて。
"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

18 ■UN
19 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

原文字＝Lempel-Zivコード

I=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

…どうでしょう？

http://ja.wikipedia.org/wiki/LZ78

>>552
ア、ナルほど。
1のIMや3のM■はもっと後にコード化されるみたいですね。
もう一度やってみます。

再挑戦です。今度こそ、どうでしょうか？

0 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

原文字＝コード

I=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

…合ってますか？

"IM■ULM■UM■ULM■UND■UM■ULM■HERUM"
ではなくて
"IN■ULM■UM■ULM■UND■UM■ULM■HERUM"
　↑
でした。
しかもノートに答えが載ってました、はははは。(^^ゞ


…吊ってきます。

つか、辞書を毎回書庫に個別に保存するのは効率悪いだろ。
すでに圧縮書庫の数は大量に存在するわけだし、類似点も沢山見つかっている
頻度の高いものは共通の辞書としてあらかじめ持っておけばば数には入らず
辞書の部分だけデータは縮小されるはずだ。
共通辞書を参照するには１つの系統の辞書だとインデックスが大きくなるので
個別の特徴によって辞書の総数を減らした多段の辞書も用意しておくべき。
圧縮できない決まったパターンがある場合、それ自身（生）を持っているほうが
明らかに有用だろう。

プログラムサイズが増えるし圧縮に時間が掛かる。
特定用途に絞るならそれでいいと思うけどね。

age

>>558
>>548

このスレ残り半分だし、「特定のデータ」を圧縮するのに特化したプログラムを作らないか？



固定化されたデータ列A（たとえば、ttp://f55.aaa.livedoor.jp/~vipper/vipmemorialthread/
にHTML化されているデータを下から順に50個くっつけた奴とか）に対して

データ列B＝圧縮されたデータ列A＋圧縮に使用したバイナリデータ（実行ファイル、辞書、etc.）

となるデータ列Bを生成する時、データ列Bが(Byte単位で)最も軽くなるような圧縮ソフトを作りあって競う　とか。

「圧縮に使用したバイナリデータ」は原則、実行可能状態の時のサイズで。（zipとかupxfとかを許可するかどうかは誰かが決めてくれ。lzhはだめだろ。）
あと、「圧縮されたデータ列AはURLです」とか無しな。ローカルでクローズドなコンピュータ単体で、データ列Aが復元できなきゃ話にならん。ネットに接続は問題外で。

P.S.
解凍に必要なバイナリデータもデータ列Bに含める。
（「辞書なんて解凍側持ち、データ列Aは1byteに圧縮ﾌﾟｷﾞｬｰ」とか乱立しても面白くないため）

ソースコードの添付は義務ではないものとする。
（そんなに欲しけりゃ逆汗して手に入れるだろ。）

春の香り

都の香り


京都

集合age

モンスーンの香りがするが、別人？

辞書がどうこう言ってるやつはちょっと圧縮関係の過去ログ探して読め。
そしてサイト巡ってもう少し勉強しろ。(日本語のはまともなのがないぞ)
というか簡単なのでいいからまともに動くプログラム一から書いてみろ。
そんでもって適当なファイルでベンチマークとってみろ。
calgaryとかcanterburyのコーパスでかまわん。
「使える」アルゴリズムを造るのが如何に大変か分かるぞ。

3人寄れば文殊の知恵っていうじゃん。ここで何人寄るかは知らんが。

まず、特定のバイト列をとても効率よく圧縮できるアルゴリズムを作って、
それを改良していけば「最強の圧縮アルゴリズム」の仕様・実装について深く語り合えるかなと。

3人寄れば文殊の知恵っていうじゃん。ここで何人寄るかは知らんが。

まず、特定のバイト列をとても効率よく圧縮できるアルゴリズムを作って、
それを改良していけば「最強の圧縮アルゴリズム」の仕様・実装について深く語り合えるかなと。

そう思うのだがどうだろう？

最強の圧縮っていってるけど、
圧縮率だけでよければ、最強の圧縮は作れるにょ。
そんなのは40年前から知られているにょ。
今も昔も圧縮の研究は、
圧縮率をなるべく落さずに高速なアルゴリズムを作ることだにょ。
確率論とか情報理論はどうでもいいにょ。
確率論とか情報理論を知らない奴はもっとどうでもいいにょ。

40年前ってまさか算術符号の事じゃないだろうな？

速度なんてハードレベルで最適化させればいい

そう一瞬思ってしまった・・・不覚orz

>>570
にしても、まず圧縮率優先だろう。

アルゴリズムの計算速度の最適化ならあとからいくらでもやりようがあるが
その圧縮率が糞なら言う事ない。

キャプチャムービーの配信みたいに
リアルタイムエンコーディングが必要な場面では
速度重視のアルゴリズムも必要だと思うけどなぁ。

人間がわからないくらいにデータを間引いてしまえばいいと思うでつ。

データを、人間が認識できなくなるまで劣化させたら、それはもはや圧縮とは言えない。ごみファイル生成機である。

>>575
mp3 や jpeg など 不可逆圧縮 と呼ばれるのはそうだね。

>>575
ファイルのプロパティ見ればサイズが変わってるのが人間にもわかっちゃうよ

何の話をしているのか、整理をしたほうがいい。きっとそうだ。引力が導くよ。

人間が認識できない程度なら良い

逆に考えれば
認識できない人間を量産すればいい

つまり退化の改新という訳ですね。

ホシュ

ga

任意のビット列が与えられた場合、常にそれを元のビット列よりも短くする圧縮方法はないといわれている。

しかし、この定理に関して、私は真に驚くべき判例を見つけたが、この余白はそれを書くには狭すぎる。
そこで、私の発見した圧縮方法でこの長大な論文を圧縮してここに記す。

0

Q.E.D.

特定の圧縮アルゴリズムを用いてそれ以上短くすることのできないビット列という物は存在はするだろう
存在はするが、母数が大きくなればそのようなビット列が現れる確率は０に収束すると考えることもできるのだ
いや、そんな気がするだけで深くは考えていないので証明は勘弁するのだ

つ[THComp]

日本語文を圧縮するとき形態素解析を利用してるプログラムってある？

>>585
厳密な乱数ってのは、今までの数列から未来を予測できない。そして特定のパターン性もない。

データの圧縮ってのはデータの特徴からして、冗長な部分があるから可能なんだよ。
乱数で生成したバイト列を圧縮してみ？マジで圧縮率悪いから。

君の主張は圧縮できるほど冗長性の高いビット列が多数派ということになるが、
存在しうるバイト列のうち、冗長性の高いものは少数派だぜ。
ただ、俺らが普段使っているデータってのは意味を持つからな。だからこそ冗長性が高い。
だからこそ圧縮できるってわけだ。

つまり、熱的死が待っている。

実数の中では代数的数よりも代数的でない無理数のほうが圧倒的に多いが、
人間の目に触れる機会があるものはむしろ代数的数の方が多いとか、そんな感じか。
どんな感じだ。

>>590
そんな感じだと思っていい。

俺たちが欲しがるデータってのは何らかの規則性をもったデータがほとんどだから圧縮できる。
だが、世の中に存在しうるデータの中からすればそれは激レアなんだよ。
ほとんどのパターンは単なるノイズ。
サルにキーボード叩かせて偶然シェークスピアの名作ができる可能性を考えてみろ。
神職人が苦労して意味のあるデータを紡いでるんだよ。

圧縮ってのは等価交換なんだよ。
何かを縮める代わりに何かを増やしてるんだ。
俺たちは、自分たちが使う種類のデータが縮んで、
俺たちにとってどうでもいいデータは縮まない方法を使っているんだ。
代償になっている部分、つまり圧縮しないほうがサイズ小さいよってデータは必ずある。

>>590
人間の視覚が代数的なものしか認識出来ないってことでは？

日本語文なら、はじめから辞書を内蔵していればかなり高圧縮は出来るな

辞書があればかなり圧縮できるやつは、すべて辞書を持っていて
駄目なやつだけ実圧縮すればいいだろう

辞書のサイズは足すべきだろう

どの文にもそれなりに圧縮が効く辞書は、プログラムに持たせるべきだろう

>>594
親しい間での「あれとって」「はいよ」ってのも圧縮技術だよね。

前後の文脈と状況とで「予測の枝狩り」をした上で、さらに
お互いが脳内に保持している辞書情報を使って「解凍」している。

結局、そのときの会話以上の情報をお互いがすでに保有しているから
解凍できるのであって、圧縮というよりは通信速度の向上の話に
なっていく気もするけど、これは大容量時代を迎えた今のPC事情なら
積極的に活用していくべきだよね。



究極の圧縮言語を操るフランドルはかわいいよという話なんだけど

英語なら、
例えば、一単語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バイトだな

実行ファイルや、日本語や、英語や、個別に長めの単語をあらかじめ選んでおけば
いいんだ
これってまだ誰も実用していないだろ　作ってみるかな

英語なら、3語以上の単語を2バイト+1bitで表せば、
this is a pen　は、　17　+　9　+　9　+　17　約12.5バイトだな

　 　＼　　__　　／
　 　＿　（ｍ）　＿ﾋﾟｺｰﾝ
　 　　　　|ミ|
　　 ／ 　｀´　 ＼
　　　　　('A`)　　　　「辞書を使って辞書をあｓｓｙ（ｒｙ」
　　　　　ノヽノヽ
　　　　　　　くく

辞書は、共通のやつを実行ファイルと一緒に持っておくんだよ(内蔵してもいいし)

例えば、htmlなら、いったんhtml辞書で縮めてからテキスト辞書で縮める
そのあと通常圧縮をする
辞書がなければはじめから通常圧縮

デジタルデータは標本化できないのかな？

文字列　FClBrIAs
圧縮後　ふっくらブラジャー愛のあと


考察　人間の記憶の仕方は不思議だ

それ、圧縮してないから

いや、文字数は増えているが広義には圧縮の一種かもしれない
無意味な文字８つを、何らか意味のある情景ひとつに置き換えている

exe、text(日本語、英語、ドイツ語など)、html、jpegなどを
ビット単位で調べて、頻出ビット列の統計を取るんだ
そして、算術圧縮の要領で、ビット割り当てを行う
(辞書を作るときにアルゴリズムを使って割り当ててもその辞書と特許は関係ないはずだ)
そして、通常圧縮だ

jpegのビット列調べるのかよw
算術圧縮の意味わかってないしw

>>609
そうだよ　JPEGのビット列を調べるんだよ
種類別によって11100111がよく出てくるとか判別できるだろ
そしたらもっとも全体長が短くなるようにビットを割り当てる

jpeg共通の特徴とか特にないの、既に圧縮されてるんだから
ヘッダぐらいは圧縮できるがそれは既存のアルゴリズムで十分小さくさくなる
だいたい変換後のビット列を確定するのを遅延して圧縮率高めるのが算術圧縮だろ
算術圧縮で静的な辞書つくるとかいってる時点でかなり間抜け

わ、さくさくってなんだ

jpgが可逆にもっと小さくなるなら、それは画像フォーマットとして使ったほうが合理的だ

>>611
＞jpeg共通の特徴とか特にないの、既に圧縮されてるんだから

あるよ。
嘘だと思うなら、NASAのサイトから大き目で冗長度の高いJPGを落としてきて、
それを7zとかdgcで圧縮してごらん。ヘッダレベルでない圧縮がかかることがわかるから。

>>613
＞jpgが可逆にもっと小さくなるなら、それは画像フォーマットとして使ったほうが合理的だ

可逆で小さくなるが、可搬性が失われるので利用されないだけ。
JPEG2000でも使えば良い。

わかったからjpeg共通に出てくる特徴的なビット列とやらを出してみろよ

>>615
俺が書いているのは、jpeg共通の特徴であって、
jpeg共通に出てくる特徴的なビット列ではないのだが。
で、圧縮できることも示したのだから、やってみればいい。

http://aerobimania.ixo.jp/gymnastics3/gym3/index3.html
趣味で選んだ、このサイトの大股開きの女の子の画像がいくつまで縮められるか勝負しようぜ!
以下の画像を使用することにする
圧縮と復元ルーチンの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

落ち着け

「ふがふが」
「そうか。ふふん」

>>616
jpegがさらに圧縮できるのは"個々"の冗長性を利用してる圧縮してるんだよ
jpeg共通の特徴なんてないの。"共通"だとか"辞書"だとか根本的に間違っるだろ

また打ち間違えたorz

>>620
＞jpegがさらに圧縮できるのは"個々"の冗長性を利用してる圧縮してるんだよ

だから俺はそれを言っているのだが。

＞jpeg共通の特徴なんてないの。"共通"だとか"辞書"だとか根本的に間違っるだろ

俺はそんな主張はしていない。俺が>>614で書いたことは、
JPEGの符号化は最適ではなく(算術圧縮でもない)、値が偏る傾向があるので、
それを「jpeg共通の特徴」としているだけ。

>614で新しい話を始めたわけじゃないだろ。
他人にレス付けるときは、ちょっと前も読んで文脈を掴みましょう。

>>622
ふが

>>623
＞>614で新しい話を始めたわけじゃないだろ。

そんなのわかってる。
文脈掴めというのなら、お前が先に掴んでやれよ。馬鹿が。
俺は608の言いたいことはわかったぞ。

ttp://www.nicovideo.jp/watch/sm37132
ストーリーが超圧縮されたドラマを見るんだ

圧縮に限らないけどアルゴリズム系のスレって定期的に
おかしな理論ぶちまけるヤツが出てくるんだがなんでなんだろうな。
jpegはDCTしてハフマンかけるからjpeg特有のビット列なんてのは
基本的に出てこないはずなんだが。
jpegが再圧縮で縮んだのならDCT後の冗長性をハフマン符号で
処理し切れなかっただけだろう。
可変長で符号化されたデータなんだから固定長でモデル化する
アルゴリズム(現存するやつほぼ全て)は効かないに決まってるんだ。

>>627
普通に圧縮率下がってただけじゃね？

毎度毎度パッツンパッツンに圧縮かけてらんないよ

>>627
＞jpegはDCTしてハフマンかけるからjpeg特有のビット列なんてのは
＞基本的に出てこないはずなんだが。

DCT後のハフマン符号がある種の傾向を持つから、元の発言者は、
それをjpeg特有のビット列と言いたいんだろ。
それぐらい理解してやれよ馬鹿。

＞jpegが再圧縮で縮んだのならDCT後の冗長性をハフマン符号で
＞処理し切れなかっただけだろう。

だからそんなことはわかりきっているんだってば。

＞可変長で符号化されたデータなんだから固定長でモデル化する
＞アルゴリズム(現存するやつほぼ全て)は効かないに決まってるんだ。

7zやdgcで5%程度縮むから、効かないわけではないし、
その効率を上げるために、元の発言者は、ビット単位を考えてるんだろ。
それぐらい理解してやれよ馬鹿。

>>625
623じゃないけど(俺＝609,611,620)
・例えば、htmlなら、いったんhtml辞書で縮めてからテキスト辞書で縮める
　↓
・exe、text(日本語、英語、ドイツ語など)、html、jpegなどを
　ビット単位で調べて、頻出ビット列の統計を取るんだ
　そして、算術圧縮の要領で、ビット割り当てを行う
　(辞書を作るときにアルゴリズムを使って割り当ててもその辞書と特許は関係ないはずだ)
　↓
・種類別によって11100111がよく出てくるとか判別できるだろ
って流れだぜ。
jpegという種類によくでるビット列があって、jpeg辞書がつくれると思ってるんだぜ。
ファイル別に圧縮するのは当然可能だけど、jpeg辞書はつくれんだろ。
HTML引合いにだすくらいでやめときゃいいのに、厨まるだしじゃん。

理論よりも実装だな

普通のjpegのハフマンテーブルは、画像ごとに最適化されてるわけじゃないから、
もう少し圧縮が効く
jpegtranとか、ハフマンテーブルを最適化してjpeg化できるプログラムもあるが、
たいていは圧縮にかかる時間と圧縮率を天秤にかけて、妥協してる

zipやrarにある「速度重視」オプションで圧縮してるようなもｎｏ
そういうの基準にしてもしょうがない

>>630
＞jpegという種類によくでるビット列があって

実際あるぞ。ハフマン符号化で圧縮しているものの癖が出るから。

>>630
＞jpeg辞書がつくれると
ちょっと意味が違うけど、エロ方面では基礎実験が進んでいる。

手持ちの画像のハッシュを集めてデータベース化し
効率よく蒐集を行うプロジェクトがある。

>>248
そういう観点「所詮0と1のデータ」＝デジタルデータであるという観点であれば、
最適な圧縮方法はあるでしょう。

そうじゃない観点＝アナログデータとして扱うってことだから、これは難しいよね。

>>634
ImageDatabaseでしょ？
あれはちょっとぜんぜん違うような

>>633
あると言い張るならそのバイト列を示してくださいな
ヘッダを読みとばしてハフマン符号化されてる部分の統計とる
そのくらいのスクリプト位書けるでしょ？
統計的に厳密でなくても、風景人物CG等ゴチャマゼ
サイズ、jpeg圧縮率バラバラでサンプル数1万もあれば納得しますよ

>>637
＞あると言い張るならそのバイト列を示してくださいな

誰もバイト列なんて言ってないが？馬鹿じゃないのか。

それに何でお前の為にそこまでやってやらないといけないんだ？
別に論争しているわけでも論破しているわけでもないぞ。
納得できないならしなくていい。説得する気もない。
ただ、いろいろな圧縮アルゴリズムを作り、検証してきた中で
知っている情報を提供しているだけだ。

いろいろな可能性を考え、創造しようとしている奴の出鼻を挫くような奴は最低だと思う。

>>637
そのくらい自分でやれよ・・・
反論するなら自分で検証しろよ

あ、バイト列じゃなくてビット列か、どっちでも一緒だが
証明できないなら間違ってるって認めろよ
プログラム作れてっていったってK&Rの練習問題レベル
決して無理なこと要求してるわけじゃない

言い訳ばっかりでつまんない奴だ

#include <iostream>
#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;}

実行したディレクトリにあるファイルのビット列を調べて、回数を出します

もしまちがってたらいってくれ
間違っていなければ、jpgでやってみると0000000000( =0 )の出現率がかなり高い

>>640
＞証明できないなら間違ってるって認めろよ

もう無茶苦茶だな。
証明できない＝間違っている
ではないだろ。

お前が勝手に間違っていると思うなり、証明するなり好きにすればいい。

＞プログラム作れてっていったってK&Rの練習問題レベル
＞決して無理なこと要求してるわけじゃない

なら、お前がやれよ。

おまいら調べるツール作ったんだからやって見ろよ!

>>645
そもそも、このツールで0.1%の偏りとか検出できるの？
0.1%といっても、1MB中の1000BYTEに相当するから、統計的にはかなりのものになるが。

>>646
例えば、ファイルの内容が
111010101111000001010101010101010101010101111001
で4bitの統計を取る場合は、
(1110)=7、　(1101)=11、　・・をカウントしていくわけ

寿司食いたい

>>647
それは質問の答えになっていない。
聞いているのは、検出できるのか、できないのかだ。

偏りとは??
0000000000の出現率は2位以下の倍以上だ

>>650
「全パターンの出現率の偏り」だが、意味がわからないですか？

辞書でまとめてからBlockSortingと、BlockSortingしてから辞書でまとめる
のだと前者の方が高圧縮かな?

フレームワーク作ろうぜ

01データの統計をとって、一番高いやつを2で置き換えて
今度は3進数で一番縮むやつを3で置き換えれば良いと思うんだが>>1と同じだが

#include <iostream>
#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;}

まちがった Mビットだった

#include <iostream>
#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;}

はげしくコンパイラ依存しているのでBCCとVC++で動くやつに書き換えるよ

#include <iostream>
#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;}

#include <iostream>
#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;}

>>660
7行スレで圧縮してきてくれないか

jpegの場合、0と1の出現確率はほぼ同じだが、連続して0が続く確率がかなり高い模様だ

http://love.freedeai.com/src/up6711.txt
15桁の統計
これに基づいて最適なビット割り当てを作ってくれ

1%圧縮出来てもコスト考えたら意味ないと思うんだが。
無圧縮と同じくらい負荷が軽いならアリかも知れんが。
再圧縮かけるより別のアルゴリズムで圧縮した方が縮むぞ。

>>664
そういうことだな
しかし、textやexeは工夫する余地は多分にある

>>664
しかし最強の可逆圧縮をするにはjpegもやらないとな

>>664
それは別の人が高速化を考えればいい
効率と高速化、どっちも煮詰まってからが本当の勝負だろ

ていうかまず最強を定義してくれ

各種ファイル(テキスト、exe, jpeg, など)で他の圧縮ソフトよりも高圧縮

どんなファイルも1ビットに圧縮。

コンピューター死ぬらしいコンピューター死ぬらしいコンピューター死ぬらしいコンピューター死ぬらしいコンピューター死ぬらしいコンピューター死ぬらしいコンピューター死ぬらしいコンピューター死ぬらしいコンピューター死ぬらしいコンピューター死ぬらしい

>>663 うそこくな。絶対JPEG以外のファイル混ざってるだろ。
[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にでも通したほうがいい

>>672
＞ぱっとみ数％程度の圧縮にしかならん。その分次の段の圧縮率が下がるんだし

まあ、そうだが、わずかでも、特徴があるのと、圧縮できることは証明されたな。
誰も大幅に圧縮率が上がるなんていってないし。

>>圧縮できることは証明されたな
んなこたない。
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重圧縮のデメリットが
勝ってしまう可能性大。ほぼ無意味なことが証明されたと思うが

#include <iostream>
#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;}

>>675
長くて読む気しないので7行で頼む

#include <fstream>
#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;}

#include <fstream>
#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;}

>>674
＞a.jpg 92329b →a.jpg.zip 92437b(非圧縮)→ a.jpg.zip.7z 89987b

誰もzipで圧縮するなんて話はしてないし、
jpegが7zで圧縮できると証明できているじゃん。
jpegに冗長性があるわけだし、ビット列に特徴があるのも証明されたことになるよ。
圧縮率は微々たるものだが、間違ってはいなかったってことだ。

jpegの時点で圧縮されてるから>>674は3重圧縮なんじゃないの？

正確にはそう。
だから逆にJPEGのハフマン符号(とランレングス圧縮)だけ展開して、
高圧縮でやりなおすのが直感的には正しいと思う

>>681
それは正しいとかどうかでは無いね。
それをやったら、jpegの圧縮ではなく、別の画像圧縮形式の提案になる。
一連の話はjpegをさらに圧縮できるかどうかだし、特徴のあるビット列があるかどうか論点だった。
結論としては、圧縮率は微々たる物だが、特徴のあるビット列が存在することは証明された。

jpgをzipで圧縮可能 or jpgを7zで圧縮可能≠特徴のあるビット列が存在する

7z のレンジコーダ部分、 zipのハフマン部分だけで圧縮してて
両方とも lz部分は役に立ってない可能性がある。
んで、lz部分が役に立ってるなら特徴のあるビットデータがあると言えるかもしれんが
ハフマンとかレンジコーダで圧縮してる場合はデータに偏りがある（例えば00やFFが多い）ぐらいしか言えない。

経験的に、あまり圧縮できないファイルではlzが役に立ってない事が多い。

>>683
＞jpgをzipで圧縮可能 or jpgを7zで圧縮可能≠特徴のあるビット列が存在する

誰も圧縮可能だからという理由で、ビット列があるとは主張していないよ。
「特徴のあるビット列」はツールを実行することで証明されただけ。

結論としては、圧縮率は微々たる物だが、特徴のあるビット列が存在することは証明された。

つまり、611は間違いってことだ。

JPGよりこのスレを圧縮したい

>>684
ん？ あぁ、すまん。議論見てなかった。

ビット列に いくらかの特徴はあるのかもしれんが、
頑張ってjpg専用辞書作るに値するような特徴だとは思えないけど。

ちなみに、jpg専用辞書作ったらzipや7zに比べて大幅な圧縮率の改善を期待できると思う？

世の中には全く同一のファイルが別々の場所に保存されていることが多い
同一ファイルでなくても、複数ファイルにわたって同一の部分ビット列が存在することはさらに多い
データの保安性とのトレードオフがあるだろうけど、こういうの数を減らすことができたら効率良いよね

最近どこかで聞いた話だけど

多少圧縮率稼いだってクラスタギャップの藻屑と消えるだけだろ。

>>687
状況を限定すれば効果があるかもしれない
特定のジャンルの画像で辞書が似てるものをひとまとめにして
専用の辞書を作りそれを配布することで画像そのものの
ファイルサイズは小さく出来るかもしれない。

というわけでこのスレを借りて、フランドルの画像を集めるところから
はじめてみよう

つーか>>632は無視？
ハフマンの圧縮率下げてスピード優先にしてるんだから、
圧縮する余地が残っているのは自明なんだと思ってたが

圧縮後のビット列調べるならヘッダ部分は抜かないとフェアじゃないが、
どうやってるのかね
（C++読めんのよ・・・）

>>691
その上で圧縮率最高とかのときの話になってるのだと思ったけど。
ところでフランドル画像はまだ？

ハフマンとか算術符号とかの理屈分かっていってんのかな？
ここで特徴が〜とかいってる人。
それを分かった上で〜とかいってるのって正直電波としか思えない。
なんつーかアルゴリズムを変えて圧縮を繰り返せば
限りなくエントロピーに近づけるとか考えてそうな感じ。
頼むからもっと勉強してくれよ。

winnyは、ファイル交換ソフトじゃなくて、
究極の圧縮ソフトということにしたらよかったのに

jpegを圧縮するってのはさ、例えるなら、
八百屋でケチな主婦が30分くらいかけて野菜を1円単位で値切って
買ってきてこんなに安くなった！みたいな。
でも隣町のスーパーでもっと安く売ってたみたいな。
いや個人的にはたまには八百屋助けてやれよとか思わないでもないけど
まあ世の中合理化の時代だし競争力がないもんが淘汰されるのは仕方ないかなぁ。
潰れてビルが建ったほうが実は世のためなのかもしれないとか考えるんだけど
それってやっぱ冷たい都会の人の考えなのかとか。
でも土地持ちだったら実はウハウハだったかもしれなくて同情の余地はないのかも
とか思うんだけどそんなプライベートなことは分かんないし、
見た目にはやっぱ大変そうに見えたりもするんだけどまあやっぱ他人事だから
仕方ないんだろうなぁとか思ったりするよね。
そんな感じ。

時は金なり
うだうだ値切ってる時間あったら他の仕事して儲けろ

>>697
その考えも大事だけど、実務ではなく研究が目的なら
値切りの真理を最後まで追究するのがサイエンティスト道

他人が勝手に実現しようとする事に否定的コメントつけようとは思わない、
それを他人が勝手にやってくれると期待して理屈だけ語ってるのでなければ。
他人のやる事に否定的なコメントをつけるのは、時間の無駄を心配する卒塔婆心か
否定する事で自分を優位と思い込みたい虚栄心か、そのいずれかだろう。
あまりクドクド否定する、それも出来るか出来ないか研究してる相手に、
数％で得か損かのような話をしてもしょうがあるまい。

でも、72cmって圧縮されすぎだよな千早

算術符号が理知的過ぎてもう他を考えられねぇ

・・・この一週間に何があった

オレオレ理論で暴れたやつがいた。

オレオレ理論で暴れてたやつが
検証用のツール用意されたら
捨て台詞吐いて逃げた

アフリカではよくあること

HDDが1円あたり50MBの時代、高圧縮なんて意味ない
KGBとかGCAとかバカみたいに遅いしマジ最悪
並の圧縮率で超高速なアーカイバが最強でしょ

言ってる事は最もだが、通信コストが限りなく高い状態を考えると無駄なこととも限らない
宇宙からの通報とか。

電波・・・とどいた？


という題名のWebページを先日見つけた

宇宙犯罪者を通報しますぅ

ボイジャーとか最期の方じゃ 20bps とかだったらしいな
火星いったやつも 10Kbps とかだろ
圧縮技術が無いと宇宙じゃどうにもなんないな

火星人すみやかに出頭しなさいですぅ

火星へ 土星へ 銀河へ

そしてクラシックへ
http://pc11.2ch.net/test/read.cgi/desktop/1109102136/l50

宇宙って、圧縮もしたほうがいいんだろうけどそれよりもノイズに対する強度が重要そうだ

MTFについて質問させてください。
MTFの文字列をつかっての大まかな方法はわかったのですが、
これをバイナリで実行する場合、実際のデータと辞書内のインデックスを見分けるにはどうしたらいいのでしょうか?
初めは1バイト単位でやろうと思ってたのですが、これ自体が間違っているのでしょうか?

薄汚い派遣の国、日本

最近、職場で「出戻り寄生派遣」という言葉が囁かれています。
派遣契約を切られたにもかかわらず「次の派遣先でも切られてしまって生活できません」
などと 言って泣き落としで現場マネージャーにすら一切話がないまま再派遣契約した人のことです。
今月初め、半年前に切った派遣が出社してきてマネージャーも含めみんなびっくりしました。
影でコソコソ偉い人に泣きついて再契約したそうです。同じ部署の人には黙って・・・
そんなことまでして自宅の近くの派遣先にこだわって人間として恥ずかしくないのですか。

仕事に必要な技術がなく勉強する気もないのを逆手にとって
「私のような人の視点で仕事をすることも大切だと思います」と挨拶された時には
みんな凍りついていました。派遣でスキルアップとか言ってる癖に以前と同じように
技術を勉強する気はなく「それは私の仕事ではありません」の一点張り、
派遣で収入アップとか言ってる癖に時給は前回と同じで喜んで再契約。
結局、なんの努力もせずに派遣で安直に収入を得たいだけじゃないですか。

身分不相応な商品のローンを払うために派遣だと当然足りない収入は親にも寄生して、
いつ切られるんじゃないかとビクビクしながら人事権のある人間とだけ仲良くし、
契約終了を通知されれば泣き落とし。悲惨な人生ですね。
氏んだほうがいいんじゃないですか。

スタックに最初に256種データを適当に詰めておくと
区別の必要がなくなる。ただBLOCK SORTINGと組み合わせないで
MTF単体でつかうとLZ系よりかなり圧縮率悪いから実用的じゃない

>>717
新しいデータが出る度に追加するんじゃなくて、初めから全てセットしておくんですね。
やっと実際に使えるようになりそうです。
BWTの方は比較的楽に理解できたのですが、MTFはどうしても分からなかったので…
BWTのみにしようかと諦めていたので助かりました。

ありがとうございました。

MTFよりBWTの方が難しい気がするけどまあいいか。
MTFは実装は簡単だけど圧縮率も速度もそれほど良くないから注意な。

入力サイズ膨れるけど、16進にするとかBASE64風にエンコードするとかすればテキスト形式として扱えるんで無いか？

よくわかんねーけど圧縮って特定の文字羅列を更に少ないバイト数に置き換えてるだけ？

>>721
超大雑把に言えばそう。

19文字以内で記述できない最小の自然数

16文字に圧縮できる最大の情報量

保守

移動してきました。
http://pc11.2ch.net/test/read.cgi/tech/1183910525/510
よろしくお願いします。

>>726
こっちもスレ違いだ。そんなの最強でもなんでもない。圧縮復元相談スレにしてくれ。

最強の圧縮アルゴリズムとはいえ、
シャノンの理論の限界を超えることはできないんだよね？

>>728
最強とは適材適所に特化したアルゴリズムであり汎用ではない。
１万種類の目的別素材があれば、それら全てに特化したアルゴリズムが
１万種類必要になるということだ。圧縮する素材より複雑で、データ量が
肥大しているものこそ圧縮率は高い。
決まった仕組や特徴に対して汎用の圧縮をするのは高圧縮としては無駄の
域になるんじゃないか？

>>728
アカシックレコードを内蔵していれば、どんなファイルも100バイト程度に圧縮できる。

どこかに情報を置いとけばいい発送だな

>>730
無理無理
アカシックレコードがあったとして、
そのインデックスが何バイトになると思ってるんだよ

ちなみに円周率のランダムに並ぶ数字を使って圧縮するのも同じ

>>732
だから１００バイト程度あれば充分だろ。
人類が作れるファイルの数を計算してみろ。

>>733
つまりいずれは 8の100乗バイト をインデックスだけで消費しちゃうよね
という話じゃね？

圧縮は劇遅でも展開は超高速なアルゴリズム教えれ。

>>735
完全なスライド辞書圧縮とか？

>>735
lzxかな。そこまで圧縮率良い訳では無いけど。
あとはtek系はどうなんだろ…。

BPE

大域辞書圧縮システムってのもあったな。
でかい辞書をどこかに置いておいて個々の圧縮ファイルがそれを参照するやつ。

あーインデックスのがでかくなって使い物にならないやつな

THcompの出番か

winnyのhashって、THCompだよなあ・・・
winnyのアーキテクチャ利用して、圧縮解凍ソフトって作れないんだろうか

winny 自体、インターフェイスとか負荷のかけかたとか作りが何もかもヘタクソすぎる。

Shareのほうがもっと酷いぞ。

winnyは糞過ぎる

つまり技術的に糞でも成功するって訳だな

もう廃れたけどねｗ

現状の実際のソフトの出来はどうでもいいよ
問題は使われている技術が応用可能かどうかだ

Hashって可逆じゃないからなぁ…
よ書いてみる

ハッシュと圧縮って関係あるの？

>>750
>>742

>>742
winnyや、shareの場合、ダウンロードされたときにしか、拡散しない（アップロードしない）はずだから、
圧縮しようとした時に、ローカルにキャッシュが生成されるだけで、
圧縮にはならない。

圧縮時に、強制的に、他のp2pクライアントにアップロードする必要がある

>>752
アップロードすればいいんじゃない？

いくら圧縮してもみんなのPCに同じデータがあったら容量は発散するだけ

>>754
自分のPCさえ、容量が少なくなればそれでいい

>>755
http://pc11.2ch.net/test/read.cgi/tech/1191860116/38

それ何てURI？

iX6O/JemgsmCzYKggumMvpd0gqqJQoKzguqCxIKigumCxoKi
gqSCsYLGgvCBSSANCg0KiX6O/JemgsaCooKkiWmLdoLJkbGC
rY+skJQgDQozLjE0MTU5MjaBYyANCg0KgrGC6oLMj6yQlJNf
keY5MzI5OTI0MYyFltqCqYLnkOaC8ILdgsSC2YK1gqIgDQqB
YzA3MjE0NTQ1MjU1MjA4NzcxMzYzNzUxNTaBYyANCo3Fj4mC
zDiVto6agsmShZbagr6BQiANCoK7gqQiMDcyMTQ1NDUigsaC
zYF1g0mDaYNqgVuCtYKxgrWCsYF2gsyCsYLGgqCC6YFCIA0K
DQqCsYLqgs2Cx4KkgqKCpIKxgsaCvoFIIA0KkF+CzYnkgViC
yYm9gvCRaYKmguaCpILGgrWCxIKigumC8YK+gWMgDQqI6pHM
gUGJvYLwgseCpI1sgqaC6oLOgWMgDQoNCg0KDQoNCoLIgUGC
yILxgr6CwYLEgVuBSYFJIA0KgUCBX4FAgUCBQIFAgUCBQIFA
gUCBXoFAgUAgDQqBQIFAgUCBQIO2g7aDtiANCg==

>>758をBase46でデコードすると
オナニーってでるぜ

確かにオナニーすると出るなぁ

やっぱり歴史とか背景を知らないと、見逃してしまう面白さも
多いと思うんだよね・・・
リビングストン大佐がアーカードだったりするのもその一つかと。

作品単体で観ても確かに普通に面白いんだけど、それを踏まえないと
もったいない気がする。キスの天ぷらをポン酢で食べちゃうような感じ。

はあ？

よく見るけど意味がわからないネット用語は「gkbr」、gooリサーチ
http://internet.watch.impress.co.jp/cda/news/2007/09/25/16977.html

これはかなり参考になる

>>763
こういうの分からないっていう人はIQ低いと思う。

>>764
とっかかりになる知識があればいいけどね
kskとか知ってればgkbrとか応用できるけど

kskが初なの？
ｗｋｔｋかmjkあたりだと思ってた

AAもこの調子で圧縮できるな。
もっとも非可逆になるかも知れんが。

母音を省略して圧縮ってヘブライ語の記述かよ

せっかくだから俺は子音をいぉういぁういえいおうああ

>>764
IQ高い人はgkbrをゴキブリとも読めたりする。

日本語の五十音に当てはめるとして、
"g"一文字で5通り、"gkbr"なら、5x5x5x5=625通り。
"gkbr"を「ごきぶり」と読めるのと同じぐらい、「画家ぶる」と読んでもおかしくない。

後家腹かとｵﾓﾀ

マジレスするとそういうのは圧縮じゃなくてハッシュだろう。
不可逆圧縮と見てもいいけど。
そういう意味から言えばハッシュ==不可逆圧縮なのかもしれんな。

>>772
母音が全部消えるなら 後家いびり でもok。

>>770
なに言ってるんだ。
文脈的にゴキブリじゃ意味が通らないことぐらいは分かるだろ。
文法的にも、文章の一番最後に置いて「ケリを付ける」用法の単語なんだから
「ガクブル」だと類推できそなもんだが。
まあ、前提として「ガクブル」の単語と用法を理解してないとダメだけどな。

ガクブルを容易に類推できる人って、IQ低そうじゃないか？
覗いてる掲示板の傾向とか、そっち方面からの類推で。

人を小馬鹿にするという用途には、もう少し精度の高い
モノの括り方が必要だと思うな。

全てに潔癖で真面目、品行方正で酒も煙草もやらない政治家
がヒトラーだったりするわけだろ。

そいつは上手いこと言った

>>778
品行方正なら本を焼いたり人を焼いたりはしないけどね

結局3種類の基本アルゴリズムの応用でしかないんだから
新しいのは難しいんでないの？

3種類の基本アルゴリズムって言われて
・順次
・反復
・分岐
のことかとオモタ俺

たしかに全てはこの応用なんだが

アルゴリズムのすべてはANDとNOTで出来ている。

nandかnor

mpeg compass.jp
名古屋駅近辺でお話しましょう

PSPのファームウェアのファイルの圧縮方法がgzからKL4Eを使うように変更になったらしいけど、KL4Eの情報ってどっかにある?

さて、巷で話題のこれはどうなのかね
http://www.c10n.info/archives/720

>>787
ttp://slashdot.jp/~tt/journal/425221
256MBも食う糞アルゴリズムは要らない

>>788
手元でコンパイルして試したけど全然使わんぞ
1.5MBぐらい、算術符号使うと1/3ぐらいになる

あ、展開時だと700KBぐらいか

英語の読めない俺に解説ぷりーず

まあ要は算術符号に代わる新しいエントロピー符号化の実装ってことかと
パテントフリーとかを考えてる人にとっては嬉しいのでは?
256MBってのはhttp://cs.fit.edu/~mmahoney/compression/にあるPAQの事だと思うが、
記事自体とはあまり関係ない

>>783-784
直感で言うが、and,notの他に、回転演算(ローテートって言うんか？)が必要じゃないかと
シフト演算は回転演算とandがあれば十分実装できるけど、andとnotじゃ足し算も難しい気が

NANDがあれば何でもできる

>>793
ド・モルガンの法則って小学校か中学校か高校か大学で習わなかったか？
andとnotがあればorも作れるし、and,or,notがあれば加算器も作れる。

>>794は駄洒落なんだろうか…

We need NAND!!

NORだけはガチ

andとnotでどうやったらorが作れるのかわからん

~((~A)&(~B))

>>795
いや、ドモルガンなら分かるが、随分習う時期に幅があるな。
試しにand、or、notだけで加算機を作ってみてくれないか。頼むから。
C言語で宜しく。

どれもこれも他のbitに影響されない演算だから、それらのみを組み合わせても
足し算に必要な繰り上がりが出来ない気がするんだが。

わすれたが2の歩数とかがあるだろう

>>802
これか？
ttp://jp.youtube.com/watch?v=XICtHIuZ1u4

全加算器

>>801
単純に、あるビットからのキャリを次のビットに加算するだけだが。
擬似コードだがこんな感じで。

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);
...
あとは必要なだけ並べればいい。

>>801
数式より回路図の方が見やすいだろう。
ttp://ja.wikipedia.org/wiki/%E5%8A%A0%E7%AE%97%E5%99%A8

俺は加算器とフリップフロップを知ったときは、仕組みの単純さと
論理の美しさに感動したな。
794が言うように、NANDがあれば何でもできる。

NANDかNORかのどちらか一方があれば、ね。
一方を複数組み合わせてANDもORも作れるから。
スレ違いついでに、命令セットは１種類でおｋな話
http://en.wikipedia.org/wiki/One_instruction_set_computer

ANDとNOTでした、ごみんなさい。

Carry Look Ahead

>>807
>スレ違いついでに、命令セットは１種類でおｋな話
>ttp://en.wikipedia.org/wiki/One_instruction_set_computer

↓こいつがその実装例だよな
ttp://www.amazon.co.jp/products/dp/4839909865
インストラクションに別名付いてるけど実質1セット

>>793
シフト、ローテートは物理的に配線をずらして繋げばおｋ、ゲートは不要。
念のため。

>>792
亀だが�d

>>811
定数シフトはね

>>813
繰り返しやセレクタは、また別の話だろうな。

>>811
バレルシフタってあるんですけど。

>>815
>>814
バレルシフタは結局はnビットシフタとセレクタだ。

ナンバーワンにならなくていい、もともと特別なオンリーワン♪
無数の対象に無数の最強アルゴリズムが存在する。
つまり最強になれる対象が一つもないアルゴリズムは糞ということだ。

結論がおかしいな
たとえば全てに対して２位を取れたらそれはすばらしい物だと思わないか？

総合一位というオンリーワンだ
評価基準を変えればどんなものであっても一位になれる

極論でいうと「ｘｘｘ に対する圧縮率が ｘｘ% に一番近くなるアルゴリズム」

この前ふと思ったんだけど

一般的に、単一ファイルを圧縮してまとめるよりも
全ファイルをまとめて圧縮する方が、辞書が共通化できたりして圧縮率が良い。
.cabや.tar.gz、solidな.rarなど。
操作性は悪くなるけど。

ということは、同じ複数ファイル一括であっても、
似たようなファイルを優先して近辺に圧縮すれば
さらに僅かに圧縮率が向上するのではなかろうか。
asciiテキストとSJISテキストとバイナリとか。
あるいは、辞書だけでなくハフマン符号もタイプ別に持ったりとか。

アルゴリズムとは関係ないけど。

ブロックサイズ次第

離れてても十分有効なこともある

タイプ別辞書の方法は考えたよ　タイプ別ソートは考えなかったけど
これはまだ誰もやってないと思うよ　作ってみれば

タイプ別はなかなか分類がややこしくなる　自動生成する方法があれば良いけど
たとえばS-JISでもHTMLやC++やXMLとかまた別の分類があるし言語の分類もあるしどのくらい分類するのが良いのかある
でももっとも減らせる所を減らすべき
たとえばexeとかDLLとかもともとサイズが大きいやつ　テキストは1M以上は少ない

>>822
dgcaがやってるらしい

リアルタイムで分類して、ブロックソーディングするなら事前に辞書いらないね
辞書を用意しようとすると始めに分類しないといけない
類似度を測るにはベクトル空間モデルがいいと思うよ
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

類似度順に並べ替えてブロックソーディングするプログラム作ってみるかな　DGCAが最高とは限らないし
何Kバイトずつに区切るとか、ブロックソーディングのあとにどのような圧縮するかで変わるし

同じWin32EXE(COFF)でも、コード部とデータ部、それとリソース部ではまた別物だろうね。
コードはともかく、リソースは、文字かその他かという分類もあるし。
ただ、こちらは外部から見て文字か画像か等を判別するのは無理かな。

まずはファイル分類部分をつくってみるよ

>>826
最高ではないだろうし、最高だとは誰も思ってないよ。
ただ、言えることは、まだ誰もやってないことではなく、
誰もがやったようなありふれたことだってこと。
正直、あまりにも時代遅れ。まあ、自分でいろいろやってみることには価値があるけどね。

>>820
cab、7zipあたりもやってるみたい
同じファイルばっかりだと異様にちぢむし

ブロックソーティングして全文検索しよう　鈍いが一応ソートは作った

#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]);
}

http://fx10.web.fc2.com/2chlog.gca

10ギガでもブロックソーティングできる　プログラムを作るぜ
a(n) < a(n+1)である番号に対して、それをファイルnへ書き出す
ファイルnごとにそれをソートする
未ソートなのはa(n) < a(n+1)とa(n) = a(n+1)だ
初めにソートした結果から、その一つ前が先頭より大きいものは
自然並べればソートできている　あとは連続する部分だがそれは簡単

三分割法っていうやつだが理解できない部分がありちょっと変更した

参考文献
ttp://homepage3.nifty.com/wpage/index.html

>>835
Home pageの主?情報交換しよう　10Gでもまとめてしたい

paq8o8でいいじゃん。

BMPを可逆で圧縮する手順を考えた
走査→差分→連長→ＭＴＦ→符号化

>>837
ああびっくらこいただ

人工知能の研究をしていたら
圧縮に使えることがわかってきた
詳しくは次週

>>840
記憶整理機構が圧縮アルゴリズムになるって話？

どうせ使わないなら、忘れてよし

人間の記憶は劣化を避けることは出来ないわけで
たまにサバンな人が無劣化保存を実現しているが

ブロックソーティングしたデータから全文検索する方法をFM-serachというらしい
だれか一緒に研究しましょう

http://scholar.google.com/scholar?num=100&hl=ja&ie=sjis&oe=sjis&newwindow=1&q=fm-index

FMサーチも圧縮接尾辞配列もメモリHDDを食いすぎる事がわかった
パソコンで、合計10Gのファイル達を検索できるようにしたい
元のファイルを復元出来てindexが必要ないのはブロックソーティングだが
実用的でないのが欠点　何とかならないものか

なるべくメモリHDDを減らす方法がferragina rank　でググると出てくる　今調べているところ

良くわからんけど10Gのファイルを1Gとかに分割した状態で
圧縮して連結するんじゃダメなのかね

32bitの最大値(4G)以上のファイルを扱うことが一つの目標なんです
あと分割するとサーチに時間がかかってしまいます

単語抽出法　word extractionとブロックソーティングを組み合わせると良いかも・・
ブロックソーティングや、算術圧縮や、ハフマンは1語か2語の関係しか考えない
例えば1〜4語までの関係を取り扱った方が性能良いはず

>>849
その根拠は？
PPMで次元を上げるとかえって性能が落ちるのは知ってるよな？

>>850
上の方針はあきらめましたよ　単語の出現確率でビット数を割り当てた場合、
全文検索しようとすると1bit単位でブロックソートしなくてはいけなくなります

でも圧縮率は上がると思います
算術圧縮は文字の前後の関係を考慮せず、
ブロックソーティングでは2バイトの関係だけです
日本語や英語などは2バイト以上の単語が多くあるため効果があると思います

>>851
＞全文検索しようとすると1bit単位でブロックソートしなくてはいけなくなります

ブロックソート理解していないのね。
何bit単位でもブロックソートの結果は同じ。

＞でも圧縮率は上がると思います

だから根拠は？

＞算術圧縮は文字の前後の関係を考慮せず、

そんなの後段のエントロピー符号化でモデルと関係ない。ハフマンより上なのは常識。

＞ブロックソーティングでは2バイトの関係だけです

間違い。PPMの無限大次元と同じ。

>>852
サイズが100Mだとして100M単位でブロックソーティングしたら変化無しです
あとブロックソーティングは前(後ろ)に何があるのかしか考慮しませんよ
たとえば、THという2語が多く出現すればソート語にT(またはH)が連続しますが
そのあとにEが多く出現しても、少なかったとしてもTの連続する個数には影響を及ぼしません

>>849
まあ単語レベルで分割してBWTをかければ単語間の繋がりを利用できて、
しかもインデックスのBit数を減らせるのでいいかもしれない。
が、単語間の相関性てのは相当な量を読み込まないと見えてこない。
人間の様に何十年もかけてサンプルを得ているわけじゃないから。

>ブロックソーティングや、算術圧縮や、ハフマンは1語か2語の関係しか考えない
そんなことはない。もっと勉強しろ。

>>850
それは極端な話。
PPM(というか圧縮全般)のサンプル(情報源)として英文がよく使われて、
英語の平均単語長が5くらいだったので結果としてPPMのOrderは5位で頭打ちで、
それ以上は無駄(むしろ悪いこともある)とされたから。
実際は最適なOrderは文脈に依存する。
上手いOrder FallモデルがあればPPM*は十分な性能を発揮する。
メモリさえ許せば。

abcdefgabcdefgabcdefgabcdefgという文があったとして
ハフマンや算術圧縮では全記号が等確率に出現するので圧縮はほとんどしません
しかし、A=abcdefgという単語を作ればAAAAになります

>>855
そりゃモデル化の問題だ。
7byteで一単語(つまりアルファベットサイズ56bit)とすれば
エントロピー符号(算術符号・ハフマン符号)でも結局同じになる。
この単語長を可変にして単語を辞書番号に変換したのがLZ符号。

>>856
そんな事は無いですよ
A=abcdefgがかなり多く出現したとしても
通常の文書ではほかに単独でa,b,c,d,e,f,,gは現れますから
1byte単位であつかうしか無くなります

>1byte単位であつかうしか無くなります
だからそれはモデル化の問題なの。
abcdefgもaもbもcも一単語として扱えば同じ。
エントロピー符号はシンボル単位だから
シンボルがどうなっているかはモデルとは無関係。

日本語や英語の文書の話をしています

テキストかどうかは本質的に関係ない。
もっと勉強してくれ。

初めに言っていた、算術とハフマンは1語の関係しか考慮せず、
ブロックソーティングは2語の関係しか考慮しないというのは間違っていないと思いますが

>>860
7byte(56bit)単位で扱える日本語や英語の文書は無いと思いますよ
モデルの話をしています

>>853
影響する。
しないと思い込んでいるのは、THだけ考えているから。
SHとか入ってくると状況が変わってくる。

間違っているいないの問題ではなく
BWTはただの変換でエントロピー符号とは全然性質が違うということ
を理解してほしい。
BWTが2語しか考慮しないのは確実に間違っている。

>>861
間違い。

>>863
THとSHが隣接しているか、していないかはソートに影響を及ぼさないと思いますが

>>862
だから、単語をどうやって分けるかは算術符合だのハフマンだのとは
別の問題なの。

>>866
隣接しているなんて書いてないが。
ブロックに含まれるかどうかが問題なんだってば。

もしかしてエントロピー符号はみんなfv(fixed to variable)と勘違いしてないか？

>>867
単語(一語)はすでに分けられているとして話してます　例えば日本語や英語です
>>868
文書に含まれているかどうかだけならば出現頻度に影響しますが
2語や3語や4語のつながりとは関係ないことになります

>>870
設定を後から付け加えても駄目だよ。

俺はここで終わりにする。
IDないから分からんかも知れんが
>>854,856,858,860,864,867,869
は俺。

>>870
関係があるから、BWTしたものがより圧縮しやすくなるんだってば。
２語の関係だけと思うなら、PPMのそれと比較してみろよ。
PPMとBWTの違いは、時系列情報があるかないかの違いしかない。
処理方法は全く違うが、本質的には同じものなんだってば。

ここにこう書いてある　


http://www.ipa.go.jp/NBP/14nendo/14youth/mdata/2-8.htm
WX法は現在の圧縮アルゴリズムの中心であるLZ法とは違い
全体のデータ構造を調べて単語を抽出するので単語抽出の妥当性がよくなる．
また，高圧縮率を誇るブロックソート法と比べても
「単語間の距離」　「単語長と出現数の関係」
「単語が出現する範囲 」といった情報を利用できる点で，WX法は優れている．

ということは、ブロックソーティングは、
「単語間の距離」　「単語長と出現数の関係」「単語が出現する範囲 」
という情報を利用していないと言うことだ

>>874
BWTは、「単語間の距離」は利用していないが、結果的に、隣接しているか否かの情報は利用している。

隣接しているかどうかなので2語のみだろう
初めに言ったとおりだ

2語の前後だけで、単語のよく出現する範囲などは関係がない

>>876
だから、それが間違い。

間違いの具体例を挙げてください　間違いと言っているだけではわからないですよ

>>879
BWTは２語の関係だけでなく、 ブロックサイズ分の文字の長さの関係が反映されている。
だからこそ、その当時、BWTが注目されたわけなんだが。

******XYZ*****というデータは、
XとY 、 YとZはつながっていますが、ソートしてしまえば
それらは別々の位置へ移動してしまいます

XY*********YZ********
というデータをソートしても同じ結果です
だから3語の関係は無くなってしまいます

>>881
＞というデータをソートしても同じ結果です

これが間違い。

*****の部分は同様の単語が出現したとして

******XYZ*****
の巡回データは、
YZ***********X
Z***********XY
になる

XY*****YZ*****
の巡回データは、
Y*****YZ*****X
Z*****XY*****Y
になる

これをソートして末尾のデータを出力すれば同じだよ

いや書いててわかったが****の部分が全く一致していないとソートの順序が変わるな
ということは3語目も結果に影響するな　間違えていたよ　ｽﾏｿ

>>881

わかりやすい例で書くなら、
AAAXYZAAAXYZAAAAAAAAAYY
と
AAAXYAAAYZAAAXYAAAYZAAA
は全然異なってくる

単語として成り立つ範囲の影響があることはわかった
単語抽出が価値あると思ったがそうなるとやる意味がないといえる
ということはzipやPPMに圧縮率で劣る点はないって事か?
１語目の影響が完全に2語目を上回っているところが少し弱点にはなり得えそうだが・・そんなことはないか?
T*Eに対して*に入る語を予測しようとするとき、TとEの2語に影響されるが
ブロックソーティングでは価値に対する重みがないか

>>881
文中にXYZが多くあればソート後、YZ…Xが大量にできる
XYとYZが個別にある場合は、Y…Xが大量にできる
しかしYで始まる巡回文字列はいっぱいあるので
末尾のX自体は飛び飛びにしか並ばない
YZで始まる巡回文字列はあまりないからXが結構並ぶ
つまりあなたの勘違い

ブロックソーティングを後方からソートしたらどうなるものか?
通常のやつでは、△○○○としたとき
○○○から△を予測することに等しいといえるが
後方ソートでは、○○○△に対して前方から最後の１語を予測するのと同じ
こっちの方が予測が成り立ちやすいか?

それ逆順に並べかえてからブロックソートするのと同じじゃないか
どうせBZIP2の人が既に試してるだろうけど

>>888
やってみればわかるが、どちらにしてもほとんど変わらん。

rar最強

>>888
Efferosだっけ？女性の研究者が関係論文を出している。日本の有村氏とかも。
ブロックソーティングの理論解析は10年〜5年前にほぼ終わってる。


以下亀レス。

>>850
PPMの次元を上げると性能が落ちるのは、モデル化の方法が最適ではなかったから。
これは、PPMZあたりでも語られている。日本だと横尾氏あたりか。

目標は10ギガ程度の高速なブロックソーティングと、それを全文検索出来るように圧縮すること

ブロックソーティングが目的になっているのはなんでよ
手段の一つに過ぎないはずだが

>>894
このへん参照してみて
http://www.google.com/search?q=%22fm-index%22+ferragina

圧縮率を上げるためSjisに統一して難しい語を易しい語に変換したいと思います
2バイトが一致したときに置き換えると間違えることがあります　1バイト文字が混在しているためだと思います
どのようにして正確に変換出来ますか

例えば・・・
�瓔鴾戌ﾘ�^�u�~�������拐蹄ｩ�ｷ����
朗隆塚晴猪益神祥福靖精羽諸都飯飼

とりあえず文字コードの話は確実にスレ違い。
変換の仕方は他所で聞くべき。
つか文字コード変えたら不可逆になる場合も出てくると思うが。
変換前の情報も残すのか？
それを承知の上ならマッピングの都合でs-jisよりeucの方が圧縮しやすいぞ。

バリナリは除外して文字だけでやるので、
英数字、記号は半角、カタカナは全角に統一して不可逆で格納します
これは検索とサイズに有効です

>これは検索とサイズに有効です
といわれてもな…
ここんとこよく現れてるブロックソートの人だよね?
ここで聞くよりとりあえずググる。
http://www.google.com/search?hl=ja&q=s-jis+%E5%88%A4%E5%AE%9A&lr=
不可逆でいいならs-jisより内部でアルゴリズムに合わせて
全部マップし直した方がさらに速く圧縮も効くと思うぞ。

>>897
情報サンクス　eucに統一することにしました　
カタカナを信頼性あるソフトで変換しておけば
2バイトの一致を調べるだけで置き間違いが起こらないと思います

うんうん
隔離スレとしてちゃんと機能してるな

http://homepage3.nifty.com/DO/direct_linear_sa.htm

Ko & Alulu法を実装したいのですが、概要はわかるのですができあがりまで遠いです
解説かコードありませんか

自己解決しましたよ　世界最速のブロックソートライブラリ作るぜ!

Ko & Alulu法で計算途中で次のような長さがある程度短いデータをソートする必要があります
abcde
ades
abc
adc

多分木に格納して順に呼び出せばソート出来そうなんですけど
どのように実装すれば良いと思いますか?数ギガのデータだとメモリに入りきるのか不明です

分布カウンタを利用したradixソートを手前からすれば良くね?

たとえば10G バイトのデータがファイルに格納されているとします
x[n]< x[n+1] となるn番目の文字をTypeAといい、TypeAでないものをTypeBと言います。
先頭がTypeAで残りがTypeBで構成される文字列全てをソートしたい
最速でソートするにはどうすればいいか?というものです

>>905
ファイルへのアクセスがタイムロスになると思うのですが、なるべくランダムアクセスを減らして
一度に読み込んだ方が良いと思いますが・・どのようにしたらいいでしょうか?
重複は削除します

>>906
10Gのブロックなんてソートはできても解凍でないって
ブロックサイズが大きくなる程
指数関数的に解凍が遅くなるってわかってるよね？
ましてメモリに全部載らないものどうやって解凍するの？

これ使えばすべてをメモリ上にのせて操作する必要ないです


高速かつ省メモリで文字列を扱うデータ構造「wavelet tree」
　このWTを利用することで、近年提案されている圧縮全文索引（Compressed Suffix Arrays、FM-index、wavelet treeなど）やsuccinct data structure（括弧木など）を実現することができます。
http://codezine.jp/a/article/aid/261.aspx?p=1

>>907
メモリは使わずに済みますが、WTの索引と、圧縮元のデータにランダムアクセスする必要があるため
10ギガの8bitずつのランダムアクセスにかかる時間程度かかります　計算時間はほとんど無くランダムアクセスだけの時間だけと思います
WTの構築にすこし時間がかかりますが

ブロックソート法は、もともとランダムアクセス時間がO(1)のモデルを前提としている。

HDDへのアクセスを極力減らしたいなら、マージ法を改良していくしかなさそうだね。
代わりに計算量が増えるけど。

>>902のKo & Alulu法は、2分割法の一般化です
これを使えば、>>906の部分列のソートだけで実質的にブロックソートが完了出来ます
とても長い列をソートしなくて済みます　(もともとは10Gサイズの列でした)
>>908のwavelet treeを使えば、ブロックソートされたデータの全文検索や、
任意の文書をそのサイズに応じた時間で復元出来ます
圧縮と全文検索を実現したいと思います

ブロックソートで連続データを増やす未発表と思われるテクニックを発見しましたよ
ここだけで特別に教えます　語の頻度を調べて高頻度順に番号を付け替えます

すると例えば
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で無いデータが入ったら駄目ですが。。。
でも可能性として少し連続が増えそうです　より増やせそうなテクニックはありますか

やったことあるよ。
たいして効果ないw
未発表なんじゃなくて意味ないから誰も言わないだけ。

>>908,911
＞ これ使えばすべてをメモリ上にのせて操作する必要ないです
いやHDにランダムアクセスなんて選択肢はないんだって。爆遅だから。
＞ 任意の文書をそのサイズに応じた時間で復元出来ます
初めから文書単位で圧縮しとけば修正のたびに10Gも圧縮し直さないで済む

当たり前だが一応いっておくと文書単位で圧縮しても
ファイルを跨ってwavelet tree作っとけば全文検索できる
全体を一個に圧縮する意味はほとんどないと思うよ

文書単位にしたら例えば、thisが存在する文書を一斉に求められません

圧縮しなきゃ全て解決じゃね？
俺天才じゃね？

>>914
キーワードの周囲の文200文字だけとかなら200回だけのアクセスです
一瞬です　あと全データを復元することはまれです
ソート済みのデータが一定以上の大きさになったらひとまとめにして
小さい(100M以下とか)ならば復元してから追加すればいいかと思います
検索対象が増えますが

>>917
ブロックソートすることによって全文検索が可能になるんですよ

>>906のソートで良い方法思いつきましたよ
まず、3桁以下の場合、256*256*256個のビット配列のビットを立てます
4桁の場合は、ハッシュを使ってバッファに蓄えておきます　一杯になっなら4桁をHDDをビット配列と見なして書き出します
5桁以上のものは、そのままHDDに書き出しておいてあとで普通にソートをします
あとは順番に呼び込めばソート出来ます　これで4桁以下の文字はソートせずに済みます

ランダムアクセスの遅さはSSD時代になれば解消すると希望的観測

ブロックソート＋BPEが平均的に性能よさそうな気がする。

ランレングスで特許獲れたら俺さま億の世界へＧＯ？

>>923

主語による。

特許が使ってもらえたらの話

そういや、そろそろ大抵の圧縮方法は特許切だよな？

古典的なヤツはね

幸福な世界はいつおとづれますか

それは
・おまいの圧縮アルゴリズムの特許で大儲け
・現行全ての圧縮アルゴリズムの特許が切れてフリーに
・おまいが壺サイズに圧縮されてから千の風に伸長される
の何れの幸福のことですか？

壷の転送データが今より圧縮されて２ちゃんねるの運営費を心配しなくて良くなる

圧縮・解凍に使う辞書を作って、その容量を1Pぐらいにすれば
とんでもない圧縮率が実現できそうだが、時間もとんでもなくかかりそうだ。

もう URL でいいんじゃ

URLって転送量を考えるとまったく圧縮できてないだろ

>>933
概要とURLが貼ってあれば転送量は減る可能性が高い

専ブラに辞書持たせる

２ちゃん専用辞書みたいなのを鯖側と専ブラ側で共有しておくわけか。
板ごととかカテゴリごとに辞書を作ったらよさげ？

ちょっと質問なんですが、
ほとんどのデータを可逆圧縮で４０％以下に
出来るソフトって需要あります？
その、売れるんでしょうか？

４０％くらいでは需要は無いでしょうか？

>>937
MP3とかJPGとかPNGとかも40%になるなら需要あるはず

>>937
どんなzipを食わせても平均して40%以下に圧縮できるなら、ぜひ買わせてもらおう。

>>938
レスありがとうございます。

プログラムのことはあまり詳しくないので
がんばって、プログラムに取り組んで行きたい
と思います。

圧縮って簡単にエントロピーを超えられそうな気がするから困る

でもPNGはまだまだ圧縮しようがあると思うなぁ…ちょっと作ってみるかな。