編集距離 (レーベンシュタイン距離)

同じ計算を何度もしている

kitten を sitting に変えるには、1 文字ずつ「置き換える」「消す」「足す」のどれかを選びます。最小で何回で済むかを知りたい。これが編集距離で、スペルの候補出し、DNA の比較、git diff の親戚まで、同じ考え方が使われています。

素直に考えると、先頭の 1 文字ごとに 3 通りの選択肢があり、その先でまた 3 通りに分かれます。10 文字なら分岐は数万通りです。

ここで手を止めて、分岐の中身を見てみます。「kitten の後ろ 4 文字を sitting の後ろ 5 文字に変えるには」という同じ問いが、別々の枝の先で何度も出てきます。同じ問いを毎回ゼロから解き直しているのが、爆発の正体です。

もっと分かりやすい例で確かめます。

fib(5) を計算すると fib(2) は 3 回、fib(1) は 5 回呼ばれます。fib(30) では fib(2) が 50 万回を超えます。答えは毎回同じなのにです。

1 度出した答えを取っておくのがメモ化、小さいほうから順に埋めていくのがボトムアップ、埋めるときの計算式が漸化式です。用語はこれだけで、あとはどんな表を作るかの話になります。

1 マスは 3 つの手から決まる

表の縦を「s1 を何文字まで見たか」、横を「s2 を何文字まで見たか」にします。マスの中身は「そこまでを一致させるのに必要な最小の回数」です。

今見ている 2 文字が同じなら、何もしなくてよいので、左上のマスの値がそのまま入ります。違うなら、次の 3 つを比べて一番小さいものに 1 を足します。

• 上のマス — s1 の文字を 1 つ消した場合
• 左のマス — s2 の文字を 1 つ足した場合
• 左上のマス — 1 文字を置き換えた場合

どれがどれか迷ったら、上に動くと s1 が 1 文字短くなり、左に動くと s2 が 1 文字短くなる、と手を動かして確かめてください。左上は両方が同時に短くなるので、置き換えです。

一番上の行と一番左の列は、片方が空文字列のときです。空から 3 文字を作るには 3 回足すしかないので、0、1、2、3 と並びます。ここを埋めないまま 0 のままにすると、表全体が小さくなって答えがずれます。

答えは右下のマスです。左上から右下へ向かって、行ごとに順に埋めていけば、必要な値は必ず埋まった後になります。

添字が 1 つずれる

表には空文字列の行と列があるので、m + 1 行 n + 1 列を用意します。そのぶん、マスの番号と文字の番号が 1 つずれます。

i 番目のマスは「最初の i 文字」を表すので、比べる文字は i 番目ではなく i - 1 番目です。ここを合わせ忘れると、最初の 1 文字を無視した答えや、範囲外のエラーになります。

やってみよう

• horse と ros の表を紙に書いて埋める。答えは 3
• 同じ文字列同士なら、左上から右下まで斜めに 0 が並ぶ
• 片方が空文字列なら、答えはもう片方の文字数と同じになる

1. 戻り値は s1 を s2 に変えるのに必要な最小編集回数 (整数)
2. 編集操作は挿入・削除・置換の 3 種類で、それぞれ 1 回として数える
3. 二次元 DP テーブルを用いて O(m * n) で計算すること