【2ch】圧縮アルゴリズム【オリジナル】
■ このスレッドは過去ログ倉庫に格納されています
0001１
NGNG中途半端に圧縮されて拡張子が.2ch
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デフォルトの名無しさん
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通り持って直前の文字で切り替える
少し良くなる（かも知れない）けどぱっとしないなぁ…
■ このスレッドは過去ログ倉庫に格納されています