【2ch】圧縮アルゴリズム【オリジナル】
■ このスレッドは過去ログ倉庫に格納されています
0001１
NGNG中途半端に圧縮されて拡張子が.2ch
0751デフォルトの名無しさん
NGNGだから最初にランレングスしたり
ブロックのバイト列の終端にどの数よりも必ず大きく（小さく）なる値を割り当てて
比較長を短くしたりする、いろいろな工夫があるんだろ？
0752デフォルトの名無しさん
NGNGブロックサイズを（完全と比べて）果てしなく大きく取ることが出来るので
ある種のデータではブロックが小さい完全ソートより
良好な結果を得ることが出来ると思うんだが。
0753デフォルトの名無しさん
NGNGだから単純なソートだと遅いから高速化に苦労してたって、>>748が言ってるだろ？
0754デフォルトの名無しさん
NGNGそれならば、すでに先人が苦労した成果があるんだから
後からそれを利用するだけなら大した苦労も無いだろう。
0755デフォルトの名無しさん
NGNG話の筋を追えんやつだな（ｗ
0758デフォルトの名無しさん
NGNG80行で完全ソート書いてみて >>SYN
0759デフォルトの名無しさん
NGNG0760デフォルトの名無しさん
NGNG0761デフォルトの名無しさん
NGNGオーダーにするとその通りだけど、限定ソートなら 1(n/2)+ちょっと で出来るでしょ。
0762デフォルトの名無しさん
NGNG>>758
限定ソートほどじゃないけど、速度を気にしなければ、
普通に書いても2,30行ぐらいでいけます。
ちなみに展開の方は普通に10行ぐらいで書けます。
>>761
確かにバッファは減らせるけど、それによって確保できるブロックサイズは
精々数倍程度で、果てしなく大きくってほどじゃないと思うけど…
それにブロックサイズは無闇に大きくするとデータの揺らぎに対応できずに、
結果が悪くなることが多いです。
0763デフォルトの名無しさん
NGNG「540＋MTF＋ハフマン」
で圧縮ソフト組んだのですが。
MTFとハフマンはそこらへんから拾ってきたソース組み込んだだけだったけど。
いや、別にいいんだけどさ。
0764デフォルトの名無しさん
NGNG2〜30行ならうｐしてみろや
可変長符号だけで10行やそこらはかかると思うんだが
まさか最密充填コード？
0765デフォルトの名無しさん
NGNG0766ふﾄﾝｶ ◆wX94FutoNg
NGNGDVD-ROM片面２層の辞書を持っている、
有名な曲とか、定番の発言とか、全部入っている
そうしたらすごい圧縮できるんてじゃないでしょうか。
10MBのMP3が10KBに！、とか…
まぁそこまでは行かなくともですが、、まぁ多分、原理的に無理だから誰もしないんですよね、、失礼。
0767デフォルトの名無しさん
NGNG0768デフォルトの名無しさん
NGNGソース公開しろとまでは言わんが、
GCAのMAC版、Unix版が無いのはいかがなものか？
自分でＧＣＡがヘボイと言っているのならそれは自分でゴミを垂れ流してることになるだろ
0769デフォルトの名無しさん
NGNG0770デフォルトの名無しさん
NGNGクリスマスに、ってのが泣ける｡
･ﾟ･(ﾉД`)･ﾟ･｡
0771デフォルトの名無しさん
NGNG身内用に作ったものを勝手に使用しているようなものなのに、なんでえらそうなんですか
もともと趣味で作ったもの。MacやLinux版をわざわざ出すわけないでしょう
圧縮方法もまだしっかり確立していないのに
今のはテスト版のようなもの。圧縮方法がしっかりときまったらソース公開や他OS版も考えるでしょう
0772デフォルトの名無しさん
NGNG0773デフォルトの名無しさん
NGNG0774デフォルトの名無しさん
NGNGそれだけだ
0775デフォルトの名無しさん
NGNGブロックソート関連のWebページ逝けば３０行くらいで普通に載ってるぞ。
それに、bzip2のソースも実質そんなていど、といってみるテスト。
0776☆南幸☆
NGNG0778デフォルトの名無しさん
NGNGMTFが３〜４行、算術符号は５行くらいでかけるから、
qsort使ってよいなら、かなり短くなると思うよ。
0779デフォルトの名無しさん
NGNGもったいぶらずに早く書いてよ。
0780デフォルトの名無しさん
NGNG>>773
>>777
普通BWTは圧縮とは言わないから、符号化までは入れないでしょう。
後段の符号化をやらないで、ベタで垂れ流してもBWTであることには変わりないですし。
0781デフォルトの名無しさん
NGNGなあんだ。ホラかよ。
限定ソートが80行に対して２、３０行で書けるとかほざいときながら。
0782778!=780
NGNG完全ソートなら30行で書けますよね？
限定ソートの方が、工程が多い分だけ長くなるということで。
>>780
始めは俺もBWTだけを書くという話だと思ってたよ。
もしかして>>777>>781はBWTを知らないんじゃないかと・・・
0783デフォルトの名無しさん
NGNG半数が空行やコメントのプログラムが、７３行だった。実質３０行台。
うはっ、われながらひどいプログラムだ。
0784デフォルトの名無しさん
NGNGスマソ。それは遅れていただけで、やる気が無いわけではないです。
確かに今のUIがヘボイことは認めざるを得ません。
ただ、UIの発展をどういう方向に進ませるべきか意見を聞きたかったのです。
結果はDGCAで出せると思います。
同時ではないですが、MAC、Linuxの予定もあります。
0785デフォルトの名無しさん
NGNGいや、bzip2のソースもBurrowsとWheelerの論文も読んでるけどさ。
限定ソートの高速なソースは現に80行かそこらであるわけよ。>>649に。
んで、ＳＹＮは限定ソートのメリットなんて無いとほざいたわけよ。
たった２、３０行で書けると。
ホラ吹くんじゃねーよ（ｗ
0786デフォルトの名無しさん
NGNG30行で高速なブロックソート圧縮プログラム早くうｐして見せろや。
0787デフォルトの名無しさん
NGNG確かに>>649はそれはそれですごいが、
あれをBWTの限定ソートと呼ぶのはどうかと。
そんなことをいったら1次モデルもBWTの限定版になってしまうがな。
0788デフォルトの名無しさん
NGNGSYNの言うこといちいち真に受けるなよ（ｗ
だからコテハンなんてろくな香具師じゃないって。
0789デフォルトの名無しさん
NGNGじゃああんたのいう限定ソートって何？
0790デフォルトの名無しさん
NGNG限定ソートにメリットが無いことは、各種論文でも言われていると思うけど。
本当にブロックソート関連の論文読んだの？
0791デフォルトの名無しさん
NGNGbzip2みたいに、せめて100kバイト程度のブロックであって欲しいな。
0792デフォルトの名無しさん
NGNG2-30行のソースとやら晒して見せろや
嘘つきヤロウ
0793デフォルトの名無しさん
NGNGbzip2のブロックと、限定ソートの長さ制限は意味が違う。
0794デフォルトの名無しさん
NGNGそれだけかよ（ｗ
じゃあ#define直せば限定ソートになるのか？
0795デフォルトの名無しさん
NGNGあー、それなら私が悪かった。申し訳ない。
ソースコードが小さいというがメリットになると思っていなかったので。
ただ、速度を気にしないBWTは異様なほど小さく出来る。
選択ソートやバブルソート使ったら( ﾟДﾟ)ｺﾞﾙｧ！かもしれませんが。
しかし、ここはIDも出ないのですね。自分の発言がどれかわからなくなりそう。
0796デフォルトの名無しさん
NGNGここに載っているのにqsort使うと３０行くらいじゃないか？
0797デフォルトの名無しさん
NGNGまてまて、焦ってはいけない。
>>540から>>649が登場するまでだって、あれだけ時間がかかったのだ。
せめて１〜２日はまってやろうじゃないか。
0798デフォルトの名無しさん
NGNG本当に速度を気にしなくても良いなら、qsortつかって7行プログラミングできそう。
0799デフォルトの名無しさん
NGNGがいしゅつです。
すでにBWTは7行プログラミングされてます。
0800デフォルトの名無しさん
NGNGなんだもう7行で概出か・・・俺が間違ってたよ。
0801デフォルトの名無しさん
NGNGお前誰だよｗ
>>799
無かったぞ。それともたまたまdat落ちしているpart2にあったとでも？
都合がいいな。
0802デフォルトの名無しさん
NGNG0803デフォルトの名無しさん
NGNGんなこたーない。
BWTに限らずデータ圧縮モデルは遺伝子解析や言語解析などでも使われている。
0804デフォルトの名無しさん
NGNG0805デフォルトの名無しさん
NGNGJ. Seward のオリジナルの実装や、Larrson-Sadakaneの実装、二段階ソート法は、
速い上にそこそこ短い（実質50-60行くらいか）。
0806760
NGNG0807デフォルトの名無しさん
NGNGまったくだ。
いくら互換性や大量のコメントがあるからといって、実質を持ち出されてもね。
アルゴリズムそのものは単純なのにね。
0808デフォルトの名無しさん
NGNG10年近くも前のアルゴリズムじゃないか。
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まったく同意
■ このスレッドは過去ログ倉庫に格納されています