圧縮アルゴリズム考えたんですが

自分で圧縮アルゴリズム考えて実装する奴は全員ｱﾌｫ

AA板専用で作れば圧縮率1%ぐらい行く気がする

>>793
LZMAとかGCAの作者はｱﾌｫですか？

少なくともGCAの作者はｱﾌｫである

それは言えてる

GCAって色々叩かれてるけど何で？

>>798
半分の理由は作者がおたくだから
もう半分の理由はイースのスレで聞いとくれ

最近はGCAじゃなくてDGCAだぞ。拡張子はdgc（デジコ）だ。
今は7z使ってるからどうでもいいが。。。

>>799
該当スレで質問してみました。

イース総合スレ 二十二 -やっとフェルナガ終わった-
http://game10.2ch.net/test/read.cgi/game/1124315466/496

799が教えてくれると一番良いんですが。

>>801
既に回答されとるぞ(w

そっかー
ny擁護か

>>803
本人は擁護していないが、擁護していると誤解されたというのが正しい。

本人乙

>>799
その半分についてだけど（イースうんぬんは知らなかった）、おたくだからじゃないな
既知のアルゴリズムを自分が編み出したように流布しているのが問題

>>806
どういうアルゴリズムなの？

>>806
そんなことはないだろ。
作者はBlockSortingとRangeEncoderを使っていると説明している。

>>801
確かにこれじゃｱﾌｫといわれても仕方ないな…

アレの本当の問題は数年前からのトラブル。ここで全部バラそうか。

>>808
それのことじゃない。
スレと関係なくなっちゃうけど飽和演算に関してだ。

個人叩きはもういいよ

高圧縮率のプログラムは誰でも作れるけど、
ここはひとつ高圧縮率かつ解凍の速い奴たのむわ。
並び替えたり木を作ったりする奴は遅いな。
実用的圧縮率の解凍速度はLZ77系最強？

7zip

>>813
いろんなアルゴリズムを実験してみたが、
圧縮率と解凍速度は反比例するという結論に達したよ。
LZ77系最強で間違いないと思う。(メモリ喰わない上に展開が速い。)
有名どころが殆どLZ77系なのからも分かると思うが。
zip,lzh,cab,rar,7z...
bzip2は例外か。(でもbzip2はいまいちだと思う。)
圧縮率・展開速度のバランスから考えると最強はcabのlzxかな。

今後cpuのマルチコア化を考えると分散処理のしやすい
BWT系が再び注目されるんじゃないかと思ってる。

SBC
http://www.geocities.com/sbcarchiver/
LZ不使用、BWTベースで高速・高圧縮なアーカイバ

解凍速度とかメモリ気にしてるのはこのへんかな。

tek - OsaskWiki
http://wiki.osask.jp/?tek

保守

或るﾌｧｲﾙに措けるﾊﾌﾏﾝ圧縮での限界は、Nbit長のﾃﾞｰﾀｻﾝﾌﾟﾙに措いて
最頻出ﾊﾟﾀﾝから最少出ﾊﾟﾀﾝﾞまでの出現頻度が完全等しい場合にｵｰﾊﾞｰﾍｯﾄﾞに到達すると云う事である

256byte＝2048bitのﾌｧｲﾙの場合、
1bit長に分割時に措いて0の出現頻度と1の出現頻度が等しく1024回ずつ（1024Hz）
2bit長に分割時に措いては、00、01、10、11の各ﾊﾟﾀﾝが256回ずつ（256Hz）
4bit長に分割時に措いては、0000、〜、1111と各ﾊﾟﾀﾝが32回ずつ（32Hz）
8bit長に分割時に措いては、00000000、〜、11111111と各ﾊﾟﾀﾝが1回ずつ（1Hz）
16bit長に分割時に措いては、各ﾊﾟﾀﾝが0.0625回ずつ（0.0625Hz）

ﾌｧｲﾙｻｲｽﾞAの場合なら、ﾋﾞｯﾄ長Nに、ﾊﾟﾀﾝ全出現時である2のN乗したものを掛けたもの（ｱﾄﾞﾚｽ）が、
ﾋﾞｯﾄ長N時の全組合せ出現に必要な最低bit数。これでﾌｧｲﾙｻｲｽﾞを割ったものが周期（Hz）。

しかも静的ﾊﾌﾏﾝでも、動的ﾊﾌﾏﾝで圧縮した場合でもこれ以上圧縮できない状態を想定するなら、
ﾌｧｲﾙ全体で各ﾊﾟﾀﾝ均等出現と云うだけでなく、偏り無く1Hz相当ずつに全組合せが出現するﾓﾃﾞﾙの筈だ
そして1Hz内でのﾊﾟﾀﾝ出現順序が、別の1Hz分のﾊﾟﾀﾝ出現順序とも一致しないﾓﾃﾞﾙの筈だ。※

このような前提のﾌｧｲﾙを理想ﾌｧｲﾙとする。

では仮に512byte＝4096bitの理想ﾌｧｲﾙの場合、

8bitのｱﾄﾞﾚｽに対して、倍の16bit長に分割すると
2＾8の256個のｱﾄﾞﾚｽに対し、4096/16で256個のﾃﾞｰﾀが格納される。
16bit長＝65536通りであるから
全ﾊﾟﾀﾝ出現の最低周期（1Hz）にはﾋﾞｯﾄ長16に、2の16乗した数を掛けたものである1048576bitが必要である

しかしながらこのﾌｧｲﾙは理想ﾌｧｲﾙである為に
4096bitサイズに措いては、各ﾊﾟﾀﾝの出現頻度は1回で、且つ2＾16　/　2＾8　で
各ﾊﾟﾀﾝの値は平均256間隔ずつ離れた値が出現するのである。


これを利用して、元のｱﾄﾞﾚｽﾃﾞｰﾀを付属して、16bit長のﾃﾞｰﾀを降順にｿｰﾄすれば
ｿｰﾄ後の16bit長ﾃﾞｰﾀは、その一つ前の16bit長ﾃﾞｰﾀとの差分の値は256-1に集中する筈である

ｿｰﾄ前の元のｱﾄﾞﾚｽ記述用の8bitと、差分の下位8bitの内、値の集中が起こる差分値は
ﾊﾌﾏﾝ圧縮で再圧縮可能な理想状態になっているのである。

では256-1を超える部分はどうするか？と云うと、ﾍｯﾀﾞに下位bitｵﾝﾘｰのﾌﾞﾛｯｸと
上位bitを記述するﾌﾞﾛｯｸを参照する必要がある事が解るように決めたﾌﾗｸﾞ値を記述する

つまりﾌｧｲﾙ構造は、「ﾍｯﾀﾞ、下位bitﾌﾞﾛｯｸ、上位bitﾌﾞﾛｯｸ」の様に成る

と云う事は16bit＝65536通り中、最頻出は256番目で
1番目から256番目までの出現確率は50％で、257番目〜65536番目までの出現確率が50％である
つまり256に集中且つ、それ以外も下位bitも256番をﾋﾟｰｸに集中すると云う収束性の高い状態になる
上位bitも平均分布でなく256番を極大に急端な下がり型をする。

降順にｿｰﾄの16bit長ﾃﾞｰﾀであるから、差分値の総和は65535を超えないので
同じ数の最大出現回数は、「65536/差分ﾃﾞｰﾀ値+1」の回数しか取れないからである。

仮に降順ｿｰﾄ後の16bit長の最初のﾃﾞｰﾀが（そのﾌｧｲﾙの16bit長での最大値）65535だとして
・その次のﾃﾞｰﾀ（そのﾌｧｲﾙの16bit長でのNO2の大きさの値）も65536-1なら差分は0で下位bitに収まる
・その次のﾃﾞｰﾀ（そのﾌｧｲﾙの16bit長でのNO2の大きさの値）が0なら差分は65535と上位bitが8bit必要であるが
この場合はそれ以降のﾃﾞｰﾀは全て0で在る必要がある為、差分も0が続き、上位bitのｵｰﾊﾞｰﾍｯﾄﾞを越えて
下位bitのﾊﾌﾏﾝ圧縮が圧倒的に有効になるのである

理想ﾌｧｲﾙとは云えない、差分の再頻出値が510付近だとしても、
理論平均が255である為に、ﾍﾟｱﾘﾝｸﾞとして0〜9あたりも頻出し
255が下降するM字曲線ｸﾞﾗﾌとなり510以降からは極端な下降線を描くのである。


このようにあらゆる局面で既に圧縮されてのｱｰｶｲﾌﾞに対して有効な、
このｿｰﾄ-差分算出-ﾊﾌﾏﾝ圧縮の方法をｼﾝﾌﾟﾙｿｰﾄ圧縮とし以下sscとする。


私はsscと更に画期的な方法によって8GBのDVDのISOｲﾒｰｼﾞﾌｧｲﾙをzip-ssc-zip-ssc-zip-ssc-zip-sscと繰り返す事で
脅威の圧縮率10％を達成した！！！

Ω、ΩΩ　＜ﾅ、ﾅﾝﾀﾞｯﾃｰｰ！！？

そそ、そ、そのｿｰｽを此処に書きたいのだが、余白は余りにも少な過ぎる
そこで皆の協力が必要だ

＞そこで皆の協力が必要だ
まで読んだ

だだだ、だから要するにﾎﾟﾏｲﾗが代わりに作ってください(((（ ;ﾟДﾟ)))>>822

出来るんだからな！！ﾎﾝﾄ何だからな！！！！！

シャノンの定理でも読め>>823

そんな欠陥定理はもう読んだ

それは可愛いいもうパンダ♪

>>823
> 脅威の圧縮率10％を達成した！！！
> そそ、そ、そのｿｰｽを此処に書きたいのだが
> だだだ、だから要するにﾎﾟﾏｲﾗが代わりに作ってください
お前実際には試してないじゃねーか。すぐバレる嘘をつくからお前はクズなんだよ。

>>825
君は、ほらあれだろ、物理板で「相間」をやっているたぐいの人でしょ？

圧縮繰り返していたら、何もなくなりました。

(c)鳥肌実

だってｿｺは解り易くないとと申し訳ないでしょ

ﾎﾟﾏｲﾗだってﾊﾌﾏﾝ圧縮での、これ以上縮まない限界状況ってどんなだろう？
って想定した事あるでしょ？

定ﾋﾞｯﾄ長の区切ったﾋﾞｯﾄﾊﾟﾀﾝの出現値が全部均一の時じゃないか
だとすればそれを降順でｿ-ﾄして差分を取れば、各差分の取る値は収束するだろ？

収束するって事はﾊﾌﾏﾝ圧縮で圧縮し易いって事だよ

ねぇ、誰かつくってＹＯ


対象ﾌｧｲﾙをNﾋﾞｯﾄ長で区切った場合の、各ﾊﾟﾀﾝの出現頻度を実際に計測するｱﾌﾟﾘで良いからさ

圧縮ｱﾙｺﾞﾘｽﾞﾑを研究する上で、任意のNﾋﾞｯﾄ長時のﾊﾟﾀﾝ出現頻度を実際に測るｱﾌﾟﾛｰﾁ
って重要でしょ？

ね？ね？ね？

>降順でｿ-ﾄして

復元するときにもとの順番に戻すために
元の順番情報を保存しておかなければならない。

ソート済みデータが圧縮できたところで
順番情報と合わせれば圧縮できてない。

だから元の順番を記録したﾃﾞｰﾀもくっ付けるんだＹＯ

その記録ﾃﾞｰﾀがけっこう馬鹿にならないっしょ
初期状態の１０％は到底むりぽ
結局計算機負荷の割に効果ﾅｽ　無駄にﾒﾓﾘ食うし

とにかく1ﾊﾞｲﾄでも小さくしたいんだって場合にはぎりぎりまで圧縮できるかもだけどさ。
zipのrarみたいなﾓﾝでは

>>832
> 脅威の圧縮率10％を達成した！！！
> そそ、そ、そのｿｰｽを此処に書きたいのだが、余白は余りにも少な過ぎる
御託はいいからさっさとソースうｐしてみろよ。

>>833
つーか限界をこえて圧縮された情報（つまり切り捨てられた情報）をソート情報として外に
もちだしてるわけで、それらを足し合わせたら圧縮限界は超えられてない。ただの詭弁。
> zipのrar
zipのrarって何？

特定ﾌｧｲﾙに措けるﾊﾌﾏﾝ圧縮ｱﾙｺﾞﾘｽﾞﾑでの限界は
そのｱﾙｺﾞﾘｽﾞﾑでの限界であって、所謂圧縮限界でもなんでもない

>>835
シャノンの定理のどこが欠陥定理なのか書いてみろよ。
お前の頭の方が欠陥脳だろ（ﾌﾟｯ

zipで圧縮した後にrarで再圧縮するようなもんでしょ、って事だろ？

うん確かにそうだが、これ以上縮まないとされる圧縮後のﾌｧｲﾙは
圧縮限界に遠く及ばない圧縮度であると仮定して

上手くすれば圧縮済みﾌｧｲﾙの方が寧ろ縮んじゃったらどうしよう♪（*/▽＼*）って事だよキミィ〜

>>835
何言ってるの
情報量が少ないほどよく縮むだけ
音楽ファイルや乱数ファイルは、冗長度が少ないので、可逆圧縮を
しようとすれば、理論的限界がある。完全な乱数なら全く圧縮できない
可能性がある。

シャノンは円の内接正多角形と外接正多角形の外周は極限値で一致するぐらいな事しか云って無いじゃん

じゃあ、実際に計算し続ければ極限状態に出来るんですか？

ﾌｧｲﾙｻｲｽﾞは無限じゃないし、1bit未満は最適長の符号化ﾋﾞｯﾄ長は与えられないからそもそも画に書いた餅で

ﾊｲﾊｲﾜﾛｽﾜﾛｽってﾔﾂだろ

>>839
NP完全問題って言葉を知ってるかね？

MMRとかいうヴァカは、情報工学を一から勉強した方がいいな。
あ、頭悪いからそれは無理か。

>>839


　　　　さ　　っ　　さ　　と　　ソ　　ー　　ス　　う　　ｐ　　し　　ろ

だいたい理論的限界ﾌｧｲﾙがどんなﾊﾞｲﾅﾘなんだよ？
実際どうなってるんだよ？
任意のNbit長で区切って計測したら、そのﾊﾟﾀﾝは偏るのか？偏らないのか？

そもそも圧縮済みﾌｧｲﾙだからって理論的限界に全然達してないんじゃないの？
理論的限界に達する究極のｱﾙｺﾞﾘｽﾞﾑがまだないから数多のｱﾙｺﾞﾘｽﾞﾑがあるだろ

圧縮済みのﾌｧｲﾙですら圧縮限界からは掛け離れてる事を前提にすべきだろ

どんなﾌｧｲﾙでも一度圧縮したら殆ど理論的圧縮限界に近しいなんて
根拠の無い前提に基づくのはもう辞めるべきだろ

「あー馬鹿がよく釣れるなぁ(・∀・)ﾆﾔﾆﾔ」とか思ってるんだろうが、

　一人で屁理屈をこねる時間 > 数人で単なる事実とくだらない煽りを書く時間

という事実に気づいているんだろうか？

>>843
お前の妄想はどうでもいいから、ソース上げてみろって。話はそれからだ。

どうせ、ほとんど'0'で、時々まれに'1'が紛れ込んでいるような
バイナリファイルを圧縮して、「おー凄く縮んだ」とか喜んでるだけだろうが。

EAC以上に実用的なCD/DA圧縮プログラムが書けるのか？

だいたいﾊﾌﾏﾝ圧縮の解説ｻﾝﾌﾟﾙでもﾃｷｽﾄの縮みが良いように8bit長なんかで書いてるから駄目なんだよ

その上の、一度ﾊﾌﾏﾝ圧縮したらﾃｷｽﾄﾃﾞｰﾀと無関係なbit長だから、
再圧縮ならｵｰﾊﾞｰﾍｯﾄﾞみたいな書き方でさぁ、しかもさも殆ど圧縮限界を達成した風な書き方

それは只そのﾌｧｲﾙｻｲｽﾞのそのﾌｧｲﾙに措ける当該ｱﾙｺﾞﾘｽﾞﾑの限界だろ

これは生粋の洗脳だ！！！騙されないぞ！！！！！

>>847
じゃ、早くその「ファイルサイズ適応型圧縮アルゴリズム選択プログラム」
だけでもいいから、ソースを晒してみろって。

ｿｰｽでもｼｮｰﾕでも上げたいがｱｯﾌﾟﾛｰﾀﾞの余白が少な過ぎる(((（ ;ﾟДﾟ)))ｶﾞｸｶﾞｸﾌﾞﾙﾌﾞﾙ


さぁー、ﾎﾟﾏｲﾗその天才ﾌﾟﾛｸﾞﾗﾏｰ振りを発揮してください

>>844
どっちもただの時間の浪費だけどな

今ﾑ板で一番熱い一番伸びてる痛いｽﾚｯｽﾞは此処ですか？

この手の詐欺師はよく現れるけど、大盛工業のIP携帯ならともかく、圧縮ネタくらい信用されないのはない。

何年か前もこの板でスレが建つような圧縮ネタ（これは海外発だった）が出たけど　結局は詐欺師ってバレて終了！

>>849
アップローダの余白が少なすぎるってどういうことよ

ttp://www.1rk.net/

>>843
> そのﾊﾟﾀﾝは偏るのか？偏らないのか？
気づかなかったでしょ？
あらゆる圧縮は何らかの偏りを仮定してるんだよ

> 理論的限界に達する究極のｱﾙｺﾞﾘｽﾞﾑがまだないから数多のｱﾙｺﾞﾘｽﾞﾑがあるだろ
気づかなかったでしょ？
圧縮されたり　圧縮されなかったり
あらゆる圧縮は　得手不得手があるんだよ

> 圧縮済みのﾌｧｲﾙですら圧縮限界からは掛け離れてる事を前提にすべきだろ
気づかなかったでしょ？
誰でもお前に言われたくないって思ってる
THCompでもだよ

> どんなﾌｧｲﾙでも一度圧縮したら殆ど理論的圧縮限界に近しいなんて
> 根拠の無い前提に基づくのはもう辞めるべきだろ
じゃぁ　さよなら
そうだよ　もう相手にされない

君が気づいてくれたのはそれだけだったね
バイバイ

こいつ、可逆圧縮と非可逆圧縮を混同しているだけじゃないかと
思えてきた。

DCTをやっている内に頭がおかしくなって、近似と変換の区別が
付かなくなってるんじゃないだろうか。

いずれにしろ、早めに精神病院に逝く事をお勧めするな。

何か考えてるみたいだな。
http://etc3.2ch.net/test/read.cgi/bobby/1129128722/153

N個の数列が、無理数の小数点以下Y位置からN桁が一致する場所を探す事とする
無理数を任意の方程式の解と考え、方程式の係数と、一致開始位置を記録する事により圧縮する。


例えば素数列Q　の平方根でもいい。

>>857
着眼点はいいな。後は実用的な速度が出るかどうかだが。

>>853
そ、その手には乗らないぞｽﾊﾟｰﾊｯｶｰめ！！(((（ ;ﾟДﾟ)))ｶﾞｸｶﾞｸﾌﾞﾙﾌﾞﾙ


>>854
これ以上縮まない理論的圧縮限界に到達したﾌｧｲﾙが偏るのか？偏らないのか？
を聞いているんだＹＯ

＞あらゆる圧縮は何らかの偏りを仮定してるんだよ、
うん、じゃあこれ以上縮まない理論的圧縮限界と仮定したﾌｧｲﾙは全く偏ってないって事だろ？

じゃあ、全く偏ってないって事はどう云う事か？

それをNbit長時の出現ﾊﾟﾀﾝの均一頻出度、均一分布と仮定するなら
ｿｰﾄすれば均一頻出度均一分布のﾃﾞｰﾀは、差分が収束するんじゃないか
って事だよ

此処でｵｰﾊﾞｰﾍｯﾄﾞを超えて縮むようなら
それはまだ理論的圧縮限界に到達してなかったって事だし

そこでｵｰﾊﾞｰﾍｯﾄﾞに到達するなら、それはｱﾙｺﾞﾘｽﾞﾑ上の理論限界だって事だろ

πには全ての数列が含まれている。　よってサイズとπの一致開始位置で表現すれば、圧縮可能か否か

>>859
ソース晒せソース(棒読み)

>>857
係数と桁数を記録する領域の方が大きくなるだろ。
ならんようにすると圧縮率が極端に悪くなりそう。

全く隔たっていないとは、検出可能な全ての手段を使って隔たっていないという事であり

では検出可能な全ての方法とは何か？
M系列乱数の一部を持ってきたように、隠れた隔たりがある可能性をどう排除するのか

と考えると、実は方法が残っているのではないかと考えてしまう。

しかし、多数のデータ列発生手段のどれかの結果であったとしても
どのデータ列発生手段かを記録するには情報量が必要であり、

結論としては、その情報を付加する事によるロスを考えて、そこそこで良いという事になる

ｷｯﾄ圧縮限界のﾌｧｲﾙってﾎﾝﾄはさり気無く偏ってるんだＹＯ

さり気無く偏ってるのにさり気無さ過ぎてどのｱﾙｺﾞﾘｽﾞﾑでもｵｰﾊﾞﾍｯﾄﾞ
どんなにｿｰﾄしても収束率が上がらずｵｰﾊﾞﾍｯﾄﾞ

つまり1/f揺らぎなんだＹＯ

んなこたぁーﾅｲ

まあ、確かに　それを吐き出すコードをEXEにすれば１Kで済む　データ列１Mを
どの圧縮ツールでも殆ど小さくならないという事はありえるだろうな

>>866は多分日本人じゃない。

LZSS辺りの最小のデコードルーチンを求めてるのですが
IA32のインストラクションで何バイトぐらいで書けそうですか？
C言語レベルでもデコード部は768バイト以下にはできたので、
アセンブラで記述すればもっと小さくなるかなって。

> πには全ての数列が含まれている。
ダウトじゃないかな。

線形合同法やM系列乱数にはNビットの0を除いた全ての値が含まれている。よって一致開始位置で表現すれば、圧縮可能か否か

まぁ、ちょっとだけ

>>859
一様分布のデータが圧縮できないことは、数学的に証明されている

数学的に証明されているのだから、手法的にどうこういっても無駄
限界を超えて圧縮できると主張するなら、元の定理の証明に誤りがあることを示しなさい(＾−＾)

一様分布に見えて、一様分布でない場合もあるんじゃないの？

たとえば、線形合同法で作った乱数列を10個毎に平均してWevファイルとして出力するプログラムがあったとする。
このプログラムのサイズが 5K 　出力サイズは 1M
このデータは一様でないので圧縮出来る。　たとえば500Kになったとする。

圧縮結果は一様であって、これをさらに圧縮する事は出来ないだろう。
しかし、元のファイルを作ったファイルはサイズ5K。
このサイズ５Kのファイルを実行するだけで復元出来てしまう。

ここは考え方を変えて
ファイルのバイナリデータを分割しファイル名にして空のファイルを作成すれば圧縮率99%の圧縮ができる

>>872
データを復元するメガデモでも作るのかね？ｗ

>>872
どうやったら一様分布でないデータが一様分布に見えますか？
馬鹿だったからってのはナシでお願いします。

>>875
　2行目以後が理解出来ないのか？

　擬似乱数列そのままが与えられたら　
　一様分布に見えるが、何サンプルがを取れば種が推定出来るだろう。つまり一様ではない。

　10個平均すれば、これは正規分布に近くなる。
　この段階でもう種を推定するのは難しくなる（情報が欠落するから）
　しかし分布は一様ではなくなった。

　これを圧縮した結果は、また一様分布に近くなる。　だから、多少圧縮出来る。


ここで作成方法を知らない第三者にこのデータを渡すと、一様分布のランダムなデータにしか見えないだろう。

結局

　擬似乱数列　⇒一方向（落とし戸）関数　

というデータ列があった場合、一様分布であっても、
作成アルゴリズムがある以上実際にはもとより短い表現が出来るわけで、これをどう理解する？

>>876
二行目が読めませんでしたか？
線形合同法で一様分布の乱数が生成されると思うのは
馬鹿以外にいるのでしょうか、と言ったんですけれど。

なんでデータに「10個平均すれば」なんて条件が付加されてるんでしょうか？
「これを圧縮する」って平均したものからどうやってもとの数字を取り出すんですか？
「作成方法を知らない」とは「馬鹿」の状態であるということが分かってますか？
圧縮限界に近づくほど一様分布に近づくために圧縮が困難になるということが分かりませんか？

>>878
　線形合同法は、一様に分布するよ。　なぜなら、結果としてそのサイズの数字を単に並べ替えているだけだからだ。　

そして、10個平均する理由は、
　・情報を欠落さる＝落とし戸効果を求めた事
　・圧縮出来るように一様分布でなく正規分布に近づけた事

だよ。

で、最後の1行は理論的には当然で常識だけど、では>>677ならどうだという事だよ。

>>879
> 　線形合同法は、一様に分布するよ。
一様に分布するといったり偏ってるといったり、一貫性がないな。
二項分布と正規分布の区別くらいつくようになってから出直してくれば？

> で、最後の1行は理論的には当然で常識だけど、では>>677ならどうだという事だよ。
８７７の「短い表現」とやらをもとの擬似乱数列に戻して見せろよ。
一方向関数を通したものをどうやって復元するのかしらんがなｗ

>>879
線形合同法って x_(n+1) = (a * x + b) (mod c) でいいんだよね?

すると、その後の10個の数列は
x_1=a^1 * x_0 + b
x_2=a^2 * x_0 + a^1*b + b
x_3=a^3 * x_0 + a^2*b + a^1*b + b
　　　　(ry)
x_10=a^10 * x_0 + a^9*b + … + b

合計すると
X=Σx_i=(a^10+a^9+ … +a)x_0 + (a^9 + 2a^8 + 3a^7 + … +10)b
ここで定数を A=(a^10+a^9+ … +a), B=(a^9 + 2a^8 + 3a^7 + … +10)b とすれば

X_(n+1) = (A * X_n + B)　(mod c)
つまり単に線形合同法のパラメータを変えただけ。

よって、10個平均した数列 X' は、
　1. 二項分布に従う 0〜9の範囲の値の c/10倍 (桁上がり)
　2. 線形合同法の 0〜c-1 の範囲の擬似乱数の十進表記での下一桁を落としたもの
以上の単純かつ分離可能な和でしかない。

>>879
線形合同法の出力は、乱数検定にかけると乱数とみなせないとなるはず

数列の任意の順列を圧縮することはできないが、
特定の条件を持った順列は圧縮できるのは明らかなわけで
線形合同法の出力を圧縮できることには何の疑問もない

>>879
> で、最後の1行は理論的には当然で常識だけど、では>>677ならどうだという事だよ。

理論では情報源が特定されすぎ（大抵、定常エルゴード）なので、
その限界なら、一様にしやすいと言える（しかも無限長で）。

実手法では、情報源も特定できていないし、情報源が異なる状況
では、その出力が一様に見えたとしても、圧縮が十分ではない変
換になってしまっていると考えられる。

そのため、実世界での性能が向上していくのは、まだまだ十分余
地がある。

>>881
　おっしゃる通りだね。
　下位ビットだけをサンプルしてゆけばある程度特徴が出てしまうかな？

??

つまり、無理数をバイナリで詰めただけのファイルでも、一般の圧縮ソフトは圧縮出来ない。
でも　πを1万桁　てな表示で圧縮出来てしまう。　
あるいは実際に計算するコードを作っても、元ファイルより小さくなる。

じゃ、これは何なんだ？　って事でしょ？

一般の圧縮ソフトが圧縮出来ないデータも、実は圧縮出来る特徴があるのではないか？
判らないだけで・・・・・と疑問が湧く・・・・人もいるわけだ。

たとえば、ノイズが録音されていると、それ以上圧縮出来ない。
でもノイズを発生した物理法則がカオスなら数式から再現出来る可能性があるんじゃないの？
というわけだ。

だからそれが乱数列に条件を加えているだけに過ぎないってことが
どうして理解できんのかな。一般に圧縮はそうやって行われてるっつーの。

そうやって不都合を指摘されるたびに話を逸らしていったところで、お前のしている
数々の間違いの原因を自分で退治していかなければ何も実を結ばないんだってば。

??

一般の圧縮ってえらいんだな。

×ノイズが録音されていると、それ以上圧縮出来ない。
ノイズであっても、振幅というかその分布によって、少しだけ圧縮できます。

新しい圧縮ｿﾌﾄが出来ます田
http://www.midl.co.jp/DLC/download_dlc_J.htm

パイとか、条件を特定しすぎ・・

圧縮の性能とは、ありとあらゆるデータをもってきたときの平均の長さを、
どれだけ小さくできるかで評価するものなわけだ

もちろん、無理数の一部だとか、M系列乱数だとか、系列の特徴を
抽出できるなら、それはそれでよいことで、
パイやルートなどの無理数の記述は、かなり短くできるだろう。
だけど、一般のデータではそれが通用しないわけだ

周波数分解やwaveletなどを考えてもらえば、わかると思う

このスレで、何でもかんでも圧縮は可能と、妄想に浸り混んでいる香具師は、
「理論的に不可能」という言葉を理解できないらしい。

「俺様が可能だと言えば可能なんだ」という世界に入り込んでしまっていて、
誰がどう言おうと訂正不可能のように見える。まさに相間の世界。
こういう香具師の頭の構造は、理系ではなく文系で、それもパラノイアが入って
いるんだろうな。

ハフマン木生成プログラム
ハフマン木の生成過程をある程度ビジュアルに確認できる


このソフトは、ハフマン木の生成過程を視覚的に見せるためのソフトウェアです。
しかし、Windows が持つツリーコントロールを使用しているため、若干見づらいかもしれません。
本ソフトウェアの機能は、
・ファイルを開き、1 byte 単位で出現回数をカウントする
・ハフマン木を生成する
・木の各ノードの情報を表示するのみです。
また、オプションで木の生成を 1 ステップ(ここでの 1 ステップとは、ノードを
1つ生成する事を言う)ごとに行うことが出来ます。

http://www.vector.co.jp/soft/win95/edu/se238266.html

-------------------------------------------------------
これで可変bit長でカウントできたら更にﾅｲｽだったのに・・・

でも(･∀･)ｲｲ！

>>894
それがどうした

>>895
触るな

ちっせぇー事言ってじゃねぇーよ

さっさと落とせよ、さっさと

>>897
お前が小さい。人の事言えた義理か（　ﾟдﾟ）、ﾍﾟｯ

いや、小さくするのが目的なんだが…

圧縮前のファイルの数列を作る数式求めてその数式を圧縮すればいいんじゃね?
うわ、俺頭良いwww

>>900
君の頭の中には、どうやらラプラスの悪魔が住み着いているようだ。

>>894
ビット単位で行う圧縮手法ならいっぱいあるので、
自分でプログラム書けばいいじゃない

そもそも今現在使われている各種の手法 Huffman, LZ77, LZ78 などなどは、
本来、アルファベットサイズは任意でよかったのだ
計算機上で実現しやすかったから、実装するときに記号単位となっただけで

論文や参考書によっては、2進数どころか3進数で書かれているものもあるぞ


>>900
その数式の記述長が、もとのデータと同程度の長さになるわけだが・・・

>>902
> その数式の記述長が、もとのデータと同程度の長さになるわけだが
ある数列に対して複数の式が対応したりすると、むしろサイズは膨らみそう。

確率で圧縮するようなやつはありますか？

>>904
あほか。氏ね

しどいわ。

THCompが最強ということで、今回の笑点はお開き

>>904
着眼点はいいと思う。つーか、俺も一度考えた。

>>904
Huffmanとか算術符号とかではなく、
次の記号が　a 1/2 b 1/2 ですよー、というような圧縮法？

それだったら、過去に1-2編論文が出ていたように思うが、
捨ててしまったのか、手持ちでは見つからなかったので、今度調べておくよ

ただ、結論としては、一意に復号可能で非瞬時な符号に含まれ、
それだったら、同等の瞬時復号符号が構築できるよ、ってなものだったと思う

へぇおもしろそうですねぇ。

シャノンの定理最強。

もしやその確率をうんぬんという手法は、
Laplace推定やKT推定、あるいはCTWのことではないか？

もっと原初に戻ってMDLモデル符号化だったりするとか？

乱数で圧縮するって誰かやってたな

>>913
俺がπや√で試した時には、100個に1個くらい小さくなったよ。
ただし、ファイルサイズが大きくなればなるほど圧縮できる確率が指数関数的に低下していく罠。

>>909
Tunstall符号のことかぁーー

>>235
π100万桁とか。

πが何桁並んでいるかを求めるプログラムにより、100万字の文字列が7文字”１000000”に、
5400万字の文字列が8文字”54000000”に圧縮される。

あくまでπの文字羅列と判っている必要があり、
πを目的の桁まで求める処理（事前に用意しておいてもいいけど）と、
その各桁が一致しているという検査が必要だけど。

（ランダムデータではないけど）非常に高圧縮率でしょ？

こんなの作ってみました。
でもあんまり小さくならない感じ。
Lcfcomp
http://www.geocities.jp/udon_hp/lcfcomp.html

http://compression.ca/act/
見て無いけど、折角だからこれと比較してみたらどうかい。

>>917-918
MaximumCompression.comのテストファイルで計測。
全体としてはあまり良い結果にはなっていませんね。
JPEGなんかは縮んでるだけで中ほどくらいにランクしてますけど(^^;

world95.txt 2,988,578 -> 2,562,986
fp.log 20,617,071 -> 16,015,141
english.dic 4,067,439 -> 3,626,157
AcroRd32.exe 3,870,784 -> 3,298,064
MSO97.dll 3,782,416 -> 3,496,360
rafale.bmp 4,149,414 -> 3,226,587
A10.jpg 842,468 -> 839,577
vcfiu.hlp 4,121,418 -> 3,483,533
ohs.doc 4,168,192 -> 3,289,340
FlashMX.pdf 4,526,946 -> 4,346,628

>>918-919
調べてくれてありがとうです。
全体としてはあんまり縮んでないですね^^;
windows xpについてる右クリック、送る、zip と比べるとmp3がまあまあ
いい感じでしたね。時々そのzipより縮んでいるファイルもありました。

πはあれとして、任意のnバイトを作るカオスとかならnが小さければ計算できるかも？
で、小さいブロックごとに圧縮とか。すげー時間がかかりそうだけど。

>>921
任意のnを生成するのは簡単だ。1ずつ数え上げるループをまわせばよい。
重要なのは、nを指定するためのパラメータの記述も考えなくてはならないということ。

Zivの固定長符号などを見てもらえばわかるように、
カオスだとか数え上げだとか、生成器にかかわらず、
エントロピーに収束することが証明できるような符号が存在する。

したがって、カオスうんうんは、πの圧縮うんぬんと同様、
きわめて狭い範囲では有効かもしれないが、一般には何ら意味がない。

>>922
そうか、だめか。

カオスうんうんって、コーンとわかめとヒジキと蒟蒻が混ざったようなアレか？

あげ

まつ

余談だが、この手の圧縮系のものは「特許だらけ」で、作るほうも
困るのでは？

うん。
だから、使う分には、zlibとかに逃げたくなる・・・。

「こういうものがあったら便利だろうな」と考えるようなものは
9割9分9厘もうすでにそれ、もしくはそれに類似したものが存在すると思え

文句をいわない嫁

オレは「1GBのファイルを1MBまで圧縮できないものか？」と
ふと考えてしまう。そんなの不可能だろうが、作れれば、どこぞの
ソフトハウスからお呼びがかかるだろうか？

全部同じデータであれば数バイトまで圧縮されるだろうね

"データは全部0な10GBのファイル。ファイル名はaaa.dat"
圧縮率一千万分の一以下。

>>933
そんなソフトがあればマジで良いよな。巨大ハードのデータが簡単に
持ち出せる。

>>934
なにかずれていないか

よく考えたらwinnyのハッシュって実用化されたTHCompそのものだよな。

>>936
それを言うならURLだって似たようなもんじゃないか

urn…いや、何でもない

音声圧縮関係について思いついた事あるんだけど、
それもここに書いていいの?

もちろん

oggよりいいアルゴリズムがあったらぜひキボン

後々考えて見るとoggの方が全然縮みそうな気がしてきた…

1.先に18〜20kHz以上の部分を音質が変化しない程度に削る
2.波形の各頂点を(x,y)の形で10進数、各桁4bitで表す
3.テキストの様に書き出したあと、zipやLHAなどで圧縮

…やっぱり縮むわけないかorz

訂正
10進数→16進数

音質が変化しない程度なんだったら、それは削ってないってことだよ。
(x,y)というのも分からんが、おそらくADPCMの方が縮むんじゃないかな。

>>942
とりあえず、普通にフーリエ変換（DCT）してレートを変えたものを比較対象としてみては？

ｱﾊﾊﾊﾊ…
思いっきり勉強不足だなこれ…
また本の山に潰されてきます
スレ汚しｽﾏｿ

各波形の頂点といっても 10KHzの成分は 44.1kだと　2サンプル毎に発生するぞ

>>946
ロスレス圧縮のまったく新規な手法は、もはや天才の発明でしかありえないほどだが、
画像音声などのロッシー圧縮では、まだまだいろいろやり方が生まれると思う。

基本をしっかり勉強すると、まずは基本手法の欠点・改善点が見えてくる。
おそらくそれはすでに他人が行っているだろうけれど、自分で理解できることが重要。
新しい論文を読んでも、そういった不備が見えてくるようなら、しめたもの。
他人の手法の改良で論文を書きつつ、新たな手法を開拓することができる。

>>948
口だけは達者だなぁ

高田純次だな

口だけじゃない。
あっちのほうも達者だ。

>>868
遅レスすまん。
15年ほど前に実行形式のプログラムが自己展開する奴を作ったことあるけど、アセンブラで116バイトだったよ。

>>747
jpegは算術符号が特許の絡みで実装できないため最終段でハフマン圧縮してるらしい。
だからゼロベタの部分はハフマン圧縮しても偏るため、再圧縮が効くときもある。

圧縮アルゴリズム考えたぞ！
まずファイルを圧縮して10分割する
一つを相手に送ってその他をCDに焼いて
郵送すれば実質圧縮ファイルの10分の1だ！
よし特許取って来よう。

応用すれば元の圧縮ファイルの100分の1や1000分の1
1000000000000000000000000分の1も可能だ！

はいはいすごすすごろくす

田中彰の応援歌を考えた。

行くぞ彰ホームラン！センターオーバーホームラン！
弾丸ライナーだ！飛ばせ！運べ！彰！

俺が考えた歌詞ですよ！
弾丸ライナーだ！の後に「ヘイ！」とか「おい！」って掛け声を入れてスタンドでジャンプするの
とかいれると面白いかもしれない。

究極の圧縮＆暗号化思いついた！



バイナリの先頭1バイト(0〜255)を鍵として、ユーザーに覚えてもらう。
それを繰り返せば0バイトになる。

よし特許。

>>958
kwsk!!

「ｋｗｓｋ」も圧縮だよなー

要するに
kuwasiku 鍵=k
→uwasiku 鍵=u
→wasiku 鍵=w
→asiku 鍵=a
→siku 鍵=s
→iku 鍵=i
→ku 鍵=k
→u 鍵=u
→

って脳で覚えてるだけじゃねーか

>>960
そりはハッシュでわ？
というかインデックス？
たまたま衝突が少ないだけ。
kwsk -> 詳しく　に１対１で戻せない。
情報が欠落してる。

なんでマジレスしてるんだ漏れ？

何そのヘブライ文字

>>962
>>961は欠落してないから圧縮なのか?

単に記憶領域を変えただけとも言う

脳が最適な状態に圧縮

脳が最適な状態に委縮

詳しく
くわしく
kuwasiku
kwsk　　　　　//uaiuの情報はどこへ…

srnnterg?>>961

>>962
JPEGが圧縮ではないそうですが、巷にあふれる言説についてコメントをどうぞ。

いやいや、このスレという有限状態において、kwskという四文字から生成しうる語句は「詳しく」となる確率が高く、ほぼ１意に復号可能と見做せるのでは？

ヒント

日本語ローマ字表記は子音と母音のセット
母音は5種類しかない
意味のある文字列の判定は誰がするか
その意味を記憶している場所はどこか

つーかＴ9

>>970
それはｋｗｓｋが、意味を持たない「記号」の羅列ではなくて、既に意味を持った「記号」となってるから。
つまりそれを解読するには「辞書」が必要。

>>973
頭文字の省略という習慣を知ってれば文脈と経験から推測できるよ。
圧縮になぞらえて言うなら、符号化方式さえ分かればおおよそ
複合可能だということだな。

おおよそでは復号されたとは言えない。
例え意味のある日本語のリストをあらかじめ辞書として全部持っていても
くわしく、けわしく、かわさき などのどれが正しいかを判定するのは不可能。

それなのに何故、記号の羅列の中にｋｗｓｋが出てきたとしても
俺らが確実に「くわしく」と読んでいるかというと
「ｋｗｓｋ＝くわしく」であってそれ以外にはありえない、という
辞書があるからであって
これは書いた人と読んだ人の辞書が違えば当然解読できない。
例えば「カワサキ」と書こうと思ってｋｗｓｋと書いても「詳しく」と読まれるだろう。
だからカワサキを圧縮することは出来ない。
つまり情報量は復号時に使われる辞書に依存すると言える。

文脈があればカワサキと書くことも読むこともできる、という意見もあるだろうが
前後の文脈というもの自体もデータなので
それも含めると情報量は増えるがサイズも増える。
なので母音抜き圧縮を辞書無しに文脈と経験で復号できると言うならば
このレスから母音だけで構成される音以外の母音を全部抜いても
次の問いに確実に正解できるはずだ。
immdnnnkikwsktittdsyu?

いままでになんかいくわしくといったでしょう？

問いは「いままでになんかいかわさこといったでしょう？」
答えは勿論0。一度も川迫なんて言ってない

>>975
>969

話ちがうが圧縮の反対でさあ。こういう掲示板で、レスに見えないデーターを
うめこむために全角空白と半角スペースを使って、

全半全　1
全全　　 0

として二進数でかきこむの。

全全半全半全全半全半全全全全全半全半全半全半全全全

これで漢字１字か……。

>>978
非可逆圧縮の場合どの程度まで情報欠落を許して
補完で元のデータとどれだけ近い状態になるか、という話になる。

母音抜き圧縮(仮)は
圧縮対象データの何十倍もの量のデータ(前後の文章)を必要とした上に
復号後に補完しても元のデータと全く違ってしまう可能性が高い。
これでは圧縮アルゴリズムとしては全く使い物にならない。

そんな可逆圧縮以上のデータ量になるのが容易に予想される
腐った非可逆圧縮は圧縮と呼ばない。ただの言葉遊びと呼ぶ。

>>975
つ 記号論

「辞書」は広辞苑とかの辞書じゃないよ。

んあ、まちげーた。

全半全　　0
全全　　　 1

だった――って、誰もこんなくすつまんねーﾚｽよまねーか。俺でもよまねーもんな　ﾐﾟ仝　ﾟ　ﾐ

>>980
「詳しく」が「詳細を教えてくれ」を意味するように、「ｋｗｓｋ」は母音抜きとかそういう問題じゃなくて、「詳しく」って意味になってるってことだろ。
だからある種の変換リストを送る側と受ける側が共有してれば、転送する情報量は少なくなるってこと。

厳密には圧縮じゃないけど、ｋｗｓｋは情報欠落してないよ。
それとも>>980は人と会話するときに、たとえば「リモコンをくれ」を言うにしても、
「赤外線で通信することによって、ある程度機械から離れたところから機器を遠隔操作できる端末をとってくれ」
とでも言わないと通じないのか？

俺は子音でなく母音を落としてるところにlossy圧縮の形が見えたな

だから俺は最初から単なる辞書だろって言ってるってば。

「辞書じゃない　経験と文脈で復号できる」と言う人が居たから
ならば君が言う通り辞書じゃないとすれば、という話をしたところ
そしたら何故かjpegの話を振られたので
ならばlossyとすれば、と話を繋げたわけだよ

ただし辞書を使えばそれは圧縮ではないわな

>>980

>>985
だって、snegとかkwskとかを知ってれば、実際に
ktkrと書いてあると、ｷﾀｺﾚのことだとわかったからなぁ。
ktkr=ｷﾀｺﾚだという辞書は判定前に持っていなかったにも
かかわらず。

ただ、これはもちろん復号先のデータに仮定をしている。
仮定の度合いが極端で、なおかつ前後の文脈で変わるのが
JPEG(JFIFか)との違いではあるが、圧縮にはデータの仮定は
つきもので、正しく復号できるとは限らないのは非可逆圧縮の常だな。

が、>975は、正しく復号できないなら圧縮じゃないと言う。
データに対する仮定をすることが辞書をもつことだと言う。
ｷﾀｺﾚを圧縮するしないにかかわらず事前に共有されている前提の
データ（=文脈と経験）のサイズをktkrのサイズに含めて問題にする。

wktk

>>987
記号論の本を1億回読んでこい。
意味は辞書と文法によって確定されるもんだ。
経験や文脈は、無意識のうちに辞書や文法に組み込まれているだけ。

基礎化

>>989
辞書と文法の話で言えばその「組み込む」ってのは
辞書の動的な生成だろ？
復号のために事前に辞書を持ってる、っていう今まで
の「辞書式だ」って話とは合わないだろ。

>>983と考えるなら事前に辞書持ってるってことに
なるけどな。

>>1
このスレを圧縮してください。

お前はアホ？
相手が全く同一のコードを共有しているわけじゃないのになぜ話が通じるか説明してみな。

>>991

事前に「リモコン」という言葉を辞書に持ってる。
動的に生成されるか否かは関係ない。

↓
↓
↓

↓


↓



↓




↓

工学土方に、言語学や哲学の概念は理解できません＞＜

ｋｓｋ

突然ですが農村の過疎化について語るスレとなりました

>>993
通じないこともあるんだよ。馬鹿？

>>994
動的か否かが関係なかったら>985の「辞書じゃなかったら」
なんて仮定が出てくるはずもない。文脈嫁。

ﾃﾗｶﾜｲｿｽ

このスレッドは１０００を超えました。
もう書けないので、新しいスレッドを立ててくださいです。。。