【2ch】圧縮アルゴリズム【オリジナル】
■ このスレッドは過去ログ倉庫に格納されています
0001１
NGNG中途半端に圧縮されて拡張子が.2ch
0546デフォルトの名無しさん
NGNG漏れの少ない脳みそを検索した結果だな……(・∀・)ｲｲ！。行けると思う。
マジで。
0547デフォルトの名無しさん
NGNG>>540 を実装してみた。符号化してないのでサイズ増えるけどｗ
復元の為の付加情報は符号化のときに一緒に折り込むのがいいかな？
0548デフォルトの名無しさん
NGNG>符号化してないのでサイズ増えるけどｗ
その処理を通す前と通した後のデータをそれぞれLZHか何かで適当に圧縮してみそ。
それで圧縮率が変わるようならモデルとしては優秀なんじゃない。
なるべく大きなデータがいいね。当然jpegやmp3はダメだぞ。
0549デフォルトの名無しさん
NGNG0550540
NGNGコンパイルしてないけど、
入力データの最初と最後に記号a を付加して、
それごとエンコードすれば、復元の為の付加情報は必要なくなると思う。
どっちがいいのか分からないけど。
...aaa abcacacabca a
0551デフォルトの名無しさん
NGNG0552540
NGNG＜エンコード＞
入力：a abcacacabca a
aの次：abccba
bの次：cc
cの次：aaaa
出力：abccbaccaaaa
＜デコード＞
入力：abccbaccaaaa
aの数：6個、bの数：2個、cの数：4個より、
abccba cc aaaa
とわかり、aから始まるので、順にたどれば、
aabcacacabcaa
となり、先頭と最後を取り除けば、
出力：abcacacabca
ダメかな…。
0553デフォルトの名無しさん
NGNGよーわからんが 最後の a って付加する必要ある？
055457
NGNGいいんじゃない？
その方法なら先頭にa(実際の実装なら'\0'か？)を付けるだけで良いと思う。
あと、その方法、なんかBlockSortingの復号みたいだな
#自分でも>>540を実装してみたけど逆に圧縮率落ちた。鬱。
0555540
NGNGたぶんない。
デコードの際、各記号の数を数えるときに都合がよかったのかな。
>>554
大量の文脈を使えばある程度効果はあると思うけど、
力不足で実装できませんでした。
0556デフォルトの名無しさん
NGNG>aの数：6個、bの数：2個、cの数：4個より、
なぜ「cの数：4個」とわかるのか？と小一時間問い詰めたい。
0557デフォルトの名無しさん
NGNGcという文字の前に来ている文字が４個、また最初の文字はaなので、cは４個
じゃないのかなぁ・・・
0558デフォルトの名無しさん
NGNG逆転文字列をブロックソートした状態になるんじゃないか？
0559540
NGNG「aの数：6個、bの数：2個、cの数：4個より」
というのは、デコード時の入力データ「abccbaccaaaa」
の各記号の個数を数えただけです。
エンコード時、最初と最後にaを付け加えることにより、
上のように単純に数えることができると考えたんだと思いますが、
余計だったかもしれません。
理屈は>>557の通り。
> 逆転文字列をブロックソートした状態になるんじゃないか？
ですね。
出力結果がブロックソート法より良くなることは無いです。
0560デフォルトの名無しさん
NGNG新しい発想でかんがえようよ！
定石やあるゴリ図無なんてｸｿ倉枝よ！
0561デフォルトの名無しさん
NGNG0562デフォルトの名無しさん
NGNG符号化はもうほとんど算術符号になってるよ。
一部の分野でGolomb符号などが使われているくらい。
今問題にしているのはモデル化の話。
0563デフォルトの名無しさん
NGNG算術符号は特許問題がやっかいなので使わぬが吉。
RangeCoderにしとけ。
0564デフォルトの名無しさん
NGNGRangeCoderも白っぽいけど灰色という罠
0565デフォルトの名無しさん
NGNG0566これでええやんけ
NGNG// 希望の圧縮率にできる限り近い圧縮をおこなっちゃうよっ
bool compresser(void *soce //圧縮対象メモリ
,int soce_size //圧縮対象メモリサイズ
,void *dest //展開先メモリ
,int dest_size //展開先メモリサイズ
,int compress_rate) //希望の圧縮率
{
if( compress_rate<1 || 99<compress_rate ){
printf("1〜99 の間で指定しろや！");
return false;
}
for(int i=0,w=0; i<soce_size; i++){
if( (rand()%100) > compress_rate ) continue;
if( dest_size>=w ){
ptinrf("展開先ちゃんと確保しろや！");
retunr false;
}
dest[w++] = soce[i];
}
print("%d％に圧縮しますた[ハート]",w*100/soce_size);
return true;
}
0567デフォルトの名無しさん
NGNG0568デフォルトの名無しさん
NGNG99を指定すると無圧縮に…
0569デフォルトの名無しさん
NGNGfile.open();String content = file.readAll();file.close();
file.rename(Base64.encode(content));
file.open();file.write(filename);file.close();
0570デフォルトの名無しさん
NGNG_（ ´∀｀） （´∀｀ ）
三(⌒), ノ⊃ （ >>1 .） 糞スレは
￣/ /) ） | | |
. 〈＿）＼_） （__（_＿_）
∧＿∧ .∧＿∧
（ ´∀） （´∀｀ ）
≡≡三 三ニ⌒) >>1 .） 立てるなって
/ /) ） ￣.| | |
〈＿_）＿_） （__（_＿_）
∧＿∧ ,__ ∧＿∧
（ ´）ノ ）:;:;)∀｀）
/ ￣,ノ'' >>1 . ） 言ってるだろうが
Ｃ /~ / / /
/ / 〉 （__（＿_./
＼__）＼）
ヽ ｌ /／
∧＿∧(⌒) ―― ☆ ―――
（ ） /|ｌ ／/ | ヽ ヴォケがーー！
（/ ノｌ|ｌｌ ／ / | ヽ
（Ｏ ノ 彡'' / .|
/ ./ 〉
＼__）_）
0571566
NGNGおお、そだな。 0-99の乱数発生だな。
rand関数 滅多につかわんので、まちがえちまった。 % 演算把握の問題って向きもあるが。
> if( ((rand()%100)+1) > compress_rate ) continue;
こんな感じでかんべんしてくれ。
0572デフォルトの名無しさん
NGNGBlockSortingみたいにMoveToFrontにして前の出力との
位置の差を算術符号かstart-step-stop符号で符号化す
れば圧縮できるだろう。
たぶん、素の(0次の)MTFよりは良くて、BlockSortよりは
悪い、実に中途半端な圧縮率が得られてスレの主旨に
ぴったりでは。速度も中間になる(BSよりはだいぶ速い)
はず。
0573デフォルトの名無しさん
NGNG0574デフォルトの名無しさん
NGNG圧縮は当然できるだろ。
0次のMTFと比べてどうかはわからんが。
0575デフォルトの名無しさん
NGNGなんでできると思うんだ？
0576540
NGNG1次に限らずとも可能ですよ。
おっしゃるとおり、2次程度の540 → MTF → 算術でそれなりに縮みます。
大量の文脈を使用する場合、>>547のソースでいう code_count の
扱いが問題になると思います。
0577デフォルトの名無しさん
NGNGいや、これ次数を高くしたらつまんないと思う。
普通のPPMコーダとかの、高次混合モデルを
作るやつの方が良くなっちゃう。
単にバッファを1MBくらいに大きくしてみれば？
0578540
NGNGそうかもしれませんね。
ただ、1次と2次の性能の差はかなり大きかったです。
バッファは8Mでテストしたと思いますが、
これを増やしてもそれほど意味は無いはず。
0579デフォルトの名無しさん
NGNG>>572
0次と1次じゃなくて、1次と2次では？ 540のアルゴリズムは2次の
エントロピーコーダですよね。
0580デフォルトの名無しさん
NGNG0581デフォルトの名無しさん
NGNGこんなのがあった…。
0582デフォルトの名無しさん
NGNG>>572を実装しますた。頻度表も>>552と同じような方法で追い出し。
SSS符号はイマイチな予感（LZFGで使ってるの位しか知らない…）。
次のアプローチとしてはSSSの代わりに連長＋RangeCoderを導入するか
二次化なんだろうけど、さて。
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デフォルトの名無しさん
NGNG■ このスレッドは過去ログ倉庫に格納されています