« MSufSort-2.0 | トップページ | 0.2.1 »

Improved Two-Stage Algorithm

なぜか 二段階ソート法の要ソート数を減らすべくいろいろとやってます ・・ 今のところ こんな感じ。 Manzini のコーパスでは、 要ソート数が三分割法の rate-2 よりも少なくなります。 ( 入力されるデータによっては逆に多くなるものもある。。 )

要ソート数の割合 (単位: %)
FilenameSizets-1ts-2copyabc-1abc-2itssort
chr22.dna3455375863.3140.9035.5631.6728.3926.68
etext9910527734049.4133.7749.7546.8733.2631.10
gcc-3.0.tar8663040056.9340.3942.6340.6429.1226.77
howto3942210554.1736.1445.5142.4430.6428.55
jdk13c6972889952.1035.2547.6346.6332.8630.06
linux-2.4.5.tar11625472057.1541.3644.1242.5630.2826.80
rctail9611471115151.4335.3649.0048.0634.1230.28
rfc11642190159.2841.6640.1740.4628.3725.83
sprot34.dat10961718655.4535.7643.1442.7729.3329.26
w3c210420157952.1835.5447.4647.4133.2329.90

ts-1 と ts-2 は二段階ソート法の rate-1 と rate-2、 copy は Copy 法、 abc-1 と abc-2 は三分割法の rate-1 と rate-2、 itssort は今回の改良した二段階法。

linksSuffix Arrays に論文を追加しました。 様々な Suffix Array 構築アルゴリズムについて調べられています。 ( 三分割法 や Kao法 は無かったけど・・ )

|

« MSufSort-2.0 | トップページ | 0.2.1 »

コメント

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/154471/41473654

この記事へのトラックバック一覧です: Improved Two-Stage Algorithm:

« MSufSort-2.0 | トップページ | 0.2.1 »