ビットパラレル手法によるアライメントアルゴリズム
こっちのPDFのほうがフォントがきれい
著者情報が削られている
Abstract
近似文字列照合問題は,2 つの文字列と閾値が与えられて,片方の文字列の部分文字列のうち,もう一方の文字列との編集距離が閾値以下となるものを見つける問題である.この問題をビットパラレルと呼ばれる手法により高速に解くアルゴリズムがMyers により提案されているが,出力として編集距離だけではなくアライメントも求める場合には適用できない.本論文では,近似出現に対するアライメントについての正規形の概念を導入し,Myers のアルゴリズムを近似文字列照合に対するアライメント問題へ拡張する. 著者
これ以上は紙にちゃんと書いて考えないとダメだな
2022-02-02
05:34:18 ちゃんと読みたくなってきた
active読書用project
目次
序論
準備
近似出現に対するアライメント
アルゴリズム
ビットパラレル手法によるアルゴリズム
アライメントアルゴリズムへの拡張
実験
結論
参考文献