[B! bwt] taroleoのブックマーク

A Lightweight External Memory BWT Construction Algorithm

Welcome to the home page of bwte: the first tool for the direct construction of the BWT of large files in external memory. Direct construction means that the BWT is built directly, without first computing the suffix array. bwte accesses the disk data only by sequential scans so it takes full advantage of the modern caching architectures. In addition, it stores all files (input, output, and interme

taroleo 2010/02/17

bwt

リンク

Google Sites: Sign-in

Not your computer? Use a private browsing window to sign in. Learn more about using Guest mode

taroleo 2009/07/17

リンク

Burrows-Wheeler変換の線形時間アルゴリズム - DO++

研究紹介です。今夏のSPIRE 2009という学会で "A Linear-Time Burrows-Wheeler Transf orm using Induced Sorting", D. Okanohara, K. Sadakane, SPIRE 2009 pdf(draft) というのを発表します。これは与えられた文字列に対し接尾辞配列を経ないでBurrows-Wheeler変換を直接行うというもので、アルファベットサイズによらず入力長に対して線形時間で行えます。基本的なアイディアは昨年のInduced Sortingによる接尾辞配列の線形時間構築アルゴリズム（いわゆるSAIS）を接尾辞配列を使わないでシミュレートするものです。pushとpop操作だけからなり、そのまま外部記憶上での構築とかにも対応できるようになっています。 Burrows-Wheeler変換（BWT, Block S