レーベンシュタイン距離で文字列の類似度を高速に取得する

2020/02/232020/03/11

はじめに

文字列の類似度について考えます。具体的には、レーベンシュタイン距離を使用して文字列の類似度を測定します。ただし、レーベンシュタイン距離では、速度が遅いため、高速化します。高速化に伴ってレーベンシュタイン距離とは別物になってしまいますが、類似度としての役割は果たせます。

最終的には、文字列類似度としてレーベンシュタイン距離ではなくn-gramを使用する方法を採用しました。レーベンシュタイン距離では、高速化しても遅すぎるのとn-gramの類似度が使用目的に合致していたため、採用しました。

n-gramで文字列の類似度を測定する

※ウェブページで使用したかったため、使用言語はJavaScriptです

レーベンシュタイン距離

レーベンシュタイン距離の概要としては、文字列Aから文字列Bへ変更するのに、挿入・削除・置換を何回行えば変更できるかの問題を解くアルゴリズムです。

オーダーは、O(N*M)で正直遅いです。ただ、単純でわかりやすいので文字列の類似度としては、一般的です。次のコードは、レーベンシュタイン距離のWikipediaの擬似コードをそのまま、JavaScriptに書き換えたものです。

levenshteinDistance.jsfunction levenshteinDistance(str1, str2) {
  var r, c, cost, 
      d = [];

  for (r=0; r<=str1.length; r++) {
    d[r] = [r];
  }
  for (c=0; c<=str2.length; c++) {
    d[0][c] = c;
  }
  for (r=1; r<=str1.length; r++) {
    for (c=1; c<=str2.length; c++) {
      //cost = str1[r-1] == str2[c-1] ? 0: 1;
      cost = str1.charCodeAt(r-1) == str2.charCodeAt(c-1) ? 0: 1;
      d[r][c] = Math.min(d[r-1][c]+1, d[r][c-1]+1, d[r-1][c-1]+cost);
    }
  }
  return d[str1.length][str2.length];
}

レーベンシュタイン距離（最適化 + 中断）

上記コードに最適化と中断処理を追加したコード。（配列の作成方法は、C言語等と異なりJavaScript固有の最適化処理を組み込んでいます）

計算量は、O(N*M)です。ただし、編集距離が短い場合、他2つより明らかに遅いです。ですが、編集距離が長くなると、中断の数値次第では善戦します。

levenshteinDistance.jsfunction levenshteinDistance(str1, str2, threshold) {
  var s1, s2, len1, len2;
  if (str1.length < str2.length) {
    s1 = str1;
    s2 = str2;
  } else {
    s1 = str2;
    s2 = str1;
  }
  len1 = s1.length;
  len2 = s2.length;
  if (threshold == null || threshold == 0 || threshold > len2) {
    threshold = len2;
  }
  if (len2-len1 >= threshold || len1 == 0) {
    return threshold;
  }
  var r, c, min, ins, sub,
      //d = new Array(len2);
      d = [];

  for (c=1; c<=len2; c++) {
    //d[c-1] = c;
    d.push(c);
    // Packed Array
    // see http://nmi.jp/2019-06-09-The-reason-you-should-avoid-new-array-100
  }
  for (r=0; r<len1; r++) {
    ins = min = r + 1;
    minDistance = len2;
    for (c=0; c<len2; c++) {
      //sub = ins - (s1[r] != s2[c] ? 0: 1);
      sub = ins - (s1.charCodeAt(r) != s2.charCodeAt(c) ? 0: 1);
      ins = d[c] + 1;
      //del = min + 1;
      //min = del < ins ? (del < sub ? del: sub): (ins < sub ? ins: sub);
      min = min < ins ? (min < sub ? min+1: sub): (ins < sub ? ins: sub);
      d[c] = min;
      if (min < minDistance) { minDistance = min; }
    }
    if (minDistance >= threshold) { return threshold; }
  }
  return min > threshold ? threshold: min;
}

function levenshtein(str1, str2, threshold) {
  threshold = threshold != null ? threshold: 0;
  var m = Math.max(str1.length, str2.length);
  var d = levenshteinDistance(str1, str2, (1-threshold)*m);
  return 1 - (d / m);
}

O(ND)

O(ND)アルゴリズム。原著論文は、「E. W. Myers. An O(ND) difference algorithm and its variations. Algorithmica, 1, 251-266 (1986)」です。レーベンシュタイン距離とは、違いますがだいたい一緒です（備考参照）。

