« 2005年6月 | トップページ | 2005年8月 »

MSufSort-2.0

Michael Maniscalco さんの新しい MSufSort が公開されています。というわけで、 また Suffix array 構築までの時間を計測してみました。 20050728_time.html

linksSuffix Arrays に論文を追加しました。 MSufSort-1.0 のアルゴリズムについて詳しく書かれてあります。

  • Simon Puglisi, Exposition and analysis of a suffix sorting algorithm,
    Technical report CAS-05-02-WS, Department of Computing and Software, McMaster University, Hamilton, Ontario, Canada, 2005.
    [.ps (www.computing.edu.au)]

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

ibwt の高速化

0.1.3a よりも (たぶん)高速な ibwt を実装中。。 ibwt-0.2.1a.tar.bz2

今回から、Static な Wavelet Tree に文字を n/v ずつ追加する方法に変更してます。 ("Constructing Compressed Suffix Arrays with Large Alphabets" の Incremental CSA とほぼ同じ方法)

こっそり Canonical Huffman 符号を作ってみる

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

BWT w/o sufsort - part 3

bitvector の赤黒木を skip lists に置き換えてみました。 ibwt-0.1.3a.tar.bz2

多少はメモリの使用量が改善されるかなと思っていたけど・・赤黒木とほぼ変わらず。。むうう。

huffbwt は面白そうですねえ。 .. かなり手抜きですが、 こんな感じかな?

linksCompressed Suffix Arrays and Suffix Trees に論文を追加しました。

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

« 2005年6月 | トップページ | 2005年8月 »