202228900

類似度が定義されている要素があるとする。その要素列のペアに対して、対応のずれをあるコストで許容して最良マッチングし、要素間類似度の平均を列間の類似度とする。 d(x, y) = d(y, x) は維持したい。何も考えず編集距離と同じように実装すると、 DP の経路に依って合計される要素の数が変わってしまう。対応がずれて要素列が伸び縮みしたとき、積分測度的なものが変化することを考慮する必要がある。しばし悩んでしまった。