トップページ⇒tech
32コメント10KB

超高速ブロックソーティング

■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさんNGNG
ブロックソートを超高速に行うアルゴリズムを開発しました。
ソース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
0002デフォルトの名無しさんNGNG
ないけど
0003デフォルトの名無しさんNGNG
欲しいー
0004ＳＡＧＥNGNG
もっと圧縮出来そうなデータのソートでもしっかり速いのか？
GCAだと圧縮済みデータの処理と普通ののじゃ４倍くらいは速度が変わるが。
00051NGNG
ネタでした。
0006デフォルトの名無しさんNGNG
ネタと言えばすべて済むのか？ｼﾈ
0007いつでもどこでも名無しさんNGNG
ブロックソートって JPEGでも圧縮できるらしいねえ。
速さはよくわからんけど、今度教えてもらおう。
0008名無しさんと休日（仮）NGNG
>>7
　一応言っておくけどブロックソーティング単体じゃ圧縮できない。

　ちなみにGCAでも殆ど縮まない、精々数パーセント ＞ jpeg
　ついでに言うと、すげー遅い。
　GCAであれだけの速度が出てるのは凄いと思う。
0009デフォルトの名無しさんNGNG
ネタスレage
00101NGNG
1 != 5 です。
でもネタでした。
0011デフォルトの名無しさんNGNG
ネタスレにするなんて許さないぞ。
こうなったら「ブロックソートを語る」スレに変更だ!!

>> 4
そもそも、ローテートリストのソートに使われてる
クィックソートが遅さの原因なんだよな。
だから、縮みにくいデータ(ランダムデータ)ほど速いし、
縮みやすい(0ばっかしとか)は死ぬほど遅い事になる。

PPMDに比べて、メモリー少なくてもそれに迫るだけの圧縮率を
誇るのがBWT+MTF+RLE+ENTROPY圧縮の利点だと思うんだけど、
GCAはそれを無駄にしてるような気がしなくもなくもない。

メモリー消費１６メガだっけ？でかすぎる。
0012デフォルトの名無しさんNGNG
ブロックソートは処理ブロックを大きく取ったほうが、
より理想的な結果が得られます。
当然消費メモリ、速度が犠牲になりますけど。

MTFとRLEがどうにかもう少しいい形に出来ないか研究すると面白いかも。
0013ＳＡＧＥNGNG
>>11
んじゃあ付き合ってみるか。
てゆーか逆に全０の方が速いぞ。＞GCA
そこら辺の枝切りの具合がどうなってるのか気になるところ。

BWT の利点ってでも、ブロックサイズを増やせば増やすほど（一般には）
圧縮しやすいデータになってくとこじゃん？ 簡単に高圧縮率を出そうとしたら
１６ＭＢ位は使わないとどうしようもないような。
0014デフォルトの名無しさんNGNG
>>11
>こうなったら「ブロックソートを語る」スレに変更だ!!
じゃ、どーやったら高速にBWT出来るかでも考えるか。

>>13
>てゆーか逆に全０の方が速いぞ。＞GCA
単色のBMPとか1秒かかんないしね、たぶんデータの内容によって
処理方法切り分けしてるんだと思う。
中途半端に縮みそうなデータが一番遅い ＞ GCA
0015デフォルトの名無しさんNGNG
君達に量子コンピュータを授けよう！
001611NGNG
>> 13
> http://member.nifty.ne.jp/DO/index.htm
synsir氏の↑の掲示板での発言過去ログに
部分的にヒントが見え隠れしてる。

RLEをLZに置き換えるってのを試してみたことはあったけど、
あんまりいい結果は出なかった。
RLEよりも縮むんだけど、次段のエントロピ圧縮で負ける。

場合によってはRLEよりもLZの方が行けそうに思ったんだけどなぁ。
001712NGNG
http://www.ipa.go.jp/NBP/10seika/fii_data/006/001.htm
プログレッシブソートってなんだろう。
マルチプロセッサにも適応できるソートらしいんだが。
ここのベンチを見るとLHAより速いね。

＃googleしてたら出たんだが、ACB法ってどんなだろう。
0018ＳＡＧＥNGNG
BWT自体の高速化を語るか、後段処理について語るのか。

>>16
LZ + エントロピ圧縮 かますなら、行程を完全分離しちゃうと良くない。
LHa みたいに長さコードとかも混ぜた方が結果としては圧縮率はあがるようだ。

>>17
ACB ってマルコフモデリングの亜種じゃなかった？
0019デフォルトの名無しさんNGNG
>>16
データに偏りがなくなっちゃうから駄目なんじゃないかなー。
反対に言えば、偏りが大きくなるような変換してやれば、圧縮率は上がると思うん
だけどどうだろう。

>>17
プログレッシブソートってDO++で言うところの先頭2文字での分布数えソート
みたいな物かな？
でも、同データが続いてるような場合だとこれを再帰させても要素数あんまり
へらないんだよね…。

>>18
>BWT自体の高速化を語るか、後段処理について語るのか。
　りょーほーっつーのは駄目か…
　とりあえず、高速化の方がスレタイトルは合ってるな(笑)
002018NGNG
> ACB ってマルコフモデリングの亜種じゃなかった？

自己レス。ごめんこれ勘違い。

こっちだね。→ http://www.cbloom.com/news/leoacb.html
ざっと読んだけどいまいち理解できなかった…。ちょいとマジメに読んでみるっす。
0021デフォルトの名無しさんNGNG
>BWT自体の高速化を語るか、後段処理について語るのか。
両方で行こうぜ
0022デフォルトの名無しさんNGNG



　　　　　　　　
0023うにゅうNGNG
やっぱし、速度求めるならBWTやめてST使った方が効率的だなぁ、
メモリもBWTより少なくて済からブロックサイズ増やせそうだし、
なにより速度がデータの内容に依存しないところが良い。
0024>NGNG
STってなんでしょ。
詳細希望〜
0025うにゅうNGNG
>>24
SortTransform。 上でURLでてるDO++で限定ソートっつってるやつ。

0026(使用禁止語)NGNG
でもあれソート効率悪いぜ・・・

速いからいいか。
002718NGNG
BWT == Order (n-1) の ST。
0028うにゅうNGNG
>>26
>でもあれソート効率悪いぜ・・・
確かにあんまし良くないけど、そのぶんブロックサイズ増やせばそこそこ。
っつっても対象のデータが小さいと意味無いけどね

0029デフォルトの名無しさんNGNG
age
0030デフォルトの名無しさんNGNG
BWT以外の文脈ソート法って無いの？

見たことがない。
0031デフォルトの名無しさんNGNG
acb法。
日本語の解説はみたこと無いけど英語ならあるみたい。
あとひとつくらい見た気がしたが忘れた
0032デフォルトの名無しさんNGNG
acbの日本語の解説はないのか。なるぺそ。
ありがとう。

プレフィックスリストってのはBWTなんかなぁ。
■ このスレッドは過去ログ倉庫に格納されています