超高速ブロックソーティング
1 ：デフォルトの名無しさん：
ブロックソートを超高速に行うアルゴリズムを開発しました。
ソースrarで圧縮したmpeg4圧縮のaviファイル（47＠｀176＠｀689バイト）
計測環境 PIII750MHz
GCA（オプションデフォルト、ブロックサイズ16M？）
→187.519秒
オリジナル（ブロックサイズ16M）
→66.219秒
オリジナルはブロックソート->MTF->ランレングスだけなのですが、
後段のrangecorderのことを考えてもこれは早いのではないでしょうか。
詳細はソースを見てください
http://www.angelfire.com/sc2/f_bsort/f_bsort.zip
ソースrarで圧縮したmpeg4圧縮のaviファイル（47＠｀176＠｀689バイト）
計測環境 PIII750MHz
GCA（オプションデフォルト、ブロックサイズ16M？）
→187.519秒
オリジナル（ブロックサイズ16M）
→66.219秒
オリジナルはブロックソート->MTF->ランレングスだけなのですが、
後段のrangecorderのことを考えてもこれは早いのではないでしょうか。
詳細はソースを見てください
http://www.angelfire.com/sc2/f_bsort/f_bsort.zip
|
|
|
2 ：デフォルトの名無しさん：2001/01/23(火) 22:55
ないけど
3 ：デフォルトの名無しさん：2001/01/24(水) 00:19
欲しいー
もっと圧縮出来そうなデータのソートでもしっかり速いのか？
GCAだと圧縮済みデータの処理と普通ののじゃ４倍くらいは速度が変わるが。
GCAだと圧縮済みデータの処理と普通ののじゃ４倍くらいは速度が変わるが。
ネタでした。
6 ：デフォルトの名無しさん：2001/01/24(水) 14:07
ネタと言えばすべて済むのか？ｼﾈ
7 ：いつでもどこでも名無しさん：2001/01/24(水) 15:41
ブロックソートって JPEGでも圧縮できるらしいねえ。
速さはよくわからんけど、今度教えてもらおう。
速さはよくわからんけど、今度教えてもらおう。
8 ：名無しさんと休日（仮）：2001/01/24(水) 17:35
>>7
一応言っておくけどブロックソーティング単体じゃ圧縮できない。
ちなみにGCAでも殆ど縮まない、精々数パーセント ＞ jpeg
ついでに言うと、すげー遅い。
GCAであれだけの速度が出てるのは凄いと思う。
一応言っておくけどブロックソーティング単体じゃ圧縮できない。
ちなみにGCAでも殆ど縮まない、精々数パーセント ＞ jpeg
ついでに言うと、すげー遅い。
GCAであれだけの速度が出てるのは凄いと思う。
9 ：デフォルトの名無しさん：2001/01/24(水) 20:47
ネタスレage
10 ：1：2001/01/24(水) 21:11
1 != 5 です。
でもネタでした。
でもネタでした。
11 ：デフォルトの名無しさん：2001/01/24(水) 22:52
ネタスレにするなんて許さないぞ。
こうなったら「ブロックソートを語る」スレに変更だ!!
>> 4
そもそも、ローテートリストのソートに使われてる
クィックソートが遅さの原因なんだよな。
だから、縮みにくいデータ(ランダムデータ)ほど速いし、
縮みやすい(0ばっかしとか)は死ぬほど遅い事になる。
PPMDに比べて、メモリー少なくてもそれに迫るだけの圧縮率を
誇るのがBWT+MTF+RLE+ENTROPY圧縮の利点だと思うんだけど、
GCAはそれを無駄にしてるような気がしなくもなくもない。
メモリー消費１６メガだっけ？でかすぎる。
こうなったら「ブロックソートを語る」スレに変更だ!!
>> 4
そもそも、ローテートリストのソートに使われてる
クィックソートが遅さの原因なんだよな。
だから、縮みにくいデータ(ランダムデータ)ほど速いし、
縮みやすい(0ばっかしとか)は死ぬほど遅い事になる。
PPMDに比べて、メモリー少なくてもそれに迫るだけの圧縮率を
誇るのがBWT+MTF+RLE+ENTROPY圧縮の利点だと思うんだけど、
GCAはそれを無駄にしてるような気がしなくもなくもない。
メモリー消費１６メガだっけ？でかすぎる。
12 ：デフォルトの名無しさん：2001/01/24(水) 23:31
ブロックソートは処理ブロックを大きく取ったほうが、
より理想的な結果が得られます。
当然消費メモリ、速度が犠牲になりますけど。
MTFとRLEがどうにかもう少しいい形に出来ないか研究すると面白いかも。
より理想的な結果が得られます。
当然消費メモリ、速度が犠牲になりますけど。
MTFとRLEがどうにかもう少しいい形に出来ないか研究すると面白いかも。
13 ：ＳＡＧＥ：2001/01/24(水) 23:36
>>11
んじゃあ付き合ってみるか。
てゆーか逆に全０の方が速いぞ。＞GCA
そこら辺の枝切りの具合がどうなってるのか気になるところ。
BWT の利点ってでも、ブロックサイズを増やせば増やすほど（一般には）
圧縮しやすいデータになってくとこじゃん？ 簡単に高圧縮率を出そうとしたら
１６ＭＢ位は使わないとどうしようもないような。
んじゃあ付き合ってみるか。
てゆーか逆に全０の方が速いぞ。＞GCA
そこら辺の枝切りの具合がどうなってるのか気になるところ。
BWT の利点ってでも、ブロックサイズを増やせば増やすほど（一般には）
圧縮しやすいデータになってくとこじゃん？ 簡単に高圧縮率を出そうとしたら
１６ＭＢ位は使わないとどうしようもないような。
14 ：デフォルトの名無しさん：2001/01/24(水) 23:49
>>11
>こうなったら「ブロックソートを語る」スレに変更だ!!
じゃ、どーやったら高速にBWT出来るかでも考えるか。
>>13
>てゆーか逆に全０の方が速いぞ。＞GCA
単色のBMPとか1秒かかんないしね、たぶんデータの内容によって
処理方法切り分けしてるんだと思う。
中途半端に縮みそうなデータが一番遅い ＞ GCA
>こうなったら「ブロックソートを語る」スレに変更だ!!
じゃ、どーやったら高速にBWT出来るかでも考えるか。
>>13
>てゆーか逆に全０の方が速いぞ。＞GCA
単色のBMPとか1秒かかんないしね、たぶんデータの内容によって
処理方法切り分けしてるんだと思う。
中途半端に縮みそうなデータが一番遅い ＞ GCA
15 ：デフォルトの名無しさん：2001/01/24(水) 23:52
君達に量子コンピュータを授けよう！
16 ：11：2001/01/24(水) 23:57
>> 13
> http://member.nifty.ne.jp/DO/index.htm
synsir氏の↑の掲示板での発言過去ログに
部分的にヒントが見え隠れしてる。
RLEをLZに置き換えるってのを試してみたことはあったけど、
あんまりいい結果は出なかった。
RLEよりも縮むんだけど、次段のエントロピ圧縮で負ける。
場合によってはRLEよりもLZの方が行けそうに思ったんだけどなぁ。
> http://member.nifty.ne.jp/DO/index.htm
synsir氏の↑の掲示板での発言過去ログに
部分的にヒントが見え隠れしてる。
RLEをLZに置き換えるってのを試してみたことはあったけど、
あんまりいい結果は出なかった。
RLEよりも縮むんだけど、次段のエントロピ圧縮で負ける。
場合によってはRLEよりもLZの方が行けそうに思ったんだけどなぁ。
17 ：12：2001/01/25(木) 00:00
http://www.ipa.go.jp/NBP/10seika/fii_data/006/001.htm
プログレッシブソートってなんだろう。
マルチプロセッサにも適応できるソートらしいんだが。
ここのベンチを見るとLHAより速いね。
＃googleしてたら出たんだが、ACB法ってどんなだろう。
プログレッシブソートってなんだろう。
マルチプロセッサにも適応できるソートらしいんだが。
ここのベンチを見るとLHAより速いね。
＃googleしてたら出たんだが、ACB法ってどんなだろう。
18 ：ＳＡＧＥ：2001/01/25(木) 00:46
BWT自体の高速化を語るか、後段処理について語るのか。
>>16
LZ + エントロピ圧縮 かますなら、行程を完全分離しちゃうと良くない。
LHa みたいに長さコードとかも混ぜた方が結果としては圧縮率はあがるようだ。
>>17
ACB ってマルコフモデリングの亜種じゃなかった？
>>16
LZ + エントロピ圧縮 かますなら、行程を完全分離しちゃうと良くない。
LHa みたいに長さコードとかも混ぜた方が結果としては圧縮率はあがるようだ。
>>17
ACB ってマルコフモデリングの亜種じゃなかった？
19 ：デフォルトの名無しさん：2001/01/25(木) 01:00
>>16
データに偏りがなくなっちゃうから駄目なんじゃないかなー。
反対に言えば、偏りが大きくなるような変換してやれば、圧縮率は上がると思うん
だけどどうだろう。
>>17
プログレッシブソートってDO++で言うところの先頭2文字での分布数えソート
みたいな物かな？
でも、同データが続いてるような場合だとこれを再帰させても要素数あんまり
へらないんだよね…。
>>18
>BWT自体の高速化を語るか、後段処理について語るのか。
りょーほーっつーのは駄目か…
とりあえず、高速化の方がスレタイトルは合ってるな(笑)
データに偏りがなくなっちゃうから駄目なんじゃないかなー。
反対に言えば、偏りが大きくなるような変換してやれば、圧縮率は上がると思うん
だけどどうだろう。
>>17
プログレッシブソートってDO++で言うところの先頭2文字での分布数えソート
みたいな物かな？
でも、同データが続いてるような場合だとこれを再帰させても要素数あんまり
へらないんだよね…。
>>18
>BWT自体の高速化を語るか、後段処理について語るのか。
りょーほーっつーのは駄目か…
とりあえず、高速化の方がスレタイトルは合ってるな(笑)
20 ：18：2001/01/25(木) 01:07
> ACB ってマルコフモデリングの亜種じゃなかった？
自己レス。ごめんこれ勘違い。
こっちだね。→ http://www.cbloom.com/news/leoacb.html
ざっと読んだけどいまいち理解できなかった…。ちょいとマジメに読んでみるっす。
自己レス。ごめんこれ勘違い。
こっちだね。→ http://www.cbloom.com/news/leoacb.html
ざっと読んだけどいまいち理解できなかった…。ちょいとマジメに読んでみるっす。
21 ：デフォルトの名無しさん：2001/01/25(木) 23:33
>BWT自体の高速化を語るか、後段処理について語るのか。
両方で行こうぜ
両方で行こうぜ
22 ：デフォルトの名無しさん：2001/01/26(金) 04:02
やっぱし、速度求めるならBWTやめてST使った方が効率的だなぁ、
メモリもBWTより少なくて済からブロックサイズ増やせそうだし、
なにより速度がデータの内容に依存しないところが良い。
メモリもBWTより少なくて済からブロックサイズ増やせそうだし、
なにより速度がデータの内容に依存しないところが良い。
24 ：>：2001/01/26(金) 18:16
STってなんでしょ。
詳細希望〜
詳細希望〜
26 ：(使用禁止語)：2001/01/26(金) 22:43
でもあれソート効率悪いぜ・・・
速いからいいか。
速いからいいか。
BWT == Order (n-1) の ST。
29 ：デフォルトの名無しさん：2001/01/29(月) 18:11
age
30 ：デフォルトの名無しさん：2001/01/29(月) 18:29
BWT以外の文脈ソート法って無いの？
見たことがない。
見たことがない。
31 ：デフォルトの名無しさん：2001/01/29(月) 19:08
acb法。
日本語の解説はみたこと無いけど英語ならあるみたい。
あとひとつくらい見た気がしたが忘れた
日本語の解説はみたこと無いけど英語ならあるみたい。
あとひとつくらい見た気がしたが忘れた
32 ：デフォルトの名無しさん：
acbの日本語の解説はないのか。なるぺそ。
ありがとう。
プレフィックスリストってのはBWTなんかなぁ。
ありがとう。
プレフィックスリストってのはBWTなんかなぁ。