Edit Distance
2つの単語 word1 と word2 が与えられます。1回の編集では、word1 に対して次の3つの操作のいずれかを行います。任意の位置に文字を挿入する、文字を削除する、または文字を別の文字に置き換えることです。word1 を word2 に変換するために必要な編集の最小回数を返してください。
関数
- word1string
- あなたが編集する単語
- word2string
- 到達するという言葉
- 戻り値integer
- word1 を word2 に変えるための、挿入、削除、置換の最小回数
制約
1 ≤ word1.length ≤ 5001 ≤ word2.length ≤ 500- どちらの単語も、小文字の英字のみで構成されています。
例
- 入力
- word1 = "spot"word2 = "stop"
- 出力
- 2
- 説明
- pをtに、tをpに置き換えます。
spotはstotになり、次にstopになります。単語は2か所異なり、挿入や削除では長さが変わってしまうため、1回の編集では足りません。
- 入力
- word1 = "garden"word2 = "ardent"
- 出力
- 2
- 説明
ardenを得るには g を削除し、次に末尾に t を挿入してardentを得ます。1文字ずつ置き換える場合、2つの単語はすべての位置で異なるため、コストは 6 になります。
- 入力
- word1 = "rain"word2 = "shine"
- 出力
- 3
- 説明
- r を s に、a を h に置き換え、それから e を挿入します。2 回の編集では不十分です。r と a は
shineに含まれていないため、それぞれ文字数を維持する編集が必要であり、さらに単語の長さを 1 文字増やす必要があります。
発展問題
編集の件数に加えて、編集内容を最短のリストで返すこともできますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
各単語の最後の文字を見てください。それらが同じなら、変更する必要はありますか？異なるなら、2つの単語の語尾を同じにするには、どのように編集すればよいでしょうか？
異なる最後の文字に対して、3つの選択肢があります。一方をもう一方に置き換える、
word1の最後の文字を削除する、またはword2の最後の文字を挿入する、のいずれかです。どの選択肢を選んでも、より短い接頭辞について同じ問題が残るため、最もコストの低いものを選んで1を加えます。接頭辞の長さの各ペア
(i, j)に対する答えを表に保存します。空の接頭辞のコストは、i回の削除またはj回の挿入であり、これによって最初の行と列が埋まります。残りを行ごとに埋め、最後のセルから答えを読み取ります。
解説
編集は相互に影響します。gardenとardentは6つの位置すべてで異なりますが、編集は2回で十分です。そこで、それぞれの単語の最後の文字を見ます。2つの文字が一致するか、3種類の編集のいずれかで一致させることができ、どの選択肢でも、より短い接頭辞に対して同じ問題が残ります。表を使えば、すべての接頭辞の組み合わせを一度ずつ解決できます。
再帰を使って3つの編集をすべて試してみましょう
正しいが、最大のテストでは終わらない
考え方
edits(i, j) を、接尾辞 word1[i:] を word2[j:] に変換するための最小編集回数とします。先頭の文字が一致する場合は、その文字をそのままにして両方のインデックスを進めます。一致する文字に編集を費やしても役に立たないためです。一致しない場合は、次の3つの呼び出しのうち最もコストが低いものに1を加えます。置換では両方のインデックスを進め、word1[i] の削除では i を進め、word2[j] の挿入では j を進めます。一方の単語の文字がなくなったら、もう一方に残っている文字1つにつき編集を1回行います。
不一致があるたびに3つの呼び出しが始まります。共通の文字がない15文字の単語2つでは、約6.7 × 10^10回の呼び出しが必要です。しかし、異なる組 (i, j) は (n+1) × (m+1) 個しかないため、ほとんどの呼び出しは以前の呼び出しを繰り返しています。
アルゴリズム
iがword1の末尾を過ぎている場合は、m - jを返します。jがword2の末尾を過ぎている場合は、n - iを返します。word1[i] == word2[j]の場合は、edits(i+1, j+1)を返します。- それ以外の場合は、
1 + min(edits(i+1, j+1), edits(i+1, j), edits(i, j+1))を返します。 - 答えは
edits(0, 0)です。
def minDistance(word1, word2):
n, m = len(word1), len(word2)
def edits(i, j):
# Fewest edits to turn word1[i:] into word2[j:]
if i == n:
return m - j # insert the rest of word2
if j == m:
return n - i # delete the rest of word1
if word1[i] == word2[j]:
return edits(i + 1, j + 1)
return 1 + min(edits(i + 1, j + 1), # replace word1[i] with word2[j]
edits(i + 1, j), # delete word1[i]
edits(i, j + 1)) # insert word2[j]
return edits(0, 0)接頭辞の表を埋める
考え方
dp[i][j]を、word1の最初のi文字をword2の最初のj文字に変換するための最小編集回数とします。word1[i-1]とword2[j-1]が等しければ、対角の値dp[i-1][j-1]をそのまま使います。等しくない場合は、隣接するセルの最小値に1を加えます。対角のセルは置換、上のセルはword1[i-1]の削除、左のセルはword2[j-1]の挿入を表します。基底となる行と列は0ではありません。i文字を何もない状態にするにはi回の削除が必要なので、dp[i][0] = iとなり、同様にdp[0][j] = jとなります。
spotをstopに変換する場合、最後の行は[4, 3, 2, 2, 2]です。最後のセルではtとpを比較します。その対角のセル（spoをstoに変換する場合）の値は1で、他の隣接セルの値は2なので、答えは1 + 1 = 2です。500文字の単語を2つ使う場合、各セルを定数時間で計算して、2.5 × 10^5個のセルを埋めます。
アルゴリズム
(n+1) × (m+1)個のセルを持つdpを作成し、dp[i][0] = iおよびdp[0][j] = jとします。iを 1 からnまで、jを 1 からmまで動かします。word1[i-1] == word2[j-1]の場合、dp[i][j] = dp[i-1][j-1]とします。- そうでない場合、
dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])とします。 dp[n][m]を返します。
def minDistance(word1, word2):
n, m = len(word1), len(word2)
# dp[i][j]: fewest edits to turn the first i letters of word1 into the first j of word2
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(n + 1):
dp[i][0] = i # delete all i letters
for j in range(m + 1):
dp[0][j] = j # insert all j letters
for i in range(1, n + 1):
for j in range(1, m + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j - 1], # replace
dp[i - 1][j], # delete word1[i-1]
dp[i][j - 1]) # insert word2[j-1]
return dp[n][m]2行だけを残す
考え方
行 i が読み取るのは、行 i-1 と、自分より左にあるセルだけなので、配列は2つあれば十分です。完成した行には prev、埋めている行には cur を使います。対角は prev[j-1]、上は prev[j]、左は cur[j-1] です。基底列は各行の最初の要素に置かれるので、行 i を埋める前に cur[0] = i を設定します。
word2 を word1 に変換するのに必要な編集回数は同じです。挿入と削除が入れ替わるためです。行が短い方の単語に沿って進むように単語を入れ替えましょう。最大251,001セルの表の代わりに、各行の要素数は min(n, m) + 1 になり、計算量は同じ O(n × m) です。
アルゴリズム
word2がword1より長い場合は、入れ替えます。prev = [0, 1, ..., m]を設定します。- 1 から
nまでの各iについて、cur[0] = iを設定し、表のルールに従ってcur[1..m]を埋めます。対角と上の値はprevから、左の値はcurから読み取ります。その後、prevとcurを入れ替えます。 prev[m]を返します。
def minDistance(word1, word2):
if len(word2) > len(word1):
word1, word2 = word2, word1 # the rows run along the shorter word
m = len(word2)
# prev[j]: fewest edits to turn the previous prefix of word1 into word2[:j]
prev = list(range(m + 1))
for i in range(1, len(word1) + 1):
cur = [i] + [0] * m # i letters into an empty prefix: delete them all
for j in range(1, m + 1):
if word1[i - 1] == word2[j - 1]:
cur[j] = prev[j - 1]
else:
cur[j] = 1 + min(prev[j - 1], # replace
prev[j], # delete word1[i-1]
cur[j - 1]) # insert word2[j-1]
prev = cur
return prev[m]
落とし穴と境界ケース
- 最長共通部分列の場合のように、行 0 と列 0 をゼロで埋める。
abcを空の接頭辞にするには、0 回ではなく 3 回の削除が必要です。 - 2 行版で
cur[0] = iを忘れる。最初の要素には 2 行前の値が残り、その後のすべてのセルの値がずれてしまいます。 - 一致したときに編集コストを加算する。文字が等しい場合に
1 + min(...)を使うと、aをaにするコストが 1 になります。 - 左隣の値を
curではなくprevから読み取る。左隣は、現在の行でword2[j-1]を挿入した場合の値です。 - Python で、長さ 500 の単語にメモ化再帰を使う。呼び出しの深さは 1000 に達し、デフォルトの再帰制限を超えます。
よくある質問3
Edit Distance の時間計算量はどれくらいですか？
テーブルを使った解法では、接頭辞の各ペアにつき1つのセルを定数時間で埋めます。長さが n と m の場合、時間計算量は O(n × m) です。テーブル全体を使うとメモリ計算量は O(n × m) ですが、2行だけを使えば O(min(n, m)) になります。テーブルを使わない単純な再帰の計算量は指数関数的です。
編集距離はレーベンシュタイン距離と同じですか？
このバージョンはレーベンシュタイン距離です。挿入、削除、置換のコストはそれぞれ1です。編集距離は総称です。挿入と削除のみの場合は n + m - 2 × LCS となり、同じ長さの文字列で置換のみの場合はハミング距離となります。また、隣り合う2文字の交換を加えるとダメラウ・レーベンシュタイン距離になります。
編集距離は単一の配列で解けますか？
はい。1つの配列 row をその場で、左から右へ埋めていきます。row[j] を上書きする前は、そこにはまだ1つ上の行の値が入っており、row[j-1] にはすでに現在の行の値が入っています。失われるのは対角の値だけなので、古い row[j] を変数に保存し、j + 1 の対角の値として使います。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def minDistance(word1, word2):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
word1 = "spot" word2 = "stop"
期待される出力
2