【2ch】圧縮アルゴリズム【オリジナル】
レス数が900を超えています。1000を超えると表示できなくなるよ。
0001１
NGNG中途半端に圧縮されて拡張子が.2ch
0809デフォルトの名無しさん
NGNGアルゴリズムが同じでも、コーディング能力によって倍くらいコード長が違う。
ま、>>795,>>808と同じでいまさらBWTがどうしたなんかどうでもいいが。
0810デフォルトの名無しさん
NGNGさっさと30行で書いて見せろっつーの。
0811デフォルトの名無しさん
NGNG7行プログラミングスレにありましたよ
0812デフォルトの名無しさん
NGNG圧縮できる完動品が？
0813デフォルトの名無しさん
NGNGMTFとレンジエンコーダーもあるから、自分で組み合わせてみたら。
つーか、そもそもの発言は符号化までは含まない単体のBWTについてだったのでは？
0814デフォルトの名無しさん
NGNG話してて、実際に完動するソースが出てて、
ソースのサイズ比べる話が出て、なんでそこだけ「符号化までは含まない
単体」の話になるんだよ。
0815デフォルトの名無しさん
NGNG知るかYo
0816デフォルトの名無しさん
NGNGそうかYo
0817デフォルトの名無しさん
NGNGも前らに聞いてないYo
0818デフォルトの名無しさん
NGNGそれなら、その限定ソートの部分を完全ソートに置き換えればいいだけでは？
BWTは速度を気にしなければ、
・読み込んだバッファを２倍にして同じものをコピー(2行)
・インデックス生成(1行)
・ソート(qsortでも何でもいい)(1行)
・比較関数(2,3行)
・FirstIndexとソート結果のインデックスから文字を出力(4,5行)
で書けます。マルチで書けば、ほとんどが一行に収まります。
0819デフォルトの名無しさん
NGNG0820デフォルトの名無しさん
NGNG7行スレのBWTを分解して>>649に組み込めYo
0821デフォルトの名無しさん
NGNG面倒だYo
お前がやってくれYo
0822デフォルトの名無しさん
NGNGスレの中もログの中も 探したけど見つからないのに
まだまだ探す気ですか それより自分で書いてみませんか？
ＢＷＴを ＢＷＴを 書いてみたいと思いませんか？
ウフッフー ウフッフー ウフッフー さーあー！
0823デフォルトの名無しさん
NGNGBWTは7行スレpart2にあったはず。現在dat中。
0824デフォルトの名無しさん
NGNG0825デフォルトの名無しさん
NGNGなんでqsortつかったトロいソート書くんだよ？
七行part2のブロックソートって
#include <stdlib.h>
typedef unsigned char b;e(b*s,b*d,int c){unsigned*o,i=0,r;o=calloc(65536,4);c--
;for(i;i<c;i++)o[s[i]<<8|s[i+1]]++;o[s[c]<<8|*s]++;for(i=1;i<65536;i++)o[i]+=o[
i-1];d[--o[s[c]<<8|*s]]=s[i=c-1];for(;i;i--)d[--o[s[i]<<8|s[i+1]]]=s[i-1];r=--o
[*s<<8|s[1]];d[r]=s[c];free(o);return r;}
これと
#include <stdlib.h>
typedef unsigned char B;void d(B*s,B*d,int c,unsigned x){unsigned*o,i,a=0,t[256
];memset(t,0,1024);for(i=--c;i;i--)t[s[i]]++;o=calloc(65536,4);for(;i<256;i++){
memset(d+a,i,t[i]);a+=t[i];}for(i=0;i<=c;i++)o[(s[i]<<8)+d[i]]++;for(i=1;i<
65536;i++)o[i]+=o[i-1];*d=d[x];d[c]=s[x];d[c-1]=s[--o[(d[c]<<8)+*d]];for(i=c;i>
2;i--)d[i-2]=s[--o[d[i-1]<<8|d[i]]];free(o);}
これと
#include <stdlib.h>
enum{S=256};typedef unsigned char UC;int cmp(void*a,void*b){return memcmp(a,b,S
);}UC*bs(UC*s,UC*d){UC*p,**t,i;p=malloc(S*2);t=malloc(S);for(i=0;i<S;i++)p[i]=p
[i+S]=s[i],t[i]=p+i;qsort(t,S,S,cmp);for(i=0;i<size;i++)if(p== t[i])break;*d++=
i;for(i=0;i<S;i++)d[i]=t[i][S-1];free(p);free(t);return --d;}
これくらいだぞ
0826デフォルトの名無しさん
NGNGデコるときの複雑さと遅さを考えると、使う気になれない。
0827デフォルトの名無しさん
NGNGケツから復元していけば良いだけだろ？
まぁ、キャッシュは外れまくりそうだが…
0828デフォルトの名無しさん
NGNGデコードは完全ソートの方がシンプルで高速だよね。
0829デフォルトの名無しさん
NGNG必死なヤツがいるかどうかだったのか…
おまいら必死だな（藁
0830デフォルトの名無しさん
NGNGhttp://pc3.2ch.net/test/read.cgi/tech/1036013915/
圧縮してくれ
0831デフォルトの名無しさん
NGNG0832デフォルトの名無しさん
NGNGpc3.2ch.net/test/r.i/tech/1036013915
少し短くしますた。
0833デフォルトの名無しさん
NGNG糸冬 了
0834デフォルトの名無しさん
NGNGnever
uzeee
0835shinnet
NGNG0836デフォルトの名無しさん
NGNG0837デフォルトの名無しさん
NGNG話題にも上らないよりかは。。
0838デフォルトの名無しさん
NGNGボクは、僕はyz2も大好きです！！
0839ｙｚ２
NGNG0840デフォルトの名無しさん
NGNG0841デフォルトの名無しさん
NGNGベータになるのか、アルファのまんまか、はたまた出ないのか？
0842デフォルトの名無しさん
NGNG0843デフォルトの名無しさん
NGNG0844デフォルトの名無しさん
NGNG0845デフォルトの名無しさん
NGNG初耳です。
> HSP（High Speed signal Processor）
> 各種圧縮／伸張フォーマット(*2)に対応した高速DSPです。
うーん。アルゴリズムと関係あるのか？
0846デフォルトの名無しさん
NGNG同じ全角文字はたくさん出てくるだろうし
半角文字2つの同じ並びもたくさん出てくるだろうし。
0847デフォルトの名無しさん
NGNG人様の作ったものに対して色々文句言ってるやつがいるが、
文句があるなら自分で作ればよかろう。
それも出来もしないなら、おとなしくいていろってこった。
0848デフォルトの名無しさん
NGNG激しく同意
0849デフォルトの名無しさん
NGNG同意。
0850デフォルトの名無しさん
NGNGまったく同意
0851デフォルトの名無しさん
NGNG0852デフォルトの名無しさん
NGNGSYNﾀﾝは>>847とは逆の意見という罠
download板での発言
578 名前：SYN 投稿日：02/01/23 22:44 ID:NsxsovNn
>>562
様々な改善案を教えていただけるだけでなく、本音で「ここが糞」
という意見が聞ける2chは、本当にありがたいです。
0853デフォルトの名無しさん
NGNGもっと速いバージョンはバグが入ったので、今作りなおしている。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static unsigned char *pText;
static int gLen;
int compare(const void *a, const void *b) {
int l = gLen - ((*(int *)a < *(int *)b) ? *(int *)b : *(int *)a);
int r = memcmp((const char *)(&pText[*(int *)a]),
(const char *)(&pText[*(int *)b]), l);
return (r == 0) ? (*(int *)b -*(int *)a) : r;
}
int main(int argc, char *argv[]) {
FILE *fp;
unsigned char *str;
int i, j, k, l, *aArray, *aNext, pos, list[256], sum[256];
if (argc < 2) {puts("usage> exec infile"); return -1;}
fp = fopen(argv[1], "rb");
fseek(fp, 0, SEEK_END); gLen = ftell(fp); rewind(fp);
pText = str = (unsigned char *)malloc(gLen +1);
fread(str, 1, gLen, fp);
str[gLen] = 0;
0854853続き
NGNGaNext = (int *)malloc(sizeof(int) *(gLen +1));
for (i = 0; i < 256; i++) {
list[i] = -1;
sum[i] = 0;
}
for (i = gLen; i >= 0; i--)
if (str[i] > str[i +1]) sum[str[i]] += 1;
else {
aNext[i] = list[str[i]];
list[str[i]] = i;
}
for (pos = i = j = k = 0; j < 256; j++) {
pos = i = sum[j] + pos;
for (l = list[j]; l >= 0; l = aNext[l]) aArray[pos++] = l;
qsort(aArray + i, pos - i, sizeof(int), compare);
for (l = i - sum[j]; l < i; l++) {
if (aArray[k] == 0) k++;
aArray[l] = aArray[k++] -1;
}
}
return 0;
}
0855853
NGNG0856853
NGNGint i, j, l, *aArray, *aNext, pos, list[256], sum[256], typeA[256], t = 0;
...
for (i = gLen; i >= 0; i--)
if (str[i] > str[i +1]) {
sum[str[i]] += 1;
t++;
}
else {
aNext[i] = list[str[i]];
list[str[i]] = i;
}
for (pos = i = j = 0; j < 256; j++) {
pos = i = sum[j] + pos;
for (l = list[j]; l >= 0; l = aNext[l]) aArray[pos++] = l;
qsort(aArray + i, pos - i, sizeof(int), compare);
typeA[j] = i - sum[j];
}
for (i = 0; t >= 0; t--) {
if (aArray[i] == 0) i++;
aArray[typeA[str[aArray[i] -1]]++] = aArray[i++] -1;
}
0857デフォルトの名無しさん
NGNGよくわかんないけど最後のforはもっと長くループさせないとだめじゃない?
たとえば、最後までまわすとか
for (i = j = 0; j < gLen; j++) {
0859デフォルトの名無しさん
NGNG0860デフォルトの名無しさん
NGNG0861デフォルトの名無しさん
NGNG0862デフォルトの名無しさん
NGNG0863デフォルトの名無しさん
NGNGkterm + lynx で見て、unreadable にすればいいのだ！
0864デフォルトの名無しさん
NGNGTiny なら、全体のバランスを調整するときに使ったことはあるが。
（IEのフォントサイズ小みたいに）
unreadable は本当に読めないし、つぶれるからいまいち。
0865デフォルトの名無しさん
NGNGこれってどうなのさ
0866デフォルトの名無しさん
NGNG強敵だな（ｗ
0867デフォルトの名無しさん
NGNGlossyな圧縮か。比べてもあまり意味ないな…
0868デフォルトの名無しさん
NGNG圧縮ソフトを発表した。
使用されているCATアルゴリズムは、圧縮アルゴリズムを複数用いるこ とで、例えば画像
であれば「建物」「空」といったパーツごとに最適な圧縮アルゴリズムを選択し、ファイルサ
イズを縮小する。
同社調査によれば、3.33MBのJPEG画像が、ZIP圧縮の場合3.31MBにしかならなかった
ものを、114KBにまで縮小できた。
不可逆圧縮だが、見た目上はほとんど変わらない画像になる。複数のアルゴ リズムを
利用するにもかかわらず、
「圧縮・解凍時間ともに短時間」 である点も 特徴だ。
http://pcweb.mycom.co.jp/news/2002/11/13/09.html
0869デフォルトの名無しさん
NGNG0870デフォルトの名無しさん
NGNGMPEG1をMPEG4にコンバートしてるようなもんだろ?
ZIPと比べてるのは不当表示だよ。
0871デフォルトの名無しさん
NGNG0872デフォルトの名無しさん
NGNG0873デフォルトの名無しさん
NGNG0875デフォルトの名無しさん
NGNGhttp://www.quikcat.com/
超縮は、↑の QuikCAT Messaging Optimizer の
日本語版・・・のような気がするなぁ。拡張子も同じ .qcf だし。
英語版だけど、試用できるっぽい。
495：名無しさん＠お腹いっぱい。：sage：02/11/13 (水) 23:57 ID:7Pz0RnHA
↑にあるのはただのデコーダなだけじゃない？
496：◆Ukspgzd3n6：sage：02/11/14 (木) 00:05 ID:SsZE8nfL
>>495
あ・・・そうだった。
でも、圧縮する方法あり。
http://www.quikcat.com/products/qmo/qmo_tryit.htm
要するに、[email protected] にファイルを
送ると､圧縮して返送してくれる。
ちょっと試してみる。
まだ [email protected] からの返事が無い。
ちなみに、フリーソフトの Compressed File Reader は 6MB もする。
何だかと思えば、解凍ルーチンの DLL が妙にデカい。
相当複雑なアルゴリズムなんだろうなぁ。多分。
> 相当複雑なアルゴリズムなんだろうなぁ。多分。
て、そんなこと無いな。(・∀・;)
0878デフォルトの名無しさん
NGNG漏れは、盗まれても構わないファイルを送ったYo
しかし、きちんと「圧縮してくれ」と文面に書いておかないと駄目かも。
未だに返事は来ないし。
0880デフォルトの名無しさん
NGNG翻訳サイトなんか当てにならない。
0881デフォルトの名無しさん
NGNG翻訳サイトが不自然な英語であることを見抜けないなら
0882デフォルトの名無しさん
NGNG0883デフォルトの名無しさん
NGNG情報である程度はわかったけど、詳しいインプリメンテーションが
よくわからん。何か情報ない？
0884デフォルトの名無しさん
NGNGttp://mcgi2.nifty.ne.jp/cgi-bin/thread.cgi?user_id=VZV05226&disp_no=1068&log_no=484&msg_per_page=10&def=10
これじゃ不満なのか？
（ﾟ∀ﾟ）Sﾀﾝ ﾆ ｱﾔﾏﾚ！
0885デフォルトの名無しさん
NGNGいや、情報はありがたいのだが、そのレベルはＣマガに出ているのよ。
ただＣマガのソースってコメントがほとんどないし、バグは残ってるし
で今ひとつわからん（展開スタック不足だった＞Ｃマガソース）。
ちなみに、その掲示板の「アスキー128を８ビットで〜」のくだりは半分
間違い。バイナリデータの圧縮にも効果はあるし、圧縮パラメータの
設定次第だがLZW法に近い圧縮率が得られる。しかも圧縮は遅いが
展開は高速（ビットレベルで符号化しないから当然）。
088657
NGNGhttp://www.csse.monash.edu.au/cluster/RJK/Compress/problem.html
http://www.csse.monash.edu.au/cluster/RJK/Compress/bpe.c
http://www.csse.monash.edu.au/cluster/RJK/Compress/bpd.c
日本語の解説のページは数年前はあったんだけど今は消えてる。
0887デフォルトの名無しさん
NGNGんなこたぁない。
割り当てキャラクタ数を最適化したとしてもLZファミリには及ばないよ
0888デフォルトの名無しさん
NGNG同意
＞ちなみに、その掲示板の「アスキー128を８ビットで〜」のくだりは半分
＞間違い。バイナリデータの圧縮にも効果はあるし、圧縮パラメータの
＞設定次第だがLZW法に近い圧縮率が得られる。
オリジナルのBPEは純粋に7ビットASCIIオンリーだったはず。
バイナリ対応やLZW並みの圧縮率というのは、改良版ではないか？
0889デフォルトの名無しさん
NGNGGage[1994]が見つからなかったが（雑誌の記事だから?）、
調べてみると、BPEには単純版と改良版があるらしいぞ。
そもそもその単純版が、1994年よりももっと前（70年代〜80年）に
提案された別の方法を改善したものとして存在し、
それをさらにバイナリデータ対応、LZW並みの圧縮性能にしたのがGageらしい。
やぱーり、The C Users Journal, February 1994 edition か
Cマガジンを読むしかないのか。
0890デフォルトの名無しさん
NGNG885だけど、それは頻出バイトペアや未使用キャラクタの余り数、圧縮ブロックの
サイズ設定とかでかなり違ってくると思われ。LZWに適したデータ分布やBPEに
適したデータ分布は当然あると思うし、頭ごなしに全否定するのもどうかと思うが。
で、圧縮率に関しては「近い」というのがミソで、LZW以上の圧縮を得ようとは思わ
ない。展開が非常に高速で（展開のコストが安く）実用になる圧縮率があることが
重要なんだよ。実際にCマガのをデバッグしたソースでバイナリを圧縮してみたが
多くの場合で半分から４５％程度に縮んでいた。これくらいなら十分。
0891デフォルトの名無しさん
NGNG>>889
ありがとう、参考になった。
0892デフォルトの名無しさん
NGNG検証してないけど、LZWってBPEより必ず圧縮率がいいんじゃないか？
両者とも、SEQUITORと同じ系に属するだろ？
で、両者が作る辞書のモデルを解析して比較してみれば、
その関係がわかると思うんだけど・・・。
BPEの辞書はLZWの増分分解で作成される辞書と同じ形になる・・・と思うし、
後は出現頻度順か、出現順かの違いくらいで・・・。
多分誰か解析していると思うなぁ・・・njNECで探してみるか。
0893デフォルトの名無しさん
NGNGttp://homepage1.nifty.com/author/qcf/jpegqcf.htm
0895デフォルトの名無しさん
NGNG0896デフォルトの名無しさん
NGNG差分とって、誤差が一定になるまで出力しない、っていうのじゃなかったかなぁ？
どっかの紹介記事にそういう説明があった気がする。
試しにやってみても、全然縮まなかったので、
もちろんもっとそれ以上の何かが必要なのだろうけど。
0897アフォヴァカさん
NGNGなんでファイルサイズをわざわざテキストで
出力するかイマイチ理解出来ん。
小さいファイルなら元ファイルのサイズを出力する
と確かに無駄な部分が出てくるが、それだったら
１６進表記でテキスト出力した方が効率か良いよう
な気がする・・・数字＋アルファベットで３６進数で表記とか・・・
ってここまで面倒な事はしなくていいか（ｗ
0898デフォルトの名無しさん
NGNGElias符号使えば？
記事にワケが書いてあったと思う。
それに、テキストで出力しておけば、事実上どこまでも
大きいファイルサイズも表現できると思うが。
0900デフォルトの名無しさん
NGNG別にテキストじゃなくても同じことができるし
テキストを使わないほうが小さくなることに変わりはない。
そりゃね。
Filesize のビット数を記録すれば問題ないことだし。
#テキストだとしても、ヘッダごと圧縮すれば問題ないかも。
0902デフォルトの名無しさん
NGNGそのために>>898に書いてあるような符号化法を使うんだろ？？？？
0903デフォルトの名無しさん
NGNGヘッダのサイズなんて大きな圧縮ファイルでは誤差の範囲だろ。
”Keep it simple, stupid.（単純なままにしとけって言っただろ！このヴォケが！）”だ。
0904デフォルトの名無しさん
NGNG数値1つエンコードするのが複雑だというくらいなら
そもそも圧縮プログラムなんて論外だろ。
だいいち、2進10進変換＋10進2進変換がエリアス符号に比べて
そんなにシンプルかよ。糞ヴォケ。
0905デフォルトの名無しさん
NGNG0906デフォルトの名無しさん
NGNG書庫内のファイル名も圧縮対象にするってこと？
識別用のマジックナンバー以外はやっちゃってもいいかもね。
リスト出力に多少時間かかりそうだけど。
どうでもいいけど、作るんなら統合アーカイバPrjのDLL形式にも
対応して欲しい。（GCAとか対応してたっけ？）
わざわざ独自にＧＵＩ作ったりしてるのあるけど、無駄にしか思えない。
0907デフォルトの名無しさん
NGNG0908デフォルトの名無しさん
NGNG0909デフォルトの名無しさん
NGNG「やまもと・おち」のフラッグ符号がいいかもしれないよ。
最適性の確保は難しいが、高速で、符号自身で誤り伝搬を防げるから。
まあ何にしろ、10^15程度の数値を表現するには60ビット程度あれば
一意復号可能な符号などいくらでもあるわけで。
（もちろんそれらは、加算無限大の数値をいくらでも表現できる）
レス数が900を超えています。1000を超えると表示できなくなるよ。