5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

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

1 :デフォルトの名無しさん:2006/04/26(水) 11:57:53
2bit , 3bit , 5bit ずつに頻度を取る。
2bitがいい成績だったら2bitをひとかたまりにして
2ブロック、3ブロック、5ブロックで頻度をとる。
これを繰り返す。

2 :デフォルトの名無しさん:2006/04/26(水) 11:59:11



    ラ  ン  レ  ン  グ  ス  圧  縮  法  最  強


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

3 :デフォルトの名無しさん:2006/04/26(水) 12:00:33
アカデミックにでおk

4 :デフォルトの名無しさん:2006/04/26(水) 12:07:19
圧縮率が最強なのを語ろう

5 :>>1 ハフマン・LZ77から勉強してこい:2006/04/26(水) 12:10:20
>>1
      r;ァ'N;:::::::::::::,ィ/      >::::::::::ヽ
.      〃  ヽル1'´        ∠:::::::::::::::::i
       i′  ___, - ,. = -一   ̄l:::::::::::::::l
.      ! , -==、´r'          l::::::/,ニ.ヽ
      l        _,, -‐''二ゝ  l::::l f゙ヽ |、 ここはお前の日記帳じゃねえんだ
        レー-- 、ヽヾニ-ァ,ニ;=、_   !:::l ) } ト
       ヾ¨'7"ry、`   ー゙='ニ,,,`    }::ヽ(ノ  「ハレ晴レユカイ」でも聞いてろ
:ーゝヽ、     !´ " ̄ 'l,;;;;,,,.、       ,i:::::::ミ
::::::::::::::::ヽ.-‐ ト、 r'_{   __)`ニゝ、  ,,iリ::::::::ミ    
::::::::::::::::::::Vi/l:::V'´;ッ`ニ´ー-ッ-,、:::::`"::::::::::::::;゙ ,  な!
:::::::::::::::::::::::::N. ゙、::::ヾ,.`二ニ´∠,,.i::::::::::::::::::::///
:::::::::::::::::::::::::::::l ヽ;:::::::::::::::::::::::::::::::::::::::::::/ /
::::::::::::::::::::::::::::::! :|.\;::::::::::::::::::::::::::::::/ /

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


6 :デフォルトの名無しさん:2006/04/26(水) 12:14:58
ハフマン、LZぐらい知ってるよ
俺が考えたのは2ビット(1ビットずらしも考える)、
3ビット(1ビット、2ビットずらしも考える)単位で出現頻度を調べて
頻度の高い単語を一纏めにしようというわけだ。

7 :デフォルトの名無しさん:2006/04/26(水) 12:21:39
無理だって
プログラム作ってからこい

8 :デフォルトの名無しさん:2006/04/26(水) 12:30:55
TeXでペーパー作成してから来い

9 :デフォルトの名無しさん:2006/04/26(水) 12:36:55
4bit , 6bit , 8bitは統計をとらなくてよい。
2×2 , 2×3 , 2×2×2で実現されるからだ。
たとえば英語(ASCIIコード)ならば
2ビット→2ブロック→2ブロックがいい頻度を出すだろう。

10 :デフォルトの名無しさん:2006/04/26(水) 12:38:20
ひとまとめって、どこに纏めるつもり?
纏めたはいいけど、複合化するときはどうするの。

11 :デフォルトの名無しさん:2006/04/26(水) 12:39:35
頻度の高いブロックが出続ける間は
2,3,5,7ブロックずつで統計を取る。
最後は、既存の圧縮プログラムで圧縮するんだ。

12 :デフォルトの名無しさん:2006/04/26(水) 12:41:35
>>10
単語辞書を圧縮したもののはじめに記録する。

13 :デフォルトの名無しさん:2006/04/26(水) 12:43:04
おーい早くキンタマーセマティカ君出て来いよ!
単なる糞コテなのかよ!それは

14 :デフォルトの名無しさん:2006/04/26(水) 12:47:57
たとえば110101111011101011101が与えられたとしよう。
a=1101と置換すれば

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


15 :デフォルトの名無しさん:2006/04/26(水) 12:49:02
中学生だろお前

16 :デフォルトの名無しさん:2006/04/26(水) 12:50:10
どの区切りで一単語と見なすかで全体の文字列長が変わってしまうが
その辺はなんとか考えよう。

17 :デフォルトの名無しさん:2006/04/26(水) 12:51:43
ハフマンもLZも名前だけしか知らん様子ですね。

18 :デフォルトの名無しさん:2006/04/26(水) 12:58:15
一般的にはword extraction(wx法)というやつなのだがな。
しかし単語の抽出法は工夫の余地があるはずだ!


19 :デフォルトの名無しさん:2006/04/26(水) 12:59:38
また数学的に無理だと証明されている事をこねくり回す基地外か

20 :デフォルトの名無しさん:2006/04/26(水) 13:02:33
どこに無理だと証明されているんだよ。
頻出単語を少ないbitで表現できれば文字列長が小さくなるだろが!

21 :デフォルトの名無しさん:2006/04/26(水) 13:03:48
動くプログラムを実際に作ってうpしてからこいや>>1

22 :デフォルトの名無しさん:2006/04/26(水) 13:11:50
「考える」だけなら誰でも出来るんだよ。「考える」だけならな。

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

23 :デフォルトの名無しさん:2006/04/26(水) 13:36:57
この場合おもに単語抽出方法を考えればいいわけだ。辞書を使わずに。
一般的にはどのようなアルゴリズムがあるんだ。知ってるか?

24 :デフォルトの名無しさん:2006/04/26(水) 13:56:40
人こないな〜

25 :デフォルトの名無しさん:2006/04/26(水) 14:03:26
高圧縮な単語抽出アルゴリズムが開発できれば
検索エンジンとか宇宙人語とか暗号解読とかに役立ちそうだな。

26 :デフォルトの名無しさん:2006/04/26(水) 17:27:16
1101010111001010101
が与えられたときに
a=1101010111001010101
とすれば
1101010111001010101 → a
と簡略化される

27 :デフォルトの名無しさん:2006/04/26(水) 19:22:23
bzip2最強

28 :デフォルトの名無しさん:2006/04/26(水) 20:22:37
いまのところ、量子圧縮がいちばん有望じゃない?
bit単位の(汎用的な)圧縮アルゴリズムに限界があるのは明らかなんだから。

29 :デフォルトの名無しさん:2006/04/26(水) 20:25:16
>>26
そしたら辞書に本体が必要じゃないか。あまりに大きくしすぎても駄目だと言うことだな。
最低2回は繰り返さないと。

30 :デフォルトの名無しさん:2006/04/26(水) 20:28:06
算術圧縮

31 :デフォルトの名無しさん:2006/04/26(水) 20:38:41
>>28
パソコンが2進数にもとずくんだからそれは無理だ。
現在での最強は?

32 :デフォルトの名無しさん:2006/04/26(水) 20:46:39
何でも量子と言えば何とかなると思ったら大間違いだ!

33 :デフォルトの名無しさん:2006/04/26(水) 20:48:04
漁師コンピューティング

34 :デフォルトの名無しさん:2006/04/26(水) 20:52:13
圧縮しなくても武豊より身長低いのに。

35 :デフォルトの名無しさん:2006/04/26(水) 20:54:46
>>14
じゃぁその文字列aそのものはどうやって保存するんだい?

36 :デフォルトの名無しさん:2006/04/26(水) 20:59:43
>>35
初に単語数を16bitで記録する。次に単語長を16bitで記録する。
次に単語を記録する。以下、単語数になるまで繰り返し。

37 :デフォルトの名無しさん:2006/04/26(水) 21:03:15
単語数 z=3
単語長 x=5 単語 y=11000
単語長 x'=2 単語 y'=01
単語長 x"=6 単語 y"=101011

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

38 :37:2006/04/26(水) 21:08:04
この様に文字列長を縮めてから通常の圧縮ルーチンを起動するんだ。

39 :デフォルトの名無しさん:2006/04/26(水) 21:08:23
>>37
それって最初のデータ13bit(2バイト以下)だよね。
明らかに増えてない?

40 :37:2006/04/26(水) 21:10:17
元のデータが1ギガとかだと辞書はたいしたサイズではない

41 :デフォルトの名無しさん:2006/04/26(水) 21:11:26
元のデータがギガ単位にならなければ圧縮率が高まらないアルゴリズムってどうなんだろ。

42 :37:2006/04/26(水) 21:11:54
あとどの単語に何ビット割り当てるという情報もいるな。

43 :37:2006/04/26(水) 21:12:40
>>41
没に10メガとかでもいいけど。

44 :デフォルトの名無しさん:2006/04/26(水) 21:14:28
>>14,>>35-42
それ以前に最適な辞書を作るアルゴリズムをどうやって作るのかと。

45 :デフォルトの名無しさん:2006/04/26(水) 21:23:24
talk:>>44
「最適な辞書を作るアルゴリズム」を作るアルゴリズムを作れば?

46 :デフォルトの名無しさん:2006/04/26(水) 21:30:39
>>45
頑張って!
影から応援するから

47 :デフォルトの名無しさん:2006/04/26(水) 21:46:24
同じ単語でもどこで切り出すかで長さが変わるんだよな。
少なくとも単語は2bit以上だから2bitから調査しようぜ。
それで00がかなり多いとなったら次に0がくる確率がかなり多いとかなって。

48 :デフォルトの名無しさん:2006/04/26(水) 21:48:37
0001001110000だと単語00の出現回数はいくつにしたらいいんだ?

49 :デフォルトの名無しさん:2006/04/26(水) 22:01:47
>>48
途中の01や111をどう扱うかによって変わるかと。

50 :デフォルトの名無しさん:2006/04/26(水) 22:03:58
talk:>>45
どうやって作るの?

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

51 :デフォルトの名無しさん:2006/04/26(水) 22:18:22
ちょっと前の話だが、いわゆるITバブルだったころ、
「どんなサイズのファイルでも50%に圧縮するアルゴリズムを考え付いた」といって
投資を集めていたやつがいたそうだ。しかもそのアルゴリズムは可逆なのだそうだ。

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

52 :デフォルトの名無しさん:2006/04/26(水) 22:58:37
>>1
まず、詳しい圧縮・伸張方法を説明して、且つその方法が圧縮率や処理速度の点で良い結果を出せそうだ、ということをきっちり説明してくれ。

53 :デフォルトの名無しさん:2006/04/27(木) 00:30:17
>>51
10%じゃなかったっけ?
そういえばどうなったんだろうな。

54 :デフォルトの名無しさん:2006/04/27(木) 01:12:42
どんなビット列、文字列に対しても
辞書部分 + 圧縮部分のサイズがもっとも小さくなるような
アルゴリズムをおまいらが開発するすれ。

55 :デフォルトの名無しさん:2006/04/27(木) 01:47:10
圧縮ファイルをテキストにしてそれを圧縮するを繰り返せばすげぇ圧縮できる。


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

56 :デフォルトの名無しさん:2006/04/27(木) 01:53:48
ブロックソート+BPEでいいんじゃね?

57 :デフォルトの名無しさん:2006/04/27(木) 02:01:05
最強は非可逆だって


58 :デフォルトの名無しさん:2006/04/27(木) 02:14:25
それハッシュ

59 :デフォルトの名無しさん:2006/04/27(木) 02:16:40
>>51
物理ノイズも50%に圧縮するってか。
そりゃ騙されたほうが阿呆ですなあ。

60 :デフォルトの名無しさん:2006/04/27(木) 02:40:56
BPE(Byte Pair Encoding;バイト対符号化)なんていうのがあるのか。
2ブロック限定で辞書作るアルゴリズムだな。
任意のブロックで単語を見つけ出せればいいんだが。

61 :デフォルトの名無しさん:2006/04/27(木) 06:27:03
あんまり関係ない質問で恐縮なんですが、ZIPファイルとかLZHファイル等を
扱う方法などについて詳しく載っているサイトってありますか?

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

62 :デフォルトの名無しさん:2006/04/27(木) 06:39:13
>>61
DLLをつかう。
http://www.csdinc.co.jp/archiver/lib/main.html

63 :デフォルトの名無しさん:2006/04/27(木) 06:42:35
>>62 スマンス、さすがにそれは知ってるけど、それと同じようなことを(自前で)実現するような
手法について調べたいんだけど俺のぐぐりかたがヘタクソでみつからない、ていうお話です

64 :デフォルトの名無しさん:2006/04/27(木) 06:47:37
>>63
DLL作成をぐぐる。

65 :デフォルトの名無しさん:2006/04/27(木) 06:49:28
標準の形式をしりたいということか。

66 :デフォルトの名無しさん:2006/04/27(木) 06:54:47
>>64 うう・・・ぐぐってみたですがよくわからんですorz
>>65 ええ、そんなかんじです

67 :デフォルトの名無しさん:2006/04/27(木) 07:10:39
http://www.iecapc.jp/06/diffusenew/guide/zip.html

68 :デフォルトの名無しさん:2006/04/27(木) 14:06:11
夢を語り合うスレはここですか?

69 :デフォルトの名無しさん:2006/04/27(木) 15:42:59
>37は単語と置き換える記号aを既存の記号と
かぶらせない方策を考えてない中学生。(発想力が)

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

70 :デフォルトの名無しさん:2006/04/27(木) 16:14:04
>>69
なんだと。そんなことは簡単なことだ。
算術圧縮とか、ハフマンのやり方にならえばいいんだ。
ようするに2とおりの表し方がないようにすればいい。

71 :デフォルトの名無しさん:2006/04/27(木) 16:49:24
>>1-70
君らこの辺とかちゃんと読んでる?
  ↓
http://homepage3.nifty.com/DO/algorithm.htm の人のWX法。

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

72 :デフォルトの名無しさん:2006/04/27(木) 19:29:34
>>71
>>18でちゃんと触れられてるぞ。
おまえこそちゃんと読めよw

73 :デフォルトの名無しさん:2006/04/27(木) 20:06:17
いやだから一般的なwx法の話じゃなくて、
ipa でやってた↑のアルゴリズムとか読んでるのって話だよ。

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

74 :デフォルトの名無しさん:2006/04/27(木) 20:39:00
>>73
> 誰一人読んでるようには見えないぞ。
人が読んでいる間にそういうこと言うかね

75 :デフォルトの名無しさん:2006/04/28(金) 10:39:43
11001110の場合。

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

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

76 :デフォルトの名無しさん:2006/04/28(金) 10:41:32
a=110を単語として扱うのがいいな。

77 :デフォルトの名無しさん:2006/04/28(金) 10:43:39
あまりに長い単語は出現しないだろうからソート対象にのは
16bit(16語)まででいいか。

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

79 :デフォルトの名無しさん:2006/04/28(金) 10:51:35
これならソートは必要なくデータ長×最大単語長くらいの時間で頻度が調べられる。

80 :デフォルトの名無しさん:2006/04/28(金) 10:54:19
しかし問題はより長い単語は少ない単語を含むという点だ。
単語が長いほど出現比率は下がるが。
長い方を採用するか、短くて量で勝負かだ。

81 :デフォルトの名無しさん:2006/04/28(金) 10:57:32
まずった。
0001と001と01が同じ配列に収められてしまう。
空を0、0を1、1を2に変換して記録しよう。

82 :デフォルトの名無しさん:2006/04/28(金) 11:04:01
2バイト長の配列を2^27個用意すると256Mバイト必要だ。
3の17乗は約2^27だから17bitまでの単語は登録できるな。

83 :デフォルトの名無しさん:2006/04/28(金) 11:08:39
やってみろよww

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

84 :デフォルトの名無しさん:2006/04/28(金) 12:24:28
>>80
71 のURLの人は、単語の前後の文字のエントロピを見て単語候補を絞り込んでる。
( 0110110 の中の "11" のように)前後が何時も同じときには「単語らしさ」を下げる、と。

85 :デフォルトの名無しさん:2006/04/28(金) 13:49:06
しかし実用的には単語長はいくつくらいになるんだろうか?
テキストならば8bit×5語=40bit、16bit×5語=80bitくらいだろう。
バイナリなら20bit程度なんだろうか。
この程度なら82の様にハッシュが使える。


86 :デフォルトの名無しさん:2006/04/28(金) 14:06:04
そもそも対象のデータによって最適なアルゴリズムは異なるのに、
前提条件を明確にせず、延々と馬鹿を晒し続ける奴ばっかりなのは何故なんだ?

87 :デフォルトの名無しさん:2006/04/28(金) 14:15:13
飛べない豚はただの豚。

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

88 :デフォルトの名無しさん:2006/04/28(金) 14:35:41
内容も理解せずに んなこと言われてもw

89 :デフォルトの名無しさん:2006/04/28(金) 14:48:03
画像圧縮で振幅+矩形ブロックで、そこそこの圧縮率と高速度のもの作って使ってる。
発表する場もないし、ひとりでひっそりと使ってる。時間軸圧縮も作って、やっぱり動画プログラムでこっそり使ってる。


90 :デフォルトの名無しさん:2006/04/28(金) 15:10:24
>>86
最強の称号を手に出来るのは
汎用性のある可逆圧縮だ!
データ種類なんて関係ない。


91 : ◆Dango91bHA :2006/04/28(金) 15:44:57 ?
机上の空論はいいから誰かGCA/DGCAよりイイの作って見たら?

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

92 :デフォルトの名無しさん:2006/04/28(金) 15:53:47
THcompが最強だな。
ttp://thcomp.org/~pen/pfyp/thcomp/THcomp_log.txt

93 :デフォルトの名無しさん:2006/04/28(金) 16:01:43
>>92
出た!THcomp!この手のスレには必ず出てくるな。

94 :デフォルトの名無しさん:2006/04/28(金) 16:06:58
現在世界最強はどのアルゴリズム?

95 :デフォルトの名無しさん:2006/04/28(金) 16:12:39
>>94 URLだろ
たとえば
http://www.google.co.jp/maps?f=q&hl=ja&t=k&om=1&ll=34.944347,134.427681&spn=0.085131,0.113297


96 :デフォルトの名無しさん:2006/04/28(金) 16:16:25
>>94
だからTHcompだってば。
そろそろ8バイトくらい行ってるかなw

97 :デフォルトの名無しさん:2006/04/28(金) 17:45:25
どんな計算機でも圧縮出来ない数がある。
その数は、有限だが計算機により計算する事が出来ない。
しかし、私達はその数を単に一文字で表現する事が出来る。 Ω と

98 :デフォルトの名無しさん:2006/04/28(金) 18:45:58
http://www.ice.nuie.nagoya-u.ac.jp/~h003149b/lang/p/notes/2003_12_04.html

99 :デフォルトの名無しさん:2006/04/28(金) 23:51:38
>>77
16bitだと16語どころか半角で2語しか入らないような。

100 :デフォルトの名無しさん:2006/04/29(土) 03:39:31
バイナリならそんなに16bitもあれば十分。


101 :デフォルトの名無しさん:2006/04/29(土) 03:41:03
バイナリならそんなに16bitもあれば十分。

102 :デフォルトの名無しさん:2006/04/29(土) 03:42:56
ぱくろな!

103 :デフォルトの名無しさん:2006/04/29(土) 13:46:40
ぱくった というより「引っ張った」という表現の方があってるキガス。

104 :デフォルトの名無しさん:2006/04/29(土) 17:31:22
希ガスと言えばヘリウム

105 :デフォルトの名無しさん:2006/04/29(土) 17:53:06
ヘリウムは潤沢にある。尤も、太陽と言う名前で宇宙に転がっているので熱と質量をどうするかが問題だが。

106 :デフォルトの名無しさん:2006/04/29(土) 18:05:16
俺はネオン派。

107 :デフォルトの名無しさん:2006/04/29(土) 20:46:38
僕はキセノン派

108 :デフォルトの名無しさん:2006/04/29(土) 20:47:28
>>107
キセノンって何

109 :デフォルトの名無しさん:2006/04/29(土) 20:50:40
アルゴリズムを発見した。
2進数で16bitまでの単語の頻度を調べる。
5bitの単語が100回現れるとする。その単語を1bitに変換出来たとすると
500bitを100bitに縮められる。400bit分小さくできた。
同じようにすべての単語についてなんbit縮められるか調べる。
もっとも縮められる単語を2とおく。
すると10121102221021などとなる。

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

110 :デフォルトの名無しさん:2006/04/29(土) 20:52:29
>>109
それは2進数に直した時にファイルサイズが膨れそう。

111 :デフォルトの名無しさん:2006/04/29(土) 21:01:51
>>110
それ以前に最初同一データに対して13万通り以上も調べるとなると相当時間がかかる。
あと、縮められなくなるって言うのは同一パターンがまったく含まれない時だけで、
n進数のnにあたる部分が随分大きい時になると思うのだが。

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

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

112 :デフォルトの名無しさん:2006/04/29(土) 21:10:08
>>111
78-82を参考にしてくだされ。ハッシュを使うと簡単かと。

113 :111:2006/04/29(土) 22:08:10
とりあえず2進数を圧縮して3進数にするアルゴリズムは書けた。
あとは3進数を圧縮して4進数にするのと、4進数を2進数に展開して、そいつを8こ組み合わせてファイルに書き出す。
思ったより面倒^^;


114 :・∀・)っ-○●◎:2006/04/29(土) 22:10:26
2進数→4進数のほうが圧倒的に簡単なのになんでわざわざ3進数にすんだよwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww

115 :111:2006/04/29(土) 22:15:53
>>114
そういう仕様。>>109のアイデアを実装しやすいように脳内変換して>>111(自身)が書いた通り。


116 :デフラグさん ◆WaDYW8eWxU :2006/04/29(土) 22:16:02
  [゚д゚] デフラグガカンリョウシマシタ
 /[_]ヽ
  | |
234→うがざざすだでななにににののほよわわんん倒単圧数数数的簡進進進
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww

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

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

CPU:ペンティアム4 3.0GHz

118 :111:2006/04/29(土) 22:24:39
因みに検索のテスト対象はソースファイル(10139Byte)です。

119 :復号してミナー(1/2) ◆fBLOhapji6 :2006/04/29(土) 23:01:10
9:q9)Foe0D~W4|IHgpAe7k^&EzD9x20~xa}e4QXf~}Ce_I$d^Ra#uz#px*A{}`3#
m~}]:rtwdycl|EIJkDByL>EQ={Bu~B<j7CzVX&b%3RO6#t*\HQZqzC)Z3B,7R!!p
l`]xx]f~4\FwfyD\:mr];Ne=m2081?ERp0`TLwYHpzH):yKRhrrs\V%N|h'IV3Do
S|'!%Q'Z!S`q458DrvG5&PLds<9Ml9pxdejH|-\wuFD~SK?`\P~=ep+ij^aNgT7v
woYyYZ+R^\_k&7~<$HEDe?O>Fd~ey:nw{J>|M-f}:T>I@{ZK^O`f:5+\Rlu5~U?\
~Swl#^m?8cmvx2t@{3ldz6D|w#yqn=[pwY&}~UC}3Iu~6bS\31kz%*z#o:?dsJqi
u{Yr=/}){uXu`xiYd>L\Wo3}45fKF]mNP9"u?^sD|`Xq2hyv*Q7\{Zk~xeegkd}c
>~[yN,#fj=*`@5m9yel?b|^Gh/fuO1d}5~~SpWp"+w*VDS@n<ib@:~;}h[VQW0Bd
;yaGS7\^4<qkkx|e.@kloEd-lC@D9fvakkAucOt558+x~L:rkdSs\8\}nPS{sn_b
_]l@~y_J-3>#X({^1[9ox<"3u<|eL/(j&dRl^2~ixGwz#O|?m.d5fz\`uZ1\4q=)
c25My|[f7y1{]>FUF9R=~]Kv..rO~TYt3Dw]Zc},}zZm|x{_$=Feo55(D}61Wm-s
FYQp`E^]b~~to.IObF.QQC~A3xZEsDb;|x^]&y=i.~`JVx/xI~rathp|&xnLw@:0
u:LR*f/6_7^E/L5paC}uyJoUM"i7~VbWwFGN]gKJcWyCH!K}vt}/39Lm.ysW}LNN
q[w+4]j[*o`eU!j:2h[0|zF}k^_~r|/W/"}N(YUvnA{_vPj[V\W3:z~YMk;]X]~:
{=HW+g~f5TVmhd,mIjbk\ZP`u~ik{e^ZaQdog}l8~Us%?<T~cm|nJk'@dE!ot_XK
}vz#l\~U[X{EkUkM~xEb(v{>KY'0VHen\a8~Poz~q~^^w&nGr?-<\gx0kIX&5%~R
TC(\f<<ADM]TucX%C*h~u]g^u\bY6iip|`h[qVKVs|TuCD^SN(kFn[%?{]Wwkp6^
[~Hsua3A1Uuen|-;7n,~p<&HF_vy;+x.D:8'ouudz~9;9df5+qw},Agv<]f36]ZZ
N2Yrhmv?6|L1x^&x'mtTk|2J%tyh_b@#uvW`'P~P~A}+N8#Fx~2QxHVj3lP\|JnT
xgj^i[6{0`=Z4vwWitY&k\bKaN^UL1}/o~2StK?sG~)zjX5g;8fy7(RT`UtxU`Y|


120 :復号してミナー(2/2) ◆fBLOhapji6 :2006/04/29(土) 23:02:34
L8dTnQ.^vMK=wTSg3LLb~{$BMv85+tu+Q}N8?ViG@fBA\,S97!oYjistPx@7K*~`
Tu~@53t6"k:OK&zQTFgLPqZnNhL[G@dKIRzw-1"k~!uw8u9J!\k~~RCG%mcHb1cy
g2J}Vq;nVn=yU|2WOOQz}L*8@n5+9pfWGYr-\lNOF|8IEqe>~o\pz5-|f|c+:C2&
D3Fw|ty]D\]Fc~(lSV}Q$8@|2@]*V_H~P|M=mdS|#A'5)QAdE#B*^~k]%'p[fvu3
N+"jr+}l]G8Ss?n<5!}tuI=uhhnf|6#{M7|k6^N=V?T7<{,"(s;'Sw+iD3Cd/ms8
(3~NO~yvwamsveg_[-^yr=8?URHIsc]Ri8.tYj`q.}`'|<zaM~d[0b3>o-I{{bc]
G9}te,Tqwe*xr-VBKlPv]Y%N}JDD'//J`3_tf~Hv3]q;~qjJ!>u~zc$tt7ZdyE\V
A}R~UyThXw^g~u2t#X,%>b}Pm[sB+N{r>*RE2|_cv,xA1Zs?8v_=0*{'R9v<[fII
.43~[?vZRUX`d;YSz0'y}}q9bx?2st`44`-*{0+Ur&rkb3oU}*\(,xyM={cZ$~$a
VwL*ahfhGe/s}1EwrtjW3"|g*[^0S):iu[;^Q1L;ka?[vY^J};*hIM5x$MO-pAj^
@AEr6BR**<=,Cz}n&<v~bWQARQ{h@[ljUht-lk~y}Q9qmSu~zSPC/>6yBggo(1:~
~4XsRGnf:h:Ka.R|fVx{zpWiq@eV~d2h^x,ZV|fJW^TGm7q|Ua{%*Pz6{NoY7\-L
[n21;r0G&UMxgFs.-mPd.g|<O<wRv+9OhfDAR`9lS*|o~BI{1N={3miyj~lAweiE
7BX%Zshu8Z2=7t;#`:kuTI-zS,Dahyv_gDy=Ke?QBy?mK-<kx>jfVJ}mkd~mxJu~
VL9Tv^j~C|a@sg!!!


121 :ヒント ◆fBLOhapji6 :2006/04/29(土) 23:04:54
・Range Coder
・元はbzip2で圧縮したファイル
・圧縮と言うよりは符号化だな
・デフラグさん上等


122 :デフォルトの名無しさん:2006/04/29(土) 23:06:53
>>119-120
ここは最強の圧縮のアルゴリズムについて話し合う場であり、少なくとも私は暗号化のアルゴリズムについて話し合うつもりはありません。

123 :デフラグさん ◆mRgSYalFkQ :2006/04/30(日) 00:01:14
>>121

  [ ゚д゚]y-一~~~~ デフラグ? ハァ? ヤルキデネェヨ
 ノ[ ヘ ヘ


124 :デフォルトの名無しさん:2006/04/30(日) 00:17:44
bit単位でファイル全部なめるとしゃれにならん時間かかりそうだし
2進→3進変換でさらにしゃれにならん時間かかりそうだし
2進用の辞書、3進用の辞書、4進用の辞書て具合に辞書だらけになって
あまり縮まなそうだな

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


125 :111:2006/04/30(日) 01:18:58
>>124
えぇ。もう16bitまで調べてたらしゃれにもならない時間がかかりましたよ。
10キロバイト引っ掻き回して1時間半くらいでしたかねぇ。


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


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

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


128 :デフォルトの名無しさん:2006/04/30(日) 03:49:38
バイト対符号化より縮まるはずだ!

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

129 :デフォルトの名無しさん:2006/04/30(日) 03:52:48
>>124
一回目の圧縮で辞書に登録するのは最も縮まる2進数1語のみだよ。

130 :デフォルトの名無しさん:2006/04/30(日) 04:01:57
はじめに最も縮まる単語が1101だったとして
次に3進数のビット列で最も縮まる単語が10101(2が出てこない!)
だっとするとこれを3進数として辞書に登録しなければならず
回数を重ねるごとに辞書長は長くなる。

n : 繰り返した回数。

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

131 :デフォルトの名無しさん:2006/04/30(日) 04:59:14
単語の統計の取り方と単語の切り出し方などによって縮まる単語は変わってくる。
例えば、00000だと統計的には単語00が4回出てくるが、実際圧縮してみると
220や022になる。重複している部分があるため2つしか出てこない。

132 :デフォルトの名無しさん:2006/04/30(日) 06:02:12
>>125
16bitなのはハッシュテーブルにそのまま登録できるからという理由なんです。
10Kバイト=80000語だとその16倍(単語長)くらいの繰り返しで回数求められないですか。

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

133 :デフォルトの名無しさん:2006/04/30(日) 12:40:08
  2バイトの配列を(3の16乗)個用意しておけばbit列をそのままハッシュとして登録できる。
って軽く30MB超えるんだけど

134 :デフォルトの名無しさん:2006/04/30(日) 15:15:28
>>133
41メガくらいか。

135 :111:2006/04/30(日) 17:29:16
データサイズが圧縮前より増えた^^;


開発停止しまつ。

136 :デフォルトの名無しさん:2006/04/30(日) 17:52:31
減ることはあっても増えることはないんだよ。
減るまで繰り返すんだから。

137 :デフォルトの名無しさん:2006/04/30(日) 17:57:43
んなこたーない。
どんなに続けようが増えるだけのこともある。

138 :デフォルトの名無しさん:2006/04/30(日) 18:01:05
一回目の圧縮で縮めなかったらそのままなんだよ。
圧縮の定義から。

139 :デフォルトの名無しさん:2006/04/30(日) 18:19:00
全く縮まない完全にランダムなデータはヘッダやらテーブルやらがつく分増える罠。
非圧縮にした所でやはりヘッダをつけざるを得ないし。

140 :デフォルトの名無しさん:2006/05/01(月) 04:30:23
>>139
圧縮ファイルの書式のことではないんだよ。>>109で縮まらなくなるまで
続けるといってるだろ。一回目で縮まらなければ何もしないんだよ。

141 :デフォルトの名無しさん:2006/05/02(火) 00:15:04
辞書は外部に持てばいいんじゃないの?
解凍ソフトと圧縮ソフトで同じテーブルを参照してればよい希ガス

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

142 :111:2006/05/02(火) 01:38:47
>>141
辞書を外部に持ったらデータファイル1バイトにでも圧縮できるさ。
じゃぁその外部辞書ファイルはどうやって圧縮するのかって言う話。

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

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

143 :デフォルトの名無しさん:2006/05/02(火) 03:53:16
>>141
そういうコンセプトの圧縮アルゴリズムはすでにある。
辞書が固定でしかも巨大になってしまうので汎用的ではないが、かなりの高圧縮率を期待できる。

144 :デフォルトの名無しさん:2006/05/02(火) 16:57:10
あらゆる文章は 13 バイトに圧縮可能ってやつ?w


145 :デフォルトの名無しさん:2006/05/02(火) 18:59:10
声自演も

146 :デフォルトの名無しさん:2006/05/02(火) 19:23:43
符号化の基礎は別の所で勉強することを勧める

147 :デフォルトの名無しさん:2006/05/02(火) 22:26:53
ここはDOSもばあああああああああああああああああ

148 :デフォルトの名無しさん:2006/05/02(火) 23:19:47
>>142
>辞書を外部に持ったらデータファイル1バイトにでも圧縮できるさ。
うん?汎用性なくしてどうすんの?
>じゃぁその外部辞書ファイルはどうやって圧縮するのかって言う話。
する必要ないんじゃないの?

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

とかどうですか?

149 :デフォルトの名無しさん:2006/05/02(火) 23:25:39
>1ビットずつ2個書いて16ビットにして一致する部分を探し、見つけたら8bitに置換する。

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

150 :デフォルトの名無しさん:2006/05/03(水) 00:55:18
1010を
11001100にするってことですよ。

151 :デフォルトの名無しさん:2006/05/03(水) 02:24:18
>>148
それって劣化BPEじゃね?

152 :デフォルトの名無しさん:2006/05/03(水) 16:51:46
素人考えだが、画像を圧縮するときの手法を思いついたので聞いてくらさい。
1.輝度の情報を、基色と、それとの誤差に分解。
2.基色をランレングスとかで記録。

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

153 :デフォルトの名無しさん:2006/05/03(水) 17:34:17
画像データは1KB当り1円が相場。
そのツールを公開すれば神になれる。

154 :152:2006/05/03(水) 17:44:25
な、なんだってー!
じゃあ拡張子をjpgにすれば金がワンサカ・・・。

155 :デフォルトの名無しさん:2006/05/03(水) 17:58:16
ただし名画級だとな。

156 :デフォルトの名無しさん:2006/05/03(水) 19:02:22
ファイルサイズを一定にするツールは
セキュリティ上のニーズがあるかも知れんな。
大きいものは小さく、小さいものは大きく。
すべてのファイルを10MBにするとか。

157 :デフォルトの名無しさん:2006/05/03(水) 19:33:47
ファイル分割で十分な気もするが。

158 :デフォルトの名無しさん:2006/05/03(水) 21:38:52
そういやあの頃はフロッピーサイズに分割するツール、重宝してたな。

159 :デフォルトの名無しさん:2006/05/03(水) 22:24:48
今はDVDサイズに分割するツールが重宝してるお。

160 :デフォルトの名無しさん:2006/05/03(水) 22:58:26
>>148
俺が言った「辞書」って言うのは、元ファイルとまったく同等の物。
だから辞書一つにつき2つのファイルを1バイトに圧縮する事ができるが、辞書そのものがなければ復元不可。

161 :デフォルトの名無しさん:2006/05/03(水) 23:26:37
>>160
つまりTHCompもどきだな

162 :デフォルトの名無しさん:2006/05/04(木) 00:02:13
148だけど
>>160
だから、汎用性なくしてどうすんの?
分かってて聞いてるのよ。

163 :デフォルトの名無しさん:2006/05/04(木) 09:08:37
>>161
thcompって、確か圧縮する(そもそも圧縮しないが)ファイルを削除→そのファイルを復元するとかいうネタがあったよね。

164 :デフォルトの名無しさん:2006/05/04(木) 11:43:57
>>163
・DOSの隠しファイルとして、
・WindowsNT系に存在するストリーム機能を利用して、
・数十〜250バイトのファイル内容を、ファイル名にすることで、

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

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

165 :デフォルトの名無しさん:2006/05/04(木) 11:52:34
408kbのデータをたった60バイトに圧縮することに成功しました!
そのデータを以下に示します。デコードはマウスでクリックするだけ!



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

166 :デフォルトの名無しさん:2006/05/04(木) 12:20:51
課題: 
1、どんなプログラムを使っても圧縮出来ない10Mバイトのデータを作成する それより短いコードのプログラムを作成せよ

167 :デフォルトの名無しさん:2006/05/04(木) 12:22:54
課題の補足:
 入力は行ってはいけない。 たとえば外部から乱数等の入力を行ってはいけない。
 擬似乱数を発生させてもかまわまい。



168 :デフォルトの名無しさん:2006/05/04(木) 16:08:54
かまわまい

169 :デフォルトの名無しさん:2006/05/04(木) 16:29:42
【 かまわ - まい 】
『構う』の受動態『かまわ』に、否定『まい』を付けた語句。

170 :デフォルトの名無しさん:2006/05/04(木) 16:36:28
手順:

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

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

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

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

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

171 :デフォルトの名無しさん:2006/05/04(木) 16:47:09
brainfuckでjpeg並のやつ作ったら称えてやるよ。
だからってC++のコードをbfに変換するヤツなんか作るなよ。

172 :デフォルトの名無しさん:2006/05/04(木) 19:04:58
>97=>166,167,170
読んだ雑誌の受け売りしかできんバカは黙ってろよ。

173 :デフォルトの名無しさん:2006/05/11(木) 13:57:04
agg

174 :デフォルトの名無しさん:2006/05/11(木) 19:56:59
>>173
aggwwwwwwwwwwwwwwwwwwwwwwwwwww
ワロタwwww

175 :デフラグさん ◆WaDYW8eWxU :2006/05/11(木) 21:15:39
  [゚д゚]ゝ デフラグツイデニアッシュクシマシタ
 /[_]
  | |
aggw{31}タロ

176 :デフォルトの名無しさん:2006/05/11(木) 21:28:45
寧ろegg

177 :デフォルトの名無しさん:2006/05/11(木) 21:31:59
>>175
ワが消えてるよ

178 :デフォルトの名無しさん:2006/05/11(木) 21:41:30
不可逆圧縮なんで。

179 :デフォルトの名無しさん:2006/05/11(木) 21:45:55
あれ?非可逆圧縮?不可逆圧縮?

180 :デフォルトの名無しさん:2006/05/11(木) 23:47:58
文法的には非可逆圧縮が正しいけど、不可逆圧縮という言葉も割と使われているのでどちらもいいと思う。

181 :デフォルトの名無しさん:2006/05/12(金) 21:44:43
非{可逆圧縮}
不可{逆圧縮}
このように、装飾する区切りが違います。

182 :デフォルトの名無しさん:2006/05/12(金) 21:45:13
修飾だバカボンド

183 :デフォルトの名無しさん:2006/05/13(土) 00:35:00
「(非(可逆))圧縮」だろバカ。

184 :デフォルトの名無しさん:2006/05/13(土) 20:05:44
>>181
逆 に 不可 はつかんよ。

185 :デフォルトの名無しさん:2006/05/13(土) 23:44:27
>>184
じゃぁ所謂「出来なくはない」の類の[否定+逆]の文って一体?



186 :185:2006/05/13(土) 23:46:01
[可能+否定+逆] に訂

187 :デフォルトの名無しさん:2006/05/14(日) 00:04:09
>>181
逆圧縮
ってナニ?

188 :デフォルトの名無しさん:2006/05/14(日) 00:33:43
>>185
そっちじゃなくて、
 不可罰 罰する
 不可能 能う
 不可解 解する
 不可侵 侵す
 不可逆 逆?
という話。つまり言葉としておかしい。

189 :デフォルトの名無しさん:2006/05/14(日) 03:53:49
不可は圧縮にかかる、逆も圧縮にかかる

190 :デフォルトの名無しさん:2006/05/14(日) 04:00:03
可逆は熟語。

191 :デフォルトの名無しさん:2006/05/14(日) 04:04:07
不可は熟語。

192 :デフォルトの名無しさん:2006/05/14(日) 09:41:05
gooに聞いてみた。

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

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

どうしろと

193 :デフォルトの名無しさん:2006/05/14(日) 16:50:09
何だこいつら
頭悪すぎ

194 :デフォルトの名無しさん:2006/05/15(月) 09:09:01
不可逆・非可逆で一単語だろ。
「可逆」というのが熟女

195 :デフォルトの名無しさん:2006/05/15(月) 09:41:02
>>193
おまえはどうなの?

196 :デフォルトの名無しさん:2006/05/15(月) 09:43:53
そろそろ最弱の圧縮アルゴリズムでも語ろうか。

197 :デフォルトの名無しさん:2006/05/15(月) 09:48:26
つ BASE64

198 :デフォルトの名無しさん:2006/05/15(月) 12:51:30
それが圧縮アルゴリズムである限り、最弱は只のアーカイバだろ。

199 :デフォルトの名無しさん:2006/05/15(月) 12:58:31
>>111,135
のが最強だろ。

200 :デフォルトの名無しさん:2006/05/15(月) 22:18:13
萌え

201 :デフォルトの名無しさん:2006/05/16(火) 05:47:32
>>1-200 は圧縮すると 0 bit になりました

202 :デフォルトの名無しさん:2006/05/16(火) 20:39:55
>>201
それじゃ「圧縮」ではなく「消滅」か「無視」の類。

203 :デフラグさん ◆mRgSYalFkQ :2006/05/16(火) 21:55:27
>>1-202

  [゚д゚]ゝ デフラグツイデニアッシュクシマシタ
 /[_]
  | |
"{2}({53}){53}+{2},{5}-{2}.{6}/{112}0{252}1{179}2{123}3{63}4{72}5{116}6{94}7{36}8{39}9{37}:{107}=>{47}?AB{4}C{3}D{4}E{
2}HKMNOP{2}S{2}T{2}U{2}VW{4}Y[{57}]{57}a{59}b{10}c{7}d{4}e{56}f{2}g{60}h{6}i{14}j{3}k{3}l{4}m{4}n{4}o{10}p{9}r{3}s{57}t
{13}u{2}vw{4}xz{|{2}}~ュッアイカク{2}シ{3}タ{3}ツテ{2}トニハフホマラロ{2}ワ{2}ン゙{6}゚{2}、{33}。{53},・{7}:{109}?{9}!{3}_ゝ々ー{31}
〜({5}){5}〔〕{{2}}{2}「{7}」{7}『{3}』{3}【{3}】{3}+{3}◆→{4}⇔1{3}Mw{32}ぁあ{12}い{43}う{20}え{7}お{4}か{34}が{28}き{11}
ぎ{3}く{13}け{9}こ{7}ごさ{57}ざし{77}じ{5}す{39}ずせ{4}そ{17}た{25}だ{20}ち{2}っ{24}つ{11}て{36}で{22}と{28}ど{12}な{32}
に{37}ね{2}の{103}は{31}ば{6}ひべ{2}ま{20}み{5}め{3}も{16}ゃ{7}や{5}ゅゆよ{18}ら{11}り{21}る{52}れ{16}ろ{11}わ{6}を{
40}ん{60}ァ{12}ア{7}ィイ{29}ウエ{2}ォ{50}カ{8}キク{8}グ{7}コ{7}ゴ{2}サ{6}シ{2}ジス{5}ズ{8}セタ{7}ダッ{7}ツ{5}テデ{57}ト{5
9}ド{7}ナ{3}ニ{2}ネバ{11}ピ{2}フ{64}ブ{3}プ{7}ポマミ{2}ム{9}メ{2}モ{2}ヤュ{3}ョラ{8}リ{9}ル{72}レ{7}ロ{11}ワン{7}д悪圧{
28}以{3}謂違一{4}隠永円遠俺下{2}化何{2}可{26}火{2}課{2}画{3}解{3}開外拡確{3}割{4}完換間陥基{2}岐{2}機気記輝
擬{2}義{2}逆{23}求級強局金{3}句区空繰系{2}結月{7}見元{6}言{4}限{2}後{3}語{5}誤公功構稿{53}考行{5}合頃今差
最{3}在作{5}削雑参{2}使{2}子思{3}止{3}視誌事{3}似{2}時示辞{3}式実{3}弱{2}取手{4}受{2}修終十{2}重{2}縮{28}熟{3}
出{7}順{5}所書{4}女除小{4}消{2}照{2}称上場情飾{2}色{2}侵{2}神人水{12}数{5}性成{6}正生{3}績切先{2}前{55}然全{2
}素組相装像{2}足存体{2}態大{4}題{2}只単短知張調停{3}定{6}提程訂的点度{4}土{4}投{53}当{3}等{2}頭{3}動{2}同{2}
得読内日{60}入{2}寧能{4}売発罰{2}判汎否{3}非{6}頻{2}不{15}付部復{3}物分{8}文{2}聞{3}並変返補報宝{2}方{3}法{2
}萌本埋未{2}無{52}名{105}命{3}明滅木{19}黙目戻容{2}用{3}葉{2}来{6}乱{3}利率{2}了量力{3}類{2}令{3}劣録話{2}

204 :デフォルトの名無しさん:2006/05/16(火) 22:27:26
>>203
実はかなり適当?

205 :デフォルトの名無しさん:2006/05/17(水) 03:44:22
テキストの非可逆圧縮というか、情報縮約というか、
単に出現回数を数えただけじゃないか?しかも、不正確に

206 :デフォルトの名無しさん:2006/05/17(水) 21:43:01
不可逆でいいんならいくらでも可能

207 :デフォルトの名無しさん:2006/05/18(木) 18:55:19
非可逆でいいならどんなデータでも1バイトに圧縮(縮小)できるが。

208 :デフォルトの名無しさん:2006/05/18(木) 19:06:33
>>205
「曖昧」と言うものはなかなか難しい。

209 :デフォルトの名無しさん:2006/05/19(金) 14:10:01
>>207
じゃあ漏れは0バイトに。

210 :デフォルトの名無しさん:2006/05/19(金) 14:19:59
>>208
不正確なら簡単だ

211 :デフォルトの名無しさん:2006/05/19(金) 18:09:23
>>210
ところが、情報理論的に不正確さも決められているので、
闇雲に情報を削除していけばよいということでもない。

212 :デフォルトの名無しさん:2006/05/19(金) 18:52:01
>>209
消去じゃん。

213 :デフォルトの名無しさん:2006/05/22(月) 02:22:26
昔いろんな圧縮形式の圧縮率比べまくったなぁ。
画像の可逆圧縮とか、個人で作ってる形式多くて楽しかった。
PNGしょぼいよ!!とか、PIC2つえええとか、TLG6すげえなにこれ!とか

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

215 :デフォルトの名無しさん:2006/05/22(月) 17:58:53
意味を解釈するプログラムのサイズが馬鹿でかくなる

216 :デフォルトの名無しさん:2006/05/22(月) 19:07:35
プログラムが意味を解釈する必要は無い。
記録する情報は、記録者の脳内ニューロンの繋がり(語句)を集めたもの(文章)だからだ。

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

誰か作ってくれ。

218 :デフォルトの名無しさん:2006/05/22(月) 19:12:06
age

219 :デフォルトの名無しさん:2006/05/22(月) 21:07:26
>>217
その「特殊な開始コード」に必要なビットが、バカにならんのよ。
無圧縮部分に圧縮されていない印を付けると言うことは、その部分で
データが膨らんでいると言うことだから。

220 :デフォルトの名無しさん:2006/05/22(月) 21:25:38
>>217
ASCII文書で有効文字が7750とか、もう言ってる事がめちゃくちゃ。
人格も発言内容も否定したくは無いが、会話の土台を築くために
まずは "ASCII CODE"とかの意味を調べてくれ。

221 :デフォルトの名無しさん:2006/05/22(月) 22:29:46
まあアルファベットと空白だけの文章なら一文字7bitでいけるけど、
ってそういうことを言いたかったんじゃないのか。

222 :デフォルトの名無しさん:2006/05/22(月) 22:38:31
6bitでいけるわボケ
アホは黙ってろ

223 :デフォルトの名無しさん:2006/05/22(月) 22:54:01
>>220
言いたいことの意味はわかるが「会話」じゃなくて「対話」な、
この場合。

224 :デフォルトの名無しさん:2006/05/22(月) 23:26:02
>>223
脳内定義持ち出してまで
なにを必死になってるんだろう。
とりあえず辞書引け。

225 :デフォルトの名無しさん:2006/05/23(火) 00:22:40
俺が実践している最強の画像圧縮アルゴリズム

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

226 :デフォルトの名無しさん:2006/05/23(火) 00:41:59
抜けない画像は削除
これで5%くらいまで非可逆圧縮できますよ

227 :デフォルトの名無しさん:2006/05/26(金) 07:18:06
>>225
それ、すこしでも「つぼ」間違えたらぜんぜん違うファイルにならないか?

つか保守&アゲ

228 :デフォルトの名無しさん:2006/05/26(金) 09:35:52
なんでも全部0xffに縮めて、相手が怒ってきたら謝ればいいんだよ。

229 :デフォルトの名無しさん:2006/05/26(金) 16:59:36
【IT】米Microsoft、新画像フォーマット「Windows Media Photo」発表
http://news18.2ch.net/test/read.cgi/bizplus/1148626281/

230 :デフォルトの名無しさん:2006/05/26(金) 20:07:33
>>152
写真とかだとさ、大体色の同じような場所は固まってるよね。
だからこの圧縮方法結構使えるんじゃね?

231 :デフォルトの名無しさん:2006/05/26(金) 20:43:17
1ドット単位のチェック柄の画像(ディザとか)で死亡

232 :デフォルトの名無しさん:2006/05/27(土) 00:40:30
画像で圧縮率がいいのはTLG6かな。
場合によってはERIやJPEG2000が上の場合もあるけど。

233 : ◆NEVADAi.iI :2006/05/27(土) 09:13:17
例えば、下の2行を圧縮するとき


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

89 E6 91 9C 82 C5 88 B3 8F 6B 97 A6 82 AA 82 A2
82 A2 82 CC 82 CD 54 4C 47 36 82 A9 82 C8 81 42
0D 0A 8F EA 8D 87 82 C9 82 E6 82 C1 82 C4 82 CD
45 52 49 82 E2 4A 50 45 47 32 30 30 30 82 AA 8F
E3 82 CC 8F EA 8D 87 82 E0 82 A0 82 E9 82 AF 82
C7 81 42 0D 0A

というバイト列を 16(任意だけど固定) づつまとめて


234 :デフォルトの名無しさん:2006/05/27(土) 09:14:27
89 10001001
E6 11100110
91 10010001
9C 10011100
82 10000010
C5 11000101
88 10001000
B3 10110011

8F 10001111
6B 01101011
97 10010111
A6 10100110
82 10000010
AA 10101010
82 10000010
A2 10100010

縦と横を並べ替えて

11111111 10111111
01000100 01000000
01000001 01010101
00110001 00100000
10010010 11000100
01010100 10110000
01001001 11111111
10100101 11100000

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

235 :デフォルトの名無しさん:2006/05/27(土) 14:49:20
>>233-234
文字が全部全角文字なら圧縮率が上がる可能性は十分考えられる。
半角文字列ならあんまり変わんないと思う。

236 :デフォルトの名無しさん:2006/05/27(土) 15:06:21
>>235
最上位ビットに規則性が生まれることに違いはないから改善するんでね?

237 :デフォルトの名無しさん:2006/05/27(土) 15:15:28
普通にやるより 7/8になるという主張?

238 :デフォルトの名無しさん:2006/05/27(土) 17:04:31
>>233-234
を、16づつまとめるのはめんどくさいから、全部一気に縦横並べ替えたやつを作った
何もしてないやつとZIP圧縮で比べた。データは日本国憲法

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

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

239 :デフォルトの名無しさん:2006/05/27(土) 17:32:17
そんなことしたらある文字が前後の状態で違う文字になっちゃう。
一意性がなくなって、ある時は「日本」だったのにいきなり「某国」とか。
ビット単位で変換したんなら符号化もビット単位で見ていかないと圧縮できないよ。

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

240 :デフォルトの名無しさん:2006/05/27(土) 17:41:57
俺も手を動かしてたんだが>>238に先を越された
やっぱり圧縮率下がるよなぁ

241 :デフォルトの名無しさん:2006/05/27(土) 18:51:54
16づつまとめるのがミソなんじゃないでしょうか?

242 :デフォルトの名無しさん:2006/05/27(土) 18:54:07
誰か、組み込み系で圧縮アルゴリズム使ってる人いますか?
たとえば、ログをメモリに格納する時とか
LANなどでデータを送る際に圧縮しておくるとか
組み込み系ですから、圧縮率も重要ですが、なによりも速度重視のアルゴリズムを
考える必要があるのでしょうかね?


243 :デフォルトの名無しさん:2006/05/27(土) 19:11:07
>>241
並び順が変わるだけで大して違わないんじゃね?
16バイトで割り切れないサイズの時の処理とかめんどくさいし

244 :デフォルトの名無しさん:2006/05/27(土) 19:18:01
>>242
ハードウェア圧縮なら普通にすると思う

245 :デフォルトの名無しさん:2006/05/27(土) 20:12:34
>>238
ZIP以外の形式でも調査キボン

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

246 :デフォルトの名無しさん:2006/05/27(土) 20:21:01
ホワイトノイズになってしまうっていう点で思いついたんだが

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

247 :デフォルトの名無しさん:2006/05/27(土) 21:27:20
>>246
やってみれ

248 :デフォルトの名無しさん:2006/05/27(土) 22:54:42
圧縮に関してはわからない素人ですが
テキストだろうが音だろうが画像だろうが、所詮0と1のデータですよね?

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

249 :デフォルトの名無しさん:2006/05/27(土) 23:37:21
ハフマン

250 :デフォルトの名無しさん:2006/05/27(土) 23:43:56
愛しのドレッドゾンビたんキタコレ

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

251 :デフォルトの名無しさん:2006/05/27(土) 23:44:29
激しく誤爆すいません

252 :デフォルトの名無しさん:2006/05/28(日) 00:06:44
>>248
それを討論中

253 :デフォルトの名無しさん:2006/05/28(日) 00:30:47
>>248
ありません。

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


254 :デフォルトの名無しさん:2006/05/28(日) 10:24:31
>>248
あるよ。任意のサーバーにファイルをうpしてURLを晒せばいいのさ

255 :デフォルトの名無しさん:2006/05/28(日) 10:27:28
ここで語る圧縮はやはり可逆なものに限られますか

256 :デフォルトの名無しさん:2006/05/28(日) 14:33:03 ?
辞書を毎回生成すれば
大容量の辞書を持つ必要はない

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

257 :デフォルトの名無しさん:2006/05/28(日) 19:39:14
メモリの中身を圧縮するという意味では、
バイナリデータに特化した圧縮アルゴリズムを考えればいいのでしょうか?

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

258 :デフォルトの名無しさん:2006/05/28(日) 19:41:32
組み込み系で圧縮を考えると、最悪でも数ms、できればμsの時間で
処理しないと、いけないですよね?

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

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

259 :デフォルトの名無しさん:2006/05/28(日) 19:54:16
はてなマーク多いな

260 :デフォルトの名無しさん:2006/05/28(日) 20:09:17
なんかずれてるな。
メモリの中身が判らないのに向いてるも何もあったもんじゃない。
そもそもメモリとファイルで違いなんかないだろ。

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

261 :デフォルトの名無しさん:2006/05/28(日) 23:54:18
>>257
>バイナリデータに特化した圧縮アルゴリズムを考えればいいのでしょうか?
PC で扱えるデータは「全て」」バイナリデータですよ。

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

262 :デフォルトの名無しさん:2006/05/29(月) 19:53:12
LANコントローラあたりの設計だと、圧縮していたような・・・
忘れた。

263 :デフォルトの名無しさん:2006/05/30(火) 20:53:24
ZigZagスキャンでもしとけよw

264 :デフォルトの名無しさん:2006/05/31(水) 01:21:55
なつかしの540アルゴリズム

「aaaaababababcabc」
 ↓
a:aaaaabbbbb
b:aaacc
c:a
 ↓
「aaaaabbbbbaaacca」
 ↓MTF
「a0000b0000100c01」
 ↓適当にエントロピー圧縮。
(゚д゚)ウマー

265 :デフォルトの名無しさん:2006/06/03(土) 14:13:13
ホシュ

266 :デフォルトの名無しさん:2006/06/05(月) 05:39:33
>>258
モデムのデータ圧縮


267 :デフォルトの名無しさん:2006/06/09(金) 04:39:23
ところで、結局>>1のビット羅列による圧縮はFA出たの?
モレ昔ハフマン圧縮勉強した直後の頃に似たようなこと考えたことあった。
最終的には、ファイルを"0"(0x30)と"1"(0x31)に変換してから普通に辞書圧縮したら論理的に近似可能だということに気付いた。
で詳細は忘れたが、実際にやってみて(´・ω・`)ショボーンだった記憶がある。

FAが出たなら知りたひ・・・

268 :デフォルトの名無しさん:2006/06/09(金) 08:47:12
FAという訳ではないんだが一応答えらしきものを示しておこうか。

一般に辞書との一致で置き換えるアルゴリズムは圧縮率が悪い。
何故か?
今、abc...bcd...abcdという文字列があったとする。
3つ目のabcdを符号化したい。
選択肢としてabc|dとすることも出来るし、
またはa|bcdとすることも出来る。
場合によってはa|b|c|dとしてもいい。
そしてこれらの選択肢は全て結果が等しい、つまり等価なわけだ。
同じ結果に対して別の選択肢が存在するという事は、
それはつまり冗長だということになる。
等価であるならば一つに纏めて確率を上げなければならない。

極端な例を挙げるとすると、纏め(られ)ないということは、
aaaabbbcという文字列があって、これの確率を求めた時に、
1. a 3/8
2. a 1/8
3. b 3/8
4. c 1/8
このような状態になってしまうことを意味するわけだ。
'a'を符号化する時に1,2のどちらを選んでも結果は等しい。
しかしこの時、'a'の確率は4/8でなくてはいけない。
しかし実際には分かれてしまっているため、1の'a'を選んで符号化しなければならず、
'a'一文字につき1/8ずつ無駄を増やしているということになる。

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

269 :デフォルトの名無しさん:2006/06/09(金) 22:29:04
ここでいう最強は
圧縮率がよいアルゴリズム?
それとも同じ圧縮率でも高速なアルゴリズム?
それとも実装が簡単でそこそこ高速かつ圧縮率のよいアルゴリズム?

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

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

270 :デフォルトの名無しさん:2006/06/09(金) 23:41:22
>>267
>>111が圧縮率の悪さに唖然として開発停止して以来誰も作り出すような発言や完成したような発言はしていないように思うがどうか。

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

271 :デフォルトの名無しさん:2006/06/10(土) 03:34:17
BlockSort+適応型符号化でいいような。
何が最強かも定義がわからんし。

272 :デフォルトの名無しさん:2006/06/22(木) 21:08:18
スレ違いなのはわかっています。
ですが教えてもらえないでしょうか?

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

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

274 :デフォルトの名無しさん:2006/06/23(金) 01:01:16
わかりました。
他のスレを探してみます。
スレタイからして実際にしようとした人とか
詳しい人が多そうとか思っちゃいました。

275 :デフォルトの名無しさん:2006/06/23(金) 01:05:23
いやだから、鼬害だってばさ。

276 :デフォルトの名無しさん:2006/06/26(月) 12:01:57
ネットにデータをうpってハッシュ値をURLにすればよい

277 :デフォルトの名無しさん:2006/06/27(火) 06:50:57
http://live23.2ch.net/test/read.cgi/livecx/1151356052/

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

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

278 :デフォルトの名無しさん:2006/06/27(火) 07:28:48
間違っても最強にしちゃいかんな
むしろ元サイズより増えるくらいでいいんじゃね?

279 :デフォルトの名無しさん:2006/07/01(土) 12:02:56
G Compression Archiverはどう?

280 :デフォルトの名無しさん:2006/07/03(月) 06:25:40
鼬害だって言ってるだろ、池沼か?

281 :デフォルトの名無しさん:2006/07/09(日) 03:19:12
>>278
まぁ、どんなファイルに対してもサイズを縮めることができるような可逆圧縮は存在しないからなぁ。

282 :デフォルトの名無しさん:2006/07/09(日) 16:54:18
つまり、元サイズより大きくなるのが合理的だ、と?

283 :デフォルトの名無しさん:2006/07/10(月) 08:55:58
そうだけど?
究極的には圧縮はただの変換(写像)だから、
「元のサイズ+適用したかしないかの1bit」が最小の期待値になる。

284 :デフォルトの名無しさん:2006/07/10(月) 23:24:00
>>278
無圧縮圧縮を思い出した。


285 :デフォルトの名無しさん:2006/07/26(水) 09:52:03
http://72.14.235.104/search?q=cache:z5jvOgJbrB0J:download.microsoft.com/download/1/6/a/16acc601-1b7a-42ad-8d4e-4f0aa156ec3e/WMPhotoSpec_v10.doc+WMPhotoSpec_v10.doc&hl=ja&gl=jp&ct=clnk&cd=1&client=firefox

286 :デフォルトの名無しさん:2006/09/04(月) 22:09:10
保守

287 :デフォルトの名無しさん:2006/09/30(土) 17:21:29
あげあげ

288 :デフォルトの名無しさん:2006/10/09(月) 17:34:23
圧縮のアルゴリズムって特許とか色々ありすぎ。
何を使って作ったらいいのかわからん

289 :デフォルトの名無しさん:2006/10/09(月) 17:52:55
誰も思いつかないような新しい方法を考えればいいんじゃね?

290 :デフォルトの名無しさん:2006/10/09(月) 18:45:00
>>289
その発想は無かったわ。

291 :デフォルトの名無しさん:2006/10/09(月) 19:03:06
もう、出尽くしてない?

292 :デフォルトの名無しさん:2006/10/09(月) 19:06:54
いつの時代も雑魚はそう言う。
そしてコロンブスに卵で殴り殺されるんだ。

293 :デフォルトの名無しさん:2006/10/09(月) 20:15:26
量子コンピュータやDNAコンピュータで使えるアルゴリズムという
未開拓な分野もあるぞ


294 :デフォルトの名無しさん:2006/10/09(月) 21:38:11
paq8とかlzmaとかtek5辺りのハードウェアアクセラレータまだー?
apache/firefoxで使えるようになるのはいつー?

295 :デフォルトの名無しさん:2006/10/11(水) 11:48:18
誰も思いついていないような新しい方法

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

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


296 :デフォルトの名無しさん:2006/10/11(水) 12:29:20
2. が無理だと思われ

297 :デフォルトの名無しさん:2006/10/11(水) 13:22:13
>>296
πを何千桁も覚える人がいるんだからいつかそのうちできるようになるさ。
なんだったら事前に bzip2 圧縮して小さくしておけばf;ぇkwlけ2いfそb


298 :デフォルトの名無しさん:2006/10/11(水) 13:39:40
>>297
π は 10 桁。
http://www.f7.dion.ne.jp/~moorend/news/2005020901.html

299 :デフォルトの名無しさん:2006/10/12(木) 22:38:29
>>295
人間という外部記憶装置に保存するわけですな

300 :デフォルトの名無しさん:2006/10/12(木) 22:53:09
それはしんどいですな

301 :デフォルトの名無しさん:2006/10/13(金) 03:54:09
そうだ、紙に穴を開けて保存するのはどうだろう?
オルゴールと同じ原理だ。

302 :デフォルトの名無しさん:2006/10/13(金) 04:01:14
鉛筆で書けば消せるし、また書けるよ!

303 :デフォルトの名無しさん:2006/10/13(金) 05:39:49
もはや圧縮アルゴリズムではないなw

304 :デフォルトの名無しさん:2006/10/13(金) 05:51:03
任意・ランダムで生成される32ビット情報を
24(または23)ビットにまでビット幅を圧縮してみて下さい。
intの値をfloatの仮数に埋め込みます。

305 :デフォルトの名無しさん:2006/10/13(金) 12:54:04
>>304
それ何の意味があるの?
#そもそも無理だし。

306 :デフォルトの名無しさん:2006/10/13(金) 14:12:44
意味があるかよりも、32bitを24bitに圧縮する方法ってことでしょ?
32bitが特定(や有限・決まっている)の値なら簡単なんだけどね。

307 :デフォルトの名無しさん:2006/10/13(金) 16:38:42
いやだから、24ビットに圧縮しても32ビットの空間を消費するなら意味ないじゃん。

308 :デフォルトの名無しさん:2006/10/13(金) 17:03:47
上位8ビットが非ゼロならば、情報源を含むその辺り(空間的に)の
機械や生き物が破壊されてしまうようなシステムを構築すれば良い。
表現できないものは無かったことにするという圧縮方法。

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

309 :デフォルトの名無しさん:2006/10/13(金) 17:19:37
>>304
xが32ビット整数だとして、C言語で書くと
x = (x >> 8) & 0x00ffffff;
但し不可逆。

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


310 :デフォルトの名無しさん:2006/10/14(土) 01:13:45
>>308-309
y=x & 0x00FFFFFF
これで x の8ビットを違うアルゴリズム処理すれば良さそう。
当然可逆圧縮・復元できないと意味ないけど、
残り8ビットは256通りだから、そんなに不可能ってほどでもない。

311 :デフォルトの名無しさん:2006/10/14(土) 01:31:40
32*3 = 24*4
詰めかえるだけなら圧縮とは言わないが。
前提が無いと、できるともできないともいえない。


312 :デフォルトの名無しさん:2006/10/14(土) 01:44:38
>>311

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

コラ!
ウソ言っちゃいかんにょ。

313 :デフォルトの名無しさん:2006/10/14(土) 04:35:39
>>312
いわねーよ

314 :デフォルトの名無しさん:2006/10/14(土) 22:56:30
>>313
置き換えで圧縮する、固定長符号化もたまには思い出してください(つД・)

315 :デフォルトの名無しさん:2006/10/14(土) 22:57:34
符号化

316 :デフォルトの名無しさん:2006/10/15(日) 02:35:52
>>314
任意の固定長符号で置き換えるなんて話お前しかしてねーよ

317 :デフォルトの名無しさん:2006/10/15(日) 09:22:11
なんというか問題が難しかったようですね。
int32の情報ををfloatの仮数に埋め込むというのは一例です。
intで表現される色情報 a|r|g|b を24bit構造体 struct Enc_T {char val[3];}に
埋め込むとか考えると、やる気出ますか?

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

318 :デフォルトの名無しさん:2006/10/15(日) 10:46:59
>>317
話が摩り替わってるじゃん。
int32bitをfloat32bitの仮数部に入れるって話は消費情報量を削減できてないだろ。
単に有効情報量が減るだけじゃん。

319 :デフォルトの名無しさん:2006/10/15(日) 10:52:00
>>318
>>304によると32ビット情報を24ビット(23ビット)に圧縮してからだと思うが
もしかして、float f=3.14f; int j=(int)f と勘違いしてないか?

320 :デフォルトの名無しさん:2006/10/15(日) 10:59:12
32ビットの情報を24ビットに圧縮しても、その情報を32ビットのマスに入れたんじゃ意味ないだろと言っている。

321 :デフォルトの名無しさん:2006/10/15(日) 11:17:35
>>320
なんと言うのか、話が逸れてるんだよな…
32ビットのマスに入れるかどうかじゃなくて、
圧縮する方法・アルゴリズムが重要なんじゃないのか
その使い方や用途は君が関知する問題じゃないだろ?

322 :デフォルトの名無しさん:2006/10/15(日) 11:51:10
ランダムな32ビット整数を24ビットに圧縮するという話についてなら、とっくに無理と言ってるが。

323 :デフォルトの名無しさん:2006/10/15(日) 12:19:03
どうして?

324 :デフォルトの名無しさん:2006/10/15(日) 12:49:06
32bitに圧縮しきれない可能性があるからじゃないか?

325 :デフォルトの名無しさん:2006/10/15(日) 13:44:45
32MBを24MBに圧縮できる(アルゴリズムがある)のだから
32bitを24bitに圧縮も考え次第で出来るだろ。
アルゴリズムというのは、そういうのじゃないのか?
ところで、無理とか不可能とか何を根拠に言ってるんだろう。

326 :デフォルトの名無しさん:2006/10/15(日) 15:47:13
みんな考えてる問題の定義と目的がバラバラのようだし、
議論は無理。問題の説明が足りなさ過ぎる。

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

327 :デフォルトの名無しさん:2006/10/15(日) 16:42:58
圧縮のアルゴリズムで特許をとられないのって、何があるの?


328 :デフォルトの名無しさん:2006/10/15(日) 17:07:08
このスレはレベル低いな。
これじゃ優秀な奴は誰も来ないぞ。

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

329 :デフォルトの名無しさん:2006/10/15(日) 17:11:21
特許に引っかからないのは?って聞きたいんだろ?

330 :デフォルトの名無しさん:2006/10/15(日) 17:33:09
>>329
おまえはエスパーのようだが、どこの惑星から来た?

331 :デフォルトの名無しさん:2006/10/15(日) 18:11:16
>>327
すでに切れた特許なら再び取られることは無いだろうな

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

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

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

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

334 :デフォルトの名無しさん:2006/10/15(日) 23:16:38
どんな 32bit のデータでも常に 24bit に圧縮できるアルゴリズムがあれば、
それを何度か繰り返し使えば世の中のすべての情報は 24bit にまで圧縮できることになるな。

335 :デフォルトの名無しさん:2006/10/15(日) 23:32:29
          [゚д゚]
           [ヽ□
           |  | 
□□□□□□□□□□□□□□□□□□□□□□□□□

        [゚д゚]
         [ヽ日
         |  | 
日日日日日日日日日日日日日

     [゚д゚]
      [ヽ品
      |  | 
品品品品品品品品

  [゚д゚]
   [ヽ昌
   |  | 
昌昌昌昌

ヽ[゚д゚]ノ
  [_] 
  |  | 
 晶晶

336 :デフォルトの名無しさん:2006/10/15(日) 23:38:12
そこでTHCompですよ。

337 :デフォルトの名無しさん:2006/10/16(月) 00:58:09
いまオレすごい圧縮を考えたんだ!
データの最後のbitが0だったらそのbitを削るんだ。
1だったらそのまま。
これで1/2の確立でどんなデータ、
ランダムなデータでも1bit削れるよ!
同じ感じで後ろ(先頭でもいいけど)1byteが0x00なら削って、
0x00以外ならそのまま。
1/256の確立で1byte圧縮できるよ!

338 :デフォルトの名無しさん:2006/10/16(月) 01:09:42
>>337
削るのはいいんだがどうやって復元するつもりだ?

339 :337じゃないけど:2006/10/16(月) 01:18:14
まずはそのまま、エラーが出なければOK。
駄目なら最後に0をくっつける。
これでどんなデータでも復元できるよ。
1byteのも同じ感じで、エラーが出なければOK。
駄目なら最後に1byte分の0x00をくっつける。

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


340 :デフォルトの名無しさん:2006/10/16(月) 01:21:46
運まかせ

341 :デフォルトの名無しさん:2006/10/16(月) 01:31:11
>>339
その方法だとエラー検査のための仕組みを別に用意しなければいけなくて、
それを厳密に行うためには圧縮前のデータと同じだけの容量が必要になる。

342 :デフォルトの名無しさん:2006/10/16(月) 02:56:15
必要な32bitデータの入ったマシンをカメラで撮るんだ
そしたらそのマシンは捨ててしまう
これで圧縮が出来た

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

343 :デフォルトの名無しさん:2006/10/16(月) 14:08:00
どんな 32bit のデータでも常に 1bit に圧縮できるアルゴリズムがあれば、
それを何度か繰り返し使えば世の中のすべての情報は 1bit にまで圧縮できることになるな。


344 :デフォルトの名無しさん:2006/10/16(月) 15:12:08
>>343
つまり全ての情報は同じって事。あなたとわたしも全く同じ。

345 :デフォルトの名無しさん:2006/10/16(月) 15:14:41
ここは哲学的なインターネットですね。

346 :デフォルトの名無しさん:2006/10/16(月) 15:23:25
つまり、熱的終焉だな。

347 :デフォルトの名無しさん:2006/10/16(月) 15:48:03
ここは物理学的なインターネットですよ

348 :デフォルトの名無しさん:2006/10/16(月) 20:29:50
じゃあ俺は情緒的に

349 :デフォルトの名無しさん:2006/10/17(火) 00:52:06
>>344
待て、1bitなんだから0か1で全ての情報は二つに分けられることに

350 :デフォルトの名無しさん:2006/10/17(火) 01:06:39
Lz77

351 :デフォルトの名無しさん:2006/10/17(火) 12:21:41
>>349
完全平衡状態に至って熱的死を迎えるか、
再度収縮して次のビッグ・バンが起きるか、
の2つってことか。

352 :デフォルトの名無しさん:2006/10/17(火) 13:27:41
猫を殺したくなければそれ以上踏み込んじゃいかん

353 :デフォルトの名無しさん:2006/10/17(火) 14:34:14
半分死んでいて半分生きている猫

354 :デフォルトの名無しさん:2006/10/17(火) 15:18:40
轢かれて体半分潰れたが運悪く首は折れなかった みたいな感じか

355 :デフォルトの名無しさん:2006/10/18(水) 00:53:48
0.5bitの情報を記録できる素子がほしい

356 :デフォルトの名無しさん:2006/10/18(水) 03:02:37
>>355
おまいの脳細胞

357 :デフォルトの名無しさん:2006/10/18(水) 03:17:57
>>355
素子2単位で1bit分の情報を記録するようにすればいいだけじゃまいか

358 :デフォルトの名無しさん:2006/10/18(水) 05:39:05
それはつまり今の3.5in 750GBのハードディスクを作れる技術が
1.5TBで作れるようになるまで待てと言ってるのか?

359 :デフォルトの名無しさん:2006/10/18(水) 11:00:01
なんだ、来ない間にずいぶんと白熱してたんだね。
もう解決してるんだけど、つまんない話ばっかりでお前らには教えてやんない。
>>335,>>337は少し面白かったけど、まだまだ。

360 :デフォルトの名無しさん:2006/10/18(水) 12:46:53
みんなもホントは解決してるから大丈夫。

361 :デフォルトの名無しさん:2006/10/19(木) 21:29:22
最強の圧縮アルゴリズムっていうけど、
それってどんなの? オレ的には、
1つのアルゴリズムで結果を帰還させて
圧縮できなくなるまで繰り返すようなのが
美しいと思うのだけど。

362 :デフォルトの名無しさん:2006/10/19(木) 21:33:47
俺的には傾向を見つけ出してそれに基づいて圧縮するのが美しいと思うけど

363 :デフォルトの名無しさん:2006/10/19(木) 21:39:44
>>361
だから、それって具体的にどうやるわけ?

364 :デフォルトの名無しさん:2006/10/19(木) 22:34:01
あまりのアホさに361をスルーしたが、
362と363が俺の言いたかったことを言い尽くしていたことに感動した。

365 :デフォルトの名無しさん:2006/10/19(木) 23:15:05
>>361 感動した!!

366 :361:2006/10/19(木) 23:32:27
具体的な方法については言及しないつもりでした。
ただなんとなく美しい気がしたので。
自分では無理な気がしています。
具体的に無理な理由を説明できるならお願いしたいのですが・・
逆に出来るよ!というのであればなおさらお願いしますー

367 :デフォルトの名無しさん:2006/10/19(木) 23:52:18
>>361
その性質をもつ自明な圧縮の例

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

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

368 :デフォルトの名無しさん:2006/10/19(木) 23:59:57
復元は何になるの?

369 :デフォルトの名無しさん:2006/10/20(金) 00:07:52
「どんな数も」ってのは間違いか。入力は自然数限定ってことで。

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


370 :デフォルトの名無しさん:2006/10/20(金) 01:26:57
最強を語る前に最弱を語ろうではないか?


371 :デフォルトの名無しさん:2006/10/20(金) 02:28:42
圧縮になってないのは自明だな。

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

373 :デフォルトの名無しさん:2006/10/20(金) 09:34:25
>>369
その回数はどこで覚えておくの?

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

375 :デフォルトの名無しさん:2006/10/20(金) 11:48:41
>>362
そのアルゴリズムは結構出尽くしているかも…
視点を変えてみると面白い!

376 :デフォルトの名無しさん:2006/10/20(金) 18:33:36
近似する式にするってのすごいよね。


377 :デフォルトの名無しさん:2006/10/20(金) 19:29:24
どういうこと?

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

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

379 :デフォルトの名無しさん:2006/10/22(日) 00:27:04
エントロピーが云々で何とかかんとか

380 :デフォルトの名無しさん:2006/10/22(日) 13:53:49
もともと自分にとって都合のいいデータって絶対に存在しないでしょ?
何を言ってるんだ、こいつは。

381 :デフォルトの名無しさん:2006/10/22(日) 16:42:45
>>30

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

とかは、既出?

382 :デフォルトの名無しさん:2006/10/22(日) 18:39:45
ずいぶん工学よりだけど、圧縮アルゴリズムなんてそんなもんだよ。
もうすこし具体的に書かないと言いたいことが見えてこないから、
既出かどうかは分からない。

383 :デフォルトの名無しさん:2006/10/22(日) 18:49:02
少なくとも、非可逆圧縮には利用されているのは間違いなさそうな気がする

384 :デフォルトの名無しさん:2006/10/22(日) 18:56:40
>>381

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

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


385 :デフォルトの名無しさん:2006/10/22(日) 19:32:48
データによっては十分可能だと思うが

386 :デフォルトの名無しさん:2006/10/22(日) 19:38:45
スーパーマンが両手で炭の塊を圧縮したらダイヤモンドになってたが、
別物になっちゃうのはアウトだな。
スーパーマン使えねえ。

387 :デフォルトの名無しさん:2006/10/22(日) 19:44:37
高温・高圧
だからどうしてなったのか不明だな

388 :デフォルトの名無しさん:2006/10/22(日) 20:17:57
しかもカット済みのダイヤが出てきたもんな・・・

389 :361:2006/10/22(日) 20:44:43
>>380
「都合が良い」の度合いの問題ですよ〜
実用していて発生するデータの内で。
そりゃ作ろうと思えばいくらでも作れますから。

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

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

390 :デフォルトの名無しさん:2006/10/22(日) 20:49:59
圧縮で良書がないね〜


391 :デフォルトの名無しさん:2006/10/22(日) 22:10:42
圧縮でかよ!

392 :デフォルトの名無しさん:2006/10/22(日) 23:31:15
>>287ぐらいまでの停滞っぷりが嘘のようだw

393 :デフォルトの名無しさん:2006/10/22(日) 23:38:27
でも、本当に圧縮技術の良書ってないよね。
なんで?


394 :デフォルトの名無しさん:2006/10/22(日) 23:43:18
論文嫁

395 :デフォルトの名無しさん:2006/10/24(火) 21:20:41
>>390
Cマガジン
圧縮アルゴリズム


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


396 :デフォルトの名無しさん:2006/10/30(月) 15:35:26
対象が何かを分析し、対象の種類と特徴によってアルゴリズムを可変させるのが
最強のアルゴリズムであって、1つのアルゴリズムだけですべてを適用させる
汎用のアルゴリズムなどあるわけないだろ。wwwwwwwwwwwww

397 :デフォルトの名無しさん:2006/10/30(月) 19:59:09
新しいアルゴリズムは開発しないのか?

398 :デフォルトの名無しさん:2006/10/31(火) 11:43:02
助けてアルゴマン!

399 :デフォルトの名無しさん:2006/10/31(火) 16:26:51
>>268
>そしてこれらの選択肢は全て結果が等しい、つまり等価なわけだ。
>同じ結果に対して別の選択肢が存在するという事は、
>それはつまり冗長だということになる。
詳しい理論や真偽の程はともかく、感覚的に納得の行く説明dクス
>>270モレにもそのように思える。
しかしそれはモレの頭が悪い所為かも知れないと思って聞いてみた。

400 :デフォルトの名無しさん:2006/11/02(木) 13:19:10
zip32.dllとzlib使った自前のプログラムで比較したんだけど圧縮率に結構差がある。
zip32.dllはdeflateだけじゃないの?

401 :デフォルトの名無しさん:2006/11/06(月) 01:12:51
>>395
圧縮アルゴリズムは
アルゴリズムの説明は確かにいいかもだけど
プログラムについての説明がない、ソースコードのリストがあるだけ

402 :デフォルトの名無しさん:2006/11/06(月) 01:34:37
C言語の入門書でも読んでろ

403 :デフォルトの名無しさん:2006/11/06(月) 01:41:22
そうしとくぜ

404 :デフォルトの名無しさん:2006/11/06(月) 15:11:05
>>400
7z で -tgzip -mx=9 オプション指定すると、もっと圧縮された .gz
形式がでるよ。


405 :デフォルトの名無しさん:2006/11/06(月) 18:38:21
アルゴリズムばかwwww

406 :デフォルトの名無しさん:2006/11/06(月) 20:02:01
なに興奮してんの(^_^;

407 :デフォルトの名無しさん:2006/11/07(火) 13:41:46
アルゴリズム体操

408 :デフォルトの名無しさん:2006/11/11(土) 00:11:08
アルゴリラ?

409 :デフォルトの名無しさん:2006/11/30(木) 12:59:35
>>26まで読んだ俺様が以降を読まずにレス

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

410 :デフォルトの名無しさん:2006/12/01(金) 13:56:45
ボクの部屋はエントロピーが増大する一方です。


411 :デフォルトの名無しさん:2006/12/01(金) 17:55:25
ぼくのおちんこは(

412 :デフォルトの名無しさん:2006/12/02(土) 00:59:32
CRCエラーです
伸張出来ません

413 :デフォルトの名無しさん:2006/12/03(日) 01:11:57
伸ばすことに成功しました。
しかし、ふにゃふにゃになり硬くなることはありません。


414 :デフォルトの名無しさん:2006/12/03(日) 19:24:36
p2pの圧縮ソフトはどうだろうか。
1kぐらいのファイルに保存することができる。

415 :デフォルトの名無しさん:2006/12/06(水) 17:00:19
>>414
p2pのって、どういう意味だ? ファイルが分割されてあちこちのサーバにあるとか?


416 :デフォルトの名無しさん:2006/12/07(木) 11:33:09
それって結局はthcompよね

417 :デフォルトの名無しさん:2006/12/16(土) 02:31:58
質問させてください。

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

現状の候補はLZSSです。

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

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

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

418 :デフォルトの名無しさん:2006/12/16(土) 06:28:48
>>417
既存の自爆形式で何か不満でも?

419 :デフォルトの名無しさん:2006/12/16(土) 15:08:32
upx

420 :デフォルトの名無しさん:2006/12/20(水) 20:57:34
何でもいいんじゃないか?
例えば、あえてテキスト用途の圧縮方式を使ってもいいんだ!という意気込みがないとねぇ。

421 :デフォルトの名無しさん:2006/12/20(水) 22:01:20
どうでもいいことかも知れないけど、
テキストの圧縮を考えると、日本語と
欧米では事情が違うよなぁ。
UNICODEなんか、漢字がばらばらに
なってるから、圧縮難しそうと思う。

422 :デフォルトの名無しさん:2006/12/22(金) 08:54:02
感じがバラバラにならない文字コードに変換してから圧縮するんだ

423 :デフォルトの名無しさん:2006/12/25(月) 14:28:59
というか、文字の意味なんかどうでもいいから圧縮に都合が良いように
変換すれば良いんではないか?


424 :デフォルトの名無しさん:2006/12/28(木) 01:04:08
0を白、1を黒と見立ててイラストロジックにすればかなり圧縮されるのでは?
素人考えスマソ

425 :デフォルトの名無しさん:2006/12/28(木) 01:12:08
>>424
まさにその考えで実装されたのが、FAXで使用される modified Huffman
(実態は連長圧縮に近い)

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

426 :デフォルトの名無しさん:2006/12/28(木) 01:56:17
modified Huffmanって白と黒の数を数えるんでしたよね?
イラストロジックの様に黒の数だけを記録して白の数を完全に無くしてしまえば
データにもよるけれどかなり削れるんじゃないかなぁ、と
イラストロジック自体絶対に解けるものじゃないのが難点ですが
解凍時間に制限がなければ何時かは解凍できるんじゃ・・・という希望

427 :デフォルトの名無しさん:2006/12/28(木) 08:23:31
>>426
適当なイラストロジックで必要なビット数計ってごらん。大した圧縮率にならないから。

428 :デフォルトの名無しさん:2006/12/28(木) 08:28:52
>>426
>イラストロジックの様に黒の数だけを記録して白の数を完全に無くしてしまえば

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

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

430 :デフォルトの名無しさん:2006/12/28(木) 22:03:33
>>429
物怖じせず、正直に言うと、

バカじゃないの?

431 :デフォルトの名無しさん:2006/12/28(木) 22:39:01
暗黙の了解という言葉の意味を理解しているならば軽率な発言は出来ないはずだ。
情報の本質を理解している者ならばなおのこと。

432 :デフォルトの名無しさん:2006/12/29(金) 00:24:56
>>426
黒だけとかにすると、場合によっては解凍不能になるのは別に置いといて、
何ビット単位で並べるかによって圧縮率は異なるから(確率的に。なぜなら圧縮するデータが異なるため。)
いかに(時間的に)効率よく圧縮できるか、又いかに圧縮率を高められるかにおいてかなり疑問なのだが。

433 :暇人13世 ◆tAo.kQ2STk :2006/12/29(金) 00:48:59
思いついた。

まず配列に圧縮するデータを1bitづつ入れて、配列a[]とする。
変数iを設け、初期値0とする。

a[i]が0ならiを進めまくる。a[i]が1になるまで。

a[i]からa[a.lenght]までに0がなければ終了する。

a[i]が1ならa[i]からa[a.lenght]までをローテートする。a[i]が0になるまで。
この時のiの値と、回した回数を記録する。

結果的に配列a[]は0000.....00001111.....1111という配列になるので、最後に0の数と1の数を記録する。
解凍は、逆の計算を行えば出来るはず。


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

434 :デフォルトの名無しさん:2006/12/29(金) 01:41:49
>>433
MTF/UTC/ORTの族に近いと思う。いわゆる順列符号とか再帰時間符号。
ローテート回数が再帰時間に相当するようだから、当たらずといえども遠からずかと。

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

435 :暇人13世 ◆tAo.kQ2STk :2006/12/29(金) 01:52:14
実装してみたらアルゴリズムが悪いのか相当遅かった。
それと、iの値を記録せずに前回のiとの差分を記録した方が記録効率がいいことが分かった。
後ひとつは、出力結果をさらにハフマンとかで圧縮しないとファイルがでかい。
(ただし0と1の比がかなり偏っているので再圧縮は効率が高そう)

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

436 :369:2007/01/09(火) 13:45:12
>>433
iの値が0の連続の個数(のようなもの)、回した回数が1の連続の個数ってことで
たんなるランレングスのように思えるが・・・

437 :デフォルトの名無しさん:2007/01/09(火) 22:31:21
torrentファイルを使う。

438 :デフォルトの名無しさん:2007/01/13(土) 18:59:19
仮にテキストファイルだとして出現頻度が
Aが6回
Bが2回
Cが1回
Dが1回

だとすると、本来一文字に2bit使うとして、ハフマン圧縮なら

Aは1bitで済むから0.5倍
Bは2bitだから1倍
Cは3bitだから1.5倍
Dも3bitだから1.5倍

これに出現頻度を掛けると、
Aは0.5*0.5で0.25、Bは1*0.2で0.2、Cは1.5*0.1で0.15、Dも1.5*0.1で0.15

で元の0.8倍のサイズに圧縮できる
つまり元が2bit*10文字で20bitだから、0.8倍なら16bit、4bit削減できた事になる

でも全体の60%が一つの文字に集中してた場合で2割offなんて
ISOファイルを圧縮するのには余り期待は出来ないね

それと、これって圧縮実行する以前に、1度ファイルを読み切らせて、
出現頻度表を作らせた時点で解るよね?

>>1の人が言う風なノリで、2bit長から、31bit長までの30通りの頻度表を最初に作らせて
予定される圧縮率を先に算出させれば良いんでしょ?それで一番割の良い物を実行

でもこのケースだと仮に4文字とも0.25に近い割合の出現頻度だとするとオーバーヘッドが出るんじゃない?
って事は算術圧縮とか、RangeCoderとかでないと駄目ぽなのか

439 :デフォルトの名無しさん:2007/01/13(土) 19:05:53
最強の圧縮はゴミ箱だ

440 :デフォルトの名無しさん:2007/01/14(日) 00:52:13
うん。
確かに最近の OutlookExpress は最適化を行うと
dbx ファイルがごみ箱にもコピーされるようになったね。


441 :デフォルトの名無しさん:2007/01/28(日) 19:42:26
展開の速さならLZO

442 :デフォルトの名無しさん:2007/02/03(土) 13:13:52
以下の条件を満たすオープンソースの圧縮、伸張アルゴリズムはありませんか?
WEB上で公開されているものであれば良いです。

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

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


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

443 :デフォルトの名無しさん:2007/02/03(土) 13:21:55
http://wiki.osask.jp/?tek1/comp

444 :デフォルトの名無しさん:2007/02/03(土) 15:12:30
ウェーブレットとかの話はでないんだな

445 :デフォルトの名無しさん:2007/02/03(土) 15:18:41
>>442
BPEでいいじゃん。

446 :デフォルトの名無しさん:2007/02/03(土) 15:20:31
>>442
調べる能力もないのかおまいは。
ぐぐったら一番上に出てきたぞ。

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

448 :デフォルトの名無しさん:2007/02/04(日) 03:35:56
>>444
残念ながらここの住民のほとんどは、高等な数学を扱えるほど頭がよくありません。
マルチエンコードみたいな技術の動きを読み取るほどの視野も持ち合わせていません。

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

449 :デフォルトの名無しさん:2007/02/04(日) 05:11:54
>>447
ハフマンよりレンジコーダーのほうが速くね?

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

451 :デフォルトの名無しさん:2007/02/04(日) 09:39:05
上からモノ言ってる奴って他のスレでもそうだが、
自分から答えを教えるってことしないよな。
他人の非難は出来るけど、その実、自分で答えを
導き出せない、レベルの低い奴なのだろうか?
まぁ、2ch見てる程度の人間だから仕方がないかも。
他人の非難しかしない奴より、なんでもいいから、
自分の意見を述べる奴の方がましってのは、
どこにあっても同じだと思う。

452 :デフォルトの名無しさん:2007/02/04(日) 09:56:47
まあ、なんだ、落ち着けよ。
こんな過疎スレで誰に言ってるのかよく分からんが。

453 :デフォルトの名無しさん:2007/02/04(日) 10:05:33
コピペだ反応すんな

454 :デフォルトの名無しさん:2007/02/04(日) 12:25:59
>>451
どこを縦読み?

455 :デフォルトの名無しさん:2007/02/04(日) 14:05:56
>>450
ハフマンのが速いって怪しいな。もしかして静的ハフマンか?
動的なら木の操作が入る分、ハフマンの方が不利だろ。
SSE2を使って最適化したレンジコーダがハフマンに劣ることってありえない。
一度チューニングしたそのコードを書いてみ。

456 :デフォルトの名無しさん:2007/02/05(月) 02:09:26
0圧縮

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

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

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

459 :デフォルトの名無しさん:2007/02/05(月) 13:52:03
>>458
458さんのレンジコーダはそんなに速いの?
とりあえずハフマンは静的でレンジコーダは動的でいいよね?
最初からそのつもりで書いてたんだけど。
動的ハフマンとか静的レンジコーダってあまり見ないし。

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

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

460 :デフォルトの名無しさん:2007/02/05(月) 14:03:56
>>459
>とりあえずハフマンは静的でレンジコーダは動的でいいよね?

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

461 :デフォルトの名無しさん:2007/02/05(月) 14:07:42
>>459
>いきなりPPMとか言われたりして、

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

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

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

462 :デフォルトの名無しさん:2007/02/05(月) 14:14:12
>>459
エンコードするのに、バイナリサーチする馬鹿は普通いない。
それとも「圧縮」の話から、「展開」の話に摩り替えてるの?

463 :デフォルトの名無しさん:2007/02/05(月) 14:20:29
>>462
悪い俺が馬鹿だった。アンカーたどったら元は伸張の話みたいだ。orz

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

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

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

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

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

465 :デフォルトの名無しさん:2007/02/05(月) 14:50:31
>>464
>おかしいといっても実際動的ハフマンとか静的レンジコーダって殆ど使われてないし。

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

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

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

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

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

466 :デフォルトの名無しさん:2007/02/05(月) 14:52:53
>>464
>事実上この2つ以外を使うことってないと思うんだけど。

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

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

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

467 :デフォルトの名無しさん:2007/02/05(月) 14:56:18
>>464
>>PPMとかのソース見たことないんじゃないの?
>とか言われても困っちゃうんだけど。

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

468 :デフォルトの名無しさん:2007/02/05(月) 15:00:54
なんか妙に絡まれてるけどなんでだろう?
やっぱり話がかみ合ってないんだよなぁ。
ソース上げろと言われてもその前にあなたが出してくださいよ、
という話になってしまうし。
私がヘボグラマーでレンジコーダの方が速いということで終了しましょう。
バイナリのアップは止めておきます。

469 :デフォルトの名無しさん:2007/02/05(月) 15:03:31
>>467
どのPPM?
Dmitry Shkarin?

470 :お呼びじゃない?:2007/02/05(月) 15:07:12
PPMと聞くと、画像ファイルフォーマットか濃度かカントリーミュージックしか思い浮かばない漏れが来ましたよ。

471 :デフォルトの名無しさん:2007/02/05(月) 15:08:15
>>465
アルゴリズムの実行効率の優劣を論じてるんじゃなくて、

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

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

472 :デフォルトの名無しさん:2007/02/05(月) 15:58:28
>>468
>なんか妙に絡まれてるけどなんでだろう?

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

473 :デフォルトの名無しさん:2007/02/05(月) 16:04:17
>>472
そんなに違わなくね?
圧縮展開って意味なら大差ないような。
ストリームに対応出来るかどうかとか?

474 :デフォルトの名無しさん:2007/02/05(月) 16:11:49
>>473
全然違う。
静的なら頻度表が必要。動的なら不要。
出現確率の変化に動的なら対処できるが、静的では不可能。

475 :デフォルトの名無しさん:2007/02/05(月) 16:17:25
>>474
ブロックに分割したらダメなのか?

476 :デフォルトの名無しさん:2007/02/05(月) 16:18:23
>>474
それって単に多少の圧縮率の話ですよね。
それで「全然違う」かどうかは入力の性質次第かと思うが。

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

477 :デフォルトの名無しさん:2007/02/05(月) 16:21:05
まぁ、ストリームっても大概バッファリングするんだから
そんなに違いがあるとも思えないけどな。

478 :デフォルトの名無しさん:2007/02/05(月) 16:32:25
>>476
静的も動的も、ストリームに対応するかしないかはどっちも一緒。
どっちもたいていブロックに分割した上で、対応する。


479 :デフォルトの名無しさん:2007/02/05(月) 16:33:37
つまり動的か静的かはあまり意味がないってことか。

480 :デフォルトの名無しさん:2007/02/05(月) 16:37:22
>>479
違うよ。
動的か静的かは、確率変動に対応できるかどうかという違いがある。
静的は展開が速いが無駄なデータが多くなるし、圧縮時は無駄なリードが発生する。

481 :デフォルトの名無しさん:2007/02/05(月) 16:44:28
>>480
それって結局圧縮率の問題じゃね?
出現確率の変化の仕方次第じゃ動的な方が圧縮率悪かったりするよ?
それに動的だと出現しないシンボルが無駄になるんだよな。
エスケープ使うとますます遅くなるしな。

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

483 :デフォルトの名無しさん:2007/02/05(月) 17:26:15
>>482
>圧縮率無視するなら、そもそも圧縮なんかしないでいいだろ。
べつにそんな事言ってないぞ。
ていうか圧縮率の問題は比較する上で静的動的と本質的に関係なくね?

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

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

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


484 :デフォルトの名無しさん:2007/02/05(月) 17:36:19
>>483
>ていうか圧縮率の問題は比較する上で静的動的と本質的に関係なくね?

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

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

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

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

ここまでは正解。

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

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

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

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

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

485 :デフォルトの名無しさん:2007/02/05(月) 17:56:05
>>484
>ここが間違い。
>例えば、区間内に「AAAA...AAAABBBB....BBBB」というデータが与えられた場合、
>静的だとA、Bの確率が0.5になる。
ん?その区間の確率は理論上A,Bともに0.5で正しいはずだけど。
「ABABABAB...ABABABAB」も「AAAAAAAA...BBBBBBBB」も同じだよ?
どのシンボルも(AとBしかないけど)この区間においては確からしい確率が与えられてるでしょ。
極端な話「AAAAAAAAAAA」だけのデータは静的だと確率が1になるよね?ある意味ランレングス。
動的だと1/2, 2/3, 3/4, 4/5...n-1/nとなっていく訳だ。
で、極端な話0.9999999999になることはあっても決して1にはならない。
理論的には静的な方が良くなるのは分かるよね?

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

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

486 :デフォルトの名無しさん:2007/02/05(月) 18:10:00
>>485
>ん?その区間の確率は理論上A,Bともに0.5で正しいはずだけど。
「ABABABAB...ABABABAB」も「AAAAAAAA...BBBBBBBB」も同じだよ?

静的の場合はそうだが、動的の場合は違う。
動的の場合、前者は、ABともにほぼ0.5にでき、後者は、静的よりも効果的に圧縮できる。

>動的だと1/2, 2/3, 3/4, 4/5...n-1/nとなっていく訳だ。

とは限らない。もちろんその手の変化があるという意味では正解だが、
その変化の仕方はタコなアルゴリズム。

>で、極端な話0.9999999999になることはあっても決して1にはならない。

そうだよ。静的の場合その情報を頻度テーブルに書き込むわけだが、
動的の場合は、その差が動的な符号中に拡散するだけのこと。

>理論的には静的な方が良くなるのは分かるよね?

理論的には、良くならない。
高圧縮のアルゴリズムはすべて動的になっていることからもわかるはずだが。

どうしても分からないなら、2値のモデルで検証してみることだ。
区間内に出現確率の変化がある場合、動的のほうが必ず良くなるから。
そして変化が無い場合でも、動的でも静的と同レベルに抑える方法があることがわかる。

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

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

487 :デフォルトの名無しさん:2007/02/05(月) 18:15:11
「AAAB」
静的
A:3/4
A:3/4
A:3/4
B:1/4
-> 27/256 = 0.10546875
動的
A:1/2
A:2/3
A:3/4
B:1/5
-> 6/120 = 0.05000000

488 :デフォルトの名無しさん:2007/02/05(月) 18:18:07
>>487
頻度テーブルの情報量を加えてごらん。

489 :デフォルトの名無しさん:2007/02/05(月) 18:23:20
>>とは限らない。もちろんその手の変化があるという意味では正解だが、
>>その変化の仕方はタコなアルゴリズム。
どんな入力に対しても対応できる方法は存在しないよ。

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


490 :デフォルトの名無しさん:2007/02/05(月) 18:25:19
>>489
>それらは一般的な情報源に対して高圧縮率なだけ。
>例えばPAQやPPM*よりLZが倍近く高圧縮になるケースが実在する。

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

491 :デフォルトの名無しさん:2007/02/05(月) 18:27:02
>>488
1bitでイイ?

492 :デフォルトの名無しさん:2007/02/05(月) 18:29:06
>>491
どうやって表現するんだ?AAAAとAAABとAABBとABBBとBBBBが区別できないといけないだろ。

493 :デフォルトの名無しさん:2007/02/05(月) 18:33:53
以下の条件を満たすオープンソースの圧縮、伸張アルゴリズムはありませんか?
WEB上で公開されているものであれば良いです。

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

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

494 :デフォルトの名無しさん:2007/02/05(月) 18:33:58
だからよ、テーブルは任意サイズでもいいわけよ。
てことは少なくとも頻度表を除けば平均的な
区間圧縮率は静的な方が上なんだよ。
で、これにテーブルをどうするかって位の差なんだよなこれがさ。
最初から辞書として持っててもいいわけだ。
実際PAQとかDurilcaとかはテーブル持ってんだよね。

495 :デフォルトの名無しさん:2007/02/05(月) 18:42:03
>>494
>だからよ、テーブルは任意サイズでもいいわけよ。

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

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

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

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

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

496 :デフォルトの名無しさん:2007/02/05(月) 18:49:29
>>493
ランレングス

497 :デフォルトの名無しさん:2007/02/05(月) 19:03:14
だからさ頻度表は任意だから加えたらどっちが上かは
その時点で決められないんだよな。

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

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

498 :デフォルトの名無しさん:2007/02/05(月) 19:08:53
>>497
>つまりどんな入力に対しても頻度表を除けば常に静的な方が圧縮率は上。

馬鹿。

499 :デフォルトの名無しさん:2007/02/05(月) 19:11:32
>>498
馬鹿はないだろ馬鹿は。
でも間違ってないだろ?

500 :デフォルトの名無しさん:2007/02/05(月) 19:13:40
いやでもこれが間違っているとなると
シャノンの情報理論も間違ってることになるんじゃ?

501 :デフォルトの名無しさん:2007/02/05(月) 19:15:21
>>497
>動的符号化は常に被符号語が未知であるが故に確からしい確率を与えることが出来ない。
>最適な確率・符号長を与えられない時点で平均的には必ず静的より悪くなる。

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

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

502 :デフォルトの名無しさん:2007/02/05(月) 19:19:43
局所的な確率はどうやって求めんのよ?
どんな入力に対しても最適にする事は出来ないんだよ?
実装の問題とかじゃなくてさ。

503 :デフォルトの名無しさん:2007/02/05(月) 19:21:46
>>502
>局所的な確率はどうやって求めんのよ?

ベイズ推定

504 :デフォルトの名無しさん:2007/02/05(月) 19:22:42
AAAB,AABA,ABAA,BAAA
これを動的符号化で期待値求めてみてよ。

505 :デフォルトの名無しさん:2007/02/05(月) 19:26:07
>>504
A=aが1000個の固まり
B=bが1000個の固まり
に展開して、aとbで符号化してみたらどう?

506 :デフォルトの名無しさん:2007/02/05(月) 19:28:11
分かんないかなあ、次の文字が未知である以上
何やったって既知である静的符号化より区間平均が悪くなるのに。
特殊な情報源に強くする事は出来ても全般は無理よ。

507 :デフォルトの名無しさん:2007/02/05(月) 19:37:17
>>505
母数を大きく取るのね。
500/1000
501/1001
502/1002
500/1003
0.062499813247569977380545675660332
大きくとるほどに変化に強くなる。

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

509 :デフォルトの名無しさん:2007/02/05(月) 23:05:45
>>508
>で、あらゆる全てのビットパターン(未知の情報源)をトータルすると

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


510 :デフォルトの名無しさん:2007/02/05(月) 23:12:32
>>509
理論値を語ってるんじゃなかったんか。

511 :デフォルトの名無しさん:2007/02/05(月) 23:14:22
>>506
じゃあ、君の考えだとPPM法を静的にした方が圧縮率が上がるということ?
そんなことやる奴なんていないと思うが。

512 :デフォルトの名無しさん:2007/02/05(月) 23:15:54
>>510
全パターンなら、理論値だろうと実測値だろうと一緒だろ。圧縮しないのが最強だ。

513 :デフォルトの名無しさん:2007/02/05(月) 23:26:12
>>511
頻度表を除けば理論上はそうなるよ。
まあ当たり前なんだけどさ。
頻度表をどうするかはまた別の話。
durilcaとかは自前でテキスト用に辞書をもってたりする。
実用上はもちろん頻度表は動的に作ることになるだろうけどね。

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

514 :デフォルトの名無しさん:2007/02/05(月) 23:47:50
理論的に語るなら得意な情報源のみ取り出して上だというのは
おかしいだろという話なんだよ。
実際存在しうるデータってのはランダムの方が圧倒的に多いんだよ。

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

515 :デフォルトの名無しさん:2007/02/06(火) 00:17:03
>>514
>実際存在しうるデータってのはランダムの方が圧倒的に多いんだよ。

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

516 :デフォルトの名無しさん:2007/02/06(火) 00:19:38
>>513
何度も言うが、頻度表除いたらダメだろ。情報が頻度表に移動しているだけなんだから。
根本的に情報理論がわかってないんとちゃう?


517 :デフォルトの名無しさん:2007/02/06(火) 00:30:46
>>514
>動的符号化はc以外の文字にも常に確率を割り当てなきゃならない。
>既知であれば必ず最適な符号長が割り当てられる。

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

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

518 :デフォルトの名無しさん:2007/02/06(火) 00:32:21
>>515
有効じゃないなんて誰も言ってないだろ。
理論的に話してるんだから考えうるデータは全部考慮しなきゃならんだろ。

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


519 :デフォルトの名無しさん:2007/02/06(火) 00:36:57
局所的な確率が良くなっているのはワーストケースとの
トレードオフなんだよ。
圧縮率が良くなった時だけ見てるからそうなるんだよ。
よーく考えてみてよ。
理論上の話なんだから。

520 :デフォルトの名無しさん:2007/02/06(火) 00:37:18
>>518
>だが動的にすれば常に理論上圧縮率が良くなるのは違うだろ?

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

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

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

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

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

521 :デフォルトの名無しさん:2007/02/06(火) 00:38:22
>>519
理論上というのは、ランダムとか全パターンのことじゃないぞ。
根本的に何か勘違いしていると思われ。

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

523 :デフォルトの名無しさん:2007/02/06(火) 00:44:15
最適な予測で符号を求める方法も、あらかじめ符号をもつのも、情報量的には実は同じ。

524 :デフォルトの名無しさん:2007/02/06(火) 00:44:55
>>521
じゃあ理論上てのはどんなのだよ。
人それぞれ対象が違ったらそれこそ話が合わないじゃないか。


525 :デフォルトの名無しさん:2007/02/06(火) 00:48:35
>>523
究極的にはそれはその通り。
だが符号表を除けば除いた残りの部分は必ず動的より良くなる。
当たり前すぎる。
動的が常に理論的に上ってのは間違い。

526 :デフォルトの名無しさん:2007/02/06(火) 00:49:13
>>522
圧縮しやすいではなく、圧縮可能なデータ。いろいろな偏りが含まれていることが前提になる。
程度の差は様々でいいが、出現確率に差があり、相関性にも差があるのが、現実のデータ。
そういう差がないなら、それはただの乱数列であって、圧縮アルゴリズムを適用する対象外だ。
乱数であることを検出したら、圧縮しないで転送すればいいだけ。

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

527 :デフォルトの名無しさん:2007/02/06(火) 00:49:53
本来持っている情報量を下回る圧縮は出来ないってことだね。

528 :デフォルトの名無しさん:2007/02/06(火) 00:51:21
>>525
>だが符号表を除けば除いた残りの部分は必ず動的より良くなる。

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



529 :デフォルトの名無しさん:2007/02/06(火) 00:52:28
>>527
そういうこと。その中で、動的は時系列情報を利用できる。

530 :デフォルトの名無しさん:2007/02/06(火) 00:54:03
>>526
>圧縮しやすいではなく、圧縮可能なデータ。いろいろな偏りが含まれていることが前提になる。
圧縮可能かどうかはアルゴリズム次第なんだって。
そんな前提条件があるなら先に言ってくれよ。

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



531 :デフォルトの名無しさん:2007/02/06(火) 00:55:44
>>529
時系列情報て、それは結局ワーストケースとのトレードオフなんだって。


532 :デフォルトの名無しさん:2007/02/06(火) 00:56:20
>>530
理論値は理論値。確率や相関性を分散とかを適当に設定すればいいのであって。
全パターンというのは、そもそも圧縮を考える上で無意味なこと。

533 :デフォルトの名無しさん:2007/02/06(火) 00:58:10
>>531
そんなことを言うなら、頻度表もワーストケースとのトレードオフだ。バカバカしい。

534 :デフォルトの名無しさん:2007/02/06(火) 00:58:52
>>532
理論値てのは普通全部含めるだろ?
いい加減理論値って言葉はやめなよ。
特定の場合のみなら理論とはかけ離れてる。

535 :デフォルトの名無しさん:2007/02/06(火) 01:01:29
>>533
バカバカしい、って理論の話じゃなかった訳?
あなたの理論は特定のアルゴリズムで圧縮できる
特定のファイルにのみ適用されるの?

536 :デフォルトの名無しさん:2007/02/06(火) 01:06:48
>>534
>理論値てのは普通全部含めるだろ?

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

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

538 :デフォルトの名無しさん:2007/02/06(火) 01:13:09
やっぱり根っこのところで考え方が違い過ぎて議論になってないね。
とりあえず前提条件も話さずに特定の場合のみ取り出して
「理論上は…」ってのだけは止めるべきだと思うよ。

539 :デフォルトの名無しさん:2007/02/06(火) 01:18:31
>>538
理論上は静的の方が冗長な情報が含まれるから劣るんだよ。
シャッフルしたときとの差の情報が使われていないからね。
ただ、現実には理論値が出せないことがあるから、静的な方がいいこともあるだけ。
「情報量」で考えられないやつにはわからないかもしれんが。

540 :デフォルトの名無しさん:2007/02/06(火) 01:20:18
>>537
無限にアルゴリズムが存在する中では高次相関とかは無意味なんだって。
完全な乱数列かどうかなんて判定は出来ないんだから。
全次元の判定なんて不可能でしょ。
というか理論と言う時点で全ての情報源は等価である事が前提だと思うんだけど。

541 :デフォルトの名無しさん:2007/02/06(火) 01:29:29
>>540
>全次元の判定なんて不可能でしょ。

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

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

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


542 :デフォルトの名無しさん:2007/02/06(火) 01:32:05
一応断っておくがあなたの主張については
後だしの前提条件を踏まえる限りは概ね正しいと思うよ。
ただし議論するときは前提条件はきちんと提示するべきだね。

543 :デフォルトの名無しさん:2007/02/06(火) 01:37:52
>>542
全パターンなんて基地外じみた条件こそ後出しだろ。
まともな情報理論で語るなら、そんなわかりきったことを持ち出して議論を無意味にしたりはしないのが普通。

544 :デフォルトの名無しさん:2007/02/06(火) 11:42:47
結局のとこ全パターン厨って何が言いたいの?

545 :デフォルトの名無しさん:2007/02/06(火) 12:39:19
もう終わりにしろよ。

546 :デフォルトの名無しさん:2007/02/06(火) 16:58:04
どうして情報源の設定をしないのだろうか。
エルゴード情報源くらいを仮定してみては?

547 :デフォルトの名無しさん:2007/02/06(火) 23:20:22
>>541
理想論の放棄=客観的なアルゴリズム比較の放棄
と同等だわな。

548 :デフォルトの名無しさん:2007/02/06(火) 23:23:28
>>546
同意。
現代の圧縮アルゴリズム論は、もう情報源の設定が必須だな。

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

549 :デフォルトの名無しさん:2007/02/07(水) 08:42:10
Lempel-Zivについて。
"IM■ULM■UM■ULM■UND■UM■ULM■HERUM"をLempel-Zivで圧縮したらどんな風になるんでしょう?
↓ここでは最初に全部のアルファベット読み込んでるけど
ttp://en.wikipedia.org/wiki/LZW
上の例では無駄が多くなっちゃうよね?だから、動的に読むことにした。
自分で辞書とコードを作ってみたんで合ってるかどうか確認してやってください。

0 I
1 IM
2 M
3 M■
4 ■
5 ■U
6 U
7 UL
8 L
9 LM
10 M■U
11 ■UM
12 UM
13 M■UL
14 ■UL
15 ULM
16 LM■
17 M■UN


550 :デフォルトの名無しさん:2007/02/07(水) 08:43:09
18 ■UN
19 UN
20 N
21 ND
22 D
23 D■
24 ■UM■
25 M■ULM
26 ■ULM
27 ULM■
28 LM■H
29 M■H
30 ■H
31 H
32 HE
33 E
34 ER
35 R
36 RU

551 :デフォルトの名無しさん:2007/02/07(水) 08:44:06
原文字=Lempel-Zivコード

I=0
M=2
■=4
U=6
L=8
M■=3
U=6
M■U=10
LM=9
■U=5
N=20
D=21
■UM=11
■UL=14
M■=3
H=31
E=33
R=35
UM=12

…どうでしょう?

552 :デフォルトの名無しさん:2007/02/07(水) 09:00:01
http://ja.wikipedia.org/wiki/LZ78

553 :デフォルトの名無しさん:2007/02/07(水) 09:15:44
>>552
ア、ナルほど。
1のIMや3のM■はもっと後にコード化されるみたいですね。
もう一度やってみます。

554 :デフォルトの名無しさん:2007/02/07(水) 09:36:59
再挑戦です。今度こそ、どうでしょうか?

0 I
1 M
2 ■
3 U
4 L
5 M■
6 ■U
7 UM
8 M■U
9 UL
10 LM
11 M■UN
12 N
13 D
14 ■UM
15 M■UL
16 LM■
17 ■H
18 H
19 E
20 R


555 :デフォルトの名無しさん:2007/02/07(水) 09:37:45
原文字=コード

I=0
M=1
■=2
U=3
L=4
M=1
■=2
U=3
M■=5
U=3
L=4
M■U=8
N=12
D=13
■U=6
M■U=8
LM=10
■=2
H=18
E=19
R=20
UM=7

…合ってますか?

556 :549:2007/02/07(水) 11:28:47
"IM■ULM■UM■ULM■UND■UM■ULM■HERUM"
ではなくて
"IN■ULM■UM■ULM■UND■UM■ULM■HERUM"
 ↑
でした。
しかもノートに答えが載ってました、はははは。(^^ゞ


…吊ってきます。

138 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)