未知の文字列集合を、それらを連結した文字列から推測する線形時間アルゴリズム

スポンサーリンク

概要

• 論文の詳細を見る

• Tを未知の文字列の集合、Sをそれらを連結した文字列の集合とし、SからTを推測する問題を考察する。関連研究から、最適化問題として定式化し解くことは計算量的に困難と予想される。本研究では、Sの文字列を相互比較して共通部分文字列を抽出し、それらを互いの境界で分割することによりTを推測する線形時間アルゴリズムを開発した。本手法はSの大きさにかかわらず、Sの文字列長の総和Lに対してO(L)時間で処理可能なスケーラブルな手法である。本アルゴリズムの有効性を、ランダムに生成された文字列とヒトcDNA配列に対して適用する計算機実験で評価した。

• 一般社団法人情報処理学会の論文
• 2009-02-26

著者

• 安田 知弘

  株式会社日立製作所中央研究所

関連論文

• 3C-2 転置インデックスに位置情報を付与する新手法(情報検索,一般セッション,データベースとメディア)
• 未知の文字列集合を、それらを連結した文字列から推測する線形時間アルゴリズム
• ハイブリッド型文書検索システムの試作と性能評価(夏のデータベースワークショップ2007(データ工学,一般))
• ハイブリッド型文書検索システムの試作と性能評価(テキスト検索,夏のデータベースワークショップ2007(データ工学,一般))

スポンサーリンク