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

このエントリーをはてなブックマークに追加
1謎のばか
まぁ見てください。

数字列:92,95,21,86,32,65
1.まず、一個飛ばしのデータを並べていく。
  92,21,32,95,86,65
2.隣同士を比較して大きいほうが小さいほうの3倍より
  大きいとき(大きい方 ー 小さいほう)をする。
  71,21,32,95,86,65
  ここで数字を引くことができれば1に戻って繰り返す。
  これ自体圧縮しませんが、文字列を偏らせる効果があります。

しかしこのままだと、一回引いた数字が、
それ以上引けない数字になったとき、復元の時にばぐるんです。
やっぱりシャノンのいってることが正しいのかな。
理解できるかどうかわかりませんが、みてください。

ttp://www.h4.dion.ne.jp/~pc-pow/test.lzh
2 ◆vp/58lzmEY :03/01/06 07:27
40分も過ぎてるのに2get

先生、質問です
>数字列:92,95,21,86,32,65
て書いてるけど、数字列じゃ無いときはどうするの?
1バイトが0-255と考えればオケ。
4 ◆vp/58lzmEY :03/01/06 07:42
>>3
なるほど、それでunsigned charなわけですね
最終的な計算としては、数字列が大きい順に並ぶと・・・
でも、そーすると、先生の1個飛ばし手法では2バイト文字(全角)では
意味不明な並びになるんじゃ・・・
5 ◆vp/58lzmEY :03/01/06 07:45
コンパイルしたら、文句言われました
warning C4101: 'i' : ローカル変数は 1 度も使われません。
main()で宣言したiを使ってないって怒られましたけど・・・・
6デフォルトの名無しさん:03/01/06 07:56
大きい方 ー 小さいほう をした後に復元できないだろ.
必要な情報が失われてるから シャノンの定理を越えて圧縮(?)できるけど,
情報が失われてるから復元できない.
どこを引き算したか覚えておけば復元可能だけど,その情報の分が増えるので
シャノンの定理の通りになる.
7 ◆vp/58lzmEY :03/01/06 08:02
プログラマーってすごく頭いいんですね
シャノンの定理ってはじめて聞いたけど、しらべたら難しくて・・・
シグマとか対数関数とか・・・頭痛い(^.^;
8謎のばか:03/01/06 08:03
>>5
ちょいバグってるぎみ
自分で治して。
9謎のばか:03/01/06 08:05
この方法で音楽などをエンコードしてLZHなんかで圧縮してみ。
Nの値を増やせば時間かかるけど、値が偏りやすい。
メモ帳で開いたらわかるのね。
>>9
デコードできなきゃ意味なし。
11謎のばか:03/01/06 08:10
>>10
だからデコードできるようにしてほしいンダヨ
完成したら俺が特許取るから早く作れよな。
13謎のばか:03/01/06 08:15
わしはこれでいーしゅうかん悩んだ;;
>>11
デコードできるようにしたら値の偏りがなくなるけど。
15謎のばか:03/01/06 08:18
>11
??デコードでもとのデータ列に直すのよ。
>>12
2ch で「公知」されてるから無理じゃないのか?
ま、 >>1 のでは使い物にならんので >>12 が自力で完成させれば特許取れると思うけど。
その手の不可逆圧縮(?)だったら
del file とか rm file とかした方が速くて圧縮率(?)も高い、と。
18謎のばか:03/01/06 08:26
もうひとつ同じ大きさのバッファを作って、
すでに引いたなら、そのバッファに1を入れる。
後はこれを圧縮して(huff or range etc.)書き込む。
これどうよ。
19sage:03/01/06 08:27
並び変えは可逆なんだから, 引き算した場所をどうにかして記憶しとけばいいんでしょ.
毎回の引き算した場所のインデックスをヘッダに0区切りで覚えておくとかは?
あと、大抵の可逆圧縮は値が近いだけではダメで同じでないと圧縮できないので、
そんなに圧縮率は期待できないのでは? まぁ数値が近ければ同じ値になる確立も
上がるだろうけど。
それなら文字列よりも画像とか、連続的なデータで不可逆でもいいやつの方が効くんじゃないのかな。
DCTとか。
20謎のばか:03/01/06 08:28
>>17
不可逆圧縮なんていわれた。(;o;)
21謎のばか:03/01/06 08:30
>>19
大体復元できればいいってこと?
もうひとつ同じ大きさのバッファを作ったら容量が2倍だろ。
23謎のばか:03/01/06 08:31
だから、0と1のデータだから圧縮したら何とかなる?
そんなこといったらパソコンの中身は全部0と1です。
1バイトのデータに0と1しか入っていなければ圧縮できるけど、
そんなことする前に1ビットごとに0と1を入れておいたほうが容量は小さい。
それに同じ大きさのバッファに0と1を入れておいても、並び替えをしてるから、
どのタイミングで引き算をしたかわからないので、それだけはダメで、
一つの考えとしては 適当な数値を入れておいてデコードで並び替えるたびに
デクリメントして1になったら引き算のデコード(足し算)を行う。 とかいうように
すればできそうだけど、そしたらやっぱり容量が2倍です。
結論が見えた議論をしているスレはここですか?
結論は秘密ですか?
27謎のばか:03/01/06 08:46
とにかくデコードできればいいの
28&rlo;&lro;:03/01/06 08:48
もうだめぽ
29謎のばか:03/01/06 08:49
そんなこたーない
いちおうデコードできるとこまではいった。
30&rlo; &lro;:03/01/06 08:52
じゃ、かんせい
31謎のばか:03/01/06 08:53
それだと200倍ぐらいになっちゃう
おめでとう
33謎のばか:03/01/06 08:56
よし。
これでVectorにだすか
ばかも休み休みにYEAH!!
35謎のばか:03/01/06 08:59
あっ
限界のところで

out[i] += out[i + 1];

out[i + 1] += out[i];

どじゃ?
>>33
小学生〜中学生の冬休みの自由研究課題(あるのか?)だったら
それなりに評価してもらえると思われ。
37デフォルトの名無しさん:03/01/06 09:05
ごめん。関係ないけど歌丸さん危篤。
http://tv3.2ch.net/test/read.cgi/geinin/1041566708/7
まじかよ歌さん。。。
39謎のばか:03/01/06 12:37
はぁこのすれも終わりに近づいてきたなー。
40デフォルトの名無しさん:03/01/06 18:33
このスレが1000逝くまで歌さん逝かないでくれ・・・・
41デフォルトの名無しさん:03/01/06 22:28
1000 いく前にこのスレが dat 落ちしたら
歌丸さんは死なないのかもしれない。いつまでも
一度でイイから見てみたい。コドモのマンコ
>>37
こんな所にまで貼られてたとは
44デフォルトの名無しさん:03/01/07 00:21
【<芸能>歌丸 急性腹膜炎で手術】
 人気落語家で落語芸術協会副会長の桂歌丸=本名・椎名巌さん=が急性腹膜
炎のため横浜市内の自宅から救急車で同市内の病院に運ばれ、27日、4時間半
に及ぶ手術を受けた。手術は成功した。入院のため、元日からの東京・新宿の
末広亭などの初席から、約1カ月間休演する。一時は病名が定かでなかったた
め、危篤説も流れたが、28日には、一般病棟に移されるなど手術後の経過も順
調。関係者は一様にほっとしている。
>>42
子供作れ。
俺は毎日見てるぞ。
>>44
本当にほっとした。
よかったよかった。
>>45
毎日オムツ換えさせられてるとか?
>>47
むしろ率先してやってる。
>>47
風呂はいる時見る
んー。2ch圧縮アルゴスレは埋め立てられたか…。

>>1で述べてるのは「フィルタ」であって
まあ圧縮のための前処理よね。この場合は元の情報源より
変換後の情報量が増加するのは、可逆圧縮用途であればむしろ普通。
減った場合はエントロピー破壊を起こしたことに…。

正直、シャノンファノ理論とは関係ない。(情報源のモデル化適用をしてないし)

で。この減算フィルターは現状では正常デコードのしようがない罠。
「すべての桁について減算を行った」のなら、復元時に
「すべての桁について加算を行う」ことで復元できる。(WAVE-sub フィルタとかがそう)
ところが、引けるときだけしか引いてないので、
“引いたのか引いてないのか”の情報が欠落してると復元できない。

#変換後の値が「2:1」の場合、それがもともと「2:1」で減算しなかったのか、
#「3:1」の減算結果なのか、デコーダが判断する基準が欠けている。

そうすると少なくとも8バイトに付き8ビットのフラグが必要になる勘定だから、
ブロックソート(8バイト時3ビット)に比べれば、実現できても能率は相当落ちると思う。
この変換だったら、すなおにwavelet変換したほうが効率がよいと思うが。
アルゴリズムも似ているしよ。
>んー。2ch圧縮アルゴスレは埋め立てられたか…。

このスレで、継続していきやしょう。
53IP記録実験:03/01/08 21:42
IP記録実験
http://qb.2ch.net/test/read.cgi/accuse/1042013605/

1 名前:ひろゆき ◆3SHRUNYAXA @どうやら管理人 ★ 投稿日:03/01/08 17:13 ID:???
そんなわけで、qbサーバでIPの記録実験をはじめましたー。

27 名前:心得をよく読みましょう 投稿日:03/01/08 17:20 ID:yL/kYdMc
SETTING.TXT管轄でないということは全鯖導入を視野に、か?

38 名前:ひろゆき ◆3SHRUNYAXA 投稿日:03/01/08 17:22 ID:rLfxQ17l
>>27
鋭いです。

73 名前:ひろゆき ◆3SHRUNYAXA 投稿日:03/01/08 17:27 ID:rLfxQ17l
>ところで、IPが抜かれて何か今までと変わることってあるのでしょうか?
・今までより、サーバが重くなる。
・裁判所や警察からの照会があった場合にはIPを提出することがある。
>>638
こらっ!しんのすけ。
悪いこと書かないから関係ないよ
======2==C==H======================================================

         2ちゃんねるのお勧めな話題と
     ネットでの面白い出来事を配送したいと思ってます。。。

===============================読者数: 138720人 発行日:2003/1/9

年末年始ボケがそろそろ収まり始めた今日このごろのひろゆきです。

そんなわけで、年末に予告したIP記録ですが実験を開始しています。

「2ちゃんねる20030107」
こんな感じで各掲示板の最下部に日付が入ってるんですが、
20030107以降になってるところはログ記録実験中ですー。

んじゃ!

────────────────────────Age2ch─
■この書き込みは、Age2chを使って配信されています。
────────────────────────────
Keep your thread alive !
http://pc3.2ch.net/test/read.cgi/software/1041952901/l50
────────────────────────────
結論は秘密ですか?
データを推理で復元できないのだろうか?
>>58
予測復号って奴ですかい(^^;
「脳内補完」とか「錯覚」という人間自身の
予測を利用したのがJPEGやらMP3なんだけどね…。

ある程度の予測と補完は、選択したモデル化次第で
可逆圧縮でも可能だろうけれど、でもEXEファイルを
圧縮/復号した結果、正常実行可能かどうかの保証は難しいだろうな。

単に「次にくるある文字の確率が“おそらく”高いのならば、
その文字の符号語長を短縮するよう計らう」っていう観点でなら、
適応的ハフマン/算術圧縮の類でいくつかが実現されている。

60デフォルトの名無しさん:03/01/09 21:04
>>58
マルコフモデルだろ?
http://member.nifty.ne.jp/DO/algorithm/ppm.htm
<余談>
日本語の「予測」は、英語だと prediction で、「予測、予想、予言」となるのがちょっと面白い?
</余談>

予測に失敗した場合のダメージを考慮しないといけないからつらいね。
推理して(すなわち補間して?)穴埋めしても、それが間違った方向なら、
無歪みでは、
 符号化時の予測失敗は、そのままビット長の増大
 復号時の失敗は、回復不可能な無限大のダメージ
有歪みでも、
 ビット長の増大・ノイズの増加、のどちらかが起こりうる。
>日本語の「予測」は、英語だと prediction で、「予測、予想、予言」となる
ならねえよ
語源がちげえのにマップするわけねーだろ
2ch板一覧
 http://www.skipup.com/~niwatori/keijiban.htm

>728 ( ´∀`)σ)Д`) プニ
>>62
すまないが、ならない理由を教えてもらえないか?
データ圧縮で次の記号を予測することを prediction ということには間違いないのだが。
571の言いたい事が分からないので、もっと詳しく       
65は話題の人工無能かとおもてしまた。
レス番号が頓珍漢だが、突っ込みが的確だw
>>65
むしろ懐かしさすら覚えるよ。
>>65
むしろ懐かしさすら覚えるよ。
>>68
ちがうっつーの。あんな出鱈目坊と一緒にしないでくれ。
(★∀`)y─┛~~~~~2ちゃんなくなったらマスコミに対抗する手段がなくなる
>>91-92
読んでみた。
前半は難解だったけど最後まで読んだら
ネットについての理解が格段に深まった。
ありがとう。

他の人も、煽ってばかりじゃなくて
一度読んでみるといいと思う。
まあ、永遠に続くものでもないしな

ログイン出来ないんですか…?

黒星でいいか?
警察、裁判所の世話になる書き込みをしなきゃいいだけの話だろ
IP記録する事で基地外の書き込みが減るだろうから、なにも困る事はないだろう?
全鯖に入ったぞ。
http://qb.2ch.net/test/read.cgi/accuse/1042131034/312
2ちゃん史にまた1ページ加えられた。
匿名じゃなくなったら2ちゃんねるはただの掲示板じゃないの?
魅力がなくなる ->> 閉鎖
ってことにならなければよいが
勉強。
>>77
Windows に魅力が無くても MS は閉鎖しない。
匿名性のメリットはそういう点でなく、
「双方向目安箱」だと思うよ。

小泉が一般人の振りして2chで議論
これも匿名だから可能だろ?

実際に小泉がやったか知らないが…
======2==C==H======================================================

         2ちゃんねるのお勧めな話題と
     ネットでの面白い出来事を配送したいと思ってます。。。

===============================読者数: 139038人 発行日:2003/1/10

なにやら、連日メルマガだしてるひろゆきです。

そんなわけで、ログ記録実験ですが、いちいちサーバ指定するのが面倒なので、
全部のサーバに入れてみました。

重くなって落ちたりしてもご愛嬌ってことで。。。

んじゃ!

────────────────────────Age2ch─
■この書き込みは、Age2chを使って配信されています。
────────────────────────────
Keep your thread alive !
http://pc3.2ch.net/test/read.cgi/software/1041952901/l50
────────────────────────────
売られても文句は言えない。
●を買った人間は金払って2chを利用してるワケだが、
●買った人間のみID出なくなるとか、サービスありゃいいのにな。
夜勤さんはシアトル産の鯖を北海道で代理販売してるんじゃなかったっけ。
これで同人板の誹謗中傷さんも消えるでしょう
同人板の連中に潰されていった作家、サイト、関係者もさぞ浮かばれることでしょう。
アタックって2ch鯖にか?意味不明
>>85
今までは仮にハックしても誰にもバレなかったの。
証拠になるログを誤魔化す必要さえなかったし。
IPって何ですか?
漏らすバカが出るだろうというのが一番の問題なんだよ
(・∀・)チューボーですよ!
ねぇ、6億超えちゃったんだし
どこで見えるのか教えてちょーだいよ。
>今後期待できるのは、裁判例をイパーイつくってくれることくらい

そうなるでしょ。おそらくは。今後の掲示板・コミュニティ運営は
2ちゃんの失敗を参考にしてなされるでしょう。
2ちゃん自体はゆっくりと氏んで逝く。管理者が西村から山本に
変わったからと言ってどうなるものでもない。
隊長が後処理の総責任者になるんじゃない?ひろゆきはそのうち
刑事罰喰らってもおかしくないし。
IPアドレスは番号みたいなもの。
ホストは、住所みたいなもの。
IPは郵便番号みたいなもの。
両方ばれるとヤバイネ!!
つうか(^_^;)本体のレス見てないのかな?w

542 名前:マァヴ ◆jxAYUMI09s 投稿日:03/01/12 02:22 ID:kxpim/a2
いやさ(^_^;)ここでプチ法廷ごっこやっても
しょせん机上の空論だよ?
実際争点となったっていうか、法理的に詰まった点とかけはなれてるもん・・・。

ぉぃぉぃ(^_^;)
95山崎渉:03/01/13 18:56
(^^)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
---【関係者は読んでおけ。話はそれからだ。】---
http://teri.2ch.net/accuse/kako/988/988866718.html
706 名前: 19@悲惨認定らしい 投稿日: 2001/05/07(月) 18:59 ID:???
2ch擁護論者も不用論者も、時間かけてでもこのスレ読むといいぞ。
ネット倫理の理解が格段に深まる。
★★日本生命事案に見る、掲示板の削除義務★★
http://cocoa.2ch.net/hoken/kako/987/987605232.html
2ch以外も含めて、俺が見たなかで最高のスレだ。
-----
これをまとめたらしいのが
http://www.geocities.co.jp/Technopolis-Mars/6820/hoken/

裁判に勝った動物病院には、裁判の前に俺が電話で
↑のURLを教えてあげておいたのさ。
判決も↑の内容にある程度沿った内容だったしな。
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
97山崎渉:03/01/15 18:10
(^^)
プッ
99山崎渉:03/01/23 21:58
(^^)
100100 get:03/01/24 11:15
>>50
過去ログ倉庫に入ってますよ
【2ch】圧縮アルゴリズム【オリジナル】
http://pc3.2ch.net/tech/kako/1028/10285/1028570486.html
101デフォルトの名無しさん:03/02/06 01:45
>>100
パート2って無いの?【2ch】圧縮アルゴリズム【オリジナル】
の。
>>101
このスレも、タイトルだけ見たら同じに見えるから。
【2ch】圧縮アルゴリズム【オリジナル】の続きってことで再利用。

BPEに関してなのですが、
最高頻度ペアを1度も出現していない記号に置き換えるのではなく、
最高頻度ペアと最低頻度記号を交換するタイプって既にあるでしょうか?

ababcab ⇒ ccabc (ab⇔c)

となります。
あんたがったタフマン
105103:03/02/10 14:08
尚、>>103を単純に実装すると復元できないパターンが出現します。

cabaaaac ⇒ caaabbc (aa⇔b)

などがその例ですが、回避は低コストです。

また、最低頻度記号すべてを最高頻度ペアに変換する必要はありません。
変換する記号の1つ前の記号の偏りを利用して最小限に押さえます。
age
107デフォルトの名無しさん:03/02/23 00:20
>>105
スレ活性化の為にも
回避策おせーて!
BPE自体オリジナリティ感じないから、それを
アレンジしても、いまいち感はぬぐえないな

BPEは、さっきググって知ったばかりだけど
>>108
最頻digram圧縮 と呼ばれることもあるから、それで調べてみ。
とはいっても手法としてはいまいちって感じだけど。
その系統のほとんどの論文は、理論的な方面での興味が中心なので。
110デフォルトの名無しさん:03/03/14 17:38
あげますた
>>109
実用上でもLZと遜色無い程度の圧縮率は得られそうだけど、どうよ?
>>112
LZ法などという、すでに過去のものとの比較はやめようよ。
圧縮前のデータの正規化か
プログラムのコードって割と正規化しやすいんじゃないかな
.exeの圧縮って圧縮率稼げそうな漢字
>>114
LZEXE とか DIET とか、MS-DOSの時代にあったね。
それに rk も exe に特化した圧縮あるし。
Java のバイナリコード専用の圧縮ソフトもあるし。
論文も結構あるしね。

・・・つまり、参入の余地は少ないってこった・・・
>>115
普及率から考えて、7-Zip、WinRARが最大のライバルかと
117114:03/03/16 12:13
>>115
(´・ω・`)
データ圧縮はすでに90年頃から、すでに終わった分野だと言われているよね。
94年にブロックソート法が考案されたおかげで、多少息を吹き返したが。
今、研究や論文でも純粋なデータ圧縮はごくまれで、しかもデータ圧縮といっても、
マイナーな手法の改良とか、理論的・実践的に偏りすぎているものとか。
いまだに最適なものが見つかっていない通信路符号化と違って、
用意に最適な符号を構成できる情報源符号化の未来は、あまり広くない。
もしこれから誰かがすばらしい手法を発見したとしても、
ブロックソート同様、数年のうちに何千という論文が巻き起こり、結局、それで終わり。

むぅ。
>>118
でも、実装に関してはまだまだ改良の余地があるんじゃないかな?
特にPPMやLZは余地が大きそう。
(゚∀゚)でもなんていうか
データの種類でやっぱ最適解って違うっていうか
画像ファイルと音楽ファイルとじゃ適した圧縮形式違うというか
そういう感じで今後もほそぼそと進歩していくんじゃないかと
思ったりするわけで
話し違うけど、MIDIなんかある意味圧縮だと考えてもいいわけで
そいうアプローチもアリかなぁと思ったり思わなかったり
121デフォルトの名無しさん:03/03/16 19:19
なんでみんなsageるの?
もっと昔から終った終ったと言われながら発展しているのがこの分野の特徴ではないかな >>118
今後もBSみたいなのが散発的に発明され発展していくものと思われ
基本的に sage 進行の板だから。

>>120
表現形式と圧縮とは違うと思うけど。
その立場だと URL は圧縮論やアカシックレコード論と同じになる。
123デフォルトの名無しさん:03/03/17 01:03
sage進行という弱い考えに反逆する!

>>122
でも、そういうアプローチの非可逆圧縮ってあってもいいと思わない?
別に age sage は個人の好きでいいと思うよ。

だからそれを認めると、文書要約も検索エンジンの結果も圧縮ということになる。
>>124
そうですね。
圧縮技術を検索技術に活かす、あるいは統合できても、
圧縮そのものの研究・開発としては対象ではないという。
解凍結果が「似たようなもんでいい」っていうレベルの
圧縮技術だったら なんか適当な計算式で近似してみる
っていうのもありかなー、とかいう話だね
FM音源の音色データなんかも圧縮と言えなくも無いかもしれないかも
127デフォルトの名無しさん:03/03/23 03:08
BPEは圧縮が遅いのと圧縮率がたいしたことない(それでもAveで50%以下にはなる)のが
問題かな。展開は早いんで、展開時間を重視する用途には向いていると思われ。
圧縮時間を犠牲にできるならBPE + α(LZHみたいに)といった、2通りのアルゴリズムを
併用すると効果があるかもしれない。ちなみに個人的に面白いと思ったのは画像形式の
.MAG(古いな)のフラグ圧縮。「圧縮できないという情報」を圧縮するというのは面白いと
思った。
それで思い出したけど、PIC形式(懐かしいな)って
アルゴリズムを解説してるサイトある?
>>127
LZSS+Huffman の LZH, gzip は圧縮できないフラグを圧縮しているといえる?

圧縮時間が大きく展開が速いのは LZ77 系や文法圧縮法の特徴で、
LZB (だったような?)法は、かなりいけてます。
>>129
単純BPEの展開はLZ系と比べても爆速です。だって単なるスタック構造で、配列を見ながら
最終バイトペアまで分解して(配列サーチは高速)あとはポップしていくだけなんで。
BPEのいいところは、LZ系の圧縮率に近く、なおかつ展開速度が速く、消費メモリも少ないと
いうこと。用途によってはLZよりいいはず(たとえばコンシューマゲーム機でバックグラウンド
でCD読みつつ展開して使うような場合)。
>>130
ただのLZのほうが遥かに速いです。オフセットからのmemcpyだけで、余分な「消費メモリも0です。
>余分な「消費メモリも0です。
そーかな?
>>131
いや、ビットストリームを扱わないのがBPEの最大の利点なわけで。
ちょっと間違い。ビットストリームじゃなくてビットアクセス。全部バイトで
処理できるから軽いです>BPE
135デフォルトの名無しさん:03/03/23 11:54
レスを読んでないのだが、>>1の言ってることは、

「データを1バイトおきに読み飛ばして圧縮したぞ。
あとは復号する方法を考えてくれ。」

って言ってるようなもんだよね。
136デフォルトの名無しさん:03/03/23 12:02
↓↓ アダルトDVDが今ならなんと!一枚900円! ↓↓
    http://www.net-de-dvd.com/
↓↓ 特売品は、なんと一枚600円!! ↓↓
    http://www.net-de-dvd.com/
↓↓ 数に限りあり!早いもの勝ち。急げ ↓ ↓
    http://www.net-de-dvd.com/
>>134
全部バイトアクセスのLZもあるのですが。
BPEとLZ77の最大の違いは、

・圧縮したまま検索する手法が有効か(BPE)、無効か(LZ77)

ということだ!
>>138
BPEはLZ78系では?
LZ系は動的辞書なのに対し、BPEの書換えペアは静的辞書とみなせる
「LZ系」でくくると語弊ありそうなんだが…。
ほんとに“動的辞書”を使ってるのはLZ78系列ですぜ。
情報源をモデル化する過程で動的に辞書を構築する、という意味。
LZ77系列のは“スライド辞書”あるいは“移動窓”言いますが、
これはどっちかって言うと静的な(単なるFIFOバッファな)辞書なん。
BPEの“圧縮したまま検索する手法が有効”ってのもちょっと微妙。
これはBPE法が“純然たるユニバーサル符号化”ではなくて、
情報源を少量のブロックに分割しながら出ないと圧縮できないことを逆手にとって、
ブロック単位で途中からや後方からでも、任意位置の展開ができることを利用する。
余談だけどBPEと同種の考え方をユニバーサル符号化したアルゴリズムについては
→ ttp://localhost/techniqueroom/dca-6-5.html (まだ未完成なコンテンツらしいが)
142デフォルトの名無しさん:03/03/25 05:50
localhostを出されてもかなり困るわけですが
>>141
とっとと完成させて公開してね。
144デフォルトの名無しさん:03/03/25 06:19
○○○○ こんな電波はありませんか? ○○○○

荒らしなどのコピペで、厨房、工房、消防、
このような人たちをコピペで煽りを行えるコピペは無いでしょうか。
出来れば制限時間内に5レスくらい返ってくる、みたいな含蓄のあるもの。
出来ればレベルの高いものをお願いします。
荒らしと書きましたが、形式は全く問わないです。
著作権、版権も問わないです。

お願いします。
>>128
初期の頃の電脳倶楽部に載ってた様な。
>>145
あとOh!Xの1990年2月号に詳しくのっている。
ほかにもCで書かれたpicローダが巷に結構あるから参考になるかな。
>>141
ttp://multix.jp/techniqueroom/dca-6-5.html
ここですね(さらし目的じゃないです)
>>147
ユニバーサル圧縮法って書いているけど、どこにも証明がないような。
この人が考えたオリジナルの手法だよね?
多分容易に証明できるのだろうけど、それなしにユニバーサルを名乗っちゃだめだろ。
commpression
の綴りが間違ってるからじゃないのか。
PPMを「非主流のマニア向け」などと評しているところが、いやんな感じ。
PPMは今や、XML, DNA, テキストマイニング, 検索, データベース,
などの圧縮での応用で、トップクラスの利用頻度を誇っているわけでして。

あと、エントロピーという語を乱用しているような気がして、さらにいやん。
>>141
どうでもいいですが、ジサクジエン失敗ですか?
圧縮後でもパターンを作れれれば圧縮できますよね?
無秩序状態を崩すための暗号化とか無いんでしょうか。
符号に偏りが生じるようでは暗号化としてダメダメです。
まあそうなんですが、例えばコードを+1,+2,+3...+255と
順番に足していって運任せで崩すようなそんな感じの物です。
>圧縮後でもパターンを作れれれば圧縮できますよね?

つかすでに、世の中の圧縮研究者は、
そのパターンが存在すれば存在しないで済む、あるいはさせない方法を考えている。
たとえばLZ77法のポインタ表現は、かなりの無駄が生じるので、
それをエントロピー符号化するだけでも、さらに縮まる。

暗号の方は、言っていることがいまいちわからん。
>>154
ランダムな数列でも適当に加工することで、圧縮できるようにするということだと思いますが、
それがどのパターンであるかを符号化した分で、圧縮できる分は帳消しになるか肥大化します。
つまり無意味です。
>それがどのパターンであるかを符号化した分で
これを記録しないってのはどうよ?
複合化されたバイト列が大体正しい事を証明する(256bitのハッシュでも)情報を記録しておいて、
符号を解読していくの。
>>157
その場合、圧縮できる分が256bitより少ない方が圧倒的に多いのです。
適当にモデルを作って、パターンやハッシュが何通りあるか考えればわかると思います。
いや、だからパターンは記録しないんだよ。
手がかりのないところから暗号を解読するような感じ
勿論、復元できないファイルも出てくるだろうが、
それは気にしないことにする。

GUIDでも絶対に重複しないって言われてるんだから、
256bitのハッシュが有れば復元のヒントになるんじゃないかと。
>>159
何だか直感だけの気がするので、どうするとそんなことができるのか、もう少し根拠が欲しい所ですね。
また、復元できないでもいいというのはメリットがよくわかりません。
>>159
あと、私が158で書いているのはパターンではなく、256bitのハッシュ値を記録することです。
その分すらも圧縮できないということです。
最強の圧縮

MD5ハッシュ→(p2pワールド)→元ファイル

全てのファイルを16byteに圧縮できます。
>>162
アカシックレコードとそのインデックスみたいなものですね。
だからそれは(ry
>>162
Winnyの同一ハッシュな偽者が出回って問題になったことがあるのだが。
>>165
それはWinnyのキャッシュがMD5ハッシュになる以前の話なわけだが
突っ込むならそれくらいちゃんと調べてから書いてくれよ
つーかその事件が起きたからこそハッシュをMD5に変更したわけで
>>164
実際に運用可能な点が今までの机上の空論的
アカシックレコード圧縮と違う点だな
169165:03/03/27 11:32
>>166
要は1/65536なんかあてにならないといいたいのだが。
(ビットを増やしてもハッシュ値が同一になることがありえることに変わりはないし)
>>169
> 1/65536
小学校から算数やり直せ
>>165は意図的に同一ハッシュを作れるという話でぜんぜん
適切な例じゃないし。
MD5があてにならないなら現在の暗号化システムは全滅なわけだが
MD5で圧縮というのは、典型系列を圧縮するという問題そのままじゃないか?
MD5に長さ情報が入っているかどうかしらないが、
入っているならば一部手を加えて、ほとんどそのままユニバーサル符号だし、
もし入っていないならばさらに log n ビット追加するだけでユニバーサル符号になる。
↓別のネタおながいします。
・まずビットで見たときの0の個数を記録する
・次にそのデータが何番目に来るのかを記録する

たとえば 010 を符号化する場合、0が2個という情報をまず符号化する。
次に、0が2個であるすべての集合から010が辞書順で何番目に来るか、
つまり、001, 010, 100 の2番目なので2を符号化する。
それはインデクシングじゃないかい。
176デフォルトの名無しさん:03/03/28 18:19
ファイルを0バイトに圧縮するプログラムを作りました。
http://www.geocities.co.jp/Playtown-Denei/1184/satoimo/
177デフォルトの名無しさん:03/03/29 00:06
上のプログラム検証する勇者はいないのか?
178デフォルトの名無しさん:03/03/29 00:15
ふとん圧縮機のアルゴリズム誰か解明すれ!
>>178
ランレングス方式みたいものを想像してください。
布団はその性質上空気を多く含んでいるので
布団の成分を 1 、空気を 0 とすると、
10000000000000000010000000000001000001000000001000000000000000000001
このようにあらわせます。
そこで、ゼロの数のみ表記すると
11 0C 05 08 14
となります。
実際にはゼロの数(空気の割合)というのはもっと膨大なので
圧縮率は上に挙げた例よりも大きくなります。
>>176
まぁ確かに圧縮したら0バイトになるし可逆圧縮だけど、
間違いなくこれを考えた>>176はホゲ。
>>180
これってNTFSのストリーム?
182デフォルトの名無しさん:03/03/29 12:36
これって容量制限のある鯖にageた時、どういう扱いになるんかな?
183デフォルトの名無しさん:03/03/29 14:32
ロジックパズルみたいに出来ないかなー
184デフォルトの名無しさん:03/03/29 14:35
>>176
賢いやつだな!久々に感心したよ!
185デフォルトの名無しさん:03/03/29 16:59
>>182
試してみたよ。容量にカウントされなかったでつ。
おいこれって意外と使えるんじゃないか!
>>185
調子に乗って使いつづけていると、あとでしわ寄せが来る罠。
アングラ系で流行るかも
>176
面白そうだったのでやってみた
FAT16(Win98SE)でも問題無し
圧縮って言うか隠蔽向き

あぁ,本当にこれやるヤシいるんだな...
189里芋:03/03/29 22:50
自分のマシンで実行する勇者がいるとはさすが2chですな…

>>188
FAT16 は1ディレクトリに最大 65534 ファイルまでしか作れないと思うんで、
あまりデカいファイルの0バイト化はできないと思われ。
容量制限されてる無料鯖を鯖が許す限り使えるの?
>>190
サーバがNTFSならな
192里芋:03/03/30 02:06
>>191
今日日の公開されてる鯖はLinuxとかなんで、
ファイルシステムは ext2 とかだから問題ないでしょう。
>>189
でかいファイルの時はさらに深くディレクトリ掘ればできるだろ。
194デフォルトの名無しさん:03/03/31 01:42
age
195デフォルトの名無しさん:03/03/31 01:52
見た目サイズが0になるだけなの?
>>176
今のうちに特許取っとけ
>>195
ファイルのデータがあって、それを強引にサイズ0になるようにOSをだましてるとか、そういうのはないと思うよ。
漏れは怖くてためしてないが。
実際にファイルサイズが0のはず。
5MB->0バイトにしたファイル(フォルダ)をzipしたら20MBになりますた
>>198
それは言わない約束です。( ̄ー ̄)ニヤリ
いやーワラタw
201デフォルトの名無しさん:03/03/31 21:14
>>176は神!
前どっかで>>176の逆みたいなやつあったな。
フォルダの中にそのフォルダがあって(再帰みたく)、
容量がテラとか普通にいってた。
ディレクトリエントリ自体はどんどん増えるので、
unixでもquotaにはひっかかるんじゃないかな?
quotaってディレクトリの大きさって数えないっけか
204里芋:03/04/01 02:36
>>193
できるけどFATのためにそれ作るのめんどくさい。

>>198
zipとかlzhはフルパスを無圧縮で持ってるから増えて当然。

>>203
unix の場合は inode の数までならファイル作れると思う。
でも、アタックと間違えられるかも…
205デフォルトの名無しさん:03/04/02 11:39
遅レスだが。
>>24
最小単位だバイトだと信じているアフォ。
>>205
別に最小単位がバイトだと言ってるわけでもないし
バイトじゃなくてワードでも同じじゃないの?
アフォかどうかはおいといて。
207デフォルトの名無しさん:03/04/02 13:32
>>176
これ冗談じゃなくてほんとに実用に使えるよ。パスワードとか大事な暗証番号をこれで変換してどっか深いフォルダに入れれば、どんな検索かけてもまず発見されないと思う。
今のうちに特許取っとこうよ!
208デフォルトの名無しさん:03/04/02 13:38
少なくともUNISYSのGIFアルゴリズムよりは格段に使える。
209スレ違い:03/04/02 14:05
圧縮じゃなくて偽装・隠蔽じゃないの?
http://www.houko.com/00/01/S34/121.HTM
【特許法】
(特許の要件)第29条 産業上利用することができる発明をした者は、
次に掲げる発明を除き、その発明について特許を受けることができる。

1.特許出願前に日本国内又は外国において公然知られた発明
2.特許出願前に日本国内又は外国において公然実施をされた発明
3.特許出願前に日本国内又は外国において、頒布された刊行物に記載された発明
又は電気通信回線を通じて公衆に利用可能となつた発明特許出願前にその発明の属する技術の分野における通常の知識を有する者が
前項各号に掲げる発明に基いて容易に発明をすることができたときは、
その発明については、同項の規定にかかわらず、特許を受けることができない。 
大丈夫だろ
コロンブスの卵も特許取られてるしな
213デフォルトの名無しさん:03/04/06 21:02
age
214SYN ◆8smMJ0UaoA :03/04/07 01:08
>>212
winnyのログってどれでしょうか?
昔同じ大学で同じクラブにいたので、みんなで遊んでいることもあれば、
意見が合わず喧嘩したりとかもいろいろありましたが、第三者が騒ぐようなことではないです。
GCAの中の人も自分のページでちゃんと説明しているでしょ
早くDGCA正式版にならんかなー
>>214
そのものじゃないんすけど、

[BBS_ゲーム制作技術] 自作ゲームの開発状況を晒すスレ
ハッシュ 5743254f7e578f6c6972a93028c9632c
このスレの 113 の人がログ持ってるみたいです。
217山崎渉:03/04/17 15:38
(^^)
218山崎渉:03/04/20 04:24
   ∧_∧
  (  ^^ )< ぬるぽ(^^)
BlockSortingをするにはかなりメモリを使うと思いますが、大きいファイルを圧縮するときは、
ファイルを分割してソートしているんでしょうか?それとも、何かうまい回避法があるのでしょうか?
>>219
OSを信じてガンガンやる
>>219
BlockSortingに必要なメモリはだいたい
・巡回した文字列を作るのにブロックサイズ×2
・並び変わった状態を保持するためにブロックサイズ×4(sizeof(long))
で、たいていは1〜15MBくらいのブロックに分割して処理しているはず。
なお、BlockSortingはブロックサイズが大きいほど圧縮率が高いとは限らない。
222219:03/04/24 15:00
>>221
> で、たいていは1〜15MBくらいのブロックに分割して処理しているはず。
なるほど、やはり分割するんですね。

> なお、BlockSortingはブロックサイズが大きいほど圧縮率が高いとは限らない。
単純な素人考えで、ブロックサイズが大きいほうが良いと思ってました。
必ずしもそうではないんですね。
ご丁寧なレスのおかげで、勉強になりました。ありがとうございました。
comp.compression で凄い人が「凄い圧縮法」を開発したといって騒いでます…
http://member.nifty.ne.jp/yamazaki/doc/basic_compression.html
今、↑これや↓これを読んで、RangeCoderを理解しようと、やってるんですが
http://nikq.nothing.sh/junkbox/rangecoder.html

区間幅の初期値を0x80000000にするのは何でなんでしょうか?
どうして、0xFFFFFFFFとかのようにもっと大きい数値を使わないんですか?
どなたか教えてください。
>>224
特に問題ないなら0xFFFFFFFFでいいはず。
現に少し前のCマガジンに載っていた奥村晴彦氏のRangeCoderでは
0xFFFFFFFFに初期化している。

あと、RangeCoderなら ttp://www.geocities.co.jp/SiliconValley-Oakland/1680/zsaru.html
なんかがソース付でわかりやすいかと。
>>225
0xFFFFFFFFでも大丈夫なんですね。
教えてくださったURL先のページはRangeCoder以外の事についても載っていて参考になります。
色々と教えていただいて、ありがとうございました。
227デフォルトの名無しさん:03/05/12 18:25
228名無し@沢村:03/05/13 13:56
データを10個飛ばしにすれば1/10に圧縮できるよ。
データを100個飛ばしにすれば1/100に圧縮できる。
要は何個飛ばしにするかということだよ。
>>228
落ちたデータはどうするんですか(w
>>229
予測して補間
ゴルァリズム
>>230
有歪みならそれでもいいんだけれどね・・・
(つか、画像や音声の圧縮で使われる、標準的な方法だね)

無歪みにするなら、予測値とのエラーをとってGolomb符号を使うのがいいのかな。
アルファベット間の相関がない場合はほとんど意味がないから、
テキストの場合は、圧縮率を稼ぐために、何か前処理か、静的な辞書が必要だな。
それよりも、compressia のすさまじいまでの圧縮性能が気になる。しかも速いし。
ttp://compression.ca/act-win.html
ttp://www.compressia.com/

# SBCよりもちょっと遅くてちょっと高圧縮だから、ブロックソート系だろうか?
>>233
ブロックサイズを指定するというオプションからしてBlockSort系だと思われ。
235デフォルトの名無しさん:03/05/16 09:57
ベタなデータ列でもないのに、
圧縮したらとてつもなく小さいファイルサイズになるっていう
ファイルってありますか?

ベタなデータ列ってのは
例えば数字しかかかれていないテキストファイルや、
白一色のBMPファイルとか、そういう単調なファイルのことです。

だれか、意味のある複雑なファイルなのに、これこれの圧縮ソフトを
使うと異常なほどファイルサイズが縮まるというファイルを教えてください
なるべく圧縮ソフトは有名なものがいいです。
236デフォルトの名無しさん:03/05/16 10:01
例えばEXEファイルで、実行するとそこそこの機能もあるのに、
しかしある圧縮ソフトを使うと、
わずか20バイトに圧縮されてしまう。とか。

極端すぎるかなぁ。
>>236
20バイトのプログラムで何ができるのかを考えると・・・その例は極端すぎ。
現在の一般的なデータ圧縮は平均 1/4 になるといわれています。
1/8 以下に小さくできるなら、場合によっては異常といえるかもしれません。

ACT などで見てもらえばわかるように、Canterbury コーパスの kennedy.xls は、
zip や LHA などでは 1/5 にもならないのに、
それ以降のある程度の圧縮ツールでも 1/20 くらいに小さくなってきています。
238236:03/05/17 08:24
>>237
ありがとう^^
>>237
1/20 というのは 5%に圧縮されるの意味だよね?
http://compression.ca/act-canterbury.html
ここだと、zipやlhaは30%程度、最高のcompressiaで13%。

http://corpus.canterbury.ac.nz/details/cantrbry/Excl.html
ここにはbzip2-6が0.99とか書いてあるけど、これは単位がわからん
(cat が 8.00 になってるし、、)
>>239
8.00 を基準にするのは bit per character (bpc) ですね。
1記号を何ビットで表現できるかです。
普通のデータなら1記号8ビットなので cat だと 8.00 bpc
>>239
ACT は canterbury コーパス全部のファイルを圧縮した結果です。
圧縮できるのは、そのうちの kennedy.xls というファイルです。
>>235
意味のなくてしかも見方によっては非常に単純な内容だけど
00 01 02 ... fe ff 00 01 ... というように 00〜ff が順に繰り返されるデータは
まともな圧縮ソフトであればどれでも、大変小さくなります。
>>243
データ圧縮ハンドブック、買って読むがよい。
旧とっぱん、現ビアソンエデュケーションだったか。
DO++氏のWX法が公開されてまつ。
ttp://member.nifty.ne.jp/DO/
246山崎渉:03/05/28 13:00
     ∧_∧
ピュ.ー (  ^^ ) <これからも僕を応援して下さいね(^^)。
  =〔~∪ ̄ ̄〕
  = ◎――◎                      山崎渉
247名無し@沢村:03/05/28 13:16
おまいらよ、すべてのデータは1ビットに圧縮できるよ。
おれはたとえ何兆ギガバイトのデータだろうと1ビットに圧縮できるアルゴリズムを開発したよ。
まあ企業秘密なんで、詳しくは教えられないがね…。
その名は「量子重ねあわせ圧縮アルゴリズム」というんだよ。
つまり1ビットの中に、何兆ギガものデータを量子的重ねあわせの状態で詰め込むんだよ。
この技法を使えば全宇宙の全データを1ビットの中に詰め込むことも可能だよ。
おまいらには、想像もつかない超高度な技法よ♪
沢村って、なんでこんなにかわいそうなんでしょうか。
量子情報理論の参考書を2・3行見るだけで、自分が愚かなことを口にしたことがわかるのに。
他の書き込みもそうだけど。
>>248
沢村は、検索エンジン&ロボット&人工無能フィルターです。
適当なニュース記事を沢村言葉に加工して、2ch にこぴぺするだけです。
251デフォルトの名無しさん:03/05/29 23:29
沢村はhello worldをすばらしいソフトとかいっている時点で糞。
というかプログラミングできるの?
>>251
あの程度しかできないんだろうな。
出来れば公開するようなタイプだろうし。
253デフォルトの名無しさん:03/05/30 00:13
LZWの米国特許が、この6月で切れますね。
LZWの日本特許は、来年の6月19日・・・

もうちっとのしんぼうですね。
>>253
すでに関連特許が示されているので、期間延期な罠
>>252
あの程度しかとはひどい言い草だな。
人工無能であれだけ出来ればかなり高性能といってもいいぞ。
沢村のあれ以下のソフトってあるの?w
257デフォルトの名無しさん:03/05/30 01:08
>>254

なぬ?情報知ってたら、開示きぼー
258デフォルトの名無しさん:03/05/30 12:49
>>247
重ね合わせ状態を生成するプログラムが何兆ギガバイト罠
そもそも、重ね合わせたものを「ビット」などと呼称しない罠。
せめて「量子ビット」と書けや。
260デフォルトの名無しさん:03/05/30 22:28
「シャノンの定理」で検索してもわかりやすく解説してるHPがみつからなくてこまってます
どこかないですか?
261500MHz鈴木:03/05/30 23:05
LZWばりばりパクってますがナニか?
>>260
植松先生のリンクをいろいろ辿ってみたらいかがでしょう。
http://www.it.ss.titech.ac.jp/uematsu/uematsu-j.html
http://eprints.it.ss.titech.ac.jp/
264デフォルトの名無しさん:03/05/31 01:28
LZWの期限切れオフやろうぜ!!
ところで、いまさらLZWごときが使用できて何がうれしいのでしょう?
GIF? compress?
スライド辞書は展開速いから良く使うけど
>>264
日本では2004年に切れるとか。
ttp://www.kmonos.net/wlog/

>>265
LZ78系のアルゴリズムを遠慮なく開発できるようになるのが大きいかと。
(他の特許に引っかかるかもしれんけど)
>>267
いや、それも含めて >>265 は今更といっているのでは?
大学の研究発表に特許が及ばないから、LZW系列は1990年には出尽くしている。
今後、企業でLZWの商品化ができるとしても、すでにくそのやくにもたちゃーしねぇ。
>>268 すでにくそのやくにもたちゃーしねぇ。

何で? もっといいアルゴリズムがあるから?
gzipにも問題ありとしてるF社なんかは喜びそーだが
>>269
gzip は LZ77 + Shannon-Fano だから、LZW とは全然関係ないはず。
gzip が問題なのは、LZ77 に Hash を組み合わせる手法に関して。
詳しくは、奥村せんせーのページをみてね。

F社って富士通? べつに伏せる必要はないと思うが。
富士通は、国内外の有名圧縮研究者から、独自手法を買い取って、
特許の問題がない手法を実装している。これ、誰でも知っている有名な話。
271253:03/06/23 21:19
 話を振った本人なので、一応、結果報告を・・・

LZW圧縮に関する特許が6月20日に米国で失効しました。
同特許は、日本では、来年の6月19日あるいは20日の
いずれかに失効します。

以下、そのソース
http://www.upfrontezine.com/upf-344.htm

And the patent on LZW compression expires 20 June.
Owner Unisys says it has no plans to extend the patent.
LZW is used by several graphics formats, including
GIF and TIFF. CNET guesses this may cause the
never-particularly-popular freeware-alternative PNG
to fade away.

和訳:(間違ってたらごめん)
・・・LZW圧縮に関する特許が6月20日に失効する。
特許所有者のUnisys社はこの特許の延長計画を持たない。
LZW圧縮は、GIFやTIFFを含む、グラフィックフォーマットの
いくつかで利用されている。
CNETは、今まで特に人気を得られなかった、代替フリー
フォーマットのPNGが、これによって消え行く運命だと見ている。
PNGは消えないと思うけど、MNG/JNGがね・・・腐ってるね・・・終わってるね
>>272
仕様が固まるのが遅かった。
IEが対応しなかった。

これが全てだと思う。
274デフォルトの名無しさん:03/06/24 01:38
GIF フリー来たー

のであげてみたけど、どうよ? GIF 使ってる?
特許ってサーバの所在国に及ぶんだっけ?
それとも管理者?コンテンツ製作者?
>>271
http://internet.watch.impress.co.jp/www/article/2003/0612/unisys.htm
> なお、UNISYSは、LZWに関してこれ以外に2件特許出願中で近く成立するとも発表しており、
> 今後GIF技術が完全開放となるかどうかは、知的財産権の状況推移を見守る必要がありそうだ。

って書いてあるんだけど。どーなんだろね?
>>276
前科×犯の凶悪犯が更正することはまれ。
アメリカが戦争を放棄することはありえない。
UNISYSがLZWを(ry
まあ、なくなるまでしゃぶりつくすだろうね。
企業だし、利益もとめるのは悪くはないが・・・。
圧縮じゃなくて偽装・隠蔽じゃないの?
280デフォルトの名無しさん:03/08/01 17:08
なんかおもしろいな
281山崎 渉:03/08/02 02:05
(^^)
282山崎 渉:03/08/15 16:10
    (⌒V⌒)
   │ ^ ^ │<これからも僕を応援して下さいね(^^)。
  ⊂|    |つ
   (_)(_)                      山崎パン
保守
↑mailto:xxxli
複数の英文の圧縮に適した方法とは何でしょうか?

ブロックソーティングが良さそうだったのですが、
個々の英文を単体で取り出せるような仕様にしたいので、
これではちょっと効率悪そうなので・・・。
ちなみに現在はハフマン法で圧縮、約50%のサイズです。
>>285
BPE(Byte Pair Encoding)なんてどうでしょう?
ttp://www.gigamixonline.com/ds2/ds2bpe.html

あと、WordExtraction法なんてのもあるけど。
ttp://member.nifty.ne.jp/DO/algorithm.htm
287285:03/09/05 22:04
報告。
BPE法→ハフマン化したら圧縮率50→60%に・・・。
ブロックソート→MTF→ハフマンでも60%くらいでした。
単語単位で圧縮もやってみましたが、圧縮率はほとんど変わらず。
やり方悪いのかなぁ・・・。
>>285
一般的にテキスト系にはPPMが効く。
>>287
普通の英文を普通に圧縮したら、1/5 から 1/6くらいになると思うよ。

あと、英文を個々に取り出そうとすることと、圧縮率を上げようとすることに、
トレードオフが存在する。
・gzipやHuffman,個々のファイルで別々に圧縮する → 取り出しは容易だが圧縮率は悪い
・bzip → 圧縮率はそれなり。取り出しはやや遅い。検索だけなら速い。
・ppm系 → 圧縮率は高い。取り出しや検索はかなり遅い。
290高速伝道師:03/09/11 23:29
*量子圧縮アルゴリズム*
近年脚光を浴びつつある、次世代の符号圧縮技術である「リーネスト法」。
その実態は、これまでの量子圧縮法とは毛並みの違うものであることが判明した。
まさに『次世代量子圧縮アルゴリズム』である。
一口に量子圧縮アルゴリズムとは言っても、それは多岐にわたる。
しかし、現在主流とされる「ケルカゴ法」よりも、速度面では平均20%向上、
圧縮率ではなんと平均40%も向上すると見られており、これにより
量子アルゴリズムを取り入れない、従来の手法での圧縮率に匹敵する
圧縮ソフトウェアが誕生することが容易に想像できる。
これまでの量子圧縮アルゴリズムは、速度的な面からみれば従来の
よりも段違いの素早さを持っていたが、その特性上、圧縮率を
それに匹敵するほどに高めることは困難とされていた。
しかし「リーネスト法」は、これまでの量子圧縮アルゴリズムが皆一様に
抱え込んでいた『負の損価』の問題を、巧妙な手法によりクリアし、
一気に過去の圧縮アルゴリズムを叩き落とす"キラーアルゴリズム"と化す様相を
呈してきたのである。詳細はこちら↓
http://2next.net/test/read.cgi/lobby/1049166960/l50
>>290
ぉおぉぉおおおおぉぉ!?
なんかすげー圧縮法だな!
てかそれで圧縮できるんか?
リンク先みたところ、
量子っていうだけあって量子コンピュータ向きだね
でも普通のコンピュータでも無理ではないらしいね
実際のとこどうなんだろなぁ
使えるアルゴリズムなのかね?
>>287
BSやMTFは単体では圧縮しないハズ...
MTFで文字の出現頻度が偏るからハフマンが効きやすくなるのか.
ランレングス等と組み合わせてみてはどうよ?
293デフォルトの名無しさん:03/09/12 23:37
>>290
その圧縮法、20年ぐらい前に一度騒がれたな。
当時は夢物語って言われたけど
今のPCの性能を見ると不可能ではない気もする
でも圧縮率が毎回違うのは気分が悪い
でも速度面で異常なアドバンテージがあるなら
買いかもしれない
294デフォルトの名無しさん:03/09/13 09:22
>>247
そもそも1ビットにゃ1か0しか入んないでしょ。
>>294
量子ビット(キュービット)には、0か1であるかの確率を入れられるので、
原理的には古典ビットなら何ビットも入れられます。
うんこあげ

ぼとっ
rarで十分だろ?
>>295
量子ビットって複数無いと意味無いんじゃなかったかな?
1キュービットしかないときは2^1で2ビットしか入らなかったはず・・・。
nキュービットあって、それらが関係をもって2^nビット入るっていう感じじゃなかったっけ?
bitにすると0か1かしかないんだから
0が何個かあった後には1、1が何個かあった後には0っていうのは分かりきってるんで
個数だけをメモっていくってのどうですか?
たぶん・・・サイズは逆にものすごく膨れ上がる(死
例えば00010100110なら3111221
何個あるかというフラグにはとりあえず3bitほど(0個〜7個まで。7個を超えた場合には次の数0個にして)

あぁ、だめぽ。これじゃぁ全然縮まない。
スルーきぼんぬ
>>299
ランレングス
FAX などに利用されている。
301299:03/09/24 16:39
えっ、マジで?使えるんか、、、コレ。

よーし、パパ新しいの考えちゃうぞー。
>>301
FAXでは、ランレングスにハフマンを適用した変形ハフマン法が使われているよ。
べた画像には、ランレングスが極めて有効だね。
ただ、ランレングスにさえ、さまざまな手法があるので、圧縮は奥が深い。

Huffman, Ziv-Lempel, ブロックソート法などの有名どころは知っておくと吉。
また、Elias(整数符号, MTF), Golomb-Rice, 算術符号なども。
303デフォルトの名無しさん:03/09/25 00:38
辞書圧縮を考えた。
出てくる符号の種類の平方根を基数とした2けたの数字を辞書の番号として書き込んで行く

例えば、abcdefghiabcdefghiという文字列のみ入ったテキストファイルを考える。
ここには9種類の文字が出てくるので9の平方根を基数とした3進数2桁の文字列とする
すると、"000102101112202122000102101112202122"のようになる。
1.これは、2までしか出てこないのでそれぞれ2bitで表現して36bitで表現できる。
2.もしくは、ブロックソーティングしてRLEすれば小さくなる(はず)
>>303
統計情報を利用していないので、単なるHuffman符号よりも性能が悪くなるはず。
ちなみに、記号が n 種類出現するときの符号語長は(底が2の) log n ビット。
あと、a = b^2 のとき、a をそのまま符号化するのと、bb と符号化するのでは、
後者の方が必ず前者以上の長さになることが証明されている。

1. の手法は 36 bits ではなく、2 x 36 = 72 ビットではないか
2. 辞書の変換が文脈を破壊する可能性があるため、ブロックソートの効率が悪くなるかも
 (ブロックソートは数学的な証明が少ないので、はっきりといえないのでつ・・・)

上記文字列 9 種 18 文字なら、18 log 9 〜 57 bits を目指そう!
がんばっ!
>>304
まともな検討ありがとう。
実は、種類を減らし同じ数字を出やすくすることで圧縮しやすい符号を作るのが
目的だった。(約束は反古に)
で、1.は辞書の部分を単純に考えると72bit消費し、全く圧縮されていない。
種類が256種近辺で元の倍にもなる。
>>305
>...種類を減らし同じ数字を出やすく...

記号列が連続性を持つならMTFを使うべし。
そうでないなら、ブロックソート&MTFがまさにそれ。
1文字3bitの数0から7を一個ずつ適当に8つ並べる
「27506341」
1bitにする。
「010111101000110011100001」
BWTする
「101001101001101100101010」
3bit数に戻す
「51515452」

だめ?
>>307
何がいいの?悪いの?
ちなみに、復号できるの?
>>307
それが実用的な変換だからこそ、ブロックソートやMTFは有効だ。
しかし、変換をすればするほど、実はエントロピーが増大することに気づこう。

そして、各記号が1回ずつしか出てこない系列の符号化に際し、
BWTを行って何の意味があるのか説明できるまでがんばろう。
テキストの不可逆圧縮をやってみる。

1.文中に出てくる「です」「ます」等を「だ」「である」等に変換。
2.全角英数を半角に変換。
3.難しい単語を同じ意味のよく使う単語に変換。
4.外来語を簡単な日本語や英語等に変換。(「インターネット」を「the Internet」とか)
...

圧縮後でもパターンを作れれれば圧縮できますよね?
無秩序状態を崩すための暗号化とか無いんでしょうか。
>>311
圧縮後の状態は「そのデータをあらわすために必要な最低限の量」になっているので、
それ以上の圧縮ができない。
(理論上は)
圧縮後にパターンがあれば圧縮できる。
十分に無秩序(パターンなし)の状態から方法Xを使ってパターンを作った場合、それを再圧縮することは可能だ。
だが、暗黙の前提としての複号可能化を考えると、方法Xの情報も伝えなければならない。
結局トータルの情報量は減ることはない。むしろ増える。
>>311
圧縮後にパターンを作ることを考えるより、
圧縮しやすいパターンに変換することを考えるべし。
315デフォルトの名無しさん:03/10/05 02:58
そういえば昔、画像のMAGってフォーマットの「美点」として、
「lzhで固めるとよく縮む」ってのが必ず挙げられてたな(藁
>>315
MAG自体がlzに似たアルゴリズム(一致を左・上から見つける)なので、
lzhでの再圧縮がそこそこ有効なのは十分にありえますな。

巣のままだと、圧縮率をそこそこにして、展開速度を速くできたし、
lzhでさらに圧縮できるのに、lzhもそれなりに展開速度が速い。
内部で圧縮率・展開速度を変更できるパラメータを持つよりも、長所を訴えやすかったのかも。
>>316
LZ系とMAKI02は似てるなんてもんじゃないだろ。
(そもそもLZ77とLZ78じゃかなり違うのに系っていうのもアレだが…)

ランレングスやBPEも(一致を左から見つけるから)LZ系に似てるのか?
何故似ているとLZHで再圧縮が効くんだ?
LZ系ならどれもLZHで再圧縮が効くって事か?
>>317
詳しいことは専門家に譲るとして・・・間違っていたら教えてね。

考えてみた理由 (1)
MAGやLZSSは、一致を置き換えるが、エントロピー符号化していない。
したがって、LHAでエントロピー符号化されるため、再圧縮が効く。

理由 (2)
MAGやLZSSは、固定長符号を使用する(んだと思う。間違ってたらすまソ)
その後、LHAをかけることは、アルファベットのk次拡大を行った上で、
再帰時間を符号化することに相当するものに等しい。
新しい圧縮技術考え付いた!!
試してみたらjavadoc.zipとかエロ動画.rmとか圧縮済みの
ファイルも50%ぐらいに再圧縮可能で、復元も可能。
これ発表したらお金持ちになれる?
>>319
「永久機関を発明した!!」って言ってる人と同じ運命になる。
うーん。
圧縮出来るファイルと出来ないファイルがあるなー。
zipでもjpgでもうまくいくのは50%、うまくいかないのは
200%ぐらいの伸張率って感じ。
うまくいかない場合はアルゴリズム変えて再試行とか
やってみるか。
圧縮可能かチェックして、
可能なら圧縮すればいいし、
不可能なら今のヘッダに"だめぽ"とつけ加えたらいいのでは?
だめぽ は圧縮不能フラグ
>>321
ネタだろ。世界最強のでも、通常のjpegやzipを50%になんてできない。
オリジナルの部分は秘密でもいいから、既存の技術は何を使っているか書いてみろ。
どうせハッタリだろうが。
>>323
jpegならできるぞ。



不可逆でよければ。
325319:03/10/21 21:49
>>322
そだね。もうだめぽって出力しよう。

>>323
参考にしたのはBPE
7zip で作った zip は、その他の zip ツールで作った最高圧縮の zip ファイルよりも10%以上小さくなることがある。
逆に言えば最低圧縮(非圧縮は不可としても)の zip なら 50% はありえるかもな。
0バイトのファイルを大量に含んだ.zipなら50%圧縮も可能。
圧縮が効いたのは無圧縮zipと
ビットレートが無駄に高いrmでしたってオチだろ。
329319:03/10/22 21:47
>>326
>>327
>>328
細かいことをごちゃごちゃ言わなくていいから、
発表したらお金持ちになれるのかどうかを答えろ
>>329
なれない。釣り師になれるだけ。
>>329
1/100圧縮という前例があるだろ。
発表したら、嘲笑をもらえるよ。
>> 329
1/100圧縮のヤシはお金もちになれたのか?
>> 331だった。はは
>>329
ただ発表しただけでは、お金持ちにはなれない。
335329:03/10/24 22:11
じゃあどうすればいいの?
どっかの企業に売り込むとか?
特許取ったら逆に誰も使わなそうだしなー。
>>335
まずは >>1 みたいに検証できるものをアップしろ。
保守
338デフォルトの名無しさん:03/10/28 10:16
RangeCoderで除算を使わずに高速に展開することは可能でしょうか?
>>338
RangeCoderで一番時間がかかるのは、
二分検索でシンボル決定するところだから
除算減らした程度では何も変わらないと思われ。
>>338
2の冪に揃えれば多少は速くなる。しかし、圧縮率は落ちる(ことが多い)。

>>339
確率情報を与えるのは、rangecoder以前の仕事と考えられるが、
速度の変化はわずかという意見に激しく同意。
KTYが消えちゃったんです
>>341
PAQ4 のクローンという疑惑が comp.compression で浮上してたから、
そのせいでない?
runlengthしてblocksortしてhuffman圧縮が最高ですか?
>>344
Static PPMが結構すごいらしい。
πを求める公式は、πを圧縮したもの。
Algorithmic information theory ?
Streaming Network Range Compression (SNRC)技術 を開発したぜ。
これはすごいぜ?
まあStreaming Network Range throgh Keep(SNRK)技術が
根底にあるんだけどな。まずSNRKについて説明。
今まではデータは各々のローカルに保持するものだったろう?
経由しているネット(網)自体(ケーブル等)に保持しようと
しなかったのではないか?
もちろん網によるデータの損失などは考慮済みであり、
損失特性を利用しての保持ができる。
・今までの構図
PC(100GB)-------この経路はただ通過するだけ-------PC(100GB)
・これからの構図
PC(100GB)-経路の保持量に依存するデータ量が保持可--PC(100GB)

欠点は経路が事故や停電等により機能遮断した場合、
保持されているデータが全て失われることだ。
それがなければ理論値では
100MLAN、経路長500m ならば 約40,000GBのデータが保持される
これをSNRC圧縮とリレーGG(Genu-Gear )で拡張することにより
実測値平均 無圧縮54,000GBのデータが保存できる
(理論値は200,000GBだがかなり損失の影響が大きい為)

これを発表したらどうなるかな?
age
>>348
10年位前に雑誌(アスキー?)のジョーク記事で読んだな。
いや、マジで。
351デフォルトの名無しさん:04/01/01 22:48
俺はどんなものでも最低でも4分の3に圧縮できる方法を知っている
どっかに板にどんなファイルでも0バイトに圧縮できる可逆圧縮ツールもあったな…
>>352
このスレの>>176な…
ある意味マジなところがすげぇ
へー、オモロイな
NTFSにストリームなるものがあるのか
これを利用してるウィルスもあるんだな

>>351
「どんなものでも」はありえないYO
>>354
可逆とは言ってない気がするが?
海外掲示板用オフラインリーダーを作るスレ
http://pc2.2ch.net/test/read.cgi/tech/1072883528/

海外でよく使われていうる掲示板スクリプト
専用のオフラインリーダー作って下さい。

必要な条件はID、PASSを管理できること、
OpenJaneみたいな三面型の見た目。
簡単にローカライズできるように言語ファイルを採用
357HOSHU:04/01/30 21:13
ttp://www.cs.fit.edu/~mmahoney/compression/
ニューラルネットを使った圧縮!?
>>357
P5、P6、P12 などはその通りだが、PAQ 系は別物。
PAQ 系は各種のモデル化手法をごちゃ混ぜにした方式だったかと。
PPM (Prediction by Partial Matching) や CTW (Context Tree Weighting) に
近い感じかな?
>>351
1bitデータの圧縮おながいします
>>359
1bit 1キャラクタだけなら既存の方法で相当小さくできるぞ。
もちろんPCで扱うからそのデータを表現するには1-数byteになるだろうがな。
圧縮と符号化の関係をちゃんとりかいすることだ
361デフォルトの名無しさん:04/02/07 10:26
テキストの圧縮率が良くて(少なくともzip以上)、実装が簡単で
展開が速い圧縮法ってある?
>>361
GCAの最初の実装の(現バージョンは違う)
BlockSorting→MTF→RLE→RangeCoder
がいいかな。
概念の理解や実用化にはちょっと苦労するかも知れんけど。

ttp://www.geocities.co.jp/SiliconValley-Oakland/1680/zsaru.html
363361:04/02/07 13:27
>>362
やっぱりそれか。
というかちょうどそこ読んでたところ。
まだRangeCoderが理解できてない…
展開は遅いけど、最近ppm系が気になる・・・。
ppmz [ttp://www.cbloom.com/src/ppmz.html] が凄げだそうですが
結構読むのは大変そう。
会社で圧縮アルゴリズム考えてて、上司にこれ使っていいっすか!ときいたら
「おまえがすべての圧縮の特許を調べてそれがどれにも抵触してないことを証明できれば、いいよ」
と言われた
素晴らしい上司だな。
>>365
うっかり使用すると、会社がつぶれかねん。

特許フリーをうたっているアルゴリズムを使用するか、
国内で特許問題が解決済みの製品(富士通のダメツールとか)を使うかしれ。
誰かJava(*.java,*.class)ファイルに特化した圧縮アルゴリズム考えて
>>368
jarだな。

javaが動作する環境なら(JRE,JDKがあるなら)、圧縮・展開できるすぐれもの!
それだけでなく、なんと圧縮した状態でもclassファイルを実行できる。
>>369 釣られると、それって結局ZIP圧縮な(ry
371361:04/02/09 16:39
RangeCoderに入る前に文字の出現頻度から
おおよその圧縮率を求める方法ってないのかな?
いちいち通して確認してたらとんでもなく時間かかるし…
今のところ
A[1]^2 + ... + A[n]^2 //Aは各要素の出現回数
これが大きいほど圧縮率が良くなると考えてるんだけど。
これが分かれば配列内の数値の比較だけで済むから
MTFとRLEの最良の組み合わせを考える時間が減るんだな。
>>371
単純に
 foreach(要素の数だけ)
  合計 += 各要素のビット数 * 各要素の出現回数
ってやるんじゃダメなん?

ビット数は必要な精度を満たすなら不動小数点数でも固定小数点数でも良いと思うけど。
>>371
Cマガ2002年7月号より

i = 0〜255とする
p[i] → iの出現確率のとき

エントロピー(もとの1バイトを何ビットに縮められるか)の限界は
(p[i] + log2(1 / p[i])) の合計

※C99以前では log2(x) = log(x) / log(2.0) で代用
>>373
> (p[i] + log2(1 / p[i])) の合計
p[i] * log2(1 / p[i]) じゃなくて?

あと log2(1 / p[i]) は圧縮限界の値なのでサイズに余裕持たせとくとか、
ちゃんと RangeCoder の実装にあった式使うとかしないとオーバーフローする可能性あるよ。
>>374
まぁ、誤差はせいぜい数バイトper1M文字。
rangecoderや算術符号で吐き出すバッファ分+誤差数バイトとっとけばおk。

>>371
rangecoder通しても通さなくとも、実はほとんど時間はかわらない罠。
確率を算出するまでが、全体の9割方。
しかも、mathライブラリでlogを求めると、結局同じくらいの時間がかかる。
376361:04/02/10 00:02
みんなレスありがd

>>372
foreachって知らなかったんだけどPerlなの?
各要素のビット数ってのは8なら3で256なら8ってことかな?

>>373
やっぱりそういう式があるんだね。
log使うのか。

>>374
*,+どっちが正しいのかな?

>>375
うーん、そうか、というかそうだよね。
時間はたいして変わらないよね。

でも展開速度考えてRLEを挟まないオプションを入れようかと
考えてたんだ。
で、MTF -> RCの場合は
例えば出現回数100,20,5,3,1(要素5,MTF後を想定)みたいなのがあった時に
100 -> 99, 20 -> 21
みたいな変化をしたら確実に圧縮率が下がるのは分かるんだけど、
100 -> 99, 20 -> 25, 5 -> 1
みたいな変化をした場合には逆に上がるかもしれないじゃない。
(漏れの2乗和計算によると後者のほうが圧縮率高い)
こういう場合は3要素だけの比較で済むわけで。

いや、まだ全然実装してなくて全部思考実験の段階なんだけどさ。
実際コーディング始めたらどうでも良くなりそうな気もするけど。
377名無しさん@お腹いっぱい。:04/02/10 00:12
夢物語,それとも大発明? 「100分の1以下」の圧縮技術
http://www.itmedia.co.jp/news/0202/21/e_zeosync.html
1/100でも映画をフロッピーには無理だろ・・・
1/40のMPEG2でさえあのでかさだ
>>377
これ、もう1年前の話か。
げ、違う。2年前か。
そのままじゃなく既存のもしくは別のlossy方式と組み合わせてってことだろうに
いや劣化なしにってあるから違うだろ。
劣化が無いのはZeroSyncの妄想圧縮アルゴリズムの話であって、
それの応用については一切言及されてないと思うんだけど?

>そういう技術があれば,映画をまるまる一本,ダイヤルアップモデムを使って簡単に転送できるし

映画に付いてはこれしか語られてないんだから。
しかしMPEG1でも1GB強
そこから100分の1しても10MB、、フロッピーはどうしても無理が・・
>>384
(・3・) そこで夢の次々次世代スーパーフロッピーですYO
モデムもメディアも進化したってことだな
しかし、>>377のリンク先の会社のリンク、みごとに何も無いな・・・
>>383
あれは全部妄想でしょ。
応用って何?
>>387
「そういう技術があれば」から続く話だろ
妄想技術と、それがあると仮定した場合の話
妄想だから応用がないとでも言いたいの?
全てのデジタルデータが1/100になるならもう一回かければさらに小さくなるのかね・・・
ほぼって書いてある。
しかし、いまさらこんな古い記事を議論して何がやりたいんだ、おまいら?
>>388
それが実現可能な技術なら応用も有りだけど。
不可能な技術に応用はないだろ。
>>391
意味が無いといえばそらそうだが、
もしもの話をしているのはあの記事なんで
苦情ならそっちへ頼むよ
>>392
引っ張り出してきた >>377 はお咎め無しですか?
394373:04/02/10 09:26
>>376
ごめん、*の方が正しかった。すまそ。
395最近考えた事:04/02/10 14:49
圧縮アルゴリズムは,考えはじめるとキリがないんだよな……

どんなデータも
・利用するジェネレータの種類
・そのジェネレータへ与える値
・そのジェネレータが生成したデータを適用する位置
・ゞ 適用する長さ
・ジェネレータが適用できなかったノイズの値と位置
という 5 つのデータに変換できないだろうか?
つまり,元データを生成する命令群 (Midi みたいな感じ) になる.
・ジェネレータが適用できなかったノイズの値
・その位置
6つだった
>>395
あー、元データのバイナリ列を生成する有限状態機械表現によって
元データを表す(ことが圧縮になっている)って方法の一種かな。

どっかの学会誌で読んだことがあったような。
うーん、実用性とかまでは憶えてないな、すまん。
>>362
GCAって今はどうなってんの?
>>398
後継のDGCA Ver.1.00が先日公開されますた
aiueo.txt
----------------------------
かきくけこさしすせそたちつてと[EOF]
----------------------------

↓圧縮

かきくけこさしすせそたちつてとaiueo.txt
----------------------------
[EOF]
----------------------------

0バイトになりますた
>>400
不可逆
>>400
ワラタ(230バイトまで0バイトに圧縮できるね)
データを付加して圧縮して、もとの領域ちょうどにするアルゴリズムが存在する。
・Lossless information embedding -- new paradigm in watermarking (題名度忘れ)、
・情報埋め込みをともなう無ひずみデータ圧縮(似たような名前でいくつかあったような)

これらは、nバイトの領域にmバイトの別データを付加してnバイトに圧縮する。
しかも、この埋め込み圧縮は可逆だから、
A1+B1 <-> A2
A2+B2 <-> A3
A3+B3 <-> A4
...
A?+B? <-> Ax
と繰り返しても、AxからすべてのAi,Biを復元することができる。
さて、これは真であろうか。
復元するための情報を記録しておく領域が必要だが
真といえば真だな
>>404
復元できないか、できても値に意味がない状態を判別すれば
余分な領域は必要ないのでは?
406デフォルトの名無しさん:04/02/13 03:55
そんなことはないでしょう
407デフォルトの名無しさん:04/02/13 08:44
>403
XORなら望みの動作をするだろうが
圧縮とは呼ばない
>>406-407
元の論文をよみませう

J.Fridrich and M.Goljan and Rui du,
Lossless data embedding -- new paradigm in digital watermarking,
Emergin Applications of Multimedia Data Hiding, No.2, pp.185-196, 2002.

儘田真吾, 横尾英俊
情報埋め込みをともなう無ひずみ圧縮
第26回情報理論とその応用シンポジウム(SITA2003), pp.691--694, 2003.

どちらの方法であっても、
埋め込むデータに制限をつければ、無限回の埋め込みが可能。
データに制限をつけない場合は、埋め込み回数に限度あり。
>>407
XORより、足し算に近いものです。
1+1+1+...=n さて、nから1を何度復元できるでしょうか。みたいな。
そんなもん紙にメモしておくか、ネット上に置いておけばいい。
>>409
それは埋め込まれたデータが1であるという
復元するための情報をプログラムがもっているだけの気がするんだけど?
元々のデータnバイトを圧縮してmバイトにして、
n-mバイトのデータをcatすればいいわけだ。
>>412
その圧縮操作で1ビットたりとも圧縮できなかったらどうすんのさ。
>>413
>データに制限をつけない場合は、埋め込み回数に限度あり。

ってことでそ?
もっと力を込めて圧縮する
コンプレッサー 大地に(ry
>>414
埋め込むデータって埋め草のデータじゃなくて本体のほうかい。
しょーもな。
418デフォルトの名無しさん:04/02/27 23:33
>>416
はしるーはしるー
  なんなんだこれは.どんなファイルも1バイトになるぞ.

  どーなっとるんだ?
>  なんなんだこれは.どんなファイルも1バイトになるぞ.
               ^^^^^^^^^^^^^^^^^^^^^^^^
そんなわけがありません.
うおー俺の秘蔵のあのファイルが0xB6になっちゃった!
うわすっげ。
試しに俺の自作小説UPします。
なんかの新人賞に送ろうと思ってるものです。
たぶん最終選考には残る。

0x4E
「もっとがんばりましょう」
>>422
0xd4
>>419-
盗作はよくありません
なっつかしいこと書いてるなおい。
zobとか東京BBSに当時いた人ならわかるか。
元ネタってASAHIじゃなかったの?
429デフォルトの名無しさん:04/03/08 08:05
1/256の確率でいかなるデータも50%圧縮するプログラムを開発したぜ!!

255/256の確率でそのデータはお亡くなりになりますが?へへへ。
1177回程同じデータを突っ込めば99%の確率で半分になるのか。
便利だな。
根気さえあればどんなデータも1byteになるわけだな。
あぁ、圧縮したデータですら1/256の確率でさらに50%圧縮できるぜ!!

圧縮したいデータをアップロードして対応するURLを圧縮データとすれば任意のデータを十分小さく圧縮できる。
何でそんな簡単なことが思いつけないんだろうここの連中は。
>>433
とっくの昔に議論済み。
まあお前さんは、もう一度「本当に1/256なのか」考え直す必要がありそうだな。
>>433
Winnyは強力な圧縮ソフトですね
1/256に圧縮するアルゴリズムを256通り用意すれば完璧だな
なんでやねん ( ´∀`)σ)Д`) >>437
>>437
2^256個用意しないとだめだべ〜
65536通りのランダムな数値列を用意する。
適当な方法で圧縮。
圧縮されたデータをさらに圧縮。
縮まなければ用意した数値列(0)を鍵にしてバイナリを変換。
また圧縮してみる。
それでも縮まなければ次の数値列(1)でバイナリを変換。
挫けず圧縮。
もし2バイト以上縮んだらしめたもの。その数値列の番号を圧縮データに付加しておく。
これで元データよりほんの少し小さくなる。
そして更に圧縮。
・・・
これを繰り返すことでかなり圧縮できるのではと思う今日この頃。
エントロピーについて勉強すべし
>もし2バイト以上縮んだらしめたもの。

そのような奇跡が何度起こる事でしょうか。
ちなみに、複数回の圧縮を行ったり、パラメータを増やしたりするものについては、
MDL基準とかAIC基準を使って考えると良いでしょう。
その奇跡は0.002%の確立でしか起きなくてもいいんですよ。
昔、偽装とか流行ってたころ圧縮ファイルを更に圧縮しまくってた
ことが有って更に縮むことが稀に有ったんですよね。
勿論ヘッダの部分が圧縮されたとかそういう事を除いてです。
>>440
>>443
奇跡が起こってサイズが小さくできる期待値よりも、
バイナリ変換をしたかどうかというフラグですべてのファイルが増加する期待値の方が大きいです。
つまりやるだけ無駄。
アレだね、在る乱数列の中から目的のパターンを取り出せるシードを保存しようとすると、
シードのサイズが元のパターンより大きくなるっていう。
特定の圧縮形式の特性に特化した圧縮をするほうが話は早いだろ。
いろいろ圧縮の研究をした結果、
zipはとても良く出来たフォーマットだなと改めて思った。
いや、zipというかLZ法という意味なんだけど。
殆どメモリを使わずに高速に展開出来るってのは凄いよ。
BWTなんかは圧縮率が良くて動作も高速だけど
最低でもオリジナルサイズの数倍のメモリが必要だし。
PPMは遅いしメモリが少ないと性能を発揮できない。
>>447
BWTは先頭2文字限定ソートにすればメモリもブロックサイズの倍で済むよ。
>>448
szipのこと?
あれだと今度はブロックサイズを大きくしないとそれなりの圧縮率が稼げないと思うんだけど。
"円周/直径" ってべらぼうに圧縮率高いよね
>>449
思うんだけど。

実際にやってみれば分かるけど、16Mもブロックサイズを取れば
違いが出ても2-4%位なもんだよ。
>>451
使用するメモリの量を限定ソート(szip)なら減らせますと言っているのに、
ブロックサイズをそんなに大きくしたら、意味がないと思うのですが…
>>450
円周率はいつから有理数になったんだオイオイ
md5sum 求めるのって、どのくらいコストかかるのかと思ってテストしたら、
katmai@500 で 1〜3バイトを総当たりするのに 40秒もかかるんすね。

256バイト単位で md5sum を保存していけば ウマー と妄想してたのに。
どうやったらそこまで遅くできるのか疑問
つか、256バイト単位だと md5sum の衝突が起こると思うんだがどうやって圧縮に使うつもりなんだろ。
>>455
脳内でなくて、実際に検証してその発言してる?

>>456
他のCRC等と組み合わせるとか、なんとでもなると思うけど。
結局 56 バイトのデータがあるのと同じになっちゃうし処理時間はそれなりかと。

>457
>他のCRC等と組み合わせるとか、なんとでもなると思うけど。
ならない。
仮に CRC32 と組み合わせたとしようか。
MD5 で 128bit、CRC32 で 32bit。当然のことながら最大でも 2^128 * 2^32 = 2^(128+32) = 2^160 種類しか
データを表現できない。
256 バイトのデータは 2^(256*8) = 2^2048 種類のデータがあるので必ず衝突する。
固定長のデータと対応付けを行う限り、衝突を回避するためには 256 バイト「以上」のデータが必要。
ってか、むしろ基本だと思われ。
基本を語りたい初心者の方がいるようだね。

衝突したところで、中身が正常でないことを検出できるしくみを
考えればいいんじゃないの?
正常でない事を検出できる可能性が高い仕組みならあるけど
正常でない事を検出させるためには>>458
固定長符号とレートをキーワードにして調べるがよい。
元ファイルのデータをnByteとするとき
ファイルを1bitに圧縮して
1/2^(8n)の確率で元に戻るソフト作ったんですが、
売れますか?
>462
元ファイルの容量nをどこに格納しているかによる
本当に1/2^(8n)の確率で元に戻るのか?
元のファイルサイズが分からないから1/2^(8n)の確率すら達成できないんじゃ…
冗長性皆無のデータnビットについて、
n-1ビットで表現可能というのは論理的に破綻している。

…って解釈であってるよな?
>>465
YES!
2ビットのデータを1ビットで表現することを考えれば、
数学的にも証明できる。
>>463-464
そこでバグの登場ですよ
> 179 名前:名無しさん@お腹いっぱい。[] 投稿日:04/08/27(金) 09:27 ID:E/gdTjI+
> 俺、凄いアルゴリズムを考えた。
> 円周率って無限に続くから、適当な数列も
> 円周率をずっと計算していたらいつかは出てくるはずだろ?
> つまりその適当な数列の桁が2桁でも百万桁でも
> 円周率を計算したら同じ部分があるはずだよね。
> だから、圧縮ファイルに
> 「円周率の134895983桁から394384433499桁まで」という
> 数バイトの情報で100MBのファイルを格納できるのでは?
> ダメ?
469デフォルトの名無しさん:04/08/28 06:53
>469
波形と言ってるからDCT関係かな。
劣化せずに1/200はすごいな。
なんでDCTが出てくんだよ
472デフォルトの名無しさん:04/08/28 19:21
音声などのデータを200分の1以下に圧縮できる技術を開発

ソフト開発のジェイジーエス(東京・文京、里見和彦社長)は音声などのデータ量を
200分の1以下に圧縮できる技術を開発した。音や映像を波形データとしてとらえ、
数式に変換することで圧縮比率を高めた。ソフト会社や携帯端末メーカーなどに売り込む。
 開発した圧縮技術の名称は「MYC(マイク)」。元データを波の変化としてとらえ、
約50種類の数式を活用してデータ量が最も少ない数式に変換する。
映像データも色や輝度などの変化を数式に置き換え、圧縮する。プログラムに学習機能を
持たせており、似たデータは次回以降、さらに効率的に圧縮できる。
http://bizplus.nikkei.co.jp/genre/it/index.cfm?i=2004082408456b7

デモ
http://www.jgs-g.co.jp/hdtl/myc/index.html

>>472
ライセンス絡みで一般ピーポーには使えないと思われ
それはひょっとしてボコーダーの一種なんじゃないか、と言ってみるテスト。
可逆っつーとこがすげーな
例の1/100圧縮と同じ匂いがする
>>475
可逆なんてどこに書いてある?
単純な数式に変換したら可逆とはいえない。
478475:04/08/29 00:15
>>477
100% 一致しますた

MD2(sample1.mp3)= d2fba763f6deee7429d50ad6be186866
MD2(sample2.mp3)= d2fba763f6deee7429d50ad6be186866

MDC2(sample1.mp3)= dd0edeab9639f659516ced5d42bb8c78
MDC2(sample2.mp3)= dd0edeab9639f659516ced5d42bb8c78

MD4(sample1.mp3)= d5bbdb1a2fe752e26912b46c2de1aaf8
MD4(sample2.mp3)= d5bbdb1a2fe752e26912b46c2de1aaf8

MD5(sample1.mp3)= 459b5336617ea8d0751c4c3ca8ae9d41
MD5(sample2.mp3)= 459b5336617ea8d0751c4c3ca8ae9d41

RIPEMD160(sample1.mp3)= 6409593a12be100f02b7ebb05d5775022d5e2c5b
RIPEMD160(sample2.mp3)= 6409593a12be100f02b7ebb05d5775022d5e2c5b

SHA(sample1.mp3)= c9b5897a17ad7ad6379330a3b7b83f095fadac7e
SHA(sample2.mp3)= c9b5897a17ad7ad6379330a3b7b83f095fadac7e

SHA1(sample1.mp3)= b44cc8afa7e6a572578576603bd50df73f3ea775
SHA1(sample2.mp3)= b44cc8afa7e6a572578576603bd50df73f3ea775
>>475

デモページを見て、

なんで可逆で「音質重視」なんだよ

と思った。
480477:04/08/29 00:17
あ、ごめん、よく読んでなかった。

独自のアルゴリズムを用いて、音データ(波形)から完璧な数式を求めることに成功しました。そして求められた数式から元の波形データを再現することに成功しました。

って書いてある。
>>479
笑つた
名前:名無しさん@お腹いっぱい。[sage] 投稿日:04/08/29(日) 00:28 ID:iJVx+Vsb
>>736
hug_flashで音源抜き出すとどっちもmp3のうえ
md5が一致したんだが…w

740 名前:名無しさん@お腹いっぱい。[sage] 投稿日:04/08/29(日) 00:28 ID:/CuMc/+B
Flash内のMP3ファイルを抜き出して比較したら、圧縮前と圧縮後でバイナリ一致したそうで…。
まぁ可逆圧縮なのかも知れないがw

だってさ
ttp://www.jgs-g.co.jp/hdtl/myc/index.htmlに電話番号書いてあるから
だれかこの事実を問い詰めてみてください。
484デフォルトの名無しさん:04/08/30 12:18
>>483
電話してみたよ。
会社名を名乗ったら担当の方につながりました。

「WEBに乗せてるflashは、波形を見られてしまうとマズいのでわざと同じデータにしている。
 実際に圧縮したMYCバイナリを公開することはできない。
 圧縮したMYCは本当に同じように聞こえるので、あれは嘘ではない。」

だそうです。
ならflash乗っけなきゃいいじゃん
【技術/IT】データ量を200分の1以下に圧縮する音声映像圧縮技術
http://news16.2ch.net/test/read.cgi/scienceplus/1093621474/

>約50種類の数式を活用してデータ量が最も少ない数式に変換する。
>プログラムに学習機能を持たせており、似たデータは次回以降、さらに効率的に圧縮できる。
波形テーブルでも用意してインデックス値にでも変換するんでないの。
>>484
それは詐欺っていうんじゃ・・・・
サンプル消したか?証拠隠滅?
>画像や文字情報も波形に変換することができます
文字情報圧縮しても不可逆だとダメぽ
それとも文字を図形として扱う? 元より大きくなりそう
490デフォルトの名無しさん:04/08/30 23:41
サンプル復活。
491デフォルトの名無しさん:04/08/31 00:42
円周率暗号ってまだ特許とられてない?
データと一致する桁の場所を示す数値の桁数が、
圧縮前のデータよりも小さくなることを証明したなら特許ものかもね
特許の前に数学界でセンセーションを巻き起こすだろうけど
>492
先生ショー?
どういうプレイですか? どこでいくらで見れる?
>>491
特許取る前に2chで発表してるから、多分もう特許とれない。
495デフォルトの名無しさん:04/09/03 13:16
>>491
単なる思い付きじゃなくて、実現可能なアイデアにしたら特許取れるよ。
あ、でも特許って、出願して類似の特許がなければ結構とれるんじゃないかな。
その特許が有効かどうかは、司法の場で争うことになるとか。
それ考えると、特許の維持費って結構かかるとか。

日本じゃなかったっけ?
そりゃアメリカの話。
日本は結構きっちり審査するよ。
学のない漏れが適当に考えただけだけど、
全てのデータの集合の要素数は加算だと思う。
1番目から順に、0,1,00,01,10,11,000,001... みたいな感じで。
だから任意のデータは「n番目のデータ」という形で表現できるけど、
nはそのデータ以上の長さになってしまうから意味ない。
円周率暗号とやらはデータを重ね合すことができから多少は圧縮できるのかもしれないが、
結局は既存の圧縮技術の範疇になるのではないかな。
それはいくらなんでも適当すぎるよ。
500デフォルトの名無しさん:04/09/03 22:25
まったくよくよんでないけど
音声情報って、前サンプルとの情報差が少ないから
サンプル間の差をとって圧縮すれば
分解能自体めちゃめちゃ上がるんじゃないのだろうか
しかも差をとるから情報が偏るし
どうなのよ
>>500


それを通称ADPCMって言うんですけどね?
502デフォルトの名無しさん:04/09/03 23:41
え!?あるのすでに。
でか超簡単だからどうせ誰か思いついてるだろうとはおもったが
あるのかやっぱり、うんうん、あたりまえかぁ
>>502
1階微分でなく2階微分にすればさらに圧縮率上がるよ。
PNGなんがの画像フォーマットでも圧縮前のプレフィルタで
近傍の画素の差分とってるよ。
504デフォルトの名無しさん:04/09/04 02:00
         ,-、            ,.-、
        ./:::::\          /::::::ヽ
       /::::::::::::;ゝ--──-- 、._/::::::::::::::|
       /,.-‐''"´          \:::::::::::|
     /                ヽ、::::|
    /                   ヽ|
     l  /               (      l
    .|    ●            \   |
     l  , , ,           ●     l  また騙されちゃったんだね…
    ` 、      (__人__丿    、、、   /
      `ー 、__               /
         /`'''ー‐‐──‐‐‐┬'''""´
        ./        ___ l __
         l   ./    /  |/ |
         `ー-<    /  ./  ./
           `ー‐--{___/ゝ、,ノ
505ほんたま:04/09/04 04:50
おい、おみゃ〜らよ、圧縮の必要はないぞ。
おみゃ〜らよ、圧縮はいらないということだ。自分じわかる?
おみゃ〜らよ、圧縮するかわりにノードの情報を書いておけばいい。
そしてそこからDLするようにすれば圧縮はまったく必要ない。
おみゃ〜らよ、これはまったく画期的な発想だな!エポックメーキングといってもいい!人類の歴史を変える大発見だ!
必要なのは、ノードの情報に必要なメモリだけだ。
自分じわかる?
>>505
ダウンロードする時間がもったいないから、圧縮してダウンロード時間速くしたほうがイイね
507ほんたま:04/09/04 08:58
>>506
いや、解凍する時間がもったいないから、DLして解凍する時間速くしたほうがいいだろ?
>>506
きみの8801mkIIだとそうかもしれんが。
>>505
それ、ファイルサーバって言わんか?
>>506
>ダウンロード時間速く
('A`)ハァ?
>>505
あなたの電波は強すぎて、私には受信しきれません
>>510
ファイル圧縮したほうが、ダウンロード時間速くなるだろが
時間は短くなるが速くはならんなw
>>513
あなたは国語を勉強してください。
>>505
ノードの情報が大きくなれば、そのノードの情報を圧縮しておいたらたくさんノードが覚えておけて便利だね。
516514:04/09/05 11:59
まちがえた。
× >>513
>>512
517ほんものの514:04/09/05 12:59
>>516
そうやって、偽りの人生を歩いてるわけだな。
そこまで必死になるほどのものか?
>>468
「16進数で円周率を計算中に、0と1しか出ない部分があった」
というニュースがどっかにあったような。
HDDに50GB位の最頻出パターンファイル作って
インデックス化すればいいんだよ。
超高圧縮間違いなし。
50Gだと位置指定に36ビット必要だから、5バイトの列がすべてパターンにヒットする勢いじゃないと使い物にならんね。
2^36種類のファイルの内どれだけ有効なファイルが存在するんだろうね?
0が200個並んだりとか2〜3バイトの同じパターンの繰り返しが数十回とかって円周率の中にあるのかね?
円周率使うのって本質的に>>519のとやってることは同じだし
パターンを頻出データで最適化できない分不利だな。
しかも検索が終了する保証もないし。
インデックスが十分長くなったら打ち切りとかになるんだろうけど効率悪いな。
524えせ:04/09/11 16:48:32
データは0と1の集まりだから
全ての0を「あた」という文字列に
全ての1を「た」という文字列に置換して
eofフラグに「ほあた」という文字列をおけば
ほとんどのファイルはすっきりするよ
525デフォルトの名無しさん:04/09/11 16:49:32
ひでぶ
526デフォルトの名無しさん:04/09/11 16:52:25
>>524
ワロタ
527デフォルトの名無しさん:04/09/11 17:02:06
>>524
儂のパソコンの秘密ディレクトリには
「んん〜ん〜〜〜ん〜〜〜んん…」という内容の
長い長いtxtファイルが置いてあるよ
528ほんたま:04/09/11 21:01:57
>>524
>全ての0を「あた」という文字列に
>全ての1を「た」という文字列に置換して

前者は1ビットが4バイトに増える。つまり32倍になる。
後者は1ビットが2バイトに増える。つまり16倍になる。
529デフォルトの名無しさん:04/09/11 21:08:55
>>528
テキストファイルの場合、0と1の出現回数の比はどうなってるのだろう…
530ほんたま:04/09/11 21:14:47
おみゃ〜らよ、四則演算しかできないやつが、圧縮を考えてもダメだよ。
どうせ頻出パターンを使って1+1式に圧縮することくらいしか思いつかないだろ?
まだ、データを波形に変えて、波形の重ね合わせで圧縮するとか、データの並びを数式に変えて圧縮するとかのほうがマシだが、おみゃ〜らはそれすら理解できないだろ?
数学を知らないからな…
おみゃ〜らよ、数学をやれ!!せめてリーマン面を使って圧縮するくらいのことを考えてみろよ!?
どうじ?自分じわかる?
531デフォルトの名無しさん:04/09/11 21:22:25
>>530
なんか変な日本語だよ
どこの方言?
532デフォルトの名無しさん:04/09/11 21:27:03
沢村系
533デフォルトの名無しさん:04/09/11 22:00:11
>>530
これだから、自分は頭がいいと思い込んでるお馬鹿さんは困る。
534デフォルトの名無しさん:04/09/11 22:20:26
>>529
ASCII文字のみのテキストファイルの場合、
確実に 0 が 12.5% 程度は多い。
535デフォルトの名無しさん:04/09/11 22:29:16
>>534
つーことはむしろ、1→「あた」、0→「た」にしたほうが
それっぽいテキストができるというわけだな。
536デフォルトの名無しさん:04/09/11 23:15:14
>ata
This is a pen.
54 - たあたたあたたあたたた
68 - たあたあたたあたたたた
69 - たあたあたたあたたたあた
73 - たあたあたあたたたあたあた
20 - たたあたたたたたた
69 - たあたあたたあたたたあた
73 - たあたあたあたたたあたあた
20 - たたあたたたたたた
61 - たあたあたたたたたあた
20 - たたあたたたたたた
70 - たあたあたあたたたたた
65 - たあたあたたたあたたあた
6e - たあたあたたあたあたあたた
2e - たたあたたあたあたあたた
0a - たたたたあたたあたた
537デフォルトの名無しさん:04/09/11 23:15:42
>ata
貴社の記者が汽車で帰社した
8b - あたたたたあたたあたあた
4d - たあたたたあたあたたあた
8e - あたたたたあたあたあたた
d0 - あたあたたあたたたたた
82 - あたたたたたたあたた
cc - あたあたたたあたあたたた
8b - あたたたたあたたあたあた
4c - たあたたたあたあたたた
8e - あたたたたあたあたあたた
d2 - あたあたたあたたたあたた
82 - あたたたたたたあたた
aa - あたたあたたあたたあたた
8b - あたたたたあたたあたあた
44 - たあたたたたあたたた
8e - あたたたたあたあたあたた
d4 - あたあたたあたたあたたた
82 - あたたたたたたあたた
c5 - あたあたたたたあたたあた
8b - あたたたたあたたあたあた
41 - たあたたたたたたあた
8e - あたたたたあたあたあたた
d0 - あたあたたあたたたたた
82 - あたたたたたたあたた
b5 - あたたあたあたたあたたあた
82 - あたたたたたたあたた
bd - あたたあたあたあたあたたあた
0a - たたたたあたたあたた
538デフォルトの名無しさん:04/09/11 23:24:38
ということは・・、

あたたたたたたあたた
あたあたたたあたたあたた

あたたたたたたあたた
あたあたあたたあたたたあた

あたたたたたたあたた
あたあたたあたあたたあたあた
539デフォルトの名無しさん:04/09/11 23:30:09
#include <conio.h>
#include <stdio.h>

#define STR0 "た"
#define STR1 "あた"

int main(int ac, char *av[])
{
  unsigned char ch;
  int i;

  while((ch = getch()) != 0x04)
    for(i = 0; i < 8; i++, ch <<= 1)
      printf("%s", (ch & 0x80) ? STR1 : STR0);

  return 0;
}
540デフォルトの名無しさん:04/09/11 23:33:34
こんなのはどう?
圧縮効果もあるみたいだけど。

BPCS-Steganography
http://www.know.comp.kyutech.ac.jp/BPCS/DPENV/DPENV-home.html
541デフォルトの名無しさん:04/09/11 23:40:26
これって画像をリサイズしたり解像度を変えたり、保存形式を変換したりしても、
埋め込んだ情報は復元出来るの?
542デフォルトの名無しさん:04/09/11 23:42:12
>>541
なにいってんだよ
できるわけないじゃん
543デフォルトの名無しさん:04/09/12 00:56:19
>>524-539
ケンシロウ進数
544デフォルトの名無しさん:04/09/12 03:40:32
>>542
出来るだろ
出来ないんなら厨房が作った偽装ソフトと変わらんぞw
545デフォルトの名無しさん:04/09/12 06:31:20
>>540
最下位ビットを書き換えるだけじゃないか...
研究でするようなことじゃないな
546デフォルトの名無しさん:04/09/12 08:35:41
算術符号ってエントロピー圧縮っていいますが
最近のBS+算術とかPPMはエントロピーを越えてるってことでいいんでしょうか?
547デフォルトの名無しさん:04/09/12 08:46:10
別に昔ながらのLZでも同じ事だけど。
548デフォルトの名無しさん:04/09/12 10:53:59
>>545
いまどきそんなステガノグラフィ研究してる人なんかいないよw
そんなのは本当に初期の頃の話だろ
549デフォルトの名無しさん:04/09/12 12:57:46
>>546
超えちゃいねぇよ。「マルコフ情報源」でぐぐっとけ。
550デフォルトの名無しさん:04/09/12 13:00:49
>>530
バカだなお前な。算術符号なんて、四則演算オンリーじゃんかよw
無知を晒すのもほどほどにしろよww
551 ◆FIcNi4f8js :04/09/12 14:07:07
>>543
01 -> あ
11 -> た
10 -> ほ
00 -> っ
くらいな変換がちょうどいいかも。

552デフォルトの名無しさん:04/09/12 14:09:36
>>551
01 10 00
553デフォルトの名無しさん:04/09/12 15:12:35
画像まとめるのにzipの無圧縮を重宝しとります。
554デフォルトの名無しさん:04/09/12 15:14:50
>>551
そのまま、新しい文字コード「ケンシロウコード」にしちまえ。
555デフォルトの名無しさん:04/09/12 18:47:31
>>530
そもそもコンピュータが四則演算(+論理演算)しか出来ないよ。
556デフォルトの名無しさん:04/09/12 18:57:09
四則演算すら出来ませんが?
最も基本的なところを見ると、できることは通信と辞書引きと論理演算だけ。
557デフォルトの名無しさん:04/09/12 20:27:38
555の言うコンピュータが何を示してるのかによるな。
558 ◆FIcNi4f8js :04/09/13 08:27:44
>>556 は、ハードウェア的には論理演算だけで四則演算を実現してるって言いたいんだと思う。
559未熟な中学2年生です:04/09/13 15:57:42
最近アルゴリズムに興味が沸いてきました
私が考えているテキストファイル圧縮ですが
まず元データバイナリを条件付きのビット反転などをして頻度に偏差を付けます。
(8bit解釈時に7が多くて9が少ないとかに)
んで頻度が多いデータを1xとか1xxとかの3bit以下に置換し
残りのデータの頻度に偏差が残っていれば
それも01xとか01xxとかなるべく短い値に置換。
残りのデータは少し長くなるのを我慢して
状況に応じて0xxxxや00xxxxや001xxxx等のかぶらない値に置換します。
ヘッダ部が大きくなりそうですが、いかがでしょうか?
560デフォルトの名無しさん:04/09/13 16:03:53
>>559

残念だな。

これは俺が特許申請願いを申請中だ。
早いもの勝ちなんでね、ごめんね。

しっぽり設けて、かわいい風俗嬢と結婚するね。
ごめんねw
561デフォルトの名無しさん:04/09/13 16:16:22
>>560
しかしその特許申請願いを申請された俺様が、自分の名前で特許出願した。
儲かったら、かわいい風俗嬢を指名できる程度に金払ってやろう。
562デフォルトの名無しさん:04/09/13 16:31:00
中学二年と言うのにリアリティがあるな
563デフォルトの名無しさん:04/09/13 16:49:32
>>559
マジレスするけど、
>んで頻度が多いデータを1xとか1xxとかの3bit以下に置換し
これは要するにエントロピー符号というやつで既に存在してる。
ハフマン符号・レンジコーダ(算術符号)てのがそう。
優秀な圧縮解凍ソフトはほぼ確実にこれらを使ってるよ。

>まず元データバイナリを条件付きのビット反転などをして頻度に偏差を付けます。
これがどういうものか良く分からんのだが、
元に戻すためにその条件を付与しなければならないので、
あまりサイズが変わらない可能性がある。

大前提として変換したビット列はそれぞれ一意に識別できなきゃいけない。
例えば0を開始ビットとして続く1の数でシンボルを表すとか。
α符号だったかなんだか忘れたけど他にも面白い符号理論があるんで調べてみるといいよ。
564デフォルトの名無しさん:04/09/13 16:55:24
>>563
ケンシロウ符号化はどうですか
565デフォルトの名無しさん:04/09/13 17:31:17
>>564
むしろ北斗神数
566未熟な中学2年生です:04/09/13 17:53:08
>>563
マジレスありがとうございます。
やっぱり既にある考えでしたか。残念です。
初めて「全てのデータを短くする必要はない(場合によっては長くなってもかまわない)」と
思いついた時は興奮しました。

偏差を付与の符号が長くなるとの事ですが
これは処理した回数(最大でデータの長さbit数^2 -1)で行けそうです
100ビットなら最大でも9999

でも既に誰かが考えてると思うとくじけそうです。
ありがとうございました。今日は早く寝ます
567デフォルトの名無しさん:04/09/13 18:37:58
>>566
そう、大抵誰かがもう考えていたりするw
でも自分で思いついたってのはすごくいい事だよ。

まず固定長・可変長符号の違いをきちんと理解しよう。
例えばabcdの4文字をあらわすのには
固定長符号だと 00 01 10 11
可変長符号だと 0 10 110 111(1110)
可変長の方は0が来たらその符号の終わりが来たという意味で、
0の前にいくつ1があったかで識別してる。
4つめの111は例外で、本来は終端の0が必要だけど、
4文字しか必要ないので3つ1が続いたらそこで打ち切るという事。

こうしてみると各記号が平均的に出現した場合、
固定長の方が少ないビット数で符号化出来ることが分かる。
何故なら符号を2bitという暗黙のルールで区切れるから。
可変長はそれが出来ないのでどうしても平均的な符号長は悪くなるわけだ。
ただし各記号に頻度の偏りがある場合(テキストとかいろいろ)はそうでもなくて、
頻度の高い文字に短い符号を割り当てる事でトータルのサイズを減らす事が出来る。

基本的にはこんな感じで圧縮をしていくんだな。
568デフォルトの名無しさん:04/09/13 18:44:11
モールス信号(俗称トンツー)は可変長
しかも不可逆
569デフォルトの名無しさん:04/09/13 18:51:49
モールス信号は可逆だろ
んじゃなきゃ使えね
570デフォルトの名無しさん:04/09/13 19:30:43
最近の子供は発育が良いな
俺が中2の頃は・・
571デフォルトの名無しさん:04/09/13 19:58:54
俺が中2の頃の方がマシだったかもしれん
あの頃は拙いながらも一応形になるまでソフトを作っていたけど
コーディングに拘りだしてからは不満が出るとすぐ捨てるクセがついた。
572デフォルトの名無しさん:04/09/13 21:11:07
俺が?
573デフォルトの名無しさん:04/09/13 21:13:27
どうみても「は」と書くべきところ
574ほんたま:04/09/13 21:26:48
おみゃ〜らよ、あるデータを圧縮して元に戻せないなら、不可逆変化だ。
これは熱力学第2法則にあたる。
おみゃ〜らよ、圧縮において熱力学第2法則が成り立つなら、同様に熱力学第1法則も熱力学第3法則もなり立つはずだが、自分じどうだ?
おみゃ〜らよ、熱力学第1法則はエネルギー保存の法則だ。
つまり元のデータを圧縮しても、圧縮されたデータに元のデータの全エネルギーは保存されているのではないか?ということだ。
おみゃ〜らよ、熱力学第3法則は、温度が絶対零度のときエントロピーは0になるというものだ。
つまりこれは絶対零度の条件下で圧縮すれば、データのサイズを0にまで縮めることができるのではないか?ということだと思うのだ。
おみゃ〜らよ、自分じどうよ?
575デフォルトの名無しさん:04/09/13 21:44:01
絶対零度の条件下では何も出来ないと思うが?
576デフォルトの名無しさん:04/09/13 21:49:43
俺が中2だった頃でイイじゃねーか。
577デフォルトの名無しさん:04/09/13 23:00:37
今出先なんだが
モールス信号ってのは不可逆なのか?
気になるので携帯で答えが分かるサイト教えて
578デフォルトの名無しさん:04/09/13 23:03:39
>>577
モールス信号で漢字を表現してください。
579デフォルトの名無しさん:04/09/13 23:06:04
へが長音(・)
ムが単音(−)

字間に間を入れる決まりだが それを無視すりゃ
モームス信号も不可逆っちゃ〜不可逆
580デフォルトの名無しさん:04/09/14 00:34:32
符号化について考えるのは今では馬鹿。
算術符号はエントロピーの限界に等しいといってもいいから、
これ以上のものはもう出てこない。
やりようがあるのは、モデル化の方。
581デフォルトの名無しさん:04/09/14 01:27:12
エントロピー圧縮後のデータは圧縮率の強弱にかかわらず
均一にランダムな状態ですね
あらゆる方向から偏りを作り出すのは不可能な状態
エントロピー圧縮部分で圧縮率を稼ぐのは無理です。
ブロックソートやPPMのように前処理としてより偏りの大きく
なる変換方法を考えたほうがいいでしょう

582未熟な中学2年生です:04/09/14 09:30:29
昨日はありがとうございました
固定長の考え方を考えていたのですが
3^2 =2^3+1 ってのを巧く利用できないでしょうか
アルゴリズム中で3進数を使う場合に
フラグビットを用意する必要がなくなると思うのですが。
583未熟な中学生です:04/09/14 09:51:50
つまりx000(2)〜x111(2)【xは符号】となるデータを
00(3)〜21(3)として、符号が必要な時に22(3)を使う考えなんですが
584デフォルトの名無しさん:04/09/14 09:53:20
学校は?
情報の時間なんじゃないの?
586未熟です:04/09/14 12:33:35
友人や教師に言っても「オマエ暇だな。そんな事やって役に立つの?」って言われました。
親に言ったら、壊れた人を見るような哀れむような目で見られました。
昨日 遅くまで両親が話していたんですが
きっと心配になって私の事を相談してたんだと思います。
587デフォルトの名無しさん:04/09/14 13:15:07
>>586
親・友人・教師は情報系の勉強の価値を理解していない香具師が殆どだから真に受けることはない。
漏れもよくクラスメート・親・教師に馬鹿にされたが、「こいつらは馬鹿だから漏れがやっていることの価値が分からないだけだ」
と自分に言い聞かせて何とかやり過ごしてきた。
実際、今思い出しても親や教師の方が明らかに間違ったことを言っていたと思っている。
588デフォルトの名無しさん:04/09/14 14:54:49
3進数コンピュータ理論は新しく構想されている
利点は アルファベットの大文字小文字の処理に特化している事
(0000=null,0001=a,0222=z,1001=A,1222=Z)
データに重みが付与できる事(これは理解してないので説明省略)
ちなみに211(3)と書くよりも0とアルファベットを利用して書く方が一般的らしい(実際には聞いた事ないけど)
589デフォルトの名無しさん:04/09/14 22:11:27
>>588
> (0000=null,0001=a,0222=z,1001=A,1222=Z)
じゃあ 1000(3) は?
590デフォルトの名無しさん:04/09/14 23:06:49
spらしい
ってかspってなんだ?
591デフォルトの名無しさん:04/09/14 23:16:08
>>590
ジャッキーチェンのSP
592デフォルトの名無しさん:04/09/14 23:22:39
>>587
で、いまでも同僚・親・上司から馬鹿にされてるんだね。
593デフォルトの名無しさん:04/09/14 23:32:00
>>583
フラグの有無が偏っていればそれなりに圧縮できるかもしれませんが、
全体的にはそんなに圧縮かからないような希ガス。
どうなんでしょ?
594デフォルトの名無しさん:04/09/14 23:46:31
ところで、

>>582-583
これって、例えばバイト単位の場合「0〜127 + 符号コード」の
頻度表を作ってエントロピー符号化にかければいいんじゃないでしょうか?
ビットもまんべんなく使えますし。

出しゃばってスマソ、首吊ってきます。
595デフォルトの名無しさん:04/09/14 23:55:27
>>594
まぁまぁ良い大人が中学生相手に…。
生温かく見守ってあげましょうや

spはspeak(er)の略ですな
喋ったりBeep鳴らしたりする時に使うと思います
596 ◆FIcNi4f8js :04/09/15 09:18:07
一応マジレスすると space だと思う
597デフォルトの名無しさん:04/09/15 16:09:23
このスレで、数レス後にネタ扱いされましたが

まぁなんとかなりました

そんなこのスレよ

ありがとう

特許とか面倒だorz
598デフォルトの名無しさん:04/09/15 16:18:45
圧縮・暗号化は、特許がからみやすいナーバスな分野だからな。
599デフォルトの名無しさん:04/09/16 21:57:11
>>559
自分も中2ですが
とてもあなたのことを尊敬しました。

RAID3 or RAID5のパリティについて深く考え込んでいた自分が馬鹿らしい
600デフォルトの名無しさん:04/09/16 23:20:37
BlockSort法で並べ替えたtextを微分して偏差を作る方法を実験してみようと
プロトタイプのソースを書いてみた

短い文ならBS法のメリットがないし
長文になるとメモリが足りずに止まる

ダメポ
601デフォルトの名無しさん:04/09/16 23:48:02
ケンシロウコード化したファイルを
BS法で並べ替え
2文字め以降は前文字と同じなら「た」違うなら「あ」と置き換える
かなりの確率で「た」が続く文になるはず
602デフォルトの名無しさん:04/09/17 01:40:54
つまんないネタをいつまでも引っ張るねぇ
603デフォルトの名無しさん:04/09/17 01:44:30
>>602
ばかやろう!標準だ。
604デフォルトの名無しさん:04/09/17 01:47:14
今日ひとりで、いつも行く喫茶店でコーヒーを飲んでいたら一つ前の席にOL風の女性が座
っていて、それが超美人!僕はボーと見惚れていると彼女がハンドバックを持ったままトイ
レへ行きました、5分位して帰って来たので、もしやウンチでもしたのか?今行けば彼女の
便臭が嗅げるかもと思い僕もトイレに入りました、ちなみにトイレは男女兼用です中に入る
と香水の香だけでした失敗かと思い念のため汚物入れを開けると、ありました温もりの残る
ナプ感激して広げると信じられない位の量の生レバーがドッサリと乗っていました、その場
で全部口に含み僕はまだ暖かい生レバーを全部、口に入れてしまいました、こんなに大量の
レバーを一度に入れた事はありません彼女は会社から帰る途中ナプキンを取り替えられ無か
ったので溜まっていた分が出たのか半端な量ではありません口が膨らんでしまう位の固まり
です僕はナプキンをポケットに入れ出ました席に戻ると彼女はまだ居ました僕の方を見てい
ます、少し頬っぺたが膨らんでいましたが、まさか僕の口の中に自分の生理が入ってるなん
て思うはずがありません!僕はゆっくりと彼女の顔を見ながらホカホカの生レバーを味わい
食べましたズルッと喉を通りました。
605デフォルトの名無しさん:04/09/17 19:51:49
乱数圧縮
一定の乱数発生ルーチンを使って「シード」と「一致しているところまでの長さ」を使って圧縮展開する?
606デフォルトの名無しさん:04/09/17 19:55:59
>>605
You're ZeoSync!
607デフォルトの名無しさん:04/09/17 20:03:14
What's ZeoSync?
608デフォルトの名無しさん:04/09/17 20:05:13
Oh! ZeoSync!
609デフォルトの名無しさん:04/09/17 20:09:04
Yeah! Zojirushi!!
610605:04/09/17 20:11:46
いや、一致するのが1バイトしかなかったら圧縮効かないし、一致する要素増やそうとしてシードを大きくしたら一致要素が短いとこで効率落ちるし。
611ほんたま:04/09/23 04:44:48
おみゃ〜らよ、可逆圧縮は存在しないぞ。わかるか?
おみゃ〜らよ、すべての圧縮は不可逆圧縮だ。自分じわかるかな?
おみゃ〜らは、物理を知らないから、可逆圧縮が可能だと勘違いしてるのよ。
おみゃ〜らよ、この世にまったく同じものは存在しないのだぞ!!
素粒子のレベルに至るまでこの世にあるものは、まったく同じものは2つとない。
つーことは圧縮して解凍したら、それは元のデータとは違ったものになってしまうということだ。
自分じわかるかな?
612デフォルトの名無しさん:04/09/23 09:39:12
>おみゃ〜らは、物理を知らないから、可逆圧縮が可能だと勘違いしてるのよ。

おまいは、シャノンの情報理論を知らないから、可逆圧縮が不可能だと勘違いしてるのよ。
613デフォルトの名無しさん:04/09/23 09:51:00
>>611
圧縮の定義がおみゃーだけ違ってる
614デフォルトの名無しさん:04/09/23 10:54:08
情報理論に物理とか関係ないんだよ
写真だって写真じゃないだとPCの中では
シャノンの定理は物理じゃないんだよ
擬似的に利用できる情報が生み出せりゃいいんだよ
この世にはまったく対になるものが2つ存在するんだよ
片方なんてありえないんだよ
それが量子論なんだよ
そしてこのスレはいかにエントロピーに早くそして近くするかってのを
妄想してるんだよ
そういうスレなんだよ
615デフォルトの名無しさん:04/09/23 11:05:13
量子コンピューティングをしらないのか。
616デフォルトの名無しさん:04/09/23 11:06:57
>>611
コンピュータ上に理論的に構築されるデータが違うものになってしまうことは無いが、媒体に記録されたアナログ的な量は同じにはならないだろうね。
617デフォルトの名無しさん:04/09/23 12:42:13
>>611
んなこと言ってるから、物理板でだぁれからも相手してもらえないんだよ。
そろそろ自分の頭が良くないって事実に気付いたほうが幸せな人生を送れると思うぞ、沢村。
618デフォルトの名無しさん:04/09/23 12:56:26
>>611
質問。

   mov bx,ax

っていう命令を実行した後のaxとbxの中身は同じものか?
>>611の理屈に則って説明してくれ > ほんたま
619ほんたま:04/09/23 22:37:03
>>611
おみゃ〜よ、axとbxの中身はまったく別物だ。
おみゃ〜よ、axからbxへの転送は不可逆だ。
ウソだと思ったらaxレジスタとbxレジスタの中身を覗いて、電子をひとつひとつ調べてみろ!!
自分じわかる?
620デフォルトの名無しさん:04/09/23 22:49:59
>>619
電子を一つ一つ調べるのは大いに結構なんだけど
実際に調べると調べる前と大きく結果が変わるけど

もしaxレジスタとbxレジスタの電子がまったく同じでも観測することで
まったく違うことになるぞ
621デフォルトの名無しさん:04/09/23 23:24:23
>>619
あっそう。じゃ、このサブルーチン呼んだらaxには何が入って戻るんだ?

sub:
  mov bx,ax
  cmp ax,bx
  jz L1
  mov ax,0
  ret
L1:
  mov ax,1
  ret
622ほんたま:04/09/24 05:46:33
>>620
>もしaxレジスタとbxレジスタの電子がまったく同じでも観測することで
まったく違うことになるぞ

おみゃ〜よ、だから言ったろ、まったく違うことになるって。
自分じわかった?
623デフォルトの名無しさん:04/09/24 09:12:37
おそらく日本にはコミュニケーション能力に致命的なダメージを与える
未知なるウィルスが蔓延しているに違いない。
624デフォルトの名無しさん:04/09/24 14:43:03
一つの教室に「人が何人いるか」が重要なんであって
人でさえあれば「誰が居るか」なんて問題じゃないっての
625デフォルトの名無しさん:04/09/24 15:27:00
コミュニケーション能力とは他人を否定しないことから始まる
626621:04/09/24 18:50:43
>>622
卑怯者だね、沢村君。都合の悪いことは無視か?

 #”マシン語の神”を自称するキミのことだから、
 #あの程度のコードを読み解けないはずはないよね?

>>621 の問いに正解を出せば >>611 の間違いを自ら認めることになるし、
間違った回答をすれば、今後アセンブラで偉そうなことは言えなくなるわけだ。

さ、答えておくれよ。あのサブルーチン呼ぶと戻ってくるのは0か、1か?


あ、もちろん「>>611は嘘でした」宣言でも「ボクはコンピュータわかりません」宣言でも構わないよ。
627デフォルトの名無しさん:04/09/24 19:31:23
沢村君って、屁理屈の塊でつね。
628デフォルトの名無しさん:04/09/24 19:38:53
情報の圧縮伸張で永久機関作ってくれそうな勢いだな。
629デフォルトの名無しさん:04/09/24 20:52:15
NTFSファイルストリームを使えば圧縮率∞%だよ。
630デフォルトの名無しさん:04/09/24 23:59:05
http://do.sakura.ne.jp/~junkroom/cgi-bin/megabbs/lounge/file/1096037269_1/
http://do.sakura.ne.jp/~junkroom/cgi-bin/megabbs/lounge/file/1096037269_2/

ここの人たちは圧縮・解凍に詳しそうです。
ハフマン圧縮のプログラムを書いてみたのですが、お暇な方、添削お願いします。
厳し目にみて下さい。よろしくお願いします。
631ほんたま:04/09/25 06:23:53
おみゃ〜らよ、圧縮のすごいアルゴリズムを考えたら、特許庁に特許を申請すればいいの?
早口言葉のとうきょうとっきょきょきゃきょくは違うの?
632デフォルトの名無しさん:04/09/25 07:13:22
>>621
沢村にシカトされたようなので、漏れが答えよう。
答えは1だ。jz命令で少し悩んだ。
不安になったんで、VCで実験させていただきました。低レベルでスマソ。

沢村って、自分に都合の悪いことはとことん無視だな。
メンヘル板逝け。喪前のためのスレを探しておいてやったから。
http://life6.2ch.net/test/read.cgi/utu/1093735148/
優しい人が多いから、多少のことは許してくれるだろう。
だからといって、あんまり迷惑かけすぎるんじゃないぞ。お兄さんとの約束だぞ!
633デフォルトの名無しさん:04/09/25 12:05:34
ほんたまの負け〜wwwwww
634デフォルトの名無しさん:04/09/25 13:15:12
>>631は沢村の「>>611は嘘でした。ボクはコンピュータわかりません」宣言つーことでFA?
635デフォルトの名無しさん:04/09/25 18:48:30
>>630
ざっと眺めてみただけだが、それなりに良くできていると思うぞ。
ただ一つ、符号表をまるまる格納している点を除けば・・・

>>630の方法だと、符号表の格納に最大9*256=2304バイトも使用してしまい、効率が悪すぎ。

代わりに各記号の出現頻度を格納し、復号器側でHuffman木をもう一度生成してやれば
4*256=1024バイトで済むでしょ。

さらに、出現頻度の代わりに各記号に割り当てられたHuffmanCodeのビット長のみを格納しても、
符号器と復号器でうまいことやれば全く同じHuffman木を生成できたりする。この方法なら、HuffmanCodeの
最大長を32ビットと仮定しても6*256=1536ビット、つまり192バイトで済む。

この最後の手法は、実際にdeflateアルゴリズムでも使われていたりする。
気になったらRFC1951を斜め読み汁。
636デフォルトの名無しさん:04/09/25 20:08:06
>>630
圧縮と関係ないけど、
buf = (write_buf >> 24);
fwrite(&buf, 1, 1, fp_out);
buf = ((write_buf >> 16) & 0xff);
fwrite(&buf, 1, 1, fp_out);
buf = ((write_buf >> 8) & 0xff);
fwrite(&buf, 1, 1, fp_out);
buf = (write_buf & 0xff);
fwrite(&buf, 1, 1, fp_out);
この部分は
for (i=3; i>=0; i--) {
  buf = 0xff & (write_buf >> 8*i);
  fwrite(&buf, 1, 1, fp_out);
}
にするとスッキリ。
ウィンドウズでリトルエンディアンなら普通に
fwrite(&write_buf, 4, 1, fp_out);
ビッグエンディアンならちょっと邪道に
for (i=0; i<4; i++) fwrite(((unsigned char *)&write_buf)+i, 1, 1, fp_out);
637ほんたま:04/09/25 23:31:23
特許庁は以前霞ヶ関の通産省の近くにあるのを見たことがあるんだけど、早口言葉でおなじみの東京特許許可局ってどこにあるの?
638デフォルトの名無しさん:04/09/25 23:52:05
必死だねぇ沢村。
で、どっちなの、0?1?
639デフォルトの名無しさん:04/09/25 23:59:52
>>637
通産省から名前の変わった経済産業省内にあると思うが?違ったかな?
640630:04/09/26 00:11:10
630です。635氏、636氏レスどうもです。
なるほど、vlc表の格納は9バイト固定では多すぎますか。
fwrite() X 4 については一つの関数にまとめるかどうか迷ったんですが、
ま、いいかとw
ようやくCというものがわかりかけてきて、もう少しまとめられる部分を
まとめ、圧縮率・圧縮時間を良く出来るようにしたいと思います。
641デフォルトの名無しさん:04/09/26 06:25:35
>>637
http://www2.mnx.jp/~kez9184/log/0203/02030301.htm
こういう騒ぎが起きて消滅したのさ。
642デフォルトの名無しさん:04/09/27 04:21:03
>>637
何処にも無い<マジレスカコワルイ
643デフォルトの名無しさん:04/10/04 00:21:09
IDがZIP
644デフォルトの名無しさん:04/10/04 01:00:34
>>643
おめ
645デフォルトの名無しさん:04/10/04 07:54:00
>>643
ほんとだスゲー!!!
646デフォルトの名無しさん:04/10/04 20:35:43
>>643
( ゚д゚)

(つд⊂)ゴシゴシ
 
(;゚д゚)

(つд⊂)ゴシゴシ
  _, ._
(;゚ Д゚) …?!

(*゚∀゚) スゲェ!!!
647デフォルトの名無しさん:04/10/16 08:54:40
質問させてください。
昔のCMAGAZINEの記事(1999年1月)を何となく読んでいて
LZH-Lightが紹介されているのを見つけたのですが、
このアルゴリズムって(圧縮前の)生データの転送等には
もう当たり前に使われているのでしょうか?
事情に精通しているかたは素人向けに少しばかり講釈をお願いできませんか?
648デフォルトの名無しさん:04/10/16 11:14:29
>>647
現在では HTTP とかだとデータ転送時に deflate が当たり前に使われてる。

LZH-Light ってのは deflate は圧縮時に数百kbもメモリを使ってて重い、
小さいデータの圧縮率が悪い、ってのを解決しようとしたらしいけど。
使われてるか、って聞かれたら全然使われてないのでは?
649647:04/10/16 12:41:40
>>648
ありがとうございます。こんなに早く的確な答えが返ってくるとは思いませんでした。

WEBサーバが対応していれば、
ユーザは知らず知らずのうちにdeflateを使っているという感覚なのかな…
LZH-Lightの有望な用途は(ストリーミングなどと違って)
データの欠落の許されない小パケットのリアルタイム系という理解でよろしいのでしょうか?
もしくは、省メモリで済むということで、携帯電話等のアプリにLZH-Light組み込めば
少しは転送が早くなるかも?
650デフォルトの名無しさん:04/10/17 16:14:40
よーわからんけど,deflateが発動する条件ってどんな感じなん?
651デフォルトの名無しさん:04/10/17 16:26:00
HTTP_ACCEPT_ENCODING
652デフォルトの名無しさん:04/11/12 18:39:22
ホシュ
653デフォルトの名無しさん:04/11/13 16:26:49
PPMのアルゴリズムをCで書いたアルゴリズムどっかに落ちてませんか?
なければココ見りゃ作れるよ的なサイトを教えてください。
本気できぼんぬ。
654デフォルトの名無しさん:04/11/13 16:30:54
C言語で書いたプログラムでした。
意味不明スマソ。
そしておながいします。
655SYN ◆Dgc0R/.dgc :04/11/13 17:15:18
656653:04/11/13 19:55:43
無学ですいません。

PPM* paper

ここかと思ったんですが404でした。

Download C source code (49k) for PPMZ

ここのヤツ落とせばいいんでしょうか?
見たところ、PPMの新しいののPPMZってのを
作りましたって感じですよね?


657デフォルトの名無しさん:04/11/14 01:56:58
>>655
PCゲーム板にお帰りくださいw
658デフォルトの名無しさん:04/11/15 10:34:24
>>653
昔、PPM*の論文読んで作れましたが、とても人様に見せられません
suffix tree だとか context trie で作ったものです

あと、最近参考しているサイト
ttp://homepage3.nifty.com/wpage/
で、PPM*の実装があるようですよ
659デフォルトの名無しさん:04/11/15 23:34:13
C++でもよいというのなら、ttp://www.compression.ru/ds/ のPPMdがおすすめ。
PPM系の実用上のネックである速度・メモリ使用量に優れているのが特徴。
660653:04/11/16 20:30:57
やはり人が作ったプログラムはムズくて読めませんね(><)
頑張って自分で作ってみることにしました。
ありがとうございますー
661デフォルトの名無しさん:04/11/22 15:59:08
662653:04/12/04 23:38:56
C++でPPMとPPM*作ったんですが、とても大きいデータを
扱うと謎な結果が出力されてしまいます。
まさかPPMはmallocを使わないとだめぽですか?
663デフォルトの名無しさん:04/12/05 05:33:54
>>662
どこかバグってるんじゃないの?
この手の圧縮ソフトは遅くなるからmallocとか使わないで
先にバッファサイズ分のメモリ確保してスタックなりキューなりにして使った方がいいよ。
664653:04/12/05 11:30:58
>>663
一応カルガリーのbib.txtで試してみました。
スタックやキューはちょっとよく分からないので頑張って調査してみます。

おっと、今日は日曜日だ。ガッコにイケネ・・・・・・orz

木構造(文脈トライ)を使ってやってるんですが、1次トライで
やってみたら根以外は絶対子ノードができないはずなのに
bib.txtでやると出来てしまうんですよね。

日記レス申し訳ないっす。
665653:04/12/05 23:57:54
連レス&自己レスすいません。
ちょっとしたミスが原因で、メモリは一応確保できてたみたいです。

完成してるはずなんですがなぜかbpcを見るとおかしいくらい結果が悪いので
調整してみます。PPM極めた先輩が欲しい・・・。
666デフォルトの名無しさん:04/12/06 01:35:13
>>665
WittenだかMoffatだかClearyだかが、サンプルプログラム書いていたような
データ圧縮ハンドブック にも、PPMの実装が載っているので参照されたし
667653:04/12/09 02:59:05
>>666
レス遅れてすいません。

今日、やっとPPM*が完成しました。PPMもすぐ完成するはずです。
皆さんほんとありがd!

原因は未だによくわからないんですが、if、else周りを綺麗に整理したら
すんなりゴールしました。この調子で卒論ガンガン進んでいきたいです。
668653:04/12/19 04:39:18
色々論文を検索したのですが、
PPMの改良はPPM*よりもはるかにすすんでPPMZなんて
すごいモノもあるようですね。

勉強不足すぎて鬱状態です・・・

PPM*からの改良を卒論の提案にするには
もはや時代錯誤で意味のないことなのでしょうか?

たとえPPM*からの改善に成功したとしてもPPMZを出されて、
「コレのが全然いいじゃん、何のためにそんなことしたの?」
と言われそうで。。。
669デフォルトの名無しさん:04/12/19 11:18:06
>>668
データ圧縮を実際の圧縮性能だけで語るには、もう無理がある。
圧縮関係の論文の大半は、もっと別の視点で書かれていることがわかると思う。

卒業論文なら、なぜその改良が有効なのかを説明できれば十分だろう。
670653:04/12/19 19:35:48
データ圧縮アルゴリズムの評価項目として
圧縮率、計算量、メモリ量以外にあるのでしょうか?
理論的な解析のようなことですか?

やはり乗りかかった船で、時期的にもテーマ変更は不可能なので
PPMの圧縮率改善で行きます。色々見てるとやはりPPMには深く
魅力を感じますし。

671デフォルトの名無しさん:04/12/20 09:03:55
>>670
論文を書く場合は、

  理論的な特徴があり → それが発揮されて(率や速度などの)圧縮性能が改善される

という流れがある。
もちろん、逆の場合として、その技術の解析をするという流れもできる。
しかし何れにしろ、論文を書く上で重要なのは、理論的な背景を述べること。

歴代の論文うんぬんでいえば、有名な論文は、理論的な主張をしたものが多い。
LZ78やHuffman、算術符号なども、エントロピー達成が主張のメインなわけで。
672デフォルトの名無しさん:04/12/20 17:39:45
既に他人がやっていることをやってる論文に価値ってあるの?
PPMは研究し尽くされていて、車輪の再発明にならない?
673デフォルトの名無しさん:04/12/20 18:59:20
>>672
早く大きくなって”日本の大学の卒論”書いてくれ。
すでにいいとこ出てたらスマソ。
674デフォルトの名無しさん:04/12/20 19:13:02
>>672
PPMにも研究の余地はかなりあります。
圧縮手法としては出尽くされたかんもありますが、
「なぜPPMだと圧縮できるのか?」は算術符号の理論的解析の域を出てません。

まぁ、それはそもそも現在の論文では、無記憶情報源が主流なので。
一般情報源は、どんどんこれからも取り組める分野ですよー

# そう考えると、ブロックソートの方がむしろ解析が進んでいるともいえるのかなぁ
675653:04/12/20 19:24:15
やはり新しいアルゴリズムによる圧縮率改善よりも
理論的解析のが余地があるみたいですね。
修士課程ではそっち方面に行きたいです。

でもデータ圧縮自体もう修士レベルで取っ付ける切り口は
もうないのかな・・・
676デフォルトの名無しさん:04/12/20 22:43:46
>>674
PPMもBWTも似たものですよ。符号化のアプローチが違うだけで。
677デフォルトの名無しさん:04/12/21 01:21:45
>>675
1980年代後半には、もう圧縮は終わりと言われていた。
そんな中で生まれたブロックソート法のように、まだ新しいものができるかもしれない。

>>676
ご存知だと思うが、そこまでいうと、LZ77とPPMも同じものになってしまうんで・・・
(一致を確率で置き換えることで、変換(エミュレート?)可能)
678653:04/12/21 01:28:44
気付いたらずっとコテでしたのでもうやめますね。

>>677
では今圧縮を専門に研究する価値はもうないでしょうか?
こういう事を言ってしまったらお終いかもしれませんが
やはり限られた時間なので、価値のある研究がしたいです。

まあ人によって価値なんて違いますが。主観でいいので
お願いします。
679SYN ◆Dgc0R/.dgc :04/12/21 02:14:35
限界が見えるのはまだだいぶ先のことだと思います。
終わりどころかどんどん進化しています。
http://www.maximumcompression.com/

自分は研究する価値は十分あると思っています。
というか、その道で研究をしたかったです。物理屋だったんで出来ませんでしたが。
680デフォルトの名無しさん:04/12/21 03:10:55
>>678
考えている方向がどういうものかわからんが、、、

大学での専門研究として、データ圧縮を取り組むのはおすすめできない。
学生の卒業研究なら、まだ余地はあるかもしれないが、生涯圧縮のみというのは困難を極める。
>>679 でいう圧縮手法をメインとする、世界の研究者というものは数えるほどしか居ない。
むしろ、趣味や企業として開発するには、こちら。

大概は、シャノン理論やらの情報理論のひとつとして、データ圧縮(情報源符号化)を扱うというか。
研究者としてそういう方面なら、かなり需要はあるというか、まだまだ未開の地。

まぁ、好きな道なら、しばらく取り組んでみるがよいかと。
681678:04/12/22 09:19:57
>>680
うちの研究室では割と主流にあたるんですが
データ圧縮アルゴリズムの改善をしています。
中にはLZや文法法、画像圧縮もいますが僕はPPMで
作ってる感じですね。
最初はキーファ、ヤングのgreedy grammarの論文を読んでました
がPPMに移行しました。

無学で詳しくは分からないのですが、今現在は多分>>680にある
理論的なことを修士課程でやろうかという流れです。
全く分野を変えてしまうのも学部での研究をムダにしてしまいそうですし。
682デフォルトの名無しさん:04/12/26 00:40:01
このスレを5分で斜め読みしたオレの思いつきだけど、
因数分解を使うことでデータ圧縮できそうだと思った。
683デフォルトの名無しさん:04/12/26 22:47:01
>>682
残念ながら、無理
684デフォルトの名無しさん:04/12/27 10:32:12
>>682
因数分解とか数式とか、いろいろ言われているけれど、圧縮ができなくもないことは確か。
ただ、そのアルゴリズムや検証が頓珍漢なので、信用されない。

たとえば、きっちり理論的に認められているのは、木やオートマトンによるデータ圧縮。
これはデータの動きを数式で表現するといえなくもない。
685デフォルトの名無しさん:04/12/27 14:15:50
>>684
そんな事は言えません。適当な事を言うな。
686デフォルトの名無しさん:04/12/27 20:08:22
圧縮の式を証明ってか導くときには因数分解は必要になるかもしれんが。
プログラム的には変形した最終形だけあれば良い。あたりまえのことだが。
687デフォルトの名無しさん:04/12/28 11:28:24
画像や心電図で、数式で圧縮するという論文ありますね
ちゃんと一定の評価もでているようなので、今後も研究が続くと面白そうですね
休みなので手元に論文がないので、タイトルなどは書けませんが、citeseerにありました


因数分解について、ちょっと思いついたので
  ある数値を表現するのに、2の冪で近似する
  すなわち、 4 = 2^2, 13 ≒ 2^4, 70000 ≒ 2^16
  肩の数字を、何らかの符号を使って出力

かなりしょぼいですが…
688デフォルトの名無しさん:04/12/28 11:34:12
>>684 >>685
数式の定義?がお二人で違うと思いましたが…どうでしょう?
CTWなどは、系列に対する数式を得ることで符号化するものと捕らえられなくもないと思います。
689デフォルトの名無しさん:05/01/04 03:26:29
情報通信関連の話題専門の2ch風掲示板を作りました。
もしよろしかったら使ってください。
http://scs.dip.jp/
690デフォルトの名無しさん:05/01/15 01:46:43
>>689でantidictionaryという圧縮方式があったのですが
citeseerで調べたところ論文が少ないみたいですが
今流行っているんですか?
性能や情報源符号化での位置づけ?などご存知の方がいたら教えてください。
691デフォルトの名無しさん:05/01/15 11:10:27
>>690
2000年に発表されて、関連論文はまだ3本くらいしかないと思う
レターや発表ならそこそこある

流行というか、某教授とその研究室でやっていて、
関連が徐々に広まっているところ

ブロックソートのようにブレイクするものではなく、
情報理論の隙間を埋める手法のひとつなのだろう
692デフォルトの名無しさん:05/01/19 04:37:39
>>690
> 今流行っているんですか?
流行ってるって言われたら流行ってないよねえ。
極めてじみーな話だし、今後人気が出ることもまるで考えられない。
今の段階でこういう話って、そもそもテイストがひどく悪いような。

>>691
> 情報理論の隙間を埋める手法のひとつなのだろう
そんなにスケールの大きな話じゃない。
693デフォルトの名無しさん:05/01/30 18:05:14
age
694デフォルトの名無しさん:05/03/07 08:41:33
圧縮と直接関係はないんだけど、
RARやDGCAについてるリカバリ機能ってどんなアルゴリズムなんでしょう?
とりあえずデータを二次の配列として捉えて行・列ごとのXORをとったものを
付加しておけば1バイトの破損を修復できることが分かったんだけど、
2バイト以上の破損は発見できても修復出来ないです。
ましてや欠損があった場合はお手上げです。
複数箇所の破損欠損に対してはどのような方法を取ればよいのでしょう?
695デフォルトの名無しさん:05/03/07 14:31:06
696デフォルトの名無しさん:05/03/07 14:33:50
697デフォルトの名無しさん:05/03/07 21:36:49
698デフォルトの名無しさん:05/03/07 21:48:54
699デフォルトの名無しさん:05/03/08 03:58:18
何かと思えば一人TMJか
くそっ
700デフォルトの名無しさん:05/03/08 04:00:42
TMJってなんだよ
圧縮すんなよ
教えてくれよ
答えてよ
お願い
ねぇ
701デフォルトの名無しさん:05/03/08 16:14:11
TMJってすげー懐かしいんだが
702デフォルトの名無しさん:05/03/09 09:08:20
くそっ
と書いたがリンクを延々辿ったらちゃんとゴールがあったのでちょっぴり感動したがな

あとTMJは展開するとTarai Mawashi Japanになります
703デフォルトの名無しさん:05/03/09 09:27:31
組込み用データなら圧縮に幾ら時間をかけてもOK。
そのかわりに伸張時にリーズナブルなワークメモリ、高速展開を目指すべし。
ということでPPMで数Kで展開できるアルゴリズム作ったけど誰か買って・・・
704デフォルトの名無しさん:05/03/09 13:23:04
PPMのデコードってLZ77より小さくなる?
705デフォルトの名無しさん:05/03/09 13:31:07
PPMの展開って圧縮と同じコストがかかる(=遅い)というイメージがあるんだけど……
706デフォルトの名無しさん:05/03/09 21:11:56
>>704
LZ77なら数十バイトくらいで復号ルーチン書いたものがあったはず

>>705
PPMは、符号化と復号で(まったくではないが)同じ作業をするから、
使用メモリも時間もほぼ同じ(くらい多い・遅い)
707デフォルトの名無しさん:05/03/10 00:26:55
じゃあ703はアルゴリズム選択の時点で間違ってるということでは?
708デフォルトの名無しさん:05/03/10 11:30:02
組込用の場合、圧縮ファイル作成に幾ら時間がかかろうがOK。
問題は伸張時だな・・・
Windowsの様に潤沢なメモリとかは望めないので全部解凍しない
で目的のデータのみを展開するランダム展開とかの手法がよろし
いかと。
709デフォルトの名無しさん:05/03/10 13:39:20
>>708
組み込みでわざわざランダム展開が必要なケースってあるの?
つーか普通にLZ系にすれば?ランダム展開もできないことないし。
組み込みって聞くと圧縮率より速度が重要な気がするんだけど。
710デフォルトの名無しさん:05/03/11 00:52:56
展開時の速度、コード量なら BPE とか。
711デフォルトの名無しさん:05/03/11 01:20:49
>>709
つーか元データの形式やハードウェアの環境が具体的に示めされて
ないのに何とか方がいいとか、なんとかアルゴリズムがいいなんて
推測できるんだ?
学問じゃなく仕事や公開する場合は、将来特許がらみで嫌なことに
ならないとか、メンテナンスも容易にできるように実装するっての
が大事だよな。

712デフォルトの名無しさん:05/03/11 16:24:32
>>711
いや、単にLZ系しかあんま知らないもんで。
特許については展開だけなら大丈夫と思うけど。

>>710
BPEは圧縮率が大したことないから速度優先する時だね。
コード量はデコードだけならBPEもLZもあまり変わらないから。
BPEと何か他と組み合わせる事にするとLZが有利になってしまうかも。
713デフォルトの名無しさん:05/03/14 17:28:41
よくしらんけど圧縮って 文字とかバイナリとかを数値(10進数)に
変換して /2 を繰りかえせば 小さくなると思う。
解凍の際に *2 を繰り返す(ヘッダーに記述されている)

でいいんじゃないの?
714デフォルトの名無しさん:05/03/14 17:40:27
レス待ちage
715デフォルトの名無しさん:05/03/14 17:47:42
↑馬鹿注意
716デフォルトの名無しさん:05/03/14 17:52:31
>>715
間違っているなら 詳細にお願いします

訂正:
割り切れない事もあるので 割り切れるまで 探す
717デフォルトの名無しさん:05/03/14 17:54:18
間違ってるも何もそれで圧縮してみりゃわかるだろこのチンカス
718デフォルトの名無しさん:05/03/14 17:58:35
面接官「特技はミナデインとありますが?」
ジョン「俺は、リーダー・ジョン・スミス大佐。通称ハンニバル。
    魔法と魔力の達人。
    俺のような天才でなければミナデインは務まらん。」
面接官「・・・で、そのミナデインは当社において働くうえで
    何のメリットがあるとお考えですか?」
フェイスマン「俺はテンプルトンペック。通称フェイスマン。
       自慢のミナデインに、警察はみんなイチコロさ。
       100ヒットポイントのダメージを与えてやるぜ。」
面接官「ふざけないでください。それに100って何ですか。だいたい・・・」
クレイジーモンキー「よおお待ちどう。俺様こそマードック。
          通称クレイジーモンキー。
          ミナデインの腕は天下一品!
          ヒットポイント?HPとも書きます。だから何。」
面接官「聞いてません。帰ってください」
コング「B・A・バラカス。通称コング。
    ミナデインの天才だ。面接官だって吹っ飛ばしてみせらぁ。」
面接官「いいですよ。使って下さい。
    ミナデインとやらを。それで満足したら帰って下さい。」
全員「俺達は、道理の通らぬ世の中をあえて爆破する、
   ミナデイン野郎Aチーム!
   でも今日はMPが足りないみたいだ。」
面接官「帰れよ。」
719デフォルトの名無しさん:05/03/14 17:58:44
>>717
そうですね
720デフォルトの名無しさん:05/03/15 03:10:29
>>713
マジレスしてみるか・・・  間違っていたら訂正よろ

ランダム系列における奇数と偶数の出現確率は 1/2
ゆえに、/2 できる確率は、p=1/2 の幾何分布とみなすことができる

このとき、/2 できる回数の期待値は 2 である
8ビットを1記号とすると、割る回数を符号化するのに必要なビット数は log9 ビット

したがって、1記号当たりの圧縮率の期待値は (6 + log9) / 8 > 8 であり、
このままでは圧縮することはできない

log9 の部分を何とかできれば、6/8 +x までいけるかもしれない
といったところか
721720:05/03/15 03:12:44
訂正:
> したがって、1記号当たりの圧縮率の期待値は (6 + log9) / 8 > 8 であり、

期待値は (6 + log9) / 8 > 1.0 であり
722デフォルトの名無しさん:05/03/15 05:55:16
>ランダム系列における奇数と偶数の出現確率は 1/2
それを相手にして勝てるアルゴリズムって……

>割る回数を符号化するのに必要なビット数は log9 ビット
分布の情報がバッサリ逝っちゃってると思います。
723デフォルトの名無しさん:05/03/15 09:09:06
>>722
もとのアルゴリズムが、奇数偶数しか相手にしていないから、
確率2分の1を想定するのは問題ないかと。

log9の件は、上限を無視すれば、最適な符号は一進符号だよね?
すると上限を加味しても、平均2ビット弱になると思うので、
結局ほぼ圧縮できないことになるかと。


ところで、
>>716
>割り切れない事もあるので 割り切れるまで 探す

がよくわからんです。
このアルゴリズムだと、割り切れない場合は(フラグを立てるとしても)無視するのだと思うところ。
724デフォルトの名無しさん:05/03/15 10:31:30
>>716案は結局ダメなの?

じゃ16進数を32進数にするとか
725デフォルトの名無しさん:05/03/15 12:09:56
>>724
何ビット(何進数は意味がないよ)であろうが、

 A-x +y,
 A:一度に符号化する(数値と見なす)ビット数 x:削減できるビット数 y:xの値を記述するためのビット数

であり、x ~ y だから、圧縮はできない。
これは、奇数偶数で判別し、かつ削減量を記述しなくてはならない限り無理。
726デフォルトの名無しさん:05/03/15 12:43:44
漏れ的には、レンジコーダー改+PPM予測頻度テーブルΣチューンが最強・最速(展開時)
727デフォルトの名無しさん:05/03/15 15:26:20
ランダム展開って任意のファイル単位じゃなくて任意データ単位での
展開ってことですか?
728デフォルトの名無しさん:05/03/15 19:03:55
>>727
708の事ならそうじゃないの?
文脈的にシーケンシャルとの対義語の意味で間違いないと思うが。
729デフォルトの名無しさん:05/03/15 19:39:44
ランダム展開で、blockwiseじゃないものって何かありますか?
元データの xx byte目が欲しい、という要求にピンポイントで応答できるものとか

Huffmanでそういうものを見たような気がしますが、手元に論文もないし、
題名や著者も思い出せません
今現在は、元データ一定バイトブロック単位で圧縮することと、
圧縮データを直接検索する手法を組み合わせた手法を、自前で実装していますが、
圧縮率もいまいちですし、どうにも応答が遅いんで
730デフォルトの名無しさん:05/03/15 20:32:16
そんなの論文読まずとも圧縮アルゴリズムによるでしょ。
ハフマンなら区切りの良いとこのビットの位置でも覚えとくだけだし。
731デフォルトの名無しさん:05/03/16 01:57:15
>>729
あるよ、圧縮率はrkuよりちょっといいぐらいだけど。
他の優先順位はなによ、速度、ワークメモリ・サイズ?

つーかここであまり答えたくないんだけどね。すまん・・・

732デフォルトの名無しさん:05/03/16 03:11:59
>>730
それって可変長型ブロックランダム復号だと思う。

>>731
ここで議論うんぬんは同意だが、別にココ以外である必要も感じられん。
どうでもいいが。
733デフォルトの名無しさん:05/03/16 03:25:09
ストリームの対義語だとおもふ
734デフォルトの名無しさん:2005/04/07(木) 22:16:25
アルゴリズムかんがえました。ブロックソートとおんなじ様なもんですけど。

文字列 theahaaha
1.2文字目を見る. tの次はh
2.3文字目を見る. hの次はe
3.4文字目をみる. eの次はa
4.5文字目を見る. aの次はh
5.6文字目を見る. hの次はaとすると 2 .と区別が付かないので、ahの次はa
6.7文字目を見る. haの次はa
7.8文字目を見る. aの次はh(4と同じ)
8.9文字目を見る. ahの次はa(5と同じ)
表にすると

t|h
h|e
e|a
a|h
ah|a
ha|a
a|h
ah|a
735デフォルトの名無しさん:2005/04/07(木) 22:21:22
次に | の左の文字列(t,h,e,a,ah,ha,a,ah)を(右側を高位と思って)使ってソートする。
a|h
a|h
e|a
ha|a
h|e
ah|a
ah|a
t|h
文字列の最初の文字 t に | の右の文字を順に加えていく。
thhaaeaah
圧縮はしないが文字列が偏る。
736デフォルトの名無しさん:2005/04/07(木) 22:33:20
忘れてたけど、文字列の最後の文字aも覚えておく
復元もブロックソートそっくり。
737デフォルトの名無しさん:2005/04/08(金) 02:41:46
>>735
ソートの際の順位がよくわからないのだが、もう少し詳しく頼む
a と ah が離れていたり、ha の次に h があったりするのがよくわからない
右側が高位だすると、e の後に ha がくる?


ソート順位に関して不明なので、未検証だが、
>>734-736 は prefix sorting ではないだろうか?
738734:2005/04/08(金) 16:45:28
>>737
ごめん。eとha逆です。

しかも、これ考えたときは簡単に復元できた(はず)なのに、いまやってみたら復元できない orz
復元法をメモっとけばよかった。(前に復元できたのが偶然だとは思いたくない)

prefix sorting っていうのがあるんですか?ちょっと調べてみます。
739734:2005/04/08(金) 16:46:30
すいません。 "haとhが逆" の間違いです。
740734:2005/04/08(金) 16:51:52
いま考えたら、復元不可能な氣がしてきた。

復元時に得られる情報が、直前の一文字しかないので、
直前の一文字が同じもの同士並べ替えたらだめですね。

おさわがせしてすいませんでした。
741デフォルトの名無しさん:2005/04/08(金) 18:04:01
>>734
まぁ、少し落ち着いて。

theahaaha に対して次のように、左側の文字列を設定すれば復元可能
(ただし、先頭のtの前は、ループして末尾がつながるとする)

aaha|t
t|h
aa|h
ea|h
eaha|a
e|a
aah|a
eah|a
th|e
この左側を、逆順に見てソートするときの、右側を書き出すと
hhtaaaaeh    記号単位でソートしたものを接続して
aaaaehhht    下から上に見て、接続を行なうと

theahaaha   元の記号列に復元できる

これが、prefix sorting
742741:2005/04/08(金) 18:09:10
prefix sorting と suffix sorting の関係は

s = theahaaha の逆転文字列を s' = ahaahaeht とすると
s の prefix sorting と s' の suffix sorting が同じ関係にある
すなわち、得られる変換文字列が同一になる

実際 s' = ahaahaeht を suffix sorting してみると、
>>741 の hhtaaaaeh が得られる事がわかる
743デフォルトの名無しさん:2005/06/09(木) 03:59:11
保守
744デフォルトの名無しさん:2005/06/11(土) 00:08:16
良スレ
ホス
745デフォルトの名無しさん:2005/06/15(水) 14:15:35
プログラムなんて触ったこともないし、
圧縮アルゴリズムとか言われてもさっぱりなオレだけど。

gif画像ってx方向に連続したデータをギュギュっと詰めちゃってるって聞いたんだ。

動画の圧縮ってのは、z方向に連続したデータをギュギュッと詰めてるの?
次のコマ(フレーム?)と重ねたときに同じ色が出てたらそれを圧縮〜みたいな。

ちょっと気になっただけなんだけどね
746デフォルトの名無しさん:2005/06/16(木) 12:00:34
>>745
次のコマとの差分をとって圧縮してる。
だから動きが激しいと差分がでかくなって圧縮率が落ちる。
というか画像が荒くなる。
747デフォルトの名無しさん:2005/06/22(水) 22:17:46
ttp://www.maximumcompression.com/data/jpg.php

jpegなのにSTUFFIT 9.0だけ異様に縮んでる。
jpegってほぼランダムだよね。
もしかして展開してから圧縮し直してるのか?
でも復元してjpeg圧縮しても元のjpegとバイナリ一致するとは限らないし…謎だ。
748デフォルトの名無しさん:2005/06/22(水) 23:35:00
>747
JPEG というオプションを適用しているみたいなので構造を認識した上で何がしか処理をしてるんだろうけど。
749デフォルトの名無しさん:2005/07/07(木) 11:45:33
ハフマン符号ってやっぱり解凍速いんだね。
どっかにレンジコーダは速いって書いてあったけど、
それは厳密な算術符号と比べての話で、
どうやってもハフマンよりは速くならなかったよ。
圧縮は確かにハフマンより速かったけどモデル化の部分に埋もれて差は殆ど出ないし。
いまだにハフマンが使われてる理由が分かった感じ。
750デフォルトの名無しさん:2005/07/09(土) 09:03:47
2種類の分銅A,Bを使って、じゃがいも1gの物を量るために
成分A,Bを求める、またその正当性も求めるというアルゴリズムは
どのようにかけばいいのでしょうか?
知ってる方いましたらどうかおしえてください。
751デフォルトの名無しさん:2005/07/09(土) 13:23:34
>>750
もう一度見直そう・・・

・スレはあっているのか
・日本語がおかしくないのか
752デフォルトの名無しさん:2005/07/09(土) 16:51:47
>>751
知らないならでしゃばるな
753デフォルトの名無しさん:2005/07/09(土) 17:51:07
日本語おかしい
754デフォルトの名無しさん:2005/07/09(土) 23:51:35
とりあえずじゃがいも1gを求める為に
天秤と分胴A.Bを使って求めたい。
その時の成分A,Bを定義しなさい。
またその正当性も求めなさい。

つまりこういうことこれで日本語理解できるか?
755デフォルトの名無しさん:2005/07/10(日) 00:32:20
なんにしろ、明らかにスレ違いなんだから帰れよ
756デフォルトの名無しさん:2005/07/10(日) 04:11:30
知ってるけど
おしえない。
どうか、とお願いされても
絶対に
おしえない。
757デフォルトの名無しさん:2005/07/10(日) 04:58:42
>>754
最近こういうやつよく見る
同一人物か?
758デフォルトの名無しさん:2005/07/10(日) 05:28:54
じゃがいもを圧縮してみる

でんぷんが! でんぷんが染み出してくる!!
(ヨウ素液で紫確認済み)


不可逆圧縮・・・完成
759デフォルトの名無しさん:2005/07/10(日) 05:29:39
ちなみに、分銅は小学生には圧縮不可という論文が後日発表された
760デフォルトの名無しさん:2005/07/10(日) 05:30:42

  圧  天

  縮  秤
761デフォルトの名無しさん:2005/07/10(日) 05:35:38
この成分はでねぇよぉ!!!
762デフォルトの名無しさん:2005/07/10(日) 06:00:55
とりあえずミキサーでハッシュして
圧縮すれば
それがおまえにとっての1gだ
763デフォルトの名無しさん:2005/07/10(日) 08:31:11
俺も独自に >>750 >>754 を解読してみるよ。

まず、>>750 と同一の文面がMPEG圧縮スレにあることに注目した。
つまり、圧縮にかかわっているのは間違いないのだ。

次に分銅、これは学習指導要領から、中学1年にならないと登場しないことがわかる。
同様に、じゃがいもも、小学5年生あるいは6年生からとなっている。
逆にいうと、指導要領に指定された時期から外れると、まずこれらの事象は出現しない。
すなわち、ここまでのことから、質問者の立場は小学生5-6年と中学1年の2期以上にわたることとなる。

次に、圧縮とジャガイモの関係を見てみよう。
ジャガイモの原産国は、ペルーである。
google で「データ圧縮 ペルー」を検索すると、このスレでもおなじみのDO++氏の文章がトップにでる。
すなわち、圧縮とジャガイモの関係は、DO++氏によって結び付けられるのだ。

ここで、分銅A,Bという2種類の物体の出現を、上記の事柄に組み合わせなくてはならない。
小学生および中学生、そしてDO++氏は人物の登場を予期させる。
それと分銅の関係といえば、答えはA,B2種類の人型分銅となる。
そしてこの人型分銅は、砂金に強く関係している。
金といえば、胡椒 1g が等価に取引されていたことが有名である。
つまり、ジャガイモ1gを量るのに必要な胡椒の量を考えるのだ。これは当然1gである。

次に、ジャガイモの成分について考える。
驚くべきことかもしれないが、ジャガイモはビタミンがとてもバランスよく含まれている。
ここでピンときただろう。
含まれているビタミンを列挙してみよう、カロチン(A)、チアミン(B1)、B2、ナイアシン(B3)、...
そう、質問者が意図する成分A,Bとは、すなわち、このビタミンのことだったのだ。
>>754 の成分A,Bの定義は、これで行えた。

さて、ここまでくれば、結論を導くのは容易であろう。
そうなれば、文字数も尽きそうなので、これ以上は書かないが、
>>750 の疑問も解けたも同然である。
764デフォルトの名無しさん:2005/07/10(日) 12:11:51
シミュレート板の最適化スレにもあったな
765デフォルトの名無しさん:2005/07/10(日) 16:39:20
はっきりいってお前達アホだろ?
この程度の問題の意味すら理解できんとは
アホに違いない。

アルゴリズム知ってるか?
日本語しってるか?
成分=ビタミンなどとか考えたやつは
アホです。
普通に考えましょう。
小学生からやりなおしてこい
766デフォルトの名無しさん:2005/07/10(日) 16:40:00
数百メガ単位の汎用辞書作っておいて
それを利用して圧縮解凍ってできないの?
こんなん誰でも思いつきそうだからできないんだろうな。
767デフォルトの名無しさん:2005/07/10(日) 16:40:43
ていうかひとりでもりあげて楽しい?
768デフォルトの名無しさん:2005/07/10(日) 16:53:42
>>766
できるよ
その代わり圧縮できるデータはごく一部のかたよったものね
EXCELとか特徴のあるバイト列には有効
てかもうあるけど
すべてを辞書引きしようとすると、辞書のインデックスの表現に結局同じバイト数必要になる
から無理なのさ
769デフォルトの名無しさん:2005/07/10(日) 22:04:47
>>766
つ[THComp]
770デフォルトの名無しさん:2005/07/10(日) 22:30:39
つまりシリアルナンバーを付ける機構とファイルのおき場所さえ確保すれば
THCompは可能なのさ。
サービス形態としてはただのReadOnlyのファイルサーバ。
問題は転送速度とかストレージの確保とかインフラの整備
シリアル管理をURI形式にして企業単位ぐらいでTHCompデータベース持ってれば便利かもしれないよ
thcp://00124242..2ch.net
とかすればいつでもとってこれる
771デフォルトの名無しさん:2005/07/11(月) 00:18:01
単なる容量無制限のあぷろだだな。
772デフォルトの名無しさん:2005/07/11(月) 11:08:11
圧縮ファイルにCRCを付けようと思うんだけど、
圧縮前のCRCと圧縮後のCRCはどっちがいいんでしょう?
二つ付けても高々8バイトだから、とりあえず両方ヘッダに入れるんだけど。
んで、解凍の時に読みながら生成していって解凍が終わったときに比較してるんだけど、
圧縮前の方で比較すると圧縮後のと比べてサイズが大きい分遅いんだよね。

で、問題なのはどっちが誤り検出として良さそうなのかって事なんです。
なんとなく圧縮前の方が妥当な感じがするんだけど。
どうなんでしょう?
デコードオプションとして選べるようにした方がいいのかな。
意見求む。
773デフォルトの名無しさん:2005/07/11(月) 11:15:21
>>772
圧縮前でしょう
圧縮後のCRCなんてファイル自体が持っているのはあてにならん
774デフォルトの名無しさん:2005/07/11(月) 11:41:10
>>772
遅いのが嫌ならベリファイオプション付けた時のみやるとか。
775デフォルトの名無しさん:2005/07/11(月) 12:34:50
圧縮後でしょう
データサイズが大きいとその分ハッシュ値の重複する確立があがってくる
データ破損の主因はデータの受け渡し、ネットとか媒体経由のさいにおこる
解凍プロセスでデータが破損することはまず考えられない
776デフォルトの名無しさん:2005/07/11(月) 12:42:41
糞メモリ
777772:2005/07/11(月) 13:38:15
むむ、意見が分かれてますね。
とりあえず落としどころとしては774さんの言うようにオプションてことになるんでしょうけど。
実際はCRC生成の部分は全体からみれば数%位でしかないんで、
デフォルトでチェックするようにするつもりなんですが。

出来たファイルを適当にいじってみたんですが、
試した範囲では今のところどちらでも100%エラーを検出してました。
ただ、本当に偶然一致した場合とか、
悪意のある人が意図的にいじった場合なんかはどうなるか分からないんですよね…
まあ、理論的には元のファイルと比較する以外に真の意味での同一性を確認することは
出来ないですから別にいいんですけどね。
どの辺に線を引くかの問題であって。

話が逸れましたけど、本当にどっちが良いんでしょうねぇ?
誰か理論的に証明出来ないですかね?
ちなみに圧縮前の方は7-8%位、圧縮後の方は3-4%位遅くなりました。
778デフォルトの名無しさん:2005/07/11(月) 18:43:15
ブロック展開時のメモリにある内にCRC計算するとか。
2回読むよりは早いと思うけど。
それと、複数の異なる検出アルゴリズムを入れれば一意性は高まるのでは。
CRCは一意性判定に使うには弱いらしいので。
779デフォルトの名無しさん:2005/07/11(月) 21:14:28
もともとCRCは小さい記憶領域の判定につかうものだからね
MD5とかのがいいだろうね
780デフォルトの名無しさん:2005/07/11(月) 22:07:07
正当かどうかは書庫を実際に開く時にしかわかんないわけだし、
特別な意図でもない限りファイル毎のチェックは不要じゃないかと。
どのみち悪意に対抗できるわけでもなく、書庫のヘッダ書き換えられたら終わり。
まあCRCで壊れてるかどうかぐらいは入ってても良いけど、
実際は書庫ファイル自体のMD5やらCRCでやりとりするだろうしね。
781775:2005/07/12(火) 08:45:28
書き換えどうのってのの対策ならなおさら圧縮後だね
チェック用ハッシュ事態を暗号化しておけばいい
そうすれば書き換えしたらエラーになって解凍プロセスに進まない
一番最悪なのは破損や書き換えられたデータが解凍プロセスに乗っけられることだから

>>780
>>実際は書庫ファイル自体のMD5やらCRCでやりとりするだろうしね。
それを手動ではなく自動でやるための仕組みのことでしょ?
782デフォルトの名無しさん:2005/07/14(木) 22:09:00
>>781
だから、圧縮後のCRCは そのファイル自身が持っていても
何の意味もないんだって
完全に別のところにCRCは置いておかないと
783デフォルトの名無しさん:2005/07/16(土) 16:09:56
まとめ
・改ざん検知
 >そもそもファイル添付のCRCに頼るな(>782)
・破損検知
 >圧縮前のCRCなんていらんだろ(>780)

「ファイル改ざん+ファイル添付CRC改ざん」でvalidな圧縮ファイルが
理屈の上では作れてしまうので、改ざん検知の用には適さない。

破損検知の観点から考えると、解凍後に「壊れてました」って分かるより
解凍前に分かるほうがよい。解凍後ファイルの信頼性で言えば、そもそも
破損圧縮ファイルを解凍できるのはどうなんだという話になるので、
破損は解凍前に検地するべきだろう。

まとめ方が非常に恣意的になってるけど、個人的にはそんなとこだろうと思う。
既存の圧縮形式を参考にしてもそんなとこじゃないだろうか。
784デフォルトの名無しさん:2005/07/16(土) 18:07:24
>>783
途中に一箇所秀吉が混じってるな
785772:2005/07/16(土) 19:44:20
CRCを別のファイルに置く事はしないつもりです。
それは通信時の手段で、正しくやり取り出来たかを確かめるものですよね?

解凍側からすれば別のプロセスで破損のチェックをしてもらって
その結果をもらう以外には受け取ったデータが正しいのか分からないわけです。
で、その破損チェックのプロセスてのは実際に全てのバイトを読み込んで
照合するしかないはずですから、結局解凍時に同時にやってしまった方が速いですよね。
まぁ、解凍とは別にCRC検査のみの機能も付ける予定ですけど。

改ざんに対してはヘッダの暗号化で対応しようと思っています。
といってもウィルス作成者とかスーパーハカーな人たちにはすぐ破られると思いますけど。
そういうのはあきらめます。

ただCRCよりも効率の良い破損チェックの方法を作れそうな気もするので
他の方法も検討中です。
実は一番困るのは不正データが来たときに
内部でオーバーフローが発生することなんですよね。
暴走する可能性があるんで出来るだけ速くかつ安全な設計にしたいです。
786デフォルトの名無しさん:2005/07/17(日) 01:28:18
>>785
改ざんも検知して防ぎたいの?

圧縮ソフトをバイナリで配布しても、
暗号化ルーチンや鍵などは、あっさり抜かれることがあるわけで。

だったら、特定少数への配布なら秘密鍵、
Webなどでの配布なら公開鍵とわけないとならない。
改ざんうんぬんについては >>783 に同意。
自前で全部実装するの、面倒だよ?
787デフォルトの名無しさん:2005/07/17(日) 17:19:42
「改ざん」って言ってるけどどういう状況を想定しているのか分からない。
元データ受け取り→ファイル改ざん+ファイル添付CRC改ざん
ってやっても、自前で新しく嘘ファイルを作っても何も変わらないじゃん。
つまり、>782
788デフォルトの名無しさん:2005/07/17(日) 17:44:58
>>782
何故何の意味もない事になるのか知りたい…
その理屈だとチェックサムとかパリティビットとかエラーチェックの類の
符号の意味が全てなくなってしまうのだが。
789デフォルトの名無しさん:2005/07/18(月) 00:19:14
>>785-788
質問者は、状況を再報告しる

・破損チェック、修復なら、配布データ中に付記すればよし
・悪意ある第三者から守りたいなら、共通鍵暗号でなければ、外部に情報を分離
790デフォルトの名無しさん:2005/07/18(月) 14:29:28
>>788
チェックサムとかエラーチェックの符号は
人間が雑誌(I/Oとか)に載ってるゲームの
マシン語ダンプリストを手入力するときに
チェックに使ったり、通信路に不安があるとき
に使うもの。
つまり、データが途中で破損したりすることを
検知するのに使われる。
この用途においては本体そのものがCRCを盛ってても
外部に分けておいても効能は大体同じくらい。

意図的な改ざんにおいては本体が盛ってても
しょうがないということを説明すると
嘘のファイルに大してCRCをつけておけば
CRCのチェックは正しいから、嘘なのに
正しくなってしまう
791デフォルトの名無しさん:2005/07/19(火) 23:06:02
そもそも圧縮とは何の関係もないな
792デフォルトの名無しさん:2005/08/31(水) 06:23:49
age
793デフォルトの名無しさん:2005/08/31(水) 06:46:45
自分で圧縮アルゴリズム考えて実装する奴は全員アフォ
794デフォルトの名無しさん:2005/08/31(水) 08:04:33
AA板専用で作れば圧縮率1%ぐらい行く気がする
795デフォルトの名無しさん:2005/08/31(水) 11:28:48
>>793
LZMAとかGCAの作者はアフォですか?
796デフォルトの名無しさん:2005/08/31(水) 12:57:18
少なくともGCAの作者はアフォである
797デフォルトの名無しさん:2005/08/31(水) 17:30:55
それは言えてる
798デフォルトの名無しさん:2005/08/31(水) 17:57:47
GCAって色々叩かれてるけど何で?
799デフォルトの名無しさん:2005/08/31(水) 22:23:45
>>798
半分の理由は作者がおたくだから
もう半分の理由はイースのスレで聞いとくれ
800デフォルトの名無しさん:2005/08/31(水) 23:25:07
最近はGCAじゃなくてDGCAだぞ。拡張子はdgc(デジコ)だ。
今は7z使ってるからどうでもいいが。。。
801デフォルトの名無しさん:2005/08/31(水) 23:56:31
>>799
該当スレで質問してみました。

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

799が教えてくれると一番良いんですが。
802799:2005/09/01(木) 00:23:12
>>801
既に回答されとるぞ(w
803デフォルトの名無しさん:2005/09/01(木) 00:36:25
そっかー
ny擁護か
804デフォルトの名無しさん:2005/09/01(木) 00:44:53
>>803
本人は擁護していないが、擁護していると誤解されたというのが正しい。
805デフォルトの名無しさん:2005/09/01(木) 00:45:36
本人乙
806796:2005/09/01(木) 13:14:35
>>799
その半分についてだけど(イースうんぬんは知らなかった)、おたくだからじゃないな
既知のアルゴリズムを自分が編み出したように流布しているのが問題
807デフォルトの名無しさん:2005/09/01(木) 13:47:24
>>806
どういうアルゴリズムなの?
808デフォルトの名無しさん:2005/09/01(木) 16:15:56
>>806
そんなことはないだろ。
作者はBlockSortingとRangeEncoderを使っていると説明している。
809デフォルトの名無しさん:2005/09/01(木) 17:10:54
>>801
確かにこれじゃアフォといわれても仕方ないな…
810デフォルトの名無しさん:2005/09/01(木) 17:21:21
アレの本当の問題は数年前からのトラブル。ここで全部バラそうか。
811デフォルトの名無しさん:2005/09/01(木) 18:08:12
>>808
それのことじゃない。
スレと関係なくなっちゃうけど飽和演算に関してだ。
812デフォルトの名無しさん:2005/09/01(木) 21:51:40
個人叩きはもういいよ
813デフォルトの名無しさん:2005/09/02(金) 08:40:03
高圧縮率のプログラムは誰でも作れるけど、
ここはひとつ高圧縮率かつ解凍の速い奴たのむわ。
並び替えたり木を作ったりする奴は遅いな。
実用的圧縮率の解凍速度はLZ77系最強?
814デフォルトの名無しさん:2005/09/02(金) 15:44:19
7zip
815デフォルトの名無しさん:2005/09/02(金) 19:52:08
>>813
いろんなアルゴリズムを実験してみたが、
圧縮率と解凍速度は反比例するという結論に達したよ。
LZ77系最強で間違いないと思う。(メモリ喰わない上に展開が速い。)
有名どころが殆どLZ77系なのからも分かると思うが。
zip,lzh,cab,rar,7z...
bzip2は例外か。(でもbzip2はいまいちだと思う。)
圧縮率・展開速度のバランスから考えると最強はcabのlzxかな。

今後cpuのマルチコア化を考えると分散処理のしやすい
BWT系が再び注目されるんじゃないかと思ってる。
816デフォルトの名無しさん:2005/09/03(土) 18:00:26
SBC
http://www.geocities.com/sbcarchiver/
LZ不使用、BWTベースで高速・高圧縮なアーカイバ
817デフォルトの名無しさん:2005/09/07(水) 23:57:23
解凍速度とかメモリ気にしてるのはこのへんかな。

tek - OsaskWiki
http://wiki.osask.jp/?tek
818デフォルトの名無しさん:2005/10/12(水) 02:47:59
保守
819MMR研究所:2005/10/28(金) 13:50:49
或るファイルに措けるハフマン圧縮での限界は、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分のパタン出現順序とも一致しないモデルの筈だ。※

このような前提のファイルを理想ファイルとする。
820MMR研究所:2005/10/28(金) 13:53:31
では仮に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ブロック」の様に成る
821MMR研究所:2005/10/28(金) 13:56:01
と云う事は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デフォルトの名無しさん:2005/10/28(金) 14:09:18
>そこで皆の協力が必要だ
まで読んだ
823MMR研究所:2005/10/28(金) 14:21:51
だだだ、だから要するにポマイラが代わりに作ってください(((( ;゚Д゚)))>>822

出来るんだからな!!ホント何だからな!!!!!
824デフォルトの名無しさん:2005/10/28(金) 14:25:28
シャノンの定理でも読め>>823
825MMR研究所:2005/10/28(金) 14:27:51
そんな欠陥定理はもう読んだ
826デフォルトの名無しさん:2005/10/28(金) 14:30:11
それは可愛いいもうパンダ♪
827デフォルトの名無しさん:2005/10/28(金) 14:33:23
>>823
> 脅威の圧縮率10%を達成した!!!
> そそ、そ、そのソースを此処に書きたいのだが
> だだだ、だから要するにポマイラが代わりに作ってください
お前実際には試してないじゃねーか。すぐバレる嘘をつくからお前はクズなんだよ。
828デフォルトの名無しさん:2005/10/28(金) 14:36:24
>>825
君は、ほらあれだろ、物理板で「相間」をやっているたぐいの人でしょ?
829デフォルトの名無しさん:2005/10/28(金) 14:46:14
圧縮繰り返していたら、何もなくなりました。

(c)鳥肌実
830MMR研究所:2005/10/28(金) 14:59:50
だってソコは解り易くないとと申し訳ないでしょ

ポマイラだってハフマン圧縮での、これ以上縮まない限界状況ってどんなだろう?
って想定した事あるでしょ?

定ビット長の区切ったビットパタンの出現値が全部均一の時じゃないか
だとすればそれを降順でソ-トして差分を取れば、各差分の取る値は収束するだろ?

収束するって事はハフマン圧縮で圧縮し易いって事だよ

ねぇ、誰かつくってYO


対象ファイルをNビット長で区切った場合の、各パタンの出現頻度を実際に計測するアプリで良いからさ

圧縮アルゴリズムを研究する上で、任意のNビット長時のパタン出現頻度を実際に測るアプローチ
って重要でしょ?

ね?ね?ね?
831デフォルトの名無しさん:2005/10/28(金) 15:52:01
>降順でソ-トして

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

ソート済みデータが圧縮できたところで
順番情報と合わせれば圧縮できてない。
832MMR研究所:2005/10/28(金) 15:57:17
だから元の順番を記録したデータもくっ付けるんだYO
833デフォルトの名無しさん:2005/10/28(金) 17:00:42
その記録データがけっこう馬鹿にならないっしょ
初期状態の10%は到底むりぽ
結局計算機負荷の割に効果ナス 無駄にメモリ食うし

とにかく1バイトでも小さくしたいんだって場合にはぎりぎりまで圧縮できるかもだけどさ。
zipのrarみたいなモンでは
834デフォルトの名無しさん:2005/10/28(金) 17:14:20
>>832
> 脅威の圧縮率10%を達成した!!!
> そそ、そ、そのソースを此処に書きたいのだが、余白は余りにも少な過ぎる
御託はいいからさっさとソースうpしてみろよ。

>>833
つーか限界をこえて圧縮された情報(つまり切り捨てられた情報)をソート情報として外に
もちだしてるわけで、それらを足し合わせたら圧縮限界は超えられてない。ただの詭弁。
> zipのrar
zipのrarって何?
835MMR研究所:2005/10/28(金) 17:24:16
特定ファイルに措けるハフマン圧縮アルゴリズムでの限界は
そのアルゴリズムでの限界であって、所謂圧縮限界でもなんでもない
836デフォルトの名無しさん:2005/10/28(金) 17:27:57
>>835
シャノンの定理のどこが欠陥定理なのか書いてみろよ。
お前の頭の方が欠陥脳だろ(プッ
837MMR研究所:2005/10/28(金) 17:32:50
zipで圧縮した後にrarで再圧縮するようなもんでしょ、って事だろ?

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

上手くすれば圧縮済みファイルの方が寧ろ縮んじゃったらどうしよう♪(*/▽\*)って事だよキミィ〜
838デフォルトの名無しさん:2005/10/28(金) 17:51:30
>>835
何言ってるの
情報量が少ないほどよく縮むだけ
音楽ファイルや乱数ファイルは、冗長度が少ないので、可逆圧縮を
しようとすれば、理論的限界がある。完全な乱数なら全く圧縮できない
可能性がある。
839MMR研究所:2005/10/28(金) 17:54:43
シャノンは円の内接正多角形と外接正多角形の外周は極限値で一致するぐらいな事しか云って無いじゃん

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

ファイルサイズは無限じゃないし、1bit未満は最適長の符号化ビット長は与えられないからそもそも画に書いた餅で

ハイハイワロスワロスってヤツだろ
840デフォルトの名無しさん:2005/10/28(金) 17:57:19
>>839
NP完全問題って言葉を知ってるかね?
841デフォルトの名無しさん:2005/10/28(金) 18:04:43
MMRとかいうヴァカは、情報工学を一から勉強した方がいいな。
あ、頭悪いからそれは無理か。
842デフォルトの名無しさん:2005/10/28(金) 18:12:29
>>839


    さ  っ  さ  と  ソ  ー  ス  う  p  し  ろ
843MMR研究所:2005/10/28(金) 18:15:54
だいたい理論的限界ファイルがどんなバイナリなんだよ?
実際どうなってるんだよ?
任意のNbit長で区切って計測したら、そのパタンは偏るのか?偏らないのか?

そもそも圧縮済みファイルだからって理論的限界に全然達してないんじゃないの?
理論的限界に達する究極のアルゴリズムがまだないから数多のアルゴリズムがあるだろ

圧縮済みのファイルですら圧縮限界からは掛け離れてる事を前提にすべきだろ

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

844デフォルトの名無しさん:2005/10/28(金) 18:15:58
「あー馬鹿がよく釣れるなぁ(・∀・)ニヤニヤ」とか思ってるんだろうが、

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

という事実に気づいているんだろうか?
845デフォルトの名無しさん:2005/10/28(金) 18:19:35
>>843
お前の妄想はどうでもいいから、ソース上げてみろって。話はそれからだ。
846デフォルトの名無しさん:2005/10/28(金) 18:21:52
どうせ、ほとんど'0'で、時々まれに'1'が紛れ込んでいるような
バイナリファイルを圧縮して、「おー凄く縮んだ」とか喜んでるだけだろうが。

EAC以上に実用的なCD/DA圧縮プログラムが書けるのか?
847MMR研究所:2005/10/28(金) 18:29:02
だいたいハフマン圧縮の解説サンプルでもテキストの縮みが良いように8bit長なんかで書いてるから駄目なんだよ

その上の、一度ハフマン圧縮したらテキストデータと無関係なbit長だから、
再圧縮ならオーバーヘッドみたいな書き方でさぁ、しかもさも殆ど圧縮限界を達成した風な書き方

それは只そのファイルサイズのそのファイルに措ける当該アルゴリズムの限界だろ

これは生粋の洗脳だ!!!騙されないぞ!!!!!
848デフォルトの名無しさん:2005/10/28(金) 18:31:01
>>847
じゃ、早くその「ファイルサイズ適応型圧縮アルゴリズム選択プログラム」
だけでもいいから、ソースを晒してみろって。
849MMR研究所:2005/10/28(金) 18:31:10
ソースでもショーユでも上げたいがアップローダの余白が少な過ぎる(((( ;゚Д゚)))ガクガクブルブル


さぁー、ポマイラその天才プログラマー振りを発揮してください
850デフォルトの名無しさん:2005/10/28(金) 18:32:10
>>844
どっちもただの時間の浪費だけどな
851デフォルトの名無しさん:2005/10/28(金) 18:36:14
今ム板で一番熱い一番伸びてる痛いスレッズは此処ですか?
852デフォルトの名無しさん:2005/10/28(金) 18:36:22
この手の詐欺師はよく現れるけど、大盛工業のIP携帯ならともかく、圧縮ネタくらい信用されないのはない。

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

853デフォルトの名無しさん:2005/10/28(金) 18:39:00
>>849
アップローダの余白が少なすぎるってどういうことよ

ttp://www.1rk.net/
854デフォルトの名無しさん:2005/10/28(金) 18:43:49
>>843
> そのパタンは偏るのか?偏らないのか?
気づかなかったでしょ?
あらゆる圧縮は何らかの偏りを仮定してるんだよ

> 理論的限界に達する究極のアルゴリズムがまだないから数多のアルゴリズムがあるだろ
気づかなかったでしょ?
圧縮されたり 圧縮されなかったり
あらゆる圧縮は 得手不得手があるんだよ

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

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

君が気づいてくれたのはそれだけだったね
バイバイ
855デフォルトの名無しさん:2005/10/28(金) 18:47:30
こいつ、可逆圧縮と非可逆圧縮を混同しているだけじゃないかと
思えてきた。

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

いずれにしろ、早めに精神病院に逝く事をお勧めするな。
856デフォルトの名無しさん:2005/10/28(金) 18:48:10
何か考えてるみたいだな。
http://etc3.2ch.net/test/read.cgi/bobby/1129128722/153
857デフォルトの名無しさん:2005/10/28(金) 18:53:23
N個の数列が、無理数の小数点以下Y位置からN桁が一致する場所を探す事とする
無理数を任意の方程式の解と考え、方程式の係数と、一致開始位置を記録する事により圧縮する。


例えば素数列Q の平方根でもいい。
858デフォルトの名無しさん:2005/10/28(金) 18:55:52
>>857
着眼点はいいな。後は実用的な速度が出るかどうかだが。
859MMR研究所:2005/10/28(金) 19:00:42
>>853
そ、その手には乗らないぞスパーハッカーめ!!(((( ;゚Д゚)))ガクガクブルブル


>>854
これ以上縮まない理論的圧縮限界に到達したファイルが偏るのか?偏らないのか?
を聞いているんだYO

>あらゆる圧縮は何らかの偏りを仮定してるんだよ、
うん、じゃあこれ以上縮まない理論的圧縮限界と仮定したファイルは全く偏ってないって事だろ?

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

それをNbit長時の出現パタンの均一頻出度、均一分布と仮定するなら
ソートすれば均一頻出度均一分布のデータは、差分が収束するんじゃないか
って事だよ

此処でオーバーヘッドを超えて縮むようなら
それはまだ理論的圧縮限界に到達してなかったって事だし

そこでオーバーヘッドに到達するなら、それはアルゴリズム上の理論限界だって事だろ
860デフォルトの名無しさん:2005/10/28(金) 19:05:07
πには全ての数列が含まれている。 よってサイズとπの一致開始位置で表現すれば、圧縮可能か否か
861デフォルトの名無しさん:2005/10/28(金) 19:11:05
>>859
ソース晒せソース(棒読み)
862デフォルトの名無しさん:2005/10/28(金) 19:28:53
>>857
係数と桁数を記録する領域の方が大きくなるだろ。
ならんようにすると圧縮率が極端に悪くなりそう。
863デフォルトの名無しさん:2005/10/28(金) 19:48:21
全く隔たっていないとは、検出可能な全ての手段を使って隔たっていないという事であり

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

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

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

結論としては、その情報を付加する事によるロスを考えて、そこそこで良いという事になる
864MMR研究所:2005/10/28(金) 19:54:13
キット圧縮限界のファイルってホントはさり気無く偏ってるんだYO

さり気無く偏ってるのにさり気無さ過ぎてどのアルゴリズムでもオーバヘッド
どんなにソートしても収束率が上がらずオーバヘッド

つまり1/f揺らぎなんだYO
865デフォルトの名無しさん:2005/10/28(金) 19:57:07
んなこたぁーナイ
866デフォルトの名無しさん:2005/10/28(金) 20:02:28
まあ、確かに それを吐き出すコードをEXEにすれば1Kで済む データ列1Mを
どの圧縮ツールでも殆ど小さくならないという事はありえるだろうな
867デフォルトの名無しさん:2005/10/28(金) 20:53:13
>>866は多分日本人じゃない。
868デフォルトの名無しさん:2005/10/28(金) 23:16:57
LZSS辺りの最小のデコードルーチンを求めてるのですが
IA32のインストラクションで何バイトぐらいで書けそうですか?
C言語レベルでもデコード部は768バイト以下にはできたので、
アセンブラで記述すればもっと小さくなるかなって。
869デフォルトの名無しさん:2005/10/28(金) 23:21:46
> πには全ての数列が含まれている。
ダウトじゃないかな。
870デフォルトの名無しさん:2005/10/29(土) 07:17:39
線形合同法やM系列乱数にはNビットの0を除いた全ての値が含まれている。よって一致開始位置で表現すれば、圧縮可能か否か

871デフォルトの名無しさん:2005/10/29(土) 07:31:14
まぁ、ちょっとだけ

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

数学的に証明されているのだから、手法的にどうこういっても無駄
限界を超えて圧縮できると主張するなら、元の定理の証明に誤りがあることを示しなさい(^−^)
872デフォルトの名無しさん:2005/10/29(土) 07:58:30
一様分布に見えて、一様分布でない場合もあるんじゃないの?

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

圧縮結果は一様であって、これをさらに圧縮する事は出来ないだろう。
しかし、元のファイルを作ったファイルはサイズ5K。
このサイズ5Kのファイルを実行するだけで復元出来てしまう。
873デフォルトの名無しさん:2005/10/29(土) 09:30:29
ここは考え方を変えて
ファイルのバイナリデータを分割しファイル名にして空のファイルを作成すれば圧縮率99%の圧縮ができる
874デフォルトの名無しさん:2005/10/29(土) 10:09:54
>>872
データを復元するメガデモでも作るのかね?w
875デフォルトの名無しさん:2005/10/29(土) 15:22:41
>>872
どうやったら一様分布でないデータが一様分布に見えますか?
馬鹿だったからってのはナシでお願いします。
876デフォルトの名無しさん:2005/10/29(土) 15:43:14
>>875
 2行目以後が理解出来ないのか?

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

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

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


ここで作成方法を知らない第三者にこのデータを渡すと、一様分布のランダムなデータにしか見えないだろう。
877デフォルトの名無しさん:2005/10/29(土) 16:05:02
結局

 擬似乱数列 ⇒一方向(落とし戸)関数 

というデータ列があった場合、一様分布であっても、
作成アルゴリズムがある以上実際にはもとより短い表現が出来るわけで、これをどう理解する?
878デフォルトの名無しさん:2005/10/29(土) 16:37:03
>>876
二行目が読めませんでしたか?
線形合同法で一様分布の乱数が生成されると思うのは
馬鹿以外にいるのでしょうか、と言ったんですけれど。

なんでデータに「10個平均すれば」なんて条件が付加されてるんでしょうか?
「これを圧縮する」って平均したものからどうやってもとの数字を取り出すんですか?
「作成方法を知らない」とは「馬鹿」の状態であるということが分かってますか?
圧縮限界に近づくほど一様分布に近づくために圧縮が困難になるということが分かりませんか?
879デフォルトの名無しさん:2005/10/29(土) 17:06:35
>>878
 線形合同法は、一様に分布するよ。 なぜなら、結果としてそのサイズの数字を単に並べ替えているだけだからだ。 

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

だよ。

で、最後の1行は理論的には当然で常識だけど、では>>677ならどうだという事だよ。
880デフォルトの名無しさん:2005/10/29(土) 17:58:16
>>879
>  線形合同法は、一様に分布するよ。
一様に分布するといったり偏ってるといったり、一貫性がないな。
二項分布と正規分布の区別くらいつくようになってから出直してくれば?

> で、最後の1行は理論的には当然で常識だけど、では>>677ならどうだという事だよ。
877の「短い表現」とやらをもとの擬似乱数列に戻して見せろよ。
一方向関数を通したものをどうやって復元するのかしらんがなw
881デフォルトの名無しさん:2005/10/29(土) 18:04:32
>>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 の範囲の擬似乱数の十進表記での下一桁を落としたもの
以上の単純かつ分離可能な和でしかない。
882デフォルトの名無しさん:2005/10/29(土) 18:18:13
>>879
線形合同法の出力は、乱数検定にかけると乱数とみなせないとなるはず

数列の任意の順列を圧縮することはできないが、
特定の条件を持った順列は圧縮できるのは明らかなわけで
線形合同法の出力を圧縮できることには何の疑問もない
883デフォルトの名無しさん:2005/10/29(土) 18:25:31
>>879
> で、最後の1行は理論的には当然で常識だけど、では>>677ならどうだという事だよ。

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

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

そのため、実世界での性能が向上していくのは、まだまだ十分余
地がある。
884デフォルトの名無しさん:2005/10/29(土) 19:02:20

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

885?:2005/10/29(土) 19:07:24
??
886デフォルトの名無しさん:2005/10/29(土) 22:15:20
つまり、無理数をバイナリで詰めただけのファイルでも、一般の圧縮ソフトは圧縮出来ない。
でも πを1万桁 てな表示で圧縮出来てしまう。 
あるいは実際に計算するコードを作っても、元ファイルより小さくなる。

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

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

たとえば、ノイズが録音されていると、それ以上圧縮出来ない。
でもノイズを発生した物理法則がカオスなら数式から再現出来る可能性があるんじゃないの?
というわけだ。
887デフォルトの名無しさん:2005/10/29(土) 22:41:50
だからそれが乱数列に条件を加えているだけに過ぎないってことが
どうして理解できんのかな。一般に圧縮はそうやって行われてるっつーの。

そうやって不都合を指摘されるたびに話を逸らしていったところで、お前のしている
数々の間違いの原因を自分で退治していかなければ何も実を結ばないんだってば。
888デフォルトの名無しさん:2005/10/29(土) 22:44:26
??
889デフォルトの名無しさん:2005/10/29(土) 22:47:22
一般の圧縮ってえらいんだな。
890デフォルトの名無しさん:2005/10/29(土) 22:52:43
×ノイズが録音されていると、それ以上圧縮出来ない。
ノイズであっても、振幅というかその分布によって、少しだけ圧縮できます。
891DLC:2005/10/29(土) 23:11:52
新しい圧縮ソフトが出来ます田
http://www.midl.co.jp/DLC/download_dlc_J.htm
892デフォルトの名無しさん:2005/10/30(日) 03:39:57
パイとか、条件を特定しすぎ・・

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

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

周波数分解やwaveletなどを考えてもらえば、わかると思う
893デフォルトの名無しさん:2005/10/30(日) 12:48:06
このスレで、何でもかんでも圧縮は可能と、妄想に浸り混んでいる香具師は、
「理論的に不可能」という言葉を理解できないらしい。

「俺様が可能だと言えば可能なんだ」という世界に入り込んでしまっていて、
誰がどう言おうと訂正不可能のように見える。まさに相間の世界。
こういう香具師の頭の構造は、理系ではなく文系で、それもパラノイアが入って
いるんだろうな。
894MMR研究所:2005/10/30(日) 15:42:50
ハフマン木生成プログラム
ハフマン木の生成過程をある程度ビジュアルに確認できる


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

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

-------------------------------------------------------
これで可変bit長でカウントできたら更にナイスだったのに・・・

でも(・∀・)イイ!
895デフォルトの名無しさん:2005/10/30(日) 15:56:09
>>894
それがどうした
896デフォルトの名無しさん:2005/10/30(日) 15:59:26
>>895
触るな
897MMR研究所:2005/10/30(日) 16:33:06
ちっせぇー事言ってじゃねぇーよ

さっさと落とせよ、さっさと
898デフォルトの名無しさん:2005/10/30(日) 17:58:49
>>897
お前が小さい。人の事言えた義理か( ゚д゚)、ペッ
899デフォルトの名無しさん:2005/10/30(日) 18:25:10
いや、小さくするのが目的なんだが…
900デフォルトの名無しさん:2005/10/30(日) 19:34:15
圧縮前のファイルの数列を作る数式求めてその数式を圧縮すればいいんじゃね?
うわ、俺頭良いwww
901デフォルトの名無しさん:2005/10/30(日) 19:45:52
>>900
君の頭の中には、どうやらラプラスの悪魔が住み着いているようだ。
902デフォルトの名無しさん:2005/10/30(日) 20:19:14
>>894
ビット単位で行う圧縮手法ならいっぱいあるので、
自分でプログラム書けばいいじゃない

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

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


>>900
その数式の記述長が、もとのデータと同程度の長さになるわけだが・・・
903デフォルトの名無しさん:2005/10/30(日) 20:46:57
>>902
> その数式の記述長が、もとのデータと同程度の長さになるわけだが
ある数列に対して複数の式が対応したりすると、むしろサイズは膨らみそう。
904デフォルトの名無しさん:2005/10/31(月) 00:58:32
確率で圧縮するようなやつはありますか?
905デフォルトの名無しさん:2005/10/31(月) 01:03:55
>>904
あほか。氏ね
906デフォルトの名無しさん:2005/10/31(月) 01:20:57
しどいわ。
907デフォルトの名無しさん:2005/10/31(月) 02:40:29
THCompが最強ということで、今回の笑点はお開き
908デフォルトの名無しさん:2005/10/31(月) 09:11:35
>>904
着眼点はいいと思う。つーか、俺も一度考えた。
909デフォルトの名無しさん:2005/10/31(月) 09:31:21
>>904
Huffmanとか算術符号とかではなく、
次の記号が a 1/2 b 1/2 ですよー、というような圧縮法?

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

ただ、結論としては、一意に復号可能で非瞬時な符号に含まれ、
それだったら、同等の瞬時復号符号が構築できるよ、ってなものだったと思う
910デフォルトの名無しさん:2005/11/01(火) 07:46:55
へぇおもしろそうですねぇ。
911デフォルトの名無しさん:2005/11/01(火) 14:10:19
シャノンの定理最強。
912デフォルトの名無しさん:2005/11/04(金) 20:09:35
もしやその確率をうんぬんという手法は、
Laplace推定やKT推定、あるいはCTWのことではないか?

もっと原初に戻ってMDLモデル符号化だったりするとか?
913デフォルトの名無しさん:2005/11/05(土) 15:29:58
乱数で圧縮するって誰かやってたな
914デフォルトの名無しさん:2005/11/05(土) 19:20:01
>>913
俺がπや√で試した時には、100個に1個くらい小さくなったよ。
ただし、ファイルサイズが大きくなればなるほど圧縮できる確率が指数関数的に低下していく罠。
915デフォルトの名無しさん:2005/11/06(日) 04:43:25
>>909
Tunstall符号のことかぁーー
916デフォルトの名無しさん:2005/11/11(金) 08:07:40
>>235
π100万桁とか。

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

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

(ランダムデータではないけど)非常に高圧縮率でしょ?
917うどん ◆7Ue7/4g.1E :2005/11/13(日) 18:09:59
こんなの作ってみました。
でもあんまり小さくならない感じ。
Lcfcomp
http://www.geocities.jp/udon_hp/lcfcomp.html
918デフォルトの名無しさん:2005/11/13(日) 18:38:28
http://compression.ca/act/
見て無いけど、折角だからこれと比較してみたらどうかい。
919 ◆rK6fgwCWsM :2005/11/14(月) 17:38:34
>>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
920うどん ◆7Ue7/4g.1E :2005/11/14(月) 19:42:12
>>918-919
調べてくれてありがとうです。
全体としてはあんまり縮んでないですね^^;
windows xpについてる右クリック、送る、zip と比べるとmp3がまあまあ
いい感じでしたね。時々そのzipより縮んでいるファイルもありました。
921デフォルトの名無しさん:2005/11/14(月) 20:32:47
πはあれとして、任意のnバイトを作るカオスとかならnが小さければ計算できるかも?
で、小さいブロックごとに圧縮とか。すげー時間がかかりそうだけど。
922デフォルトの名無しさん:2005/11/15(火) 08:01:16
>>921
任意のnを生成するのは簡単だ。1ずつ数え上げるループをまわせばよい。
重要なのは、nを指定するためのパラメータの記述も考えなくてはならないということ。

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

したがって、カオスうんうんは、πの圧縮うんぬんと同様、
きわめて狭い範囲では有効かもしれないが、一般には何ら意味がない。
923921:2005/11/15(火) 11:41:45
>>922
そうか、だめか。
924デフォルトの名無しさん:2005/11/15(火) 14:36:24
カオスうんうんって、コーンとわかめとヒジキと蒟蒻が混ざったようなアレか?
925デフォルトの名無しさん:2005/11/18(金) 02:32:54
あげ
926デフォルトの名無しさん:2005/11/18(金) 02:36:56
まつ
927デフォルトの名無しさん:2005/11/22(火) 18:31:02
余談だが、この手の圧縮系のものは「特許だらけ」で、作るほうも
困るのでは?
928デフォルトの名無しさん:2005/11/22(火) 22:05:28
うん。
だから、使う分には、zlibとかに逃げたくなる・・・。
929デフォルトの名無しさん:2005/11/22(火) 22:59:55
「こういうものがあったら便利だろうな」と考えるようなものは
9割9分9厘もうすでにそれ、もしくはそれに類似したものが存在すると思え
930デフォルトの名無しさん:2005/11/24(木) 09:43:08
文句をいわない嫁
931デフォルトの名無しさん:2005/11/26(土) 21:59:00
オレは「1GBのファイルを1MBまで圧縮できないものか?」と
ふと考えてしまう。そんなの不可能だろうが、作れれば、どこぞの
ソフトハウスからお呼びがかかるだろうか?
932デフォルトの名無しさん:2005/11/26(土) 22:10:32
全部同じデータであれば数バイトまで圧縮されるだろうね
933デフォルトの名無しさん:2005/11/28(月) 09:58:25
"データは全部0な10GBのファイル。ファイル名はaaa.dat"
圧縮率一千万分の一以下。
934デフォルトの名無しさん:2005/11/28(月) 10:10:30
>>933
そんなソフトがあればマジで良いよな。巨大ハードのデータが簡単に
持ち出せる。
935デフォルトの名無しさん:2005/11/28(月) 10:23:16
>>934
なにかずれていないか
936デフォルトの名無しさん:2005/11/28(月) 10:24:13
よく考えたらwinnyのハッシュって実用化されたTHCompそのものだよな。
937デフォルトの名無しさん:2005/11/28(月) 21:52:50
>>936
それを言うならURLだって似たようなもんじゃないか
938デフォルトの名無しさん:2005/11/28(月) 22:29:22
urn…いや、何でもない
939デフォルトの名無しさん:2005/12/16(金) 08:12:59
音声圧縮関係について思いついた事あるんだけど、
それもここに書いていいの?
940デフォルトの名無しさん:2005/12/16(金) 09:58:18
もちろん
941デフォルトの名無しさん:2005/12/16(金) 09:59:17
oggよりいいアルゴリズムがあったらぜひキボン
942デフォルトの名無しさん:2005/12/16(金) 12:53:56
後々考えて見るとoggの方が全然縮みそうな気がしてきた…

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

…やっぱり縮むわけないかorz
943デフォルトの名無しさん:2005/12/16(金) 13:08:05
訂正
10進数→16進数
944デフォルトの名無しさん:2005/12/16(金) 19:53:40
音質が変化しない程度なんだったら、それは削ってないってことだよ。
(x,y)というのも分からんが、おそらくADPCMの方が縮むんじゃないかな。
945デフォルトの名無しさん:2005/12/17(土) 04:59:08
>>942
とりあえず、普通にフーリエ変換(DCT)してレートを変えたものを比較対象としてみては?

946デフォルトの名無しさん:2005/12/17(土) 07:23:26
アハハハハ…
思いっきり勉強不足だなこれ…
また本の山に潰されてきます
スレ汚しスマソ
947デフォルトの名無しさん:2005/12/19(月) 07:36:01
各波形の頂点といっても 10KHzの成分は 44.1kだと 2サンプル毎に発生するぞ
948デフォルトの名無しさん:2005/12/19(月) 08:57:07
>>946
ロスレス圧縮のまったく新規な手法は、もはや天才の発明でしかありえないほどだが、
画像音声などのロッシー圧縮では、まだまだいろいろやり方が生まれると思う。

基本をしっかり勉強すると、まずは基本手法の欠点・改善点が見えてくる。
おそらくそれはすでに他人が行っているだろうけれど、自分で理解できることが重要。
新しい論文を読んでも、そういった不備が見えてくるようなら、しめたもの。
他人の手法の改良で論文を書きつつ、新たな手法を開拓することができる。
949デフォルトの名無しさん:2005/12/20(火) 05:31:47
>>948
口だけは達者だなぁ
950デフォルトの名無しさん:2005/12/20(火) 10:40:07
高田純次だな
951デフォルトの名無しさん:2006/01/27(金) 18:28:33
口だけじゃない。
あっちのほうも達者だ。
952デフォルトの名無しさん:2006/02/05(日) 18:56:11
>>868
遅レスすまん。
15年ほど前に実行形式のプログラムが自己展開する奴を作ったことあるけど、アセンブラで116バイトだったよ。
953デフォルトの名無しさん:2006/02/06(月) 03:39:54
>>747
jpegは算術符号が特許の絡みで実装できないため最終段でハフマン圧縮してるらしい。
だからゼロベタの部分はハフマン圧縮しても偏るため、再圧縮が効くときもある。
954デフォルトの名無しさん:2006/02/06(月) 20:24:31
圧縮アルゴリズム考えたぞ!
まずファイルを圧縮して10分割する
一つを相手に送ってその他をCDに焼いて
郵送すれば実質圧縮ファイルの10分の1だ!
よし特許取って来よう。
955デフォルトの名無しさん:2006/02/06(月) 20:34:46
応用すれば元の圧縮ファイルの100分の1や1000分の1
1000000000000000000000000分の1も可能だ!
956デフォルトの名無しさん:2006/02/06(月) 20:42:38
はいはいすごすすごろくす
957デフォルトの名無しさん:2006/02/06(月) 22:15:53
田中彰の応援歌を考えた。

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

俺が考えた歌詞ですよ!
弾丸ライナーだ!の後に「ヘイ!」とか「おい!」って掛け声を入れてスタンドでジャンプするの
とかいれると面白いかもしれない。
958デフォルトの名無しさん:2006/02/06(月) 23:45:48
究極の圧縮&暗号化思いついた!



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

よし特許。
959デフォルトの名無しさん:2006/02/07(火) 02:32:45
>>958
kwsk!!
960デフォルトの名無しさん:2006/02/07(火) 02:41:33
「kwsk」も圧縮だよなー
961デフォルトの名無しさん:2006/02/07(火) 03:24:50
要するに
kuwasiku 鍵=k
→uwasiku 鍵=u
→wasiku 鍵=w
→asiku 鍵=a
→siku 鍵=s
→iku 鍵=i
→ku 鍵=k
→u 鍵=u


って脳で覚えてるだけじゃねーか
962デフォルトの名無しさん:2006/02/07(火) 09:07:21
>>960
そりはハッシュでわ?
というかインデックス?
たまたま衝突が少ないだけ。
kwsk -> 詳しく に1対1で戻せない。
情報が欠落してる。

なんでマジレスしてるんだ漏れ?
963デフォルトの名無しさん:2006/02/07(火) 10:03:24
何そのヘブライ文字
964デフォルトの名無しさん:2006/02/07(火) 18:13:07
>>962
>>961は欠落してないから圧縮なのか?
965デフォルトの名無しさん:2006/02/07(火) 19:42:01
単に記憶領域を変えただけとも言う
966デフォルトの名無しさん:2006/02/07(火) 23:22:49
脳が最適な状態に圧縮
967デフォルトの名無しさん:2006/02/08(水) 00:38:35
脳が最適な状態に委縮
968デフォルトの名無しさん:2006/02/08(水) 00:41:27
詳しく
くわしく
kuwasiku
kwsk     //uaiuの情報はどこへ…

srnnterg?>>961
969デフォルトの名無しさん:2006/02/08(水) 01:28:11
>>962
JPEGが圧縮ではないそうですが、巷にあふれる言説についてコメントをどうぞ。
970デフォルトの名無しさん:2006/02/08(水) 01:33:29
いやいや、このスレという有限状態において、kwskという四文字から生成しうる語句は「詳しく」となる確率が高く、ほぼ1意に復号可能と見做せるのでは?
971デフォルトの名無しさん:2006/02/08(水) 02:08:38
ヒント

日本語ローマ字表記は子音と母音のセット
母音は5種類しかない
意味のある文字列の判定は誰がするか
その意味を記憶している場所はどこか
972デフォルトの名無しさん:2006/02/08(水) 02:10:58
つーかT9
973デフォルトの名無しさん:2006/02/08(水) 02:24:08
>>970
それはkwskが、意味を持たない「記号」の羅列ではなくて、既に意味を持った「記号」となってるから。
つまりそれを解読するには「辞書」が必要。
974デフォルトの名無しさん:2006/02/08(水) 02:59:12
>>973
頭文字の省略という習慣を知ってれば文脈と経験から推測できるよ。
圧縮になぞらえて言うなら、符号化方式さえ分かればおおよそ
複合可能だということだな。
975デフォルトの名無しさん:2006/02/08(水) 07:59:02
おおよそでは復号されたとは言えない。
例え意味のある日本語のリストをあらかじめ辞書として全部持っていても
くわしく、けわしく、かわさき などのどれが正しいかを判定するのは不可能。

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

文脈があればカワサキと書くことも読むこともできる、という意見もあるだろうが
前後の文脈というもの自体もデータなので
それも含めると情報量は増えるがサイズも増える。
なので母音抜き圧縮を辞書無しに文脈と経験で復号できると言うならば
このレスから母音だけで構成される音以外の母音を全部抜いても
次の問いに確実に正解できるはずだ。
immdnnnkikwsktittdsyu?
976デフォルトの名無しさん:2006/02/08(水) 08:04:01
いままでになんかいくわしくといったでしょう?
977デフォルトの名無しさん:2006/02/08(水) 08:11:58
問いは「いままでになんかいかわさこといったでしょう?」
答えは勿論0。一度も川迫なんて言ってない
978デフォルトの名無しさん:2006/02/08(水) 13:58:49
>>975
>969
979魚チョコ:2006/02/08(水) 14:28:24
話ちがうが圧縮の反対でさあ。こういう掲示板で、レスに見えないデーターを
うめこむために全角空白と半角スペースを使って、

全半全 1
全全   0

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

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

これで漢字1字か……。
980デフォルトの名無しさん:2006/02/08(水) 15:55:28
>>978
非可逆圧縮の場合どの程度まで情報欠落を許して
補完で元のデータとどれだけ近い状態になるか、という話になる。

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

そんな可逆圧縮以上のデータ量になるのが容易に予想される
腐った非可逆圧縮は圧縮と呼ばない。ただの言葉遊びと呼ぶ。
981デフォルトの名無しさん:2006/02/08(水) 17:56:50
>>975
つ 記号論

「辞書」は広辞苑とかの辞書じゃないよ。
982魚チョコ:2006/02/08(水) 18:02:15
んあ、まちげーた。

全半全  0
全全    1

だった――って、誰もこんなくすつまんねーレスよまねーか。俺でもよまねーもんな ミ゚仝 ゚ ミ
983デフォルトの名無しさん:2006/02/08(水) 18:07:44
>>980
「詳しく」が「詳細を教えてくれ」を意味するように、「kwsk」は母音抜きとかそういう問題じゃなくて、「詳しく」って意味になってるってことだろ。
だからある種の変換リストを送る側と受ける側が共有してれば、転送する情報量は少なくなるってこと。

厳密には圧縮じゃないけど、kwskは情報欠落してないよ。
それとも>>980は人と会話するときに、たとえば「リモコンをくれ」を言うにしても、
「赤外線で通信することによって、ある程度機械から離れたところから機器を遠隔操作できる端末をとってくれ」
とでも言わないと通じないのか?
984デフォルトの名無しさん:2006/02/08(水) 18:19:21
俺は子音でなく母音を落としてるところにlossy圧縮の形が見えたな
985デフォルトの名無しさん:2006/02/08(水) 18:24:36
だから俺は最初から単なる辞書だろって言ってるってば。

「辞書じゃない 経験と文脈で復号できる」と言う人が居たから
ならば君が言う通り辞書じゃないとすれば、という話をしたところ
そしたら何故かjpegの話を振られたので
ならばlossyとすれば、と話を繋げたわけだよ
986デフォルトの名無しさん:2006/02/08(水) 19:32:04
ただし辞書を使えばそれは圧縮ではないわな
987デフォルトの名無しさん:2006/02/08(水) 21:32:45
>>980

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

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

が、>975は、正しく復号できないなら圧縮じゃないと言う。
データに対する仮定をすることが辞書をもつことだと言う。
キタコレを圧縮するしないにかかわらず事前に共有されている前提の
データ(=文脈と経験)のサイズをktkrのサイズに含めて問題にする。
988デフォルトの名無しさん:2006/02/08(水) 21:36:19
wktk
989デフォルトの名無しさん:2006/02/08(水) 23:20:13
>>987
記号論の本を1億回読んでこい。
意味は辞書と文法によって確定されるもんだ。
経験や文脈は、無意識のうちに辞書や文法に組み込まれているだけ。
990デフォルトの名無しさん:2006/02/08(水) 23:33:38
基礎化
991デフォルトの名無しさん:2006/02/08(水) 23:43:32
>>989
辞書と文法の話で言えばその「組み込む」ってのは
辞書の動的な生成だろ?
復号のために事前に辞書を持ってる、っていう今まで
の「辞書式だ」って話とは合わないだろ。

>>983と考えるなら事前に辞書持ってるってことに
なるけどな。
992デフォルトの名無しさん:2006/02/08(水) 23:50:51
>>1
このスレを圧縮してください。
993デフォルトの名無しさん:2006/02/08(水) 23:55:15
お前はアホ?
相手が全く同一のコードを共有しているわけじゃないのになぜ話が通じるか説明してみな。
994デフォルトの名無しさん:2006/02/08(水) 23:58:13
>>991

事前に「リモコン」という言葉を辞書に持ってる。
動的に生成されるか否かは関係ない。
995デフォルトの名無しさん:2006/02/08(水) 23:59:59
















996デフォルトの名無しさん:2006/02/09(木) 00:03:36
工学土方に、言語学や哲学の概念は理解できません><
997デフォルトの名無しさん:2006/02/09(木) 00:04:16
ksk
998デフォルトの名無しさん:2006/02/09(木) 00:05:00
突然ですが農村の過疎化について語るスレとなりました
999デフォルトの名無しさん:2006/02/09(木) 00:06:08
>>993
通じないこともあるんだよ。馬鹿?

>>994
動的か否かが関係なかったら>985の「辞書じゃなかったら」
なんて仮定が出てくるはずもない。文脈嫁。
1000デフォルトの名無しさん:2006/02/09(木) 00:06:10
テラカワイソス
10011001
このスレッドは1000を超えました。
もう書けないので、新しいスレッドを立ててくださいです。。。