- 1 名前：デフォルトの名無しさん [2006/04/26(水) 11:57:53 ]
- 2bit , 3bit , 5bit ずつに頻度を取る。
2bitがいい成績だったら2bitをひとかたまりにして
2ブロック、3ブロック、5ブロックで頻度をとる。
これを繰り返す。
- 41 名前：デフォルトの名無しさん mailto:sage [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 名前：デフォルトの名無しさん mailto:sage [2006/04/26(水) 21:14:28 ]
- >>14,>>35-42
それ以前に最適な辞書を作るアルゴリズムをどうやって作るのかと。
- 45 名前：デフォルトの名無しさん mailto:sage [2006/04/26(水) 21:23:24 ]
- talk:>>44
「最適な辞書を作るアルゴリズム」を作るアルゴリズムを作れば？
- 46 名前：デフォルトの名無しさん mailto:sage [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 名前：デフォルトの名無しさん mailto:sage [2006/04/26(水) 22:01:47 ]
- >>48
途中の01や111をどう扱うかによって変わるかと。
- 50 名前：デフォルトの名無しさん mailto:sage [2006/04/26(水) 22:03:58 ]
- talk:>>45
どうやって作るの？
まさかとは思うが、それを作るために作るためのアルゴリズムをつくろうとか言い出す始末じゃ困るぞ。
- 51 名前：デフォルトの名無しさん [2006/04/26(水) 22:18:22 ]
- ちょっと前の話だが、いわゆるITバブルだったころ、
「どんなサイズのファイルでも50%に圧縮するアルゴリズムを考え付いた」といって
投資を集めていたやつがいたそうだ。しかもそのアルゴリズムは可逆なのだそうだ。
この詐欺師の事件の顛末、誰か知らないか？
- 52 名前：デフォルトの名無しさん mailto:sage [2006/04/26(水) 22:58:37 ]
- >>1
まず、詳しい圧縮・伸張方法を説明して、且つその方法が圧縮率や処理速度の点で良い結果を出せそうだ、ということをきっちり説明してくれ。
- 53 名前：デフォルトの名無しさん mailto:sage [2006/04/27(木) 00:30:17 ]
- >>51
10%じゃなかったっけ?
そういえばどうなったんだろうな。
- 54 名前：デフォルトの名無しさん [2006/04/27(木) 01:12:42 ]
- どんなビット列、文字列に対しても
辞書部分 + 圧縮部分のサイズがもっとも小さくなるような
アルゴリズムをおまいらが開発するすれ。
- 55 名前：デフォルトの名無しさん mailto:sage [2006/04/27(木) 01:47:10 ]
- 圧縮ファイルをﾃｷｽﾄにしてそれを圧縮するを繰り返せばすげぇ圧縮できる。
そう思ってた時期が僕にもありました
- 56 名前：デフォルトの名無しさん mailto:sage [2006/04/27(木) 01:53:48 ]
- ブロックソート＋BPEでいいんじゃね？
- 57 名前：デフォルトの名無しさん [2006/04/27(木) 02:01:05 ]
- 最強は非可逆だって
- 58 名前：デフォルトの名無しさん mailto:sage [2006/04/27(木) 02:14:25 ]
- それハッシュ
- 59 名前：デフォルトの名無しさん mailto:sage [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
ＤＬＬをつかう。
www.csdinc.co.jp/archiver/lib/main.html
- 63 名前：デフォルトの名無しさん mailto:sage [2006/04/27(木) 06:42:35 ]
- >>62 ｽﾏﾝｽ、さすがにそれは知ってるけど、それと同じようなことを（自前で）実現するような
手法について調べたいんだけど俺のぐぐりかたがヘタクソでみつからない、ていうお話です
- 64 名前：デフォルトの名無しさん [2006/04/27(木) 06:47:37 ]
- >>63
DLL作成をぐぐる。
- 65 名前：デフォルトの名無しさん [2006/04/27(木) 06:49:28 ]
- 標準の形式をしりたいということか。
- 66 名前：デフォルトの名無しさん mailto:sage [2006/04/27(木) 06:54:47 ]
- >>64 うう・・・ぐぐってみたですがよくわからんですorz
>>65 ええ、そんなかんじです
- 67 名前：デフォルトの名無しさん [2006/04/27(木) 07:10:39 ]
- www.iecapc.jp/06/diffusenew/guide/zip.html
- 68 名前：デフォルトの名無しさん [2006/04/27(木) 14:06:11 ]
- 夢を語り合うスレはここですか？
- 69 名前：デフォルトの名無しさん mailto:sage [2006/04/27(木) 15:42:59 ]
- >37は単語と置き換える記号aを既存の記号と
かぶらせない方策を考えてない中学生。(発想力が)
>>61
pkzipとかで日本語以外もぐぐりゃいいんじゃないかな。
- 70 名前：デフォルトの名無しさん [2006/04/27(木) 16:14:04 ]
- >>69
なんだと。そんなことは簡単なことだ。
算術圧縮とか、ハフマンのやり方にならえばいいんだ。
ようするに2とおりの表し方がないようにすればいい。
- 71 名前：デフォルトの名無しさん mailto:sage [2006/04/27(木) 16:49:24 ]
- >>1-70
君らこの辺とかちゃんと読んでる？
↓
homepage3.nifty.com/DO/algorithm.htm の人のWX法。
ビット単位でやるとかなりコストかかりそうだけど、速度的なチューニングを
考えなければほぼそのまま適用できるでそ。
- 72 名前：デフォルトの名無しさん mailto:sage [2006/04/27(木) 19:29:34 ]
- >>71
>>18でちゃんと触れられてるぞ。
おまえこそちゃんと読めよｗ
- 73 名前：デフォルトの名無しさん mailto:sage [2006/04/27(木) 20:06:17 ]
- いやだから一般的なwx法の話じゃなくて、
ipa でやってた↑のアルゴリズムとか読んでるのって話だよ。
誰一人読んでるようには見えないぞ。
- 74 名前：デフォルトの名無しさん mailto:sage [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個用意すると256Ｍバイト必要だ。
3の17乗は約2^27だから17bitまでの単語は登録できるな。
- 83 名前：デフォルトの名無しさん mailto:sage [2006/04/28(金) 11:08:39 ]
- やってみろよｗｗ
到底zipやrarに太刀打ちできないからｗ
- 84 名前：デフォルトの名無しさん mailto:sage [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 名前：デフォルトの名無しさん mailto:sage [2006/04/28(金) 14:06:04 ]
- そもそも対象のデータによって最適なアルゴリズムは異なるのに、
前提条件を明確にせず、延々と馬鹿を晒し続ける奴ばっかりなのは何故なんだ？
- 87 名前：デフォルトの名無しさん mailto:sage [2006/04/28(金) 14:15:13 ]
- 飛べない豚はただの豚。
戦う前から尻尾を振るのが負け犬。
戦って負けてキャンと鳴いてからが勝負さ
- 88 名前：デフォルトの名無しさん mailto:sage [2006/04/28(金) 14:35:41 ]
- 内容も理解せずに んなこと言われてもｗ
- 89 名前：デフォルトの名無しさん mailto:sage [2006/04/28(金) 14:48:03 ]
- 画像圧縮で振幅＋矩形ブロックで、そこそこの圧縮率と高速度のもの作って使ってる。
発表する場もないし、ひとりでひっそりと使ってる。時間軸圧縮も作って、やっぱり動画プログラムでこっそり使ってる。
- 90 名前：デフォルトの名無しさん [2006/04/28(金) 15:10:24 ]
- >>86
最強の称号を手に出来るのは
汎用性のある可逆圧縮だ！
データ種類なんて関係ない。
- 91 名前： ◆Dango91bHA mailto:だんごうめぇｗｗｗｗｗ [2006/04/28(金) 15:44:57 BE:286659247- ]
- 机上の空論はいいから誰かGCA/DGCAよりイイの作って見たら？
どうせZIPやLHAより小さくなるって言ってもたかが知れてるんだし
互換性・普及度が大事だと思うけどな
- 92 名前：デフォルトの名無しさん mailto:sage [2006/04/28(金) 15:53:47 ]
- THcompが最強だな。
ttp://thcomp.org/~pen/pfyp/thcomp/THcomp_log.txt
- 93 名前：デフォルトの名無しさん mailto:sage [2006/04/28(金) 16:01:43 ]
- >>92
出た！THcomp！この手のスレには必ず出てくるな。
- 94 名前：デフォルトの名無しさん [2006/04/28(金) 16:06:58 ]
- 現在世界最強はどのアルゴリズム?
- 95 名前：デフォルトの名無しさん mailto:sage [2006/04/28(金) 16:12:39 ]
- >>94 URLだろ
たとえば
www.google.co.jp/maps?f=q&hl=ja&t=k&om=1&ll=34.944347,134.427681&spn=0.085131,0.113297
- 96 名前：デフォルトの名無しさん mailto:sage [2006/04/28(金) 16:16:25 ]
- >>94
だからTHcompだってば。
そろそろ8バイトくらい行ってるかなw
- 97 名前：デフォルトの名無しさん mailto:sage [2006/04/28(金) 17:45:25 ]
- どんな計算機でも圧縮出来ない数がある。
その数は、有限だが計算機により計算する事が出来ない。
しかし、私達はその数を単に一文字で表現する事が出来る。 Ω と
- 98 名前：デフォルトの名無しさん mailto:sage [2006/04/28(金) 18:45:58 ]
- www.ice.nuie.nagoya-u.ac.jp/~h003149b/lang/p/notes/2003_12_04.html
- 99 名前：デフォルトの名無しさん mailto:sage [2006/04/28(金) 23:51:38 ]
- >>77
16bitだと16語どころか半角で2語しか入らないような。
- 100 名前：デフォルトの名無しさん [2006/04/29(土) 03:39:31 ]
- バイナリならそんなに16bitもあれば十分。
- 101 名前：デフォルトの名無しさん mailto:sage [2006/04/29(土) 03:41:03 ]
- バイナリならそんなに16bitもあれば十分。
- 102 名前：デフォルトの名無しさん [2006/04/29(土) 03:42:56 ]
- ぱくろな！
- 103 名前：デフォルトの名無しさん mailto:sage [2006/04/29(土) 13:46:40 ]
- ぱくった というより「引っ張った」という表現の方があってるｷｶﾞｽ。
- 104 名前：デフォルトの名無しさん mailto:sage [2006/04/29(土) 17:31:22 ]
- 希ガスと言えばヘリウム
- 105 名前：デフォルトの名無しさん mailto:sage [2006/04/29(土) 17:53:06 ]
- ヘリウムは潤沢にある。尤も、太陽と言う名前で宇宙に転がっているので熱と質量をどうするかが問題だが。
- 106 名前：デフォルトの名無しさん mailto:sage [2006/04/29(土) 18:05:16 ]
- 俺はネオン派。
- 107 名前：デフォルトの名無しさん mailto:sage [2006/04/29(土) 20:46:38 ]
- 僕はキセノン派
- 108 名前：デフォルトの名無しさん mailto:sage [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 名前：デフォルトの名無しさん mailto:sage [2006/04/29(土) 20:52:29 ]
- >>109
それは2進数に直した時にファイルサイズが膨れそう。
- 111 名前：デフォルトの名無しさん mailto:sage [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 mailto:sage [2006/04/29(土) 22:08:10 ]
- とりあえず2進数を圧縮して3進数にするアルゴリズムは書けた。
あとは3進数を圧縮して4進数にするのと、4進数を2進数に展開して、そいつを8こ組み合わせてファイルに書き出す。
思ったより面倒＾＾；
- 114 名前：・∀・）っ-○●◎ [2006/04/29(土) 22:10:26 ]
- 2進数→4進数のほうが圧倒的に簡単なのになんでわざわざ3進数にすんだよｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
- 115 名前：111 mailto:sage [2006/04/29(土) 22:15:53 ]
- >>114
そういう仕様。>>109のアイデアを実装しやすいように脳内変換して>>111（自身）が書いた通り。
- 116 名前：デフラグさん ◆WaDYW8eWxU mailto:sage [2006/04/29(土) 22:16:02 ]
- [ﾟдﾟ] ﾃﾞﾌﾗｸﾞｶﾞｶﾝﾘｮｳｼﾏｼﾀ
/[＿]ヽ
| |
234→うがざざすだでななにににののほよわわんん倒単圧数数数的簡進進進
ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
- 117 名前：111 mailto:sage [2006/04/29(土) 22:19:27 ]
- talk:>>109
2進数の検索をテストしているのだが、とてもじゃないが16ビットまで調べると時間食いすぎで効率悪い。
コードが悪いのかとも思うが。
備考
8ビットまで→約3分
16ビットまで→約42分
CPU:ペンティアム4 3.0GHz
- 118 名前：111 mailto:sage [2006/04/29(土) 22:24:39 ]
- 因みに検索のテスト対象はソースファイル(10139Byte)です。
- 119 名前：復号してミナー(1/2) ◆fBLOhapji6 mailto:sage [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 mailto:sage [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 mailto:sage [2006/04/29(土) 23:04:54 ]
- ・Range Coder
・元はbzip2で圧縮したファイル
・圧縮と言うよりは符号化だな
・デフラグさん上等
- 122 名前：デフォルトの名無しさん mailto:sage [2006/04/29(土) 23:06:53 ]
- >>119-120
ここは最強の圧縮のアルゴリズムについて話し合う場であり、少なくとも私は暗号化のアルゴリズムについて話し合うつもりはありません。
- 123 名前：デフラグさん ◆mRgSYalFkQ mailto:sage [2006/04/30(日) 00:01:14 ]
- >>121
[ ﾟдﾟ]y-一~~~~ ﾃﾞﾌﾗｸﾞ? ﾊｧ? ﾔﾙｷﾃﾞﾈｪﾖ
ﾉ[ ﾍ ﾍ
- 124 名前：デフォルトの名無しさん mailto:sage [2006/04/30(日) 00:17:44 ]
- bit単位でファイル全部なめるとしゃれにならん時間かかりそうだし
2進→3進変換でさらにしゃれにならん時間かかりそうだし
2進用の辞書、3進用の辞書、4進用の辞書て具合に辞書だらけになって
あまり縮まなそうだな
ところでこのスレの圧縮アルゴリズムってユニバーサル符号化の方だよな?
- 125 名前：111 mailto:sage [2006/04/30(日) 01:18:58 ]
- >>124
えぇ。もう16bitまで調べてたらしゃれにもならない時間がかかりましたよ。
10キロバイト引っ掻き回して1時間半くらいでしたかねぇ。
- 126 名前：124 mailto:sage [2006/04/30(日) 01:55:39 ]
- 違うだろエントロピー符号化だよ、よく見ろ俺。
ていうか2進だけ考えれば可変語長のHuffman符号化じゃんか
となると3進以上に変換するのは無意味だな。
たぶん2進→3進の時点で符号表の分だけサイズ増える
おとなしく算術符号なりRange Coderなり使え
- 127 名前：124 mailto:sage [2006/04/30(日) 02:07:30 ]
- 風呂入ってる間にレスついてたか
上にも書いたが>>111のやってることは可変語長のHuffman符号化と変わらん
2進の時点でエントロピー程度まで縮まるので3進以降は全く意味がない
可変語長だからユニバーサル符号化+エントロピー符号化と同程度まで
縮まる可能性はあるが時間がかかりすぎる上に動的符号化に対応できそうにないから
bzip2とか7zipより縮まるとは思えない
- 128 名前：デフォルトの名無しさん [2006/04/30(日) 03:49:38 ]
- バイト対符号化より縮まるはずだ！
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 名前：デフォルトの名無しさん mailto:sage [2006/04/30(日) 12:40:08 ]
- 2バイトの配列を(3の16乗)個用意しておけばbit列をそのままハッシュとして登録できる。
って軽く30MB超えるんだけど
- 134 名前：デフォルトの名無しさん mailto:sage [2006/04/30(日) 15:15:28 ]
- >>133
41メガくらいか。
- 135 名前：111 mailto:sage [2006/04/30(日) 17:29:16 ]
- データサイズが圧縮前より増えた＾＾；
開発停止しまつ。
- 136 名前：デフォルトの名無しさん [2006/04/30(日) 17:52:31 ]
- 減ることはあっても増えることはないんだよ。
減るまで繰り返すんだから。
- 137 名前：デフォルトの名無しさん mailto:sage [2006/04/30(日) 17:57:43 ]
- んなこたーない。
どんなに続けようが増えるだけのこともある。
- 138 名前：デフォルトの名無しさん [2006/04/30(日) 18:01:05 ]
- 一回目の圧縮で縮めなかったらそのままなんだよ。
圧縮の定義から。
- 139 名前：デフォルトの名無しさん mailto:sage [2006/04/30(日) 18:19:00 ]
- 全く縮まない完全にランダムなデータはヘッダやらテーブルやらがつく分増える罠。
非圧縮にした所でやはりヘッダをつけざるを得ないし。
- 140 名前：デフォルトの名無しさん [2006/05/01(月) 04:30:23 ]
- >>139
圧縮ファイルの書式のことではないんだよ。>>109で縮まらなくなるまで
続けるといってるだろ。一回目で縮まらなければ何もしないんだよ。
- 141 名前：デフォルトの名無しさん mailto:sage [2006/05/02(火) 00:15:04 ]
- 辞書は外部に持てばいいんじゃないの？
解凍ソフトと圧縮ソフトで同じテーブルを参照してればよい希ガス
と、暗号素人の俺が言ってみる。
|
 |
