mito2003_wx
WX法は、データを最小構成要素（以下これをUnitと呼ぶ）に分解するアルゴリズムです。 Unitは例えば、自然言語で言えば、単語などに相当し、DNAの配列情報で言えばコドンに相当します。 様々なデータに対してそれぞれのUnitを一つ一つ定義するのはコストがかかる上、柔軟性がありません。そこで、Unitは、その内部に、さらに小さい構成要素を持たないという定義とします。 WX法は、データから、統計情報を用いて、そのような独立した部分列を抽出し、全データを上の評価基準で尤も的確な形に分解するアルゴリズムです。 WX法は次の五つのステップからなります (i) 全ての部分列を列挙する (ii) それぞれの部分列に対し、Unitらしさを表す評価値を与える (iii) (ii)の評価値を用いて、Unit分解を行う (iv) (iii)の結果を用いて評価値を再計算する (v) 収束するまで(
deep shallow
(2003/01/07) Suffix Arraysは、Suffix Treeから線形時間で構築でき、Suffix Treeは線形時間で構築できることが既にわかっていたために、Suffix Arrays自身も理論的には線形時間で構築されることもわかっていました。 しかし、Suffix Treeを線形時間で構築するアルゴリズムが非常に巧妙であり、実際に利用するとなると、処理量が、O(NlogN)で直接Suffix Arraysを構築できるアルゴリズムに比べて非常に大きいために、実用上問題にならない程度の線形時間でSuffix Arraysを構築するアルゴリズムの登場が期待されてました。 そうした中、2003年に、同時に三つの直接、Suffix Arraysを線形時間で構築するアルゴリズムが発表されました。いずれのアルゴリズムもサンプルAをソートした後に、サンプルに用いていない部分Bを、Aを用
[を] 線形時間で Suffix Array 作成
線形時間で Suffix Array 作成 2005-01-23-1 [Algorithm] 週末自己啓発！アルゴリズムの勉強。趣味の世界。 taku-ku 氏に教えてもらった論文。線形時間で Suffix Array を作る話。 Suffix Tree 方式だと O(n) でできるのだがこれは違うやり方。 Juha K¨arkk¨ainen and Peter Sanders: "Simple Linear Work Suffix Array Construction", ICALP 2003, LNCS 2719, pp. 943-955, 2003. <http://www.cs.helsinki.fi/u/tpkarkka/publications/icalp03.pdf> Abstract. [...] 1. recursively sort suffixes
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サービス終了のお知らせ
white page / software
