メモ代わりの記事ですみません。
テキスト処理分野での編集距離の使い方と、バイオ分野での編集距離の使い方はだいぶ違う。
テキスト処理分野:
●どの編集操作(挿入・削除・置換)もコスト1のことが多い
●指定した編集距離以内にある文字列はすべて検出しなければならない
バイオ分野:
●置き換える文字の組などによってコストが異なる
●なるべく編集距離が小さいものを求めるが、必ずしも編集距離が最小の配列を検出しなければならないとは限らない(最小判定を編集距離の近似値で行うなど)
バイオ分野の2つ目が結構ミソなような気がする。いわゆる近似アルゴリズムってもの。個人的にはあまり興味ないのだが。
高速化の観点では、バイオ分野の1つ目はかなり障害なのかもしれない。今後精査。
テキスト処理分野での編集距離の使い方と、バイオ分野での編集距離の使い方はだいぶ違う。
テキスト処理分野:
●どの編集操作(挿入・削除・置換)もコスト1のことが多い
●指定した編集距離以内にある文字列はすべて検出しなければならない
バイオ分野:
●置き換える文字の組などによってコストが異なる
●なるべく編集距離が小さいものを求めるが、必ずしも編集距離が最小の配列を検出しなければならないとは限らない(最小判定を編集距離の近似値で行うなど)
バイオ分野の2つ目が結構ミソなような気がする。いわゆる近似アルゴリズムってもの。個人的にはあまり興味ないのだが。
高速化の観点では、バイオ分野の1つ目はかなり障害なのかもしれない。今後精査。