Burrows-Wheeler変換の線形時間アルゴリズム - DO++
研究紹介です。今夏のSPIRE 2009という学会で "A Linear-Time Burrows-Wheeler Transform using Induced Sorting", D. Okanohara, K. Sadakane, SPIRE 2009 pdf(draft) というのを発表します。これは与えられた文字列に対し接尾辞配列を経ないでBurrows-Wheeler変換を直接行うというもので、アルファベットサイズによらず入力長に対して線形時間で行えます。基本的なアイディアは昨年のInduced Sortingによる接尾辞配列の線形時間構築アルゴリズム（いわゆるSAIS）を接尾辞配列を使わないでシミュレートするものです。pushとpop操作だけからなり、そのまま外部記憶上での構築とかにも対応できるようになっています。 Burrows-Wheeler変換（BWT, Block S
はてなブックマークFirefox拡張, JavaScript で IS 法 による Suffix Array 構築 - naoyaのはてなダイアリー
昨日、はてなブックマークFirefox拡張をリリースしました。おかげさまでベータ版からダウンロード数は累積で1万ダウンロードを突破し、アクティブユーザー数も伸びています。 はてなブックマークFirefox拡張で新しいインターネットを体験しよう http://b.hatena.ne.jp/guide/firefox_addon 開発者の id:secondlife が g:subtech:id:secondlife:20090415:1239804170 で技術的な側面からのちょっとした TIPS なども紹介していますので、興味のある方はご一読ください。 検索では思いのほか SQLite の like 検索が高速なのに驚いた。はてブ検索では、検索ワードから URL, Title, コメント にマッチしたものを表示していて、それ専用の search_data だかかんらかの検索用カラムがある。
DO++ : suffix arraysやいろいろ
suffix arraysの話は半年置きぐらいに書いているのかなぁ。 (ココログ全文検索機能無くて、不便ですね・・以前どこに書いたのか分からない。） 私が以前書いたSuffix Arraysの構築方法の記事が古くなってきたので（分かりにくいし）、近いうちにライブラリと一緒に内容も更新しようかなと。今回は、忘れないうちにメモも兼ねてSuffix Arraysの高速な構築方法について。 構築で今一番速いのは、msufsortとimproved two-stage (プログラム名はdivsufsort）(its)法だと思います。これらはデータサイズに対して線形時間で構築できる方法では無いのですが、大抵のデータでは線形時間の方法より高速に構築することが可能です。 msufsortはsuffix arrays:SAを直接構築するのではなく、その逆の値であるinverted suffix arrays
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
hatena-bookmark-xul/chrome/content/common/05-SuffixArray.js at master · hatena/hatena-bookmark-xul
