トップページ | 2005年2月 »

divsufsort 0.1.3

divsufsortのバケット表関連を修正しました。んー、まあ多少コードがすっきりしたかな ? あとは、 suffix のコピー処理をもっと簡潔にできれば良いのですが。。

* ううむ.. 処理速度はちょっと遅めだけど、 M03expの圧縮率は思っていた以上に良いですね。

| | コメント (0) | トラックバック (0)

External Memory..

links / Suffix Arrays に新しい論文を追加しました。

| | コメント (0) | トラックバック (0)

rate-3

実験用なので typeC のソートだけですが、 三分割法の rate-3 を実装してみました。 .tar.bz2

うーむ、 要ソートの suffix の個数はそれなりに減少しているけど、ソート時間は rate-2 のとたいして変わらないですねえ。

* Ternary Quicksort はそれで良いと思いますよ。 (まあ、 partition の処理を別の関数に分割すれば、多少はすっきりすると思いますが..)

| | コメント (0) | トラックバック (0)

bpr algorithm - その2

ranksortとbprのSuffix Array構築までの時間を計測してみたんですが、こんな結果になってしまいました。んー、bprは使用メモリが 9n なので、もう少し (かなりか?) 処理速度を改善しないと使い物にはなりませんなあ。

| | コメント (0) | トラックバック (0)

Binary Indexed Tree

simplemodelを再実装 & Binary Indexed Tree (BIT)を実装してみました。 んー、やはり BIT の方が速いかな?

| | コメント (0) | トラックバック (0)

Ranksort

ranksort7nを再実装。 ( .tar.bz2 .tar.gz ) そのうち ranksort と bpr algorithm のSA構築までの時間を比較してみよう。

累積頻度の取得・更新なら、P. Fenwick氏のBinary Indexed Tree (BIT)という方法が比較的高速かな。実装はちょっと面倒だけど。。

| | コメント (0) | トラックバック (0)

bpr algorithm

新しいSA構築アルゴリズムの論文とソースコードを見つけたのでメモ。(linksには追加済み)

このbucket-pointer refinementという新しいアルゴリズム (Ranksortに似ていなくもないが..) は、 サフィックスの順位を格納する配列が必要なので使用メモリは9nですねえ。 ううむ、 やはり速い手法はそれなりのメモリが必要なのか。。

DataCompression.infoのドメインがオークションにかけられていますな。(cgi.ebay.com)

| | コメント (0) | トラックバック (0)

新年

あけましておめでとうございます。今年もよろしくお願いします。

過去のソースコードを整理するついでにサイトを全面リニューアルしてみました。多少は見やすくなったかな? ちなみに旧トップページはこちらです。一週間くらいしたら削除します。

| | コメント (0) | トラックバック (0)

トップページ | 2005年2月 »