Nは、str1とstr2の文字列長の合計。Dは、編集距離です。編集距離が少なければ少ないほど高速に計算できます。

editDistanceOND.jsfunction editDistanceOND(str1, str2) {
  var len1 = str1.length,
      len2 = str2.length,
      max = len1 + len2,
      offset = max + 1,
      x, y, D, k, kk,
      V = new Array(offset*2+1);

  V[1+offset] = 0;
  for (D=0; D<=max; D++) {
    for (k=-D; k<=D; k+=2) {
      kk = k + offset;
      x = (k == -D || (k != D && V[kk-1] < V[kk+1])) ? V[kk+1]: V[kk-1]+1;
      y = x - k;
      //while (x < len1 && y < len2 && str1[x] == str2[y]) {
      while (x < len1 && y < len2 && str1.charCodeAt(x) == str2.charCodeAt(y)) {
        x++;
        y++;
      }
      V[kk] = x;
      if (x >= len1 && y >= len2) { return D; }
    }
  }
  return -1;
}

function editOND(str1, str2) {
  var m = Math.max(str1.length, str2.length);
  var d = editDistanceOND(str1, str2);
  return 1 - (d / m);
}

O(NP)

O(NP)アルゴリズム。原著論文は、「S. Wu, U. Manber, and G. Myers. An O(NP) sequence comparison algorithm. Information Processing Letter. 35(6) 317-332 (1990)」です。レーベンシュタイン距離とは、違いますがだいたい一緒です（備考参照）。

Nは、str1とstr2の文字列長の合計。Pは、m,n(m>=n)として、P=(D-(m-n))/2です。なので、おおまかにO(ND)の半分の処理時間になります。

editDistanceONP.jsfunction snake(k, y, str1, str2) {
  var x = y - k;
  while (x < str1.length && y < str2.length && str1.charCodeAt(x) == str2.charCodeAt(y)) {
    x++;
    y++;
  }
  return y;
}

function editDistanceONP(str1, str2) {
  var s1, s2;
  if (str1.length < str2.length) {
    s1 = str1;
    s2 = str2;
  } else {
    s1 = str2;
    s2 = str1;
  }
  var x, y, k, p,
      v0, v1,
      len1 = s1.length,
      len2 = s2.length,
      delta = len2 - len1,
      offset = len1 + 1,
      dd = delta + offset,
      dc = dd - 1,
      de = dd + 1,
      max =len1 + len2 + 3,
      //fp = new Array(max);
      fp = [];

  for (p=0; p<max; p++) {
    //fp[p] = -1;
    fp.push(-1);
  }
  for (p=0; fp[dd]!=len2; p++) {
    for (k=-p; k<delta; k++) {
      kk = k + offset;
      v0 = fp[kk-1] + 1;
      v1 = fp[kk+1];
      fp[kk] = snake(k, (v0 > v1 ? v0: v1), s1, s2);
    }
    for (k=delta+p; k>delta; k--) {
      kk = k + offset;
      v0 = fp[kk-1] + 1;
      v1 = fp[kk+1];
      fp[kk] = snake(k, (v0 > v1 ? v0: v1), s1, s2);
    }
    v0 = fp[dc] + 1;
    v1 = fp[de];
    fp[dd] = snake(delta, (v0 > v1 ? v0: v1), s1, s2);
  }
  return delta + (p - 1) * 2;
}

function editONP(str1, str2) {
  var m = Math.max(str1.length, str2.length);
  var d = editDistanceONP(str1, str2);
  return 1 - (d / m);
}

※原著論文のURL先は、既にリンク切れしています

備考

O(ND)・O(NP)アルゴリズムは、レーベンシュタイン距離とは別物です。編集距離は、削除・挿入から算出されます。置換は、削除・挿入の2手順となります。レーベンシュタイン距離と同じ値を取得することはできません。ですが、レーベンシュタイン距離側をO(ND)・O(NP)アルゴリズムと同様の値を返すように変更することはできます。コード例を下に示す。

cost = str1.charCodeAt(r-1) == str2.charCodeAt(c-1) ? 0: 1;
↓置換の編集距離を1から2に変更する
cost = str1.charCodeAt(r-1) == str2.charCodeAt(c-1) ? 0: 2;

バグ取りの日々