Geez in the universe

レーベンシュタイン距離と似たような用途で使える 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);
}