Geez in the universe

Wiki内歌詞掲載ページ
（未掲載）

続きを読む

過去ログ倉庫を621スレ分まで配置しました。

検索もこれから621スレ分まで対応させるつもりですが、
個人的な趣味で色々やりたいことがあるので作り直しします。

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

海外にも JavaScript でレーベンシュタイン距離を計算するソースコードはいくつか見つかったんだけど、挿入、置換、削除のコストをそれぞれ指定できるようになっているソースは見つからなかったのでこれもPHPのソースコードを参照してそのまま移植。

function levenshtein(s1, s2, cost_ins, cost_rep, cost_del)
{
  if (typeof cost_ins == "undefined") cost_ins = 1;
  if (typeof cost_rep == "undefined") cost_rep = 1;
  if (typeof cost_del == "undefined") cost_del = 1;

  var l1 = s1.length, l2 = s2.length;
  var p1, p2, tmp, i1, i2, j1, j2, cp1, cp2, c0, c1, c2, ch1, ch2;

  if (l1 == 0) {
    return l2 * cost_ins;
  }
  if (l2 == 0) {
    return l1 * cost_del;
  }

  p1 = new Array(l2 + 1);
  p2 = new Array(l2 + 1);

  for (i2 = 0; i2 <= l2; i2++) {
    p1[i2] = i2 * cost_ins;
  }
  for (i1 = 0, j1 = 0; i1 < l1; i1++) {
    p2[0] = p1[0] + cost_del;
    for (i2 = 0, j2 = 0; i2 < l2; i2++) {
      c0 = p1[i2] + (s1.charAt(i1) == s2.charAt(i2) ? 0 : cost_rep);

      c1 = p1[i2 + 1] + cost_del;
      if (c1 < c0) {
        c0 = c1;
      }
      c2 = p2[i2] + cost_ins;
      if (c2 < c0) {
        c0 = c2;
      }
      p2[i2 + 1] = c0;
    }
    tmp = p1;
    p1 = p2;
    p2 = tmp;
  }
  c0 = p1[l2];

  return c0;
}