2009年07月14日

Jaro-Winkler Distance

レーベンシュタイン距離と似たような用途で使える Jaro-Winkler 距離を JavaScript で使えるように。今回は Apache ライセンスで提供されている Lucene に含まれる Java のソースを適当に移植。

function jarowinkler(s1, s2)
{
var threshold = 0.7;

var max, min;
if (s1.length > s2.length)
{
max = s1;
min = s2;
}
else
{
max = s2;
min = s1;
}

var range = Math.max(max.length / 2 - 1, 0);
var matchIndexes = new Array(min.length);
for (var i = 0; i < matchIndexes.length; ++i){ matchIndexes[i] = -1; }
var matchFlags = new Array(max.length);
var matches = 0;

for(var mi = 0; mi < min.length; mi++)
{
var c1 = min.charAt(mi);
for(var xi = Math.max(mi - range, 0),
xn = Math.min(mi + range + 1, max.length); xi < xn; xi++)
{
if ((!matchFlags[xi])&&(c1 == max.charAt(xi)))
{
matchIndexes[mi] = xi;
matchFlags[xi] = true;
matches++;
break;
}
}
}
var ms1 = new Array(matches);
var ms2 = new Array(matches);
for (var i = 0, si = 0; i < min.length; ++i)
{
if (matchIndexes[i] != -1)
{
ms1[si] = min.charAt(i);
++si;
}
}
for (var i = 0, si = 0; i < max.length; ++i)
{
if (matchFlags[i])
{
ms2[si] = max.charAt(i);
++si;
}
}
var transpositions = 0;
for (var mi = 0; mi < ms1.length; ++mi)
{
if (ms1[mi] != ms2[mi])
{
++transpositions;
}
}
var prefix = 0;
for (var mi = 0; mi < min.length; ++mi)
{
if(s1.charAt(mi) == s2.charAt(mi))
{
++prefix;
}
else
{
break;
}
}

if (matches == 0)
{
return 0;
}

var m = matches;
var j = ((m / s1.length + m / s2.length +
(m - (transpositions / 2)) / m)) / 3;

return j < threshold ? j :
j + Math.min(0.1, 1.0/max.length) * prefix * (1 - j);
}
posted by oov at 22:01| Comment(0) | TrackBack(0) | 日記 | このブログの読者になる | 更新情報をチェックする
この記事へのコメント

この記事へのトラックバック
×

この広告は180日以上新しい記事の投稿がないブログに表示されております。