【2ch】圧縮アルゴリズム【オリジナル】
■ このスレッドは過去ログ倉庫に格納されています
0001１
NGNG中途半端に圧縮されて拡張子が.2ch
0652デフォルトの名無しさん
NGNG#include <stdio.h>
#define BLOCK_SIZE 65536
#define ALPHA_SIZE 256
#define ALPHA_BITS 8
unsigned long bitbuf;
size_t bufbits;
long read_bits(size_t bits)
{
int c;
while (bufbits < bits) {
if ((c = getchar()) == EOF) return -1;
bitbuf = ((bitbuf << ALPHA_BITS) | c);
bufbits += ALPHA_BITS;
}
bufbits -= bits;
return (bitbuf >> bufbits) & ((1 << bits) - 1);
}
int sss_read(int start, int step, int stop)
{
int bits = start;
int base = 0;
int code;
while (bits < stop && (code = read_bits(1)) >= 0 && code == 0) {
base += (1 << bits);
bits += step;
}
if (code < 0 || (code = read_bits(bits)) < 0) return EOF;
return code + base;
}
0653デフォルトの名無しさん
NGNGint mtf_array[ALPHA_SIZE];
int mtf_read(void)
{
int i, v, code;
if ((code = sss_read(1, 2, 9)) == EOF) return EOF;
v = mtf_array[code];
for (i = code; i > 0; i--)
mtf_array[i] = mtf_array[i - 1];
mtf_array[0] = v;
return v;
}
unsigned char buffer[BLOCK_SIZE + 2];
long ptr[ALPHA_SIZE + 1];
size_t read_block(void)
{
int count, c;
for (count = 0; count < BLOCK_SIZE + 1 && (c = mtf_read()) != EOF; count++)
buffer[count] = c;
return count;
}
0654デフォルトの名無しさん
NGNGint main(void)
{
int i, count;
unsigned a;
for (i = 0; i < ALPHA_SIZE; i++)
mtf_array[i] = i;
while ((count = read_block()) > 0) {
buffer[count] = buffer[0];
for (i = 0; i < ALPHA_SIZE + 1; i++)
ptr[i] = 0;
for (i = 1; i < count; i++)
ptr[buffer[i] + 1]++;
for (i = 0; i < ALPHA_SIZE; i++)
ptr[i + 1] += ptr[i];
a = buffer[0];
for (i = 1; i < count; i++) {
putchar(a);
a = buffer[ptr[a]++ + 1];
}
}
return 0;
}
0655デフォルトの名無しさん
NGNGしかも(ﾟдﾟ)ﾊﾔｰ！
でも圧縮率はたいしたことないね（ｗ
0656デフォルトの名無しさん
NGNGそれは2ch版の仕様なので、製品版ならば圧縮率は向上します。
などといってみるテスト。
0657デフォルトの名無しさん
NGNG・先頭じゃなくて二番目に持ってくる
・テーブルを256通り持って直前の文字で切り替える
少し良くなる（かも知れない）けどぱっとしないなぁ…
0658デフォルトの名無しさん
NGNGすると先頭は変わらないが、先頭には何が入ってるんだ？
>・テーブルを256通り持って直前の文字で切り替える
データが小さいときは効くだろうね。
0659デフォルトの名無しさん
NGNGひょっとして540って、ソートなんかしなくても、
MTFのコンテクストを256通り持てば同じ事なんでは…
0660デフォルトの名無しさん
NGNGencode.exe < index.html > index.html.2ch
伸張した
decode.exe < index.html.2ch > index.html
感動した >all
0661デフォルトの名無しさん
NGNGだから、こんなんじゃ圧縮できないって何度も言ってんじゃん。
圧縮できてるのは、MTFのおかげ。既存のアルゴリズム。
0662デフォルトの名無しさん
NGNG意味不明。1次のMTFより圧縮率高いけど?
0663デフォルトの名無しさん
NGNG分かんないなら>>647読もうね、ボク。
0664デフォルトの名無しさん
NGNG二番目の文字が出た場合だけ、先頭と二番目を交換する。
0665デフォルトの名無しさん
NGNGunsigned char mtf_array[ALPHA_SIZE][ALPHA_SIZE];
void mtf_write(int context, int alphabet)
{
int i;
int u, next_u;
for (u = mtf_array[context][0], i = 0; u != alphabet; ) {
next_u = mtf_array[context][++i];
mtf_array[context][i] = u;
u = next_u;
}
mtf_array[context][0] = u;
sss_write(1, 2, 9, i);
}
int main(int argc, char *argv[])
{
int i, j, c, last;
for (i = 0; i < ALPHA_SIZE; i++)
for (j = 0; j < ALPHA_SIZE; j++)
mtf_array[i][j] = j;
last = 0;
while ((c = getchar()) != EOF) {
mtf_write(last, c);
last = c;
}
flush_bits();
return 0;
}
0666デフォルトの名無しさん
NGNGコードきぼんぬ
0667デフォルトの名無しさん
NGNGいったい何を根拠に圧縮率が高いと？
実際、ファイルサイズは大きくなるじゃんか。
0668デフォルトの名無しさん
NGNGハァ？
ひょっとしてコンパイル＆実行のしかたも分からんのか…
0669デフォルトの名無しさん
NGNGネタ？
実際に実行して見ろよ。
0670デフォルトの名無しさん
NGNGしたよ？ Cのソースだと大体もとの50%くらいになるよね。
0671デフォルトの名無しさん
NGNGもうそのネタいい加減あきたよ。
>>647読んで分からんやつなら何言ってもムダだし。
0672デフォルトの名無しさん
NGNG0673デフォルトの名無しさん
NGNGどっちにしても圧縮率低すぎ。
0674デフォルトの名無しさん
NGNGでも、まさかそんな初歩的なところじゃないよね。
0675デフォルトの名無しさん
NGNGDOS環境ってWinも含むんでつか？(敬語
0676デフォルトの名無しさん
NGNGうちでも全然だめ。
えらく長いネタだったな。。。
0677デフォルトの名無しさん
NGNG0678デフォルトの名無しさん
NGNG0679デフォルトの名無しさん
NGNG知らん。ANSI C互換なら動くはずだ。
0680デフォルトの名無しさん
NGNG当然binmode.oをリンクしなきゃならんけど。
0681デフォルトの名無しさん
NGNGやつらがいるらしい（フ゜フ゜
0682デフォルトの名無しさん
NGNG改行程度のことで大きくなるようなものでも圧縮って言うの？
0683デフォルトの名無しさん
NGNGみんな知ってるか？(藁
0684デフォルトの名無しさん
NGNGなんだよ、ネタかよ！
0685デフォルトの名無しさん
NGNGあるいは、Calgary corpusで試すかだ。
ちなみに paper1 で 4.679bpc だった。
0686デフォルトの名無しさん
NGNGもういいって。そのネタ、しつこいし、面白くない。
いつまで続くの？
0687デフォルトの名無しさん
NGNG0688デフォルトの名無しさん
NGNGテキストモードで入出力できるはずがないだろ。
0689デフォルトの名無しさん
NGNG大きさの話をしてるんだよ(藁
0690デフォルトの名無しさん
NGNGデータ: 圧縮後/元サイズ
bib: 66314/111261
book1: 470878/768771
book2: 361427/610856
geo: 75105/102400
news: 235941/377109
obj1: 13857/21504
obj2: 127266/246814
paper1: 31091/53161
paper2: 48992/82199
paper3: 28162/46526
paper4: 8030/13286
paper5: 7115/11954
paper6: 22117/38105
pic: 159535/513216
progc: 21760/39611
progl: 35562/71646
progp: 23932/49379
trans: 49036/93695
0691デフォルトの名無しさん
NGNGうわ、すげーバカ（藁
テキストモードって知ってるのか？
Cの入出力の話だぞ。
0692デフォルトの名無しさん
NGNG誰か教えて！
0693デフォルトの名無しさん
NGNG0694デフォルトの名無しさん
NGNGalice29.txt: 89224/152089
asyoulik.txt: 71590/125179
cp.html: 15010/24603
fields.c: 5541/11150
grammar.lsp: 1844/3721
kennedy.xls: 530275/1029744
lcet10.txt: 250429/426754
plrabn12.txt: 284824/481861
ptt5: 159535/513216
sum: 19919/38240
xargs.1: 2464/4227
0695デフォルトの名無しさん
NGNGでなきゃzipファイルを圧縮しようとしたとか。
0696デフォルトの名無しさん
NGNG厨がこんなことに関心を持つとすれば、
エロ画像かエロ動画(w
0697デフォルトの名無しさん
NGNGそりゃ元より大きくなるわな。
BMPなら圧縮できそうだが。
0698デフォルトの名無しさん
NGNGすべてぎちぎちに圧縮しているので、
できたとしてもコメント部分などのヘッダ部だけだろう。
0699デフォルトの名無しさん
NGNG540に反論して引っ込みがつくなくなったやつ、でよろしいですね(Y/y)
0700デフォルトの名無しさん
NGNG0701デフォルトの名無しさん
NGNGhttp://www.pearsoned.co.jp/washo/prog/wa_pro30-j.html
0702デフォルトの名無しさん
NGNG.2ch と い う 拡 張 子 だ ！！
というわけで、.2chをでほるとにして、引数をひとつだけとる
ようにしてくれませんかね。
0703デフォルトの名無しさん
NGNGコンソールアプリなら、
gzip, bzip2 互換のインタフェースの方が使いやすい。
0704デフォルトの名無しさん
NGNG画像どころかCソースでも圧縮できない圧縮法に何の意味があんの？
0705デフォルトの名無しさん
NGNG「圧縮できない」ネタうざすぎ。
なんの工夫もなく「圧縮できない」というウソを繰り返すだけのやつは
もう飽きたってば。
>>690 や >>694 のとおりCソースもほぼ50%に圧縮できている。
以後は >>647 >>690 >>694 に対抗したコメントを捏造するくらいの
工夫をせよ。
0706デフォルトの名無しさん
NGNG圧縮できた妄想患者はすれ違いだからさっさと出て行け。
0707デフォルトの名無しさん
NGNG本人たちが圧縮できてると思ってるんなら、それでいいじゃん。
彼らはそれで圧縮して満足なんだし、圧縮できないと思えば
普通のアーカイバを使えば済むこと。
---------------終了---------------
0708デフォルトの名無しさん
NGNG0709デフォルトの名無しさん
NGNGだから工夫しろって。
せめて >>647 に一言いってみろや。
２次のMTFと同等だから圧縮できて当り前だろ？
0710デフォルトの名無しさん
NGNG0711デフォルトの名無しさん
NGNG0712デフォルトの名無しさん
NGNG彼(ら)の頭ではうpされたコードどころかword countも理解できません。
0713デフォルトの名無しさん
NGNG647に一言いってみろや。なんにも言えないんだろ（藁
0714デフォルトの名無しさん
NGNG圧縮できる/できない で埋め立てるつもりか？
0715デフォルトの名無しさん
NGNGbib: 66314, 66687, 111261
book1: 470878, 470260, 768771
book2: 361427, 360827, 610856
geo: 75105, 76935, 102400
news: 235941, 235700, 377109
obj1: 13857, 14105, 21504
obj2: 127266, 126602, 246814
paper1: 31091, 31521, 53161
paper2: 48992, 49321, 82199
paper3: 28162, 28544, 46526
paper4: 8030, 8332, 13286
paper5: 7115, 7416, 11954
paper6: 22117, 22507, 38105
pic: 159535, 159648, 513216
progc: 21760, 22223, 39611
progl: 35562, 35849, 71646
progp: 23932, 24316, 49379
trans: 49036, 49343, 93695
優劣は微妙だが誤差範囲かも
0716デフォルトの名無しさん
NGNG平均符号長が２次MTFの出力に漸近するのは明らか。
0717デフォルトの名無しさん
NGNGなかなか見事だと思う
0718デフォルトの名無しさん
NGNGただの名無しだろ？
0719デフォルトの名無しさん
NGNGもっとも>>649-654は十分なアイデアが出尽くす前に2chエンコーダ・デコーダを
名乗ってしまったわけで、それはそれで名無しではあるが「俺が2chエンコーダ・
デコーダの作者だ」と主張しているようでいかがなものかと。
0720デフォルトの名無しさん
NGNG0721デフォルトの名無しさん
NGNG>十分なアイデアが出尽くす前に2chエンコーダ・デコーダを
>名乗ってしまった
もうここらでいいんじゃない？ 中途半端なところで。
こんな駄スレに次スレは立たないだろうし。
0722デフォルトの名無しさん
NGNG>>649-654を試してみたよ。
>>649-654を圧縮してみたわけよ。
そしたら1.93KBが1.00KBになったわけよ。
で、驚きながら出コードしてみたわけよ。
そしたら511バイトになったわけよｗ
ネカマ口調で書いてみたけど、
なんかコンパイルでミスったのか？オレは。
0723デフォルトの名無しさん
NGNGま、これもひとつの2chではあるな。
>>722
main()の頭に
setmode (fileno (stdin), O_BINARY);
setmode (fileno (stdout), O_BINARY);
入れてみても駄目かい？
0724デフォルトの名無しさん
NGNG4ビット単位とか2ビット単位とか1ビット単位で
並び替えるとどーなるんでしょう？ 意味無し？
0725デフォルトの名無しさん
NGNG(1)次数に制限のない高次のモデルを使って、
(2)符号長を1bitより短くできるような符号化をするなら、
入力を短いbitで切ってもあまり関係ない。
540とSSSだとどっちも充たさないから短いbitで切ると損。
0726デフォルトの名無しさん
NGNG0727デフォルトの名無しさん
NGNGテキスト系でだいたい半分。
当初の目的のAA系だとものによって２０％くらいまで減らせるようだ。
解凍がなかなか早いのもGood
0728デフォルトの名無しさん
NGNGunsigned char buffer[BLOCK_SIZE];
は
unsigned char buffer[BLOCK_SIZE + 1];
としないとマズイのでは。
0729デフォルトの名無しさん
NGNGソートしたらさらに圧縮率が上がったけど、けっきょく文脈ソートや
ブロックソートに近づいているようで鬱
0730デフォルトの名無しさん
NGNG.DQNがおにあいだ
まずＤＱＮｋａｒａｈａｊｉｍｅｒｅ
0731デフォルトの名無しさん
NGNGIMEを全然操れてないところがDQNぽくてナイス
0732デフォルトの名無しさん
NGNG0733デフォルトの名無しさん
NGNG0734デフォルトの名無しさん
NGNG0735デフォルトの名無しさん
NGNGcompressなんかだと単純に出現順に割り当てた
符号語を出力しますが、それをさらにMTF+可変長符号で
頻度が高いものほど短くなるように符号化する。
あらかじめ決めた辞書サイズが溢れたら、MTFで
いちばん下のところ(最近使われていないところ)
を辞書から削除する。
0736デフォルトの名無しさん
NGNG辞書の捨て方はBTLZ(V.42bisに使われたやつ)に似ているが、
あれはMTF符号化をしていなかった気がする。
0737デフォルトの名無しさん
NGNGLZ78系だと基本的には辞書に登録する単語がどんどん長くなるわけだけど
そうすると新しく登録した単語ばかりが使われることになるだろうから
MTFが効かないような気もする。
最長不使用法で古い単語を捨てて辞書を小さく保つのは有効のはず。
単純なLZ78に組み込む場合はその処理に時間がかかるのがデメリットだけど
MTFに組み合わせるなら殆ど負担にはならないのが利点かな？
0738デフォルトの名無しさん
NGNGそのエントリが他のエントリから参照されているかも知れないから。
その時はどうする？ 子供も全て捨てるか、「子供のいない最も古い
やつを捨てる」か。
0739デフォルトの名無しさん
NGNGMTFは「最近出てきたものがまたすぐ出てくる」とき良く圧縮できる。
LZ78は「一度出てきたものは辞書に登録して、
なるべく同じ出力を繰り返さない」ことを狙いとしている。
0740SYN ◆8smMJ0UaoA
NGNGきちんとした符号化を考えた時、最適(とはいわないでも良好)なモデル化とはいいがたいです。
無条件に先頭に持ってくるのは少々乱暴な感じ。
出現率をきちんと管理できるのであれば、「移動させる」MTFは必要ないです。
0741SYN ◆8smMJ0UaoA
NGNGGCAは実験的作品なので糞なのは認めます。ごめんなさい。
ただ、ガイシュツの理論だけではないです。
BWT+MTF+RangeCoderで作ってみるとわかりますが、
それだけではあまり圧縮率が出せません。
0743デフォルトの名無しさん
NGNG0744SYN ◆8smMJ0UaoA
NGNG気に入らないことがあるなら私に直接言ってください。
fjの方の方でしたら、知っていると思いますが、
「ヤりたい」のなら私はそれに付き合うつもりもあります。
某TRPG関連の方でしたら、本当の事実を知らないだけです。
その場合も私に連絡をください。真実をお伝えしますから。
わざと壊した.gcaファイルを配布する人や、ウィルス入りのファイルを
配布する人もいて、本当に困るよ…。
0745デフォルトの名無しさん
NGNGまぁ公開アルゴリズムをつかいながGCAソース非公開
アーカイバプロジェクトへのGCA/APIの一部非公開
が問題だな
0746SYN ◆8smMJ0UaoA
NGNGソースを公開していないのは、仕様変更がしにくくなるからです。
そういう意味でGCAはまだ完成していません。真打はGCAではないですし…。
それにGCAみたいなしょぼいソフトのソースなど誰も見たがらないと思う。
0747SYN ◆8smMJ0UaoA
NGNG限定ソートのメリットってほとんどないです。szipで使われていますが、
完全ブロックソートでも、あれに近いぐらいの速度が出ます。
完全＝大まかにソート(限定ソート)＋αなのですが、このαの部分って
ほとんどのファイルのデータでは極小なので、差はほとんど出ないです。
0748デフォルトの名無しさん
NGNGその割にB&Wはソートの高速化に苦労していたみたいだが。
特にバイナリで0x00が大量に続くようなとき、単純なソートだと
恐ろしく遅くなるよ。
0749デフォルトの名無しさん
NGNG0750デフォルトの名無しさん
NGNGアルゴリズムがどうの言ってる暇があったら自己展開書庫のヘタレUIを改善して欲しいよ…
0751デフォルトの名無しさん
NGNGだから最初にランレングスしたり
ブロックのバイト列の終端にどの数よりも必ず大きく（小さく）なる値を割り当てて
比較長を短くしたりする、いろいろな工夫があるんだろ？
■ このスレッドは過去ログ倉庫に格納されています