レーベンシュタイン距離(編集距離)とは、2つの文字列がどの程度異なっているかを示す数値です。
例えば「ちからうどん」を「からげんき」に編集するには以下の4手順が必要なため、編集距離は４となります。
※ 編集、削除、置換をそれぞれコスト1とした場合
- 「ち」を削除 : 「からうどん」
- 「う」を削除 : 「からどん」
- 「ど」を「げ」に置換 : 「からげん」
- 「き」を挿入 : 「からげんき」
■ 解説
「ちから」を「くらげ」に編集するための距離を求めてみましょう。
※編集、削除、置換をそれぞれコスト1とします。
1. 二次元配列を用意する
x を 編集文字列（ちから）の文字数 + 1 、 y を 目標文字列（くらげ）の文字数 + 1 とする二次元配列を用意します。
| (x = 0) | ち (x = 1) | か (x = 2) | ら (x = 3) | |
|---|---|---|---|---|
| (y=0) | ||||
| く (y=1) | ||||
| ら (y=2) | ||||
| げ (y=3) |
-
x: 編集文字列（ちから）の文字数 -
y: 目標文字列（くらげ）の文字数
編集距離は動的計画法の一種であるので、二次元配列の左上から右下に向かって要素を計算していくのですが、この二次元配列上での動きには下記の意味があります。
- 右に進むと、編集文字列を削除
matrix[0][0]からmatrix[0][1]に進むと「ち」を削除 - 下に進むと、目標文字列を編集文字列に挿入
matrix[0][0]からmatrix[1][0]に進むと「く」を挿入 - 右下に進むと、編集文字列と目標文字列を置換
matrix[0][0]からmatrix[1][1]に進むと「ち」と「く」を置換
2. 二次元配列の初期化
「長さ 0 の文字列と長さnの文字列の距離は nである」ので、空文字から編集文字列、目標文字列を作るための距離を二次元配列に書き込みます。
- 空文字から「ちから」を作るには３回の挿入が必要
- 空文字から「くらげ」を作るには３回の挿入が必要
| -(x = 0) | ち (x = 1) | か (x = 2) | ら (x = 3) | |
|---|---|---|---|---|
| (y=0) | 0 | 1 | 2 | 3 |
| く (y=1) | 1 | |||
| ら (y=2) | 2 | |||
| げ (y=3) | 3 |
3. 右下のマスに向かって編集距離を埋める
matrix[1][1] の編集距離を求めてみましょう。
matrix[1][1] に格納する値は以下３パターンの最小値となります。
- 「く」を挿入(
x = 0,y = 1からの右移動)
編集距離はmatrix[1][0] + 1で2 - 「ち」を削除(
x = 1,y = 0からの下移動)
編集距離はmatrix[0][1] + 1で2 - 「く」と「ち」を置換(
x = 0,y = 0からの斜め右下移動)
編集距離はmatrix[0][0] + 1で1
※比較対象が同一文字の場合、編集は不要なので、編集距離はmatrix[0][0]で0となります。
よって、この場合は 3. 「く」と「ち」を置換 の matrix[0][0] + 1 = 1 が最小なので 、matrix[1][1] に 1 を 格納します。
| y\x | - (x = 0) | ち (x = 1) | か (x = 2) | ら (x = 3) |
|---|---|---|---|---|
| - (y=0) | 0 | 1 | 2 | 3 |
| く (y=1) | 1 | 1 | ||
| ら (y=2) | 2 | |||
| げ (y=3) | 3 |
この考えを一般化すると、あるマス matrix[i][j] の編集距離は以下の3パターンの最小値になるといえます。
matrix[i][j - 1] + 1matrix[i - 1][j] + 1matrix[i - 1][j - 1] + 1 (比較対象が同一文字の場合はmatrix[i - 1][j - 1])
この調子で最後まで編集距離を埋めていくと下記のような値が入ります。
| y\x | - (x = 0) | ち (x = 1) | か (x = 2) | ら (x = 3) |
|---|---|---|---|---|
| - (y=0) | 0 | 1 | 2 | 3 |
| く (y=1) | 1 | 1 | 2 | 3 |
| ら (y=2) | 2 | 2 | 2 | 2 |
| げ (y=3) | 3 | 3 | 3 | 3 |
4. 編集距離
マトリックスを最後まで埋めたら、matrix[y][x]が「ちから」->「くらげ」の編集距離となります。
■ 実装例
Javaによる実装
LevenshteinDistance.java
import java.util.*;
public class LevenshteinDistance {
public static int levenshteinDistance(String str1, String str2) {
int rowLen = str2.length() + 1;
int colLen = str1.length() + 1;
int[][] matrix = new int[rowLen][colLen];
// 配列の初期化
for (int i = 0; i < colLen; i++) {
matrix[0][i] = i;
}
for (int i = 0; i < rowLen; i++) {
matrix[i][0] = i;
}
// マトリックスを埋める
for (int row = 1; row < rowLen; row++) {
for (int col = 1; col < colLen; col++) {
// 置換(左斜め上)
String c1 = str1.substring(col - 1, col);
String c2 = str2.substring(row - 1, row);
int cost1 = (c1.equals(c2)) ? matrix[row - 1][col - 1] : matrix[row - 1][col - 1] + 1;
// 削除(上)
int cost2 = matrix[row - 1][col] + 1;
// 追加(左)
int cost3 = matrix[row][col - 1] + 1;
matrix[row][col] = min(cost1, cost2, cost3);
}
}
return matrix[rowLen - 1][colLen - 1];
}
public static int min(int a, int b, int c) {
int min = a;
if (b < min) min = b;
if (c < min) min = c;
return min;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("str1 : ");
String str1 = sc.next();
System.out.print("str2 : ");
String str2 = sc.next();
System.out.println(levenshteinDistance(str1, str2));
}
}
Pythonによる実装
levenshtein_distance.py
"""
a を b に変換するための編集距離を計算するメソッド
a : 編集対象文字列
b : 目標文字列
add : a に一文字追加するコスト
remove : a から一文字削除するコスト
replace : a を一文字置換するコスト
"""
def edit_dist(a, b, add=1, remove=1, replace=1):
len_a = len(a) + 1
len_b = len(b) + 1
# 配列の初期化
arr = [[-1 for col in range(len_a)] for row in range(len_b)]
arr[0][0] = 0
for row in range(1, len_b):
arr[row][0] = arr[row - 1][0] + add
for col in range(1, len_a):
arr[0][col] = arr[0][col - 1] + remove
# 編集距離の計算
def go(row, col):
if (arr[row][col] != -1):
return arr[row][col]
else:
dist1 = go(row - 1, col) + add
dist2 = go(row, col - 1) + remove
dist3 = go(row - 1, col - 1)
arr[row][col] = min(dist1, dist2, dist3) if (b[row - 1] == a[col - 1]) else min(dist1, dist2, dist3 + replace)
return arr[row][col]
return go(len_b - 1, len_a - 1)
if __name__ == "__main__":
while True:
print("word1 word2 : ", end="")
a, b = input().split(" ")
print(edit_dist(a, b))