Don't Care記号つき文字列に対する近似マッチング・アルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
文字列の近似マッチング・アルゴリズムとしてLandauとVishkinによるアルゴリズムが良く知られている.本稿では彼らのアルゴリズムを基に開発した,Don't Care記号付き文字列に対する逐次および並列の近似マッチング・アルゴリズムを示す.なお,nをテキスト文字列の長さ,mをパターン文字列の長さ,Σを文字集合,kを許容誤差とした場合に,逐次アルゴリズムはO(√<km>nlog|Σ|log^2m/k loglogm/k)時間で動作し,並列アルゴリズムはCRCW-PRAM上でO(√<m/k>nlog|Σ|logm/k loglogm/k)個のプロセッサを用いてO(klogm)時間で動作する.さらに,より拡張した文字列パターンに対する近似マッチング・アルゴリズムも示す.
- 一般社団法人情報処理学会の論文
- 1993-10-01
著者
関連論文
- 最小キーおよび最適部分構造スクリーンの近似
- 二つの点集合の最大共通部分点集合を求めるランダマイズド・アルゴリズム
- 二次元配列間の距離について
- タンパク質立体構造の折れ線による近似とその構造マッチングへの応用
- 可変長ギャップ付き文字列に対する近似マッチング・アルゴリズム
- タンパク質立体構造に対する部分構造検索およびアラインメント・アルゴリズム
- 高次元点集合の合同性判定について
- Don't Care記号つき文字列に対する近似マッチング・アルゴリズム
- 複数の点集合の最大共通部分集合の近似可能性について