« cyclic suffix array | トップページ

unbwt_5n

某フォーラムで公開する予定のものの一部をこちらにも置いておきます。中身は5nスペースのBW逆変換アルゴリズム四種(mergedTL・indexLF・unlimTLF・biPSI)。

File: unbwt_5n.zip
Size: 15,718 bytes
 MD5: a07a2f110dd8adc4a87b695f57db10bc
SHA1: 20ea0fe7618ae51c0a9727ae5a9714b47089582d

unlimTLFはmergedTLとindexLFを組み合わせたもので、LF mappingへマージ出来ないTの部分はbinary searchを用いて復号します。そのためmergedTLとは違い2**24より大きいデータでも処理が可能です。

最後のbiPSIは、PSI arrayを少し弄って一度に二文字ずつ復号出来るようにしたものです。逆変換で最も時間のかかる最後のループ処理でのPSI arrayへのランダムアクセスを約半分に減らせるので、入力データがある程度大きい場合、一文字ベースのmergedTLなどよりも高速に処理できることが多いです。

|

« cyclic suffix array | トップページ

コメント

コメントを書く



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


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



トラックバック

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

この記事へのトラックバック一覧です: unbwt_5n:

« cyclic suffix array | トップページ