Levenshtein距離とか。

 某所のパズルでまさにこれを使う問題が出たので2年ぶりくらいに実装してみる。




●レーベンシュタイン距離

 2つの文字列があるとき、片方からもう片方に変換したい。
文字の置換・挿入、削除の3つの操作が可能なとき、一連の操作の最も少ない回数のこと。
 Googleの"もしかして"のような機能や、判別系モデルの特徴量なんかに使われていて、自然言語処理屋さんなら必ず知っている気がします。気のせいかもしれません。



 ※ちなみにこのとき、置換操作のみを許可したものがハミング距離というやつです。


 昨今(といってももうだいぶ前から)ではバイオインフォでも使われます。
面倒な話は省きますが、謎の要請により、DNA配列同士を比較したいのだけど、
DNAには塩基の置換や挿入、欠失が起こるから困ったもんだ、という、
まことにレーベンシュタイン距離の扱う問題そのものがあったりします。



閑話休題



 しかし昨今はインターネットでこの辺の説明もコードも簡単に手に入るなぁ。
上で書いた内容なんてほとんど、むしろ断然詳しくネットに乗っているので僕が偉そうに書く必要もないのですが。


 そんな感じで虚無感に苛まれていてもあれなので、その辺に出回っているものとはほんのちょっと、wikiでは扱っていない部分を付け足したスニペットをはっときます。


 何が違うかって言うと、たとえば、置換はわりとよくあるんだけど、
挿入はほとんどないし、削除にいたっては絶望的にないよね、
という事前情報を状況に対応できるよう、コストを突っ込めるようにしただけ。

 ※挿入と削除は見る方向が違うだけで、同じ処理なので、ここを変える要請があるかは不明

template< typename CostType >
int getLevenshteinDistance( const char* str1, const char* str2, CostType cost_ins, CostType cost_del, CostType cost_mut ){
	unsigned int len1 = std::strlen( str1 );
	unsigned int len2 = std::strlen( str2 );

	// alloc
	CostType **matrix = new CostType*[len1+1];
	for( unsigned int i=0; i <= len1; ++i ){ matrix[i] = new CostType[len2+1]; }

	// init dp matrix
	for( unsigned int i = 0; i <= len1; ++i ){ matrix[i][0] = i * cost_ins; }
	for( unsigned int i = 0; i <= len2; ++i ){ matrix[0][i] = i * cost_del; }
	for( unsigned int i = 1; i <= len1; ++i ){
		for( unsigned int j = 1; j <= len2; ++j ){
			CostType min = matrix[i-1][j-1] + ( ( str1[i-1] == str2[j-1] ) ? 0 : cost_mut );	// mutation 
			if( min > ( matrix[i-1][j] + cost_ins ) ){ min = matrix[i-1][j] + cost_ins; }	// insertion
			if( min > ( matrix[i][j-1] + cost_del ) ){ min = matrix[i][j-1] + cost_del; }	// deletion
			matrix[i][j] = min;

		}
	}

	for( unsigned int i = 0; i <= len1; ++i ){
		for( unsigned int j = 0; j <= len2; ++j ){
			std::cout << matrix[i][j] << " ";
		}
		std::cout << std::endl;
	}
	
	CostType result = matrix[len1][len2];

	for( unsigned int i=0; i < len1; ++i ){ delete[] matrix[i]; }
	delete[] matrix;

	return result;
}

また無駄にテンプレート。コストはintとは限らないからね!
テストしてないのでちゃんと動くのかは知りません…


●蛇足


 この辺の、文字比較の何とか距離というものは有用だからか、わりと色々な種類があって、
今回のレーベンシュタイン距離のほかにも、Jaro距離とか、Jaro-Winkler距離とか、
なんだかもう色々とわけが分からない感じになっています。


 その辺の話も、一応できるのですがまた今度。