アルファベットサイズの大きな木のSuffix Treeについて
スポンサーリンク
概要
- 論文の詳細を見る
共通接尾木(common suffix tree, CS-tree)の接尾木(suffix tree)を構築する問題は通常の単語の接尾木を構築する問題の一般化であり、オートマトンの最小化や木のパタンマッチングなどに応用がある。共通接尾木のサイズをn、アルファベットのサイズを∣Σ∣とした時、これまでBreslauerのO(nlog∣Σ∣)時間のアルゴリズムしか知られていなかったが、これは∣Σ∣が大きいとO(nlogn)かかる。本研究では、整数アルファベットに対しO(nloglogn)時間のアルゴリズムを与える。また、sharrow k-ary treeという木に対しては同じく整数アルファベットに対し線形時間アルゴリズムを与える。また、本研究ではk分木から完全平衡k分木であるようなパタンを発見するのに有効なBsuffix treeというものを提唱する。さらに、整数アルファベットの場合にこれを線形時間で構成するアルゴリズムを示す。
- 1999-09-02
著者
関連論文
- cDNAマッピングのためのマッチング連鎖アルゴリズム
- スプライスト・アライソメントに基づいたcDNAライブラリの正確なクラスタリング・アルゴリズム
- モチーフ検索アルゴリズムと遺伝子同定への応用
- アルファベットサイズの大きな木のSuffix Treeについて
- 生物学的配列の組換えの解析のための新しいアプローチ
- 電子マネーシステムにおける最適なオンラインアルゴリズム
- A^*アルゴリズムを用いたn×m最短路問題の効率的解法