編集距離は文字列処理における古典的な問題であり、1 つの文字列を別の文字列に変換するために必要な最小操作数を測定します。
問題定義#
2 つの文字列 A と B が与えられたとき、A を B に変換するための最小操作数を求めます。
毎回 1 種類の操作のみが許可され、各操作の「コスト」は 1 です。
- 文字を挿入する（Insert）
- 文字を削除する（Delete）
- 文字を置き換える（Replace）
例：
horse を ros に変換する：
horse → rorse （'h' を 'r' に置き換え）
rorse → rose （'r' を削除）
rose → ros （'e' を削除）
合計 3 ステップ → 編集距離 = 3
動的計画法による解法#
私たちは 2 次元配列 を使用して、 を に変換するために必要な最小操作数を表します。
## 初期条件
dp[0][j] = j # 空文字列を B[0..j-1] に変換：j 回挿入
dp[i][0] = i # A[0..i-1] を空文字列に変換：i 回削除
## 状態遷移方程式
if A[i-1] == B[j-1]:
dp[i][j] = dp[i-1][j-1] # 操作は不要
else:
dp[i][j] = min(
dp[i-1][j] + 1, # A[i-1] を削除
dp[i][j-1] + 1, # B[j-1] を挿入
dp[i-1][j-1] + 1 # A[i-1] を B[j-1] に置き換え
)
擬似コード：
def edit_distance(A, B):
n, m = len(A), len(B)
dp = [[0] * (m+1) for _ in range(n+1)]
for i in range(n+1):
dp[i][0] = i
for j in range(m+1):
dp[0][j] = j
for i in range(1, n+1):
for j in range(1, m+1):
if A[i-1] == B[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(
dp[i-1][j] + 1, # 削除（上に移動）
dp[i][j-1] + 1, # 挿入（左に移動）
dp[i-1][j-1] + 1 # 置き換え（左上の対角に移動）
)
return dp[n][m]
時間計算量
空間計算量
スペース計算量を最適化するために、現在の行と前の行のみを保存するロールアレイを使用できます。これは最長共通部分列問題 LCS に似ています。
変種問題#
最短編集パス問題（編集操作を復元する必要がある）
重み付き編集距離問題（各操作のコストが異なる）
Damerau-Levenshtein 距離（DL 距離、交換操作を許可）
編集パスの復元（バックトレース）#
操作手順を保存するために追加の配列を構築する必要があります。
def edit_path(A, B):
n, m = len(A), len(B)
dp = [[0]*(m+1) for _ in range(n+1)]
move = [['']*(m+1) for _ in range(n+1)]
for i in range(n+1):
dp[i][0] = i
move[i][0] = 'D' # 削除
for j in range(m+1):
dp[0][j] = j
move[0][j] = 'I' # 挿入
move[0][0] = ' '
for i in range(1, n+1):
for j in range(1, m+1):
if A[i-1] == B[j-1]:
dp[i][j] = dp[i-1][j-1]
move[i][j] = 'M' # 一致
else:
choices = [
(dp[i-1][j] + 1, 'D'),
(dp[i][j-1] + 1, 'I'),
(dp[i-1][j-1] + 1, 'R')
]
dp[i][j], move[i][j] = min(choices)
# パスをバックトレース
ops = []
i, j = n, m
while i > 0 or j > 0:
op = move[i][j]
if op == 'M' or op == 'R':
ops.append((op, i-1, j-1))
i -= 1
j -= 1
elif op == 'D':
ops.append(('D', i-1))
i -= 1
elif op == 'I':
ops.append(('I', j-1))
j -= 1
ops.reverse()
return dp[n][m], ops
状態圧縮を使用することはできません。そうしないと、パス情報が失われます。
重み付き編集距離#
置き換え操作のコストだけを考慮すればよいです。
def weighted_edit_distance(A, B, insert_cost=1, delete_cost=1, replace_cost=2):
n, m = len(A), len(B)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(n+1):
dp[i][0] = i * delete_cost
for j in range(m+1):
dp[0][j] = j * insert_cost
for i in range(1, n+1):
for j in range(1, m+1):
if A[i-1] == B[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(
dp[i-1][j] + delete_cost,
dp[i][j-1] + insert_cost,
dp[i-1][j-1] + replace_cost
)
return dp[n][m]
Damerau-Levenshtein 距離（DL 距離）#
編集距離の基礎の上に、隣接する 2 つの文字を交換できる操作が追加されます。
動的計画法の考え方を使用して行います。
: を に変換するための最小操作数を表します。
状態遷移方程式
1. もし A[i-1] == B[j-1]：
dp[i][j] = dp[i-1][j-1] （文字が同じで、操作は不要）
2. そうでない場合：
dp[i][j] = min(
dp[i-1][j] + 1, （削除）
dp[i][j-1] + 1, （挿入）
dp[i-1][j-1] + 1 （置き換え）
)
3. 交換条件を満たす場合：
A[i-1] == B[j-2] かつ A[i-2] == B[j-1]
その場合、許可される：
dp[i][j] = min(dp[i][j], dp[i-2][j-2] + 1) （交換）
擬似コード（交換操作）
for i in range(1, n+1):
for j in range(1, m+1):
cost = 0 if A[i-1] == B[j-1] else 1
dp[i][j] = min(
dp[i-1][j] + 1, # 削除
dp[i][j-1] + 1, # 挿入
dp[i-1][j-1] + cost # 置き換えまたは一致
)
# 隣接文字を交換できるか確認
if i > 1 and j > 1 and A[i-1] == B[j-2] and A[i-2] == B[j-1]:
dp[i][j] = min(dp[i][j], dp[i-2][j-2] + 1) # 交換