編集距離

2024年6月12日 #Levenshtein

概要

編集距離 (edit distance) は 2 つの文字列間で一方の文字列を他方の文字列と一致させるために必要な最小の操作回数である。これは 2 つの文字列が互いにどれだけ異なるかを定量化している。文字列の類似性を評価するために自然言語処理の分野で広く使用されている。

概要
レーベンシュタイン距離

レーベンシュタイン距離

レーベンシュタイン距離 (Levenshtein distance) は 1965 年にソビエトの数学者ウラジミール・レーベンシュタインによって定義された編集距離の一種である。編集距離の中でも最も一般的なメトリクスであり、そのため編集距離という言葉と同義に使用されることがしばしばある。

レーベンシュタイン距離は挿入、削除、置換の 3 つの操作を行うことができる。例として $a={\rm kitten}$, $b={\rm sitting}$ の 2 つの文字列について考えると、$a$ は以下の 3 つの操作で $b$ に変換できることから、レーベンシュタイン距離は 3 であることが分かる。

replace $a_1={\rm k}$ to ${\rm s}$
replace $a_5={\rm e}$ to ${\rm i}$
insert ${\rm g}$ as $a_7$

より一般的には、2 つの文字列 $a$ と $b$ に対してそれぞれの終端位置を $i$, $j$ としたとき、レーベンシュタイン距離は次の再帰的な式 ($\ref{lev}$) で求めることができる。\[ \begin{equation} {\rm lev}_{a,b}(i,j) = \begin{cases} \max(i, j) & \text{if $\min(i, j) = 0$,} \\ \min \begin{cases} {\rm lev}_{a,b}(i-1,j) + 1, \\ {\rm lev}_{a,b}(i,j-1) + 1, \\ {\rm lev}_{a,b}(i-1,j-1) + 1_{(a_i \neq b_j)} \end{cases} & \text{otherwise}. \end{cases} \label{lev} \end{equation} \]

例えば $a={\rm kitten}$, $b={\rm sitting}$ のケースにおいて、式 ($\ref{lev}$) は Figure 1 に示す表を作成しているに等しい。したがって、文字列 $a$ と $b$ の長さをそれぞれ $n$, $m$ としたときのレーベンシュタイン距離の計算量は $O(nm)$ である。

Figure 1. $a={\rm kitten}$, $b={\rm sitting}$ のレーベンシュタイン距離。横方向の増減は $a$ を $b$ に一致させるための削除操作の回数、縦方向の増減は挿入操作の回数、斜め方向の増減は置換操作の回数を示している。

$i=0$ または $j=0$ のケースでは、$a$ は $j$ 回の挿入または $i$ 回の削除操作によって $b$ と一致させることができるのは明白である。
$a={\rm k}$, $b={\rm s}$ となる ${\rm lev}_{a,b}(1,1)$ では:
1. ${\rm lev}_{a,b}(0,1)+1$: $a={\rm k}$ に対し $a={\rm sk}$ となる挿入操作 1 回 + $a={\rm s}$ とする削除操作 1 回 = 2 回
2. ${\rm lev}_{a,b}(1,0)+1$: $a={\rm k}$ に対し $a=$ となる削除操作 1 回 + $a={\rm s}$ とする挿入操作 1 回 = 2 回
3. ${\rm lev}_{a,b}(0,0)+1$: $a={\rm k}$ に対し $a={\rm s}$ となる置換操作 1 回 = 1 回

$a={\rm kit}$, $b={\rm shitt}$ の ${\rm lev}_{a,b}(3,4)$ に注目する。

function levenshteinDistance(a, b) {
  const n = a.length;
  const m = b.length;
  if (n === 0) return m;
  if (m === 0) return n;

  // 2次元配列の作成と max(i, j) if min(i, j) == 0 の初期化
  const lev = new Array(m + 1);
  for(let j = 0; j <= m; j++) {
    lev[j] = new Array(n + 1);
    lev[j][0] = j;
  }
  for(let i = 1; i <= n; i++) {
    lev[0][i] = i;
  }

  for (let j = 1; j <= m; j++) {
    for (let i = 1; i <= n; i++) {
      const cost = a.charAt(i - 1) === b.charAt(j - 1) ? 0 : 1;
      lev[j][i] = Math.min(
        lev[j - 1][i] + 1,          // 挿入操作
        lev[j][i - 1] + 1,          // 削除操作
        lev[j - 1][i - 1] + cost    // 置換操作
      );
    }
  }

  return lev[m][n];
}

編集距離

概要

Table of Contents

レーベンシュタイン距離