Jaro-Winkler距離

NLP C++ algorithm

　以前、スペルミスや「もしかして」系の機能の裏で動く技術としてわりと知られているLevenshtein距離についてちょっと書いてみました。
今回はそれと同様な用途に用いられがちなJaro-Winkler距離。


　Jaro-Winkler距離というのは、Levenshtein距離同様に文字列同士の近さを数値化するアルゴリズムです。
距離って言っても、数値が小さいほうが遠いので気をつけましょう。cos距離みたいなかんじです。

　こいつは、Jaro距離という、これまた謎の文字列類似度計測指標にすこしだけ改良を加えたもので、肝はJaro距離です。
その少しだけの改良というのは、（式を見る限り）プレフィックスのexact matchは重視しようか、という程度のもの。


　で、パパっと作れると思ったら、意外とてこずった。


　Jaro距離では文字同士の一致を取るのですが、マッチとする文字の文字位置に一定の範囲をもうけ、そのウインドウ内での一致を取ります。
また、文字位置の交換によるマッチが可能であるかどうか？という転置の考えも取り入れています。
この転置が曲者で、しばらくうんうんうなってました。


というわけでコード

// valid_distance = -1 : not consider distance between characters
unsigned int getNumRangeMatchChar( const std::string &s1, const std::string &s2, const int distance = -1 ){	
	unsigned int l1 = s1.size();
	unsigned int l2 = s2.size();
	bool ignore_distance = false;

	if( distance < 0 ){ ignore_distance = true; }

	unsigned int counter = 0;
	for( unsigned int i = 0; i < l1; ++i ){

		// setting search range
		unsigned int from = i;
		unsigned int under = l2;
		if(! ignore_distance ){
			from = ( i < (unsigned int)distance ) ? 0 :  i - (unsigned int)distance;
			under = ( i +(unsigned int)distance >= l2 ) ? l2 : i + (unsigned int)distance;
		}
		for( unsigned int j = from; j < under; ++j ){
			if( s1[i] == s2[j] ){ ++counter; }
			// NOTICE : this code consider the case i == j ( both place and character match )
		}
	}
	return counter;
}

std::string getRangeMatchChar( const std::string &s1, const std::string &s2, const int distance = -1 ){
	unsigned int l1 = s1.size(), l2 = s2.size();
	bool ignore_distance = false;

	if( distance < 0 ){ ignore_distance = true; }

	std::string ret = "";

	for( unsigned int i = 0; i < l1; ++i ){
		// setting search range
		unsigned int from = i;
		unsigned int under = l2;
		if(! ignore_distance ){
			from = ( i < distance ) ? 0 :  i - distance;
			under = ( i + distance >= l2 ) ? l2 : i + distance;
		}
		for( unsigned int j = from; j < under; ++j ){
			if( s1[i] == s2[j] ){ ret += s1[i]; }
			// NOTICE : this code consider the case i == j ( both place and character match )
		}
	}
	return ret;
}

unsigned int getNumTransposition( const std::string &s1, const std::string &s2 ){
	unsigned int c = 0;
	for( unsigned int i = 0; i < s1.size() && i < s2.size(); ++i ){
		if( s1[i] != s2[i] ){ ++c; }
	}
	return c;
	
}

// Error the case  s1 & s2 are empty
double getJaroDistance( const std::string &s1, const std::string &s2 ){
	int distance = ( s1.size() > s2.size() ) ? s1.size() : s2.size();
	if( distance < 0 ){ return -1; } 
	distance = distance / 2 - 1;
	if( distance < 0 ){ return -1; }

	int match = getNumRangeMatchChar( s1, s2, distance );
	int trans = getNumTransposition( getRangeMatchChar( s1, s2, distance ), getRangeMatchChar( s2, s1, distance ) );
	double m = (double)match;
	double t = ( (double)trans ) / 2.;

	return ( m / (double)s1.size() + m / (double)s2.size() + ( m - t ) / match ) / 3.;
}

unsigned int getLengthOfCommonPrefix( const std::string &s1, const std::string &s2 ){
	unsigned int c = 0;
	for( unsigned int i = 0; i < s1.size() && i < s2.size(); ++i ){
		if( s1[i] == s2[i] ){ ++c; } else { return c; }
	}
	return c;
}

double getJaroWinklerDistance( const std::string &s1, const std::string &s2, const double scaling = 0.1 ){
	if( scaling < 0 ){ return -1; }
	double j = getJaroDistance( s1, s2 );
	return j + getLengthOfCommonPrefix( s1, s2 ) * scaling * ( 1 - j );
}


ミソは、マッチを取るときに軸足をstring1とstring2どちらにおいても同じ数字が得られるのだけど、
マッチした文字をマッチした順に並べると、軸足の置き方によって順番が変わるよね、という話。


Levenshtein距離より精度がいいぜ、という発言をたまに聞きますが、意味が分からないのでそういう考え方はしないほうがいいと思います。
ものの尺度なので。