DPマッチングとは？

　一度計算した結果をうまく再利用して、効率的に計算することを DPマッチング（動的計画法）と呼んでいます。
　DPマッチングを用いれば、二つのパターンの要素間の対応付け（整列化）を行い ながら効率的に類似度を計算することができます。

【項　目】

例えば、

とすれば、
パターン1とパターン2との間の距離は

となる。

パターンA、パターンBがあり、


に対応しているとする。図で表わすと、

この対応を決める線を経路という。
AとBの長さを合わせるために、それぞれを次のように、AをA’に、BをB’に変形する。

2パターン間の距離は、

で表わされる。（各対応の差の2乗和の平方根である。）
パターンＡとパターンＢの対応が１本の線（経路） w(i(k),j(k), k=1,2,…)で与えられたとき、
パターン間距離は

で求められる。 ここで、は と<との 距離を表わす。
次に経路が与えられないときのパターン間距離をすべての経路wの中で最小のと定義する。

パターンＡとパターンＢとの距離　Ｄ（Ａ，Ｂ）≧０
ＡとＢが似ている ←→　Ｄ（Ａ，Ｂ）の値が小さい
以下のように、g(i,j)を定義し、漸化式を用いて効率的に g(i,j)を求めれば、パターン間距離は D(A, B)=g(I,J)により求められる。 (なお、IはパターンAの長さ、JはパターンBの長さです。)

累積距離
ここで、

g(A,B;w)は、経路が与えられたときの からまでの 累積距離である。
初期値
漸化式



この格子点はa2とb4が対応していることを表している。この点（対応）における距離をd(2,4)とする。
点から点までの距離の和をとする。

back