文字列間の類似度

2つの文字列の類似度を考えてみます。

==前置き==
類似度は次のように計算します。 2つの文字列を端から対応する1対に文字ごとに比較していきます。一対の文字が同じなら0、違う文字なら2として、これを左から右に繰り返して総和を求めます。

即ち、似ているほど類似度は小さい値になります。

例えば、 abcd と abcd は類似度0
abcc と abcd の類似度は2
abcb と adac の類似度は6 です。

これだけなら簡単ですが、もう1つ新しい要素を加えます。 文字列に*マークをいくつでも加えられるとします。そして比較する文字対の一方が*の場合は類似度1とします。

例えば、
abcd と ab*d の類似度は1
a*cd と ab*d の類似度は2 です。

ここで * は、類似度の数値を最低にするように挿入しなくてはいけないものとします。
例えば、
abcdとacdの類似度はacdに*を挿入し、a*cdとすることにより類似度は1になります。

==ここから本番==
それでは、2つの文字列に*を挿入し、類似度数を最少にする方法を示します。
ここでは abc とac の類似度計算を例にとって説明します。

類似度の計算には、2つの表を使います((1)類似度数表、(2)選択表)。

先ず、2つの初期表を用意します。

類似度数表

 選択表

次に、類似度表の空いたマスに数値を書き込んでいきます。 空いたマスの数値を計算するには、隣接する左、左下、下 の3つのマスが数値で埋まっていなくてはなりません。次の図は、隣接3マスから右上のマスの類似度を計算する方法です。

右上のマスの数値は次のどちらかになります。
min(X+1,Z+1,Y) または、min(X+1,Z+1,Y+2)です。
この2つの違いは、比較する文字が同じか否かで決まります。

例えば、次の図で?マスの数値を計算する時は、比較する文字がAとAなので、
min(X+1,Z+1,Y) を用います。比較する文字が違う場合min(X+1,Z+1,Y+2)を用います。

?セルの場合をまとめると、比較する文字がA同士で同じため、min(X+1,Y,Z+1)はmin(2,0,2)となり、0になります。 この場合、minで選ばれたのは左下なので、選択表の?のマスに左下と書き込みます。 これを繰り返して完成したものが次です。

類似度表完成

 選択表完成

類似度表の右上隅がABCとACの類似度で、ACはA*Cになって、1となります。
選択表を右上からたどるとどこに*が入るのかが分かります。
左から来た場合は縦の文字列に*が入り、A*Cとなります。
下から来た場合(上の図にはありませんが)、横の文字列に*が入ります。

==
(すみません)話がゴチャゴチャして、よくわかりませんよね。
これは来週の生物分子の授業内容です。授業では生物のアミノ酸の配列(文字列)を比較して種の間の類似度を計算します。例えば、人とウサギは、人と人参の関係より近い、なんてのを計算します。
 

 

 

コメントは受け付けていません。