Edit Distance

Q: 編集距離の時間計算量はどれくらいですか？

表を使う解法は、各接頭辞のペアにつき一定の処理で1つのセルを埋めるため、 O(n × m) 時間で実行されます。ここで、 n と m は2つの長さです。表全体を使う場合、メモリ使用量は O(n × m) です。2行を使う場合は O(min(n, m)) です。表を使わない単純な再帰の計算量は指数時間です。

Q: 編集の件数だけでなく、編集の一覧を取得するにはどうすればよいですか？

テーブル全体を保持し、 dp[n][m] から逆にたどります。文字が一致する場合は、編集せずに斜めに進みます。それ以外の場合は、値が1小さい隣のセルへ進みます。斜めは置換、上は削除、左は挿入です。 dp[0][0] まで進み、編集を逆順に読み取ります。2行版だけではこれを実行できません。以前の行を破棄しているためです。

Q: 編集距離は単一の配列で解けますか？

はい。1つの配列 row を左から右へ、その場で埋めていきます。 row[j] を上書きする前は、まだ1つ上の行の値を保持しており、 row[j-1] にはすでに現在の行の値が入っています。失われる値は対角の値だけなので、変数に保持しておきます。書き込む前に古い row[j] を保存し、それを j + 1 の対角の値として使います。

むずかしい動的計画法

+10

2つの単語、word1とword2が与えられます。1回の編集では、word1に対して、任意の位置に文字を挿入する、文字を削除する、または文字を別の文字に置き換える、のいずれかを行います。word1をword2に変換するための最小の編集回数を返してください。

関数

minDistance(word1: string, word2: string) → integer

word1string: 編集する単語
word2string: 「到達する」という語
戻り値integer: word1 を word2 に変換するために必要な挿入、削除、置換の最小回数

制約

1 ≤ word1.length ≤ 500
1 ≤ 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
説明: shinにするには、rをsに、aをhに置き換え、それからeを挿入します。2回の編集ではできません。rとaはshineには含まれていないため、それぞれの置き換えには単語を長くしない編集が必要で、さらに単語を1文字増やす必要があるからです。

提出時に隠しテスト+21件

発展問題

編集内容だけでなく、最も短い編集リストも1つ返してもらえますか？

ヒント

1つずつ開いてください。開くたびに少しずつ答えに近づきます。

3個中0個を表示

解説

編集は互いに影響し合うため、単語を位置ごとに修正することはできません。gardenとardentは6つの位置すべてで異なりますが、gを削除してすべてが左にずれれば、2回の編集で十分です。解決の鍵は、各単語の最後の文字だけに注目することです。2つの文字がすでに一致しているか、ちょうど3通りの編集のいずれかで一致させることができ、どの選択でも、より短い接頭辞に対する同じ問題が残ります。(n+1) × (m+1)個の答えを格納する表を使えば、接頭辞のすべての組み合わせを一度に解決でき、そのうち2行だけで十分です。

再帰を使って3つの編集をすべて試してみましょう

正しいが、最大のテストでは終わらない

考え方

edits(i, j)を、接尾部分word1[i:]をword2[j:]に変えるために必要な編集の最小回数とします。2つの接尾部分の先頭の文字を見てください。それらが同じなら、そのまま残して両方のインデックスを進めます。一致する文字を編集する必要はありませんし、その文字に編集を使う計画があっても、残しておく計画に変更して編集回数を増やさずに済みます。

異なる場合は、word1[i]を処理するか、word2[j]を作り出すために、編集が必要です。その方法はちょうど3つあります。word1[i]をword2[j]に置き換え、両方のインデックスを進めます。つまり、edits(i+1, j+1)です。word1[i]を削除し、iだけを進めます。つまり、edits(i+1, j)です。word2[j]をその前に挿入し、jだけを進めます。つまり、edits(i, j+1)です。答えは、3つのうち最小の値に1を足したものです。word1を使い切ったら、残りのword2を挿入します。コストはm - jです。word2を使い切ったら、残りのword1を削除します。コストはn - iです。

不一致のたびに3つの呼び出しが発生するため、処理が遅くなります。共通する文字がない15文字の単語2つの場合、呼び出し回数は約6.7 × 10^10回になり、大きなテストではそれぞれ500文字あります。しかし、異なるペア(i, j)は(n+1) × (m+1)個しかないため、ほとんどの呼び出しは以前の呼び出しの繰り返しです。

アルゴリズム

i と j から始まる接尾辞に対する edits(i, j) を記述します。
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文字に変換するための最小編集回数とします。インデックス0は空の接頭辞を表します。

遷移。2つの接頭辞の最後の文字、word1[i-1]とword2[j-1]を比較します。一致する場合はそのまま使います。つまり、左上のセルから対角線方向にあるdp[i][j] = dp[i-1][j-1]です。一致しない場合は編集を1回行い、隣接する3つのセルのうち最小の値を選びます。対角線上のdp[i-1][j-1]は、word1[i-1]をword2[j-1]に置き換えることを意味します。上のセルdp[i-1][j]は、word1[i-1]を削除することを意味します。左のセルdp[i][j-1]は、末尾にword2[j-1]を挿入することを意味します。

