DP（動的計画法）でレーベンシュタイン距離（編集距離）問題を解くまでの過程メモ

昨日は最長増加部分列の問題を解きました

https://o-treetree.hatenablog.com/entry/DPL1D

今日は、AOJの編集距離の問題を解きます。

といっても、相変わらずDPテーブルは思いつかなかったので検索してわかりやすかった解説を紹介する感じです。

参考にするのはこちら→編集距離（レーベンシュタイン距離）の求め方 - 具体例で学ぶ数学。ググってQiitaとか見たりしましたがこのサイトの説明が最も直感的でわかりやすかったです。

では、やっていきましょう。

問題

2つの文字列 $S,T$ の編集距離（レーベンシュタイン距離）を求めよ。

レーベンシュタイン距離 - Wikipedia

挿入、削除、置換の各操作のコストはいずれも $1$ とする。

制約

$1 \le |S|, |T| \le 1000$

入出力

入力 - $S,T$ をそれぞれ1行で入力
出力 - 編集距離を1行で出力

//入力
S
T
//出力
Ans

DPテーブルの作成

一応編集距離とはなんぞやというのを振り返っておきます。

例えばinputをimportに書き換えるときの編集距離は

初期状態

目標	i	m	p	o	r	t
現在	i	n	p	u	t

2文字目の置換

目標	i	m	p	o	r	t
現在	i	$ \rm{m} $	p	u	t

4文字目の置換

目標	i	m	p	o	r	t
現在	i	m	p	$ \rm{o} $	t

5文字目に挿入

目標	i	m	p	o	r	t
現在	i	m	p	o	$ \rm{r} $	t

ということで編集距離 = 3 です。

さて、今回作るDPテーブルは

$$ dp[i][j] := Sのi番目までの部分列からTのj番目までの部分列へ変換する編集距離 $$

とします。$S = \rm{input}, T = \rm{import}$ としてやってみます。

	j→	0	1	2	3	4	5	6
i↓			i	m	p	o	r	t
0		0	1	2	3	4	5	6
1	i	1
2	n	2
3	p	3			$x$
4	u	4
5	t	5

例えば $dp[3][3] = x$ のところは、inpからimpへ変換するときの編集距離で、これは2文字目を置換するだけなので $x=1$です。

すでに埋まっている値は初期値で、$dp[0][j]$ は(空文字列)から (空文字列), i, im, imp, ... に変換する編集距離なので文字数分必要ということです。$dp[i][0]$ についても、(空文字列), i, in, inp, ... から(空文字列)に変換する編集距離なので文字数がそのままdpの値になります。

答えから言いますが $dp[i][j]$ に入れる値は以下の3つの値の最小値となります。

$dp[i-1][j]$(上のマス)$+1$
$dp[i][j-1]$(左のマス)$+1$
$dp[i-1][j-1]$(左上のマス)$+c$
$c=0(S[i]=T[j]のとき)$
$c=1(S[i] \ne T[j]のとき)$

ここで $S[i]$ は文字列 $S$ の $i$ 番目の文字を表します（$1 \le i \le |S|$）。以下の、途中まで埋まった表を使って確認してみます。

	j→	0	1	2	3	4	5	6
i↓			i	m	p	o	r	t
0		0	1	2	3	4	5	6
1	i	1	0	1	2	3	4	5
2	n	2	1	1	2	3	4	5
3	p	3	2	2	1	2	3	4
4	u	4	3	3	$x$
5	t	5	4	4

$dp[4][3] = x$ は、inpu->impの編集距離です。これはinpu-(削除)->inp-(置換)->impで編集距離2ですが、 $dp[i-1][j], dp[i][j-1], dp[i-1][j-1]$ から求めてみます。

$dp[i-1][j]$(上のマス)$+1$ の意味

$dp[3][3]$ = inp->impの編集距離が既知(1)であるとき、inpu->impというのはinpu-(削除)->inp-(1)->impで達成できるため削除のコストを上乗せして $dp[4][3] = dp[3][3] + 1 = 2$ という候補がある

$dp[i][j-1]$(左のマス)$+1$ の意味

$dp[4][2]$ = inpu->imの編集距離が既知(3)であるとき、inpu->impというのはinpu-(3)->im-(挿入)->impで達成できるため挿入のコストを上乗せして $dp[4][3] = dp[4][2] + 1 = 4$ という候補がある

$dp[i-1][j-1]$(左上のマス)$+c$ ……の意味

先に $c=0$ となるパターン $S[i]=T[j]$ について、例えば $dp[2][2]$in->imの編集距離と $dp[3][3]$inp->impの編集距離が等しいのは明らかです。

さて、$dp[3][2]$ = inp->imの編集距離が既知(2)であるとき、inpu->impというのはinpu->imuの編集距離が上記のように考えて2 。そこからimu-(置換)->impで達成できるため置換のコストを上乗せして $dp[4][3] = dp[3][2] + 1 = 3$ という候補がある

これらのうち最小のもの（最短の変換方法）を選択すると $dp[4][3] = dp[3][3] + 1 = 2$ となります。

そんなこんなで完成形がこちら

	j→	0	1	2	3	4	5	6
i↓			i	m	p	o	r	t
0		0	1	2	3	4	5	6
1	i	1	0	1	2	3	4	5
2	n	2	1	1	2	3	4	5
3	p	3	2	2	1	2	3	4
4	u	4	3	3	2	2	3	4
5	t	5	4	4	3	3	3	3

求めるものは

\begin{align} & S→Tの編集距離\cr &= Sの|S|番目までの部分列からTの|T|番目までの部分列へ変換する編集距離\cr &= dp[|S|][|T|]\cr &= dp[5][6]\cr &= 3 \end{align}

となります。

実装

以上のことをコードにします。プログラミングでは $Sのi文字目$ を表すのにS[i-1]と書くので $dp[i-1][j-1]$(左上のマス)$+c$ のパターンでの一致判定の書き方に注意です。

挿入、削除、置換のコストを定数で示しています。

#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;

#define INSERT_COST 1
#define DELETE_COST 1
#define CHANGE_COST 1

int main(){
  string S,T;
  cin>>S>>T;
  int sl = S.size();
  int tl = T.size();

  vvi dp(sl+1, vi(tl+1));

  for(int i=0; i<=sl; i++)dp[i][0] = i*INSERT_COST;
  for(int j=0; j<=tl; j++)dp[0][j] = j*INSERT_COST;

  for(int i=1; i<=sl; i++){
    for(int j=1; j<=tl; j++){
      int D = dp[i-1][j] + DELETE_COST;
      int I = dp[i][j-1] + INSERT_COST;
      int C = dp[i-1][j-1] + (S[i-1]==T[j-1]? 0: CHANGE_COST);

      dp[i][j] = min({D,I,C});
    }
  }

  /* 確認用dp書き出し
  for(vi x: dp){
    for(int y: x){
      cout<<y<<",";
    }
    cout<<endl;
  }*/

  int ans = dp[sl][tl];

  cout<<ans<<endl;
}