【2ch】圧縮アルゴリズム【オリジナル】
■ このスレッドは過去ログ倉庫に格納されています
0001１
NGNG中途半端に圧縮されて拡張子が.2ch
0584デフォルトの名無しさん
NGNGでは次のネタどうぞ。
0585デフォルトの名無しさん
NGNGなんでこれで圧縮できると思うの？
0586デフォルトの名無しさん
NGNGMTFとは違う特徴をもったアルゴリズムを作りたかったからだろう。
実際、MTFでは理論的・実践的にいまいちな場面というものが存在する。
普通の定常無記憶情報源での比較ではなく、
特殊な状況で役に立つアルゴリズムというのを考えてみるのもよい。
オレは上の関連で論文を一本書いた。
0587デフォルトの名無しさん
NGNG情報理論の分かるヤツと
分からないけどとりあえずコードを書いて分かったつもりになってるヤツと
分からないのでひたすら煽るだけのヤツがいゐ…
0588デフォルトの名無しさん
NGNG分からないのでひたすら煽るだけのヤツ
0589デフォルトの名無しさん
NGNG同意。何かを分析した気になっている。
0590デフォルトの名無しさん
NGNGとりあえず情報理論の教科書でもあげてもらうか。
0591デフォルトの名無しさん
NGNGそして逆ギレ。
0592デフォルトの名無しさん
NGNG限定ソート？
0594デフォルトの名無しさん
NGNG0595540
NGNG一言で言うとそうなりますね。
単なる最大限定ソート。
次数を上げるとまさに限定ソートそのものです。
M.BurrowsとD.J.Wheelerが最初に考えたのが
540のような感じじゃないかなと思ったり。
0596デフォルトの名無しさん
NGNG0597590
NGNG韓太舜・小林欣吾、情報と符号化の数理、培風館
植松友彦、現代シャノン理論、培風館
情報理論とその応用学会編、情報源符号化 無歪みデータ圧縮
他にはデータ圧縮関連の和書洋書、アルゴリズム関連の本、
情報処理学会、電子情報通信学会、IEEE、などの論文集。
0598デフォルトの名無しさん
NGNGMTFで「何記号前に出現したか」の平均符号長は1次エントロピーに
漸近するのに対し、540だと2次エントロピーに漸近すると思うのですが。
0599デフォルトの名無しさん
NGNGわかっている人は、
MTFやブロックソートと同様、記号をかき混ぜているだけで長さは変わらない
ということがちゃんとわかっているから、大丈夫だろうけど。
わかっていない人は、
そもそも>>540の手法とMTFやブロックソート法との比較もわからないのだと思う。
0600デフォルトの名無しさん
NGNGわからない人の振りをして荒らしてるだけかも…
ってのは考えすぎか。
0601デフォルトの名無しさん
NGNG0602デフォルトの名無しさん
NGNGMTFは記号の出現頻度を故意に変えることで圧縮率を高めるし、
ブロックソートは同じ記号をまとめることで、圧縮率を高める。
だけど、これは本当に単に並べ替えてるだけ。
なぜこれで圧縮率が変わると思えるのか、それが知りたい。
どういう理論？
0603デフォルトの名無しさん
NGNGたとえ数パーセントでも圧縮されるのなら、>>1の出した仕様に適合すると思われ。
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改行程度のことで大きくなるようなものでも圧縮って言うの？
■ このスレッドは過去ログ倉庫に格納されています