【2ch】圧縮アルゴリズム【オリジナル】
■ このスレッドは過去ログ倉庫に格納されています
0001１
NGNG中途半端に圧縮されて拡張子が.2ch
0604デフォルトの名無しさん
NGNG仕事おせーな
0605デフォルトの名無しさん
NGNG↓
a:bbbbbbbb
b:aaaaaaaa
↓
符号化する、だろ。
0606デフォルトの名無しさん
NGNG馬馬 → 驫
1/3に圧縮できますた
0607デフォルトの名無しさん
NGNGだから逆転した文脈1次モデルだろ？
0608デフォルトの名無しさん
NGNG1次のハフマンで最適に符号化したとして5.868bits/symbol
(符号表その他のオーバーへッドは除く。以下同じ。)
単純なMTFの出力の1次エントロピーは5.119bits/symbol
後段にハフマンを用いると5.591bits/symbol
540+MTFの出力の1次エントロピーは、
ブロックサイズ(bytes) エントロピー(bits/symbol) ハフマン符号(bits/symbol)
4096 4.142 4.577
16384 4.043 4.489
65536 4.005 4.460
...
全部1ブロックに入るとき 3.994 4.452
なので、算術符号を用いれば最高で3.994bits/symbolくらいまで圧縮できる。
ハフマンだと4.452bits/symbol
面白いのは最後段にStart-Step-Stop符号を用いたときで、全部1ブロックに入
るとき、
(3, 2, 9)符号を用いると4.830bits/symbol
(2, 2, 8)符号を用いると4.509bits/symbol
(1, 2, 9)符号を用いると4.388bits/symbol
と、符号によってはハフマンより良い結果になる。
ちなみに、gzip -9だと2.606bit/symbol
bzip2 だと2.190bits/symbol
まで圧縮される。
0609デフォルトの名無しさん
NGNGこんな簡単なことが本当に分からんなら
もう口を出すな。
0610デフォルトの名無しさん
NGNGいや、この方法自体では圧縮はされないどころか、かえってデータ量が増える。
だから、二次圧縮後のサイズを比べてみたんだけど、この方法を使わない場合に比べて、
ほとんど差は無かった。
こう書くと、「ちょっとは差があったのか？」と聞かれると思うが、それは言葉のあやで、
この方法を使った方が小さくなることもあり、大きくなることもあり、
平均してみると、使わない方がどちらかというと小さくなる。
「使わない方が大きくなる」と言うほどは差がないので「ほとんど差は無かった」と書いただけで、
使った方が少しは小さくなるというわけではない。
で、どういう理論を思っているのかを聞いたわけ。
例えば、>>605のようなデータは、元のデータがもともと圧縮率が高く、ab2で表せる。
二次圧縮後に差が出るとは思えない。
0611デフォルトの名無しさん
NGNG「ハフマンより算術符号の方が圧縮率が高い」ということね。
0612608
NGNG> 「ハフマンより算術符号の方が圧縮率が高い」ということね。
もう一つ付け加えると
「540+MTF+SSSは、立派な圧縮アルゴリズムといえる」ということだ。
(少なくとも、1次のハフマンや単純なMTFよりは圧縮率が高い。)
0613608
NGNGこのあとMTF+(arithmetic or huffman or SSS)してくれ。
struct chain { struct chain *next; }; /* ただのchain */
int i, count;
unsigned a;
struct chain *p, *list, **head, **tail;
unsigned char *buffer;
if ((buffer = malloc(block_size + 1)) == NULL ||
(list = calloc(sizeof(struct chain), block_size)) == NULL ||
(head = calloc(sizeof(struct chain), 256)) == NULL ||
(tail = calloc(sizeof(struct chain), 256)) == NULL) {
/* エラー */
}
while ((count = fread(buffer, 1, block_size, stdin)) > 0) {
putchar(buffer[0]);
buffer[count] = buffer[0];
for (i = 0; i < 256; i++)
head[i] = NULL;
for (i = 0; i < count; i++) {
a = buffer[i];
if (head[a] == NULL)
head[a] = tail[a] = list + i;
else
tail[a]->next = list + i;
list[i].next = NULL;
tail[a] = list + i;
}
for (i = 0; i < 256; i++)
for (p = head[i]; p != NULL; p = p->next)
putchar(buffer[p - list + 1]);
}
0614デフォルトの名無しさん
NGNG0615608
NGNGint i, count;
unsigned a;
unsigned char *buffer;
unsigned *ptr;
if ((buffer = malloc(block_size + 2)) == NULL ||
(ptr = calloc(sizeof(unsigned), 257)) == NULL) {
/* エラー */
}
while ((count = fread(buffer, 1, block_size + 1, stdin)) > 0) {
buffer[count] = buffer[0];
for (i = 0; i < 257; i++)
ptr[i] = 0;
for (i = 1; i < count; i++)
ptr[buffer[i] + 1]++;
for (i = 0; i < 256; i++)
ptr[i + 1] += ptr[i];
a = buffer[0];
for (i = 1; i < count; i++) {
putchar(a);
a = buffer[ptr[a]++ + 1];
}
}
0616608
NGNG結果には影響ないけどね。
0617デフォルトの名無しさん
NGNG俺はCのソース使ってほとんど差がでないんだけど。
0618608
NGNGデータ圧縮の標準データセット。
これ知らないなら本当にモグリだな。
0619デフォルトの名無しさん
NGNGもしかして対象データのサイズが小さいとか。
どんな手法でもそうだけど、数十バイトを半分にするのは、
数百メガバイトを半分にするよりもいくぶん難しいよ。
0620デフォルトの名無しさん
NGNG自分が知っていることは相手も知っていると思うんだろうか。
0621デフォルトの名無しさん
NGNG0622デフォルトの名無しさん
NGNGMTF+SSS(3,2,9) 254543バイト
540(ブロック64KB)+MTF+SSS(1,2,9) 170454バイト
0623デフォルトの名無しさん
NGNG圧縮プログラムの比較はたいていこれを使う。
>>618はスペル間違えてるけどな（ｗ
(正しくはCalgary corpus)
0624デフォルトの名無しさん
NGNG初めて聞いたよ。
俺ってモグリだから、Calgary Corpusくらいしか知らねーや。
0625デフォルトの名無しさん
NGNG誰か教えて下さい、お願いします。
0626デフォルトの名無しさん
NGNG0627デフォルトの名無しさん
NGNG元: 1920バイト
MTF+SSS: 1470バイト
540+MTF+SSS: 1022バイト
0628デフォルトの名無しさん
NGNG何が理解できなかったの？
２次エントロピーというのが理解できないとか？
0629デフォルトの名無しさん
NGNGいや、試してダメだったと言ってるって事は、
情報理論が理解できてないだけでなく
アルゴリズムも理解できてないらしい。
0630デフォルトの名無しさん
NGNGなんで俺のところではうまくいかないんだ？
本当に他のところではうまくいってるのか？
ちょっと実行ファイル出してみろよ。
0631じゃ、ちょとだけ
NGNG0632デフォルトの名無しさん
NGNG女男女男女男女男女男女男 → 娚娚娚娚娚娚
・圧縮率1/3のケース
女男女男女男女男女男女男 → 嫐嬲嫐嬲
女女女女女女女女女女女女 → 姦姦姦姦
0633デフォルトの名無しさん
NGNGネタでした〜
0634デフォルトの名無しさん
NGNGところでmove-to-frontとstart-step-stopは理解できてるのか？
ちょっとどういう理解か説明してみ？
0635デフォルトの名無しさん
NGNG0636デフォルトの名無しさん
NGNG日頃の行ないが悪いからそういうことになるんだ
0637デフォルトの名無しさん
NGNGでなきゃ、実行ファイルを作れるソース全部あげてみろ。
0638デフォルトの名無しさん
NGNG0639デフォルトの名無しさん
NGNGところでstart-step-stopってどうコーディングすればいいのか分かりましぇん。
いろんなパラメータで実験してるところから見て恐らくstart,step,stopを
渡せばそのパラメータで符号化・複合する汎用ルーチンを使ってるんじゃないか
と思うんだけど、もしそうなら是非見せて欲しい。
車
車車 → 轟
龍龍 → 龖（たしかこれの1/3圧縮バージョンもあったはずだがWindowsにはない？）
0640デフォルトの名無しさん
NGNGlong read_bits(size_t nbits);
int write_bits(unsigned long bitvector, size_t nbits);
int flush_bits(void)
int sss_read(int start, int step, int stop)
{
int bits = start;
int base = 0;
int code;
while (bits < stop && (code = read_bits(1)) != EOF && code == 0) {
base += (1 << bits);
bits += step;
}
if (code == EOF || (code = read_bits(bits)) == EOF) return EOF;
return code + base;
}
int sss_write(int start, int step, int stop, int code)
{
int bits = start;
int base = 0;
int limit = (1 << start);
while (bits < stop && code >= limit) {
write_bits(0, 1);
base = limit;
bits += step;
limit += (1 << bits);
}
if (bits < stop) write_bits(1, 1);
return write_bits(code - base, bits);
}
0641デフォルトの名無しさん
NGNG全然圧縮されねーぞ。やっぱネタ？
0642デフォルトの名無しさん
NGNG完成してないんだよな。
完成してないものは試しようがない。
従って、圧縮されたと言ってるのは妄想。
0643デフォルトの名無しさん
NGNGｻﾝｸｽｺ!! あとでじっくり読んでみます。
>>641
否定派は否定するならするでもっと真面目にやってください。
工夫しないネタは只のゴミです。
0644デフォルトの名無しさん
NGNG0645デフォルトの名無しさん
NGNG0646デフォルトの名無しさん
NGNGでもビット入出力ルーチンも書けない>>642はどうかと思う
あと素っ頓狂なことを言っている>>641もどうかと。
SSS符号は、単なる符号なんだからモデルをちゃんと作らなくちゃ、圧縮できるはずがない。
そのためのMTFであり>>540なんだろうに。
0647デフォルトの名無しさん
NGNG高い頻度で出現する記号ほど出現間隔は短くなる。頻度の偏りが大きいと
間隔の平均値は小さくなる。これを利用したのがMTF。
「１つ前の記号がxであるときの記号aの出現頻度P2(a,x)」は、
単なる出現頻度P1(a)より一般には偏りが大きい。たとえば、Cのソースだと
改行文字の後に#が出てくる確率は、他の文字の後に出てくる確率よりずっと
高い。
なので、640のように「１つ前の記号」ごとにまとめてMTFで出現間隔をとると、
１次のMTFより平均値が小さくなる。
最悪で、前の記号と無関係（P2(a,x)＝P1(a)）の場合でも、640は１次のMTFと
同じになる。（１ブロックごとに１文字ふえるだけ。）
0648647
NGNG0649デフォルトの名無しさん
NGNG#include <stdio.h>
#define BLOCK_SIZE 65536
#define ALPHA_SIZE 256
#define ALPHA_BITS 8
unsigned long bitbuf;
size_t bufbits;
void write_bits(unsigned long c, size_t bits)
{
bitbuf = ((bitbuf << bits) | (c & ((1 << bits) - 1)));
bufbits += bits;
while (bufbits >= ALPHA_BITS) {
putchar(bitbuf >> (bufbits - ALPHA_BITS));
bufbits -= ALPHA_BITS;
}
}
void flush_bits()
{
if (bufbits > 0)
putchar(bitbuf << (ALPHA_BITS - bufbits));
fflush(stdout);
}
0650デフォルトの名無しさん
NGNGvoid sss_write(int start, int step, int stop, int code)
{
int bits = start;
int base = 0;
int limit = (1 << start);
while (bits < stop && code >= limit) {
write_bits(0, 1);
base = limit;
bits += step;
limit += (1 << bits);
}
if (bits < stop) write_bits(1, 1);
write_bits(code - base, bits);
}
int mtf_array[ALPHA_SIZE];
void mtf_write(int alphabet)
{
int i;
int u, next_u;
for (u = mtf_array[0], i = 0; u != alphabet; ) {
next_u = mtf_array[++i];
mtf_array[i] = u;
u = next_u;
}
mtf_array[0] = u;
sss_write(1, 2, 9, i);
}
0651デフォルトの名無しさん
NGNGunsigned char buffer[BLOCK_SIZE];
long list[BLOCK_SIZE], head[ALPHA_SIZE];
int main(int argc, char *argv[])
{
int i, count;
unsigned a;
long p;
for (i = 0; i < ALPHA_SIZE; i++)
mtf_array[i] = i;
while ((count = fread(buffer, 1, BLOCK_SIZE, stdin)) > 0) {
mtf_write(buffer[0]);
buffer[count] = buffer[0];
for (i = 0; i < ALPHA_SIZE; i++)
head[i] = -1;
for (i = count - 1; i >= 0; i--) {
a = buffer[i];
list[i] = head[a];
head[a] = i;
}
for (i = 0; i < ALPHA_SIZE; i++) {
for (p = head[i]; p >= 0; p = list[p])
mtf_write(buffer[p + 1]);
}
}
flush_bits();
return 0;
}
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ソースでも圧縮できない圧縮法に何の意味があんの？
■ このスレッドは過去ログ倉庫に格納されています