基底行と基底列。多くの表形式の問題とは異なり、これらは0ではありません。i文字を空の接頭辞に変換するにはi回削除する必要があるため、dp[i][0] = iです。何もないところからj文字を作るにはj回挿入する必要があるため、dp[0][j] = jです。各セルは上、左、対角線上のセルを参照するため、行ごとに左から右へ埋めていけば、必要なセルはすでに計算されています。答えはdp[n][m]です。

spotをstopに変換する場合の表を示します。列は接頭辞""、s、st、sto、stopに対応します。行""は[0, 1, 2, 3, 4]、行sは[1, 0, 1, 2, 3]、行spは[2, 1, 1, 2, 2]、行spoは[3, 2, 2, 1, 2]、行spotは[4, 3, 2, 2, 2]です。いくつかのセルを見てみましょう。sとsは一致するので、対角線上の0をそのまま使います。spとstは一致しません。隣接セルの値は、対角線上が0、上が1、左が1なので、1 + 0 = 1となり、置き換えは1回です。spoとstoはoが一致するので、そのセルの値1をそのまま使います。最後のセルでは、spotとstopのtとpを比較します。隣接セルの値は1、2、2なので、答えは1 + 1 = 2です。

表には(n+1) × (m+1)個のセルがあり、各セルの計算量は一定です。500文字の単語2つの場合、およそ2.5 × 10^5ステップになります。メモ化再帰でも同じセルを埋めますが、再帰の深さがn + m回に達することがあり、Pythonのデフォルトの上限である1000を超えます。

アルゴリズム

(n+1) × (m+1) 個のセルを持つテーブル dp を作成します。
すべての i について dp[i][0] = i、すべての j について 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 を設定します。行 0 は基底行として [0, 1, 2, ..., m] で始まります。

word2 を word1 に変換するのに必要な編集回数は同じです。挿入はすべて削除に、削除はすべて挿入になるためです。そのため、単語を入れ替えて、短い方に沿って行を進めることができます。すると各行が保持する数値は min(n, m) + 1 個になり、最大251,001個のセルからなる表を使わずに済みます。計算量は引き続き O(n × m) です。

アルゴリズム

word2がword1より長い場合は、入れ替えます。
prev = [0, 1, ..., m]を設定します。ここで、mは短い方の長さです。
iを1からnまで順に処理し、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 を空の接頭辞にするには削除が 3 回必要で、0 回ではないため、dp[i][0] は i、dp[0][j] は j でなければなりません。
2 行版で cur[0] = i を忘れる。最初の要素には 2 行前の値が残り、その後のすべてのセルがずれてしまいます。
文字が一致したときに編集コストを加える。同じ文字に対して dp[i][j] = 1 + min(...) とすると、a を a にするコストが 1 になります。一致した場合は、対角の値をコピーします。
左隣の値を cur ではなく prev から読み取る。左隣は現在の行です。word1[:i] がすでに word2[:j-1] に変換された後で、word2[j-1] を挿入する操作にあたります。
位置ごとに比較する。単語が異なる位置を数えるだけでは、挿入や削除が考慮されません。garden と ardent の場合は 6 になりますが、答えは 2 です。
500 文字の単語に対する再帰をメモ化する。呼び出しの深さは 1000 に達し、これは Python のデフォルトの上限です。

よくある質問4

編集距離の時間計算量はどれくらいですか？

表を使う解法は、各接頭辞のペアにつき一定の処理で1つのセルを埋めるため、O(n × m)時間で実行されます。ここで、nとmは2つの長さです。表全体を使う場合、メモリ使用量はO(n × m)です。2行を使う場合はO(min(n, m))です。表を使わない単純な再帰の計算量は指数時間です。

編集距離はレーベンシュタイン距離と同じですか？

はい、このバージョンはレーベンシュタイン距離です。挿入、削除、置換のコストはそれぞれ1です。編集距離はこの概念の総称です。他の種類では、許可される編集が少なかったり多かったりします。挿入と削除のみの場合は n + m - 2 × LCS となり、長さが等しい場合に置換のみを許可するとハミング距離となり、隣り合う2文字の入れ替えを加えるとダメラウ・レーベンシュタイン距離となります。

編集の件数だけでなく、編集の一覧を取得するにはどうすればよいですか？

テーブル全体を保持し、dp[n][m]から逆にたどります。文字が一致する場合は、編集せずに斜めに進みます。それ以外の場合は、値が1小さい隣のセルへ進みます。斜めは置換、上は削除、左は挿入です。dp[0][0]まで進み、編集を逆順に読み取ります。2行版だけではこれを実行できません。以前の行を破棄しているためです。

編集距離は単一の配列で解けますか？

はい。1つの配列 row を左から右へ、その場で埋めていきます。row[j] を上書きする前は、まだ1つ上の行の値を保持しており、row[j-1] にはすでに現在の行の値が入っています。失われる値は対角の値だけなので、変数に保持しておきます。書き込む前に古い row[j] を保存し、それを j + 1 の対角の値として使います。

Python

def minDistance(word1, word2):
    # ここにコードを書いてください

テストケース

ケース1

ケース2

ケース3

入力

word1 = "spot"
word2 = "stop"

期待値

Edit Distance

関数

制約

例

ヒント

解説

再帰を使って3つの編集をすべて試してみましょう

接頭辞の表を埋める

2行だけ残す

落とし穴と境界ケース

よくある質問4

似た問題