📍

レーベンシュタイン距離を完全に理解した！(C++編)

2021/12/08に公開

C++

※この記事はQiitaからの移行記事です

こんにちは、競プロ絶賛勉強中のyapattaです。

AOJ(AIZU ONLINE JUDGE)のレーベンシュタイン距離の問題を解くことができなかったから、理解するために記事を書いた。プログラミングをやってない人でも理解できる記事を書きたい。
この記事を見て、レーベンシュタイン距離について理解して頂ければ幸いである。

最後に実装されたコードが書かれているので、コードだけみたい人は是非最後だけ見て欲しい。

1)レーベンシュタイン距離(編集距離)とは？

レーベンシュタイン距離とは、とりあえず２つの文字列がどのぐらい違っている文字列か表す指標であると理解してもらえるといい。

文字列Aの中の1文字を、置換、挿入、削除を繰り返しすことで、一方の文字列Aをもう一方の文字列Bに変形する。この繰り返しの最小回数をレーベンシュタイン距離という。詳しくは以下↓

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

2)どんな問題?

まずこんな問題

Edit Distance (Levenshtein Distance) | Aizu Online Judge

ある文字列を２つ入力して、その２つの文字列のレーベンシュタイン距離を出力するという問題

3)実装方法

レーベンシュタイン距離にある、以下の２つの性質を用いて漸化式を立てることで、レーベンシュタイン距離を求められる。

注)LP(x, y)は文字列xとyのレーベンシュタイン距離を指す。

性質1) 文字列`x`の長さが`S`、文字列`y`が空文字列(長さが0)のとき、`LP(x, y) = S`

xの文字をS回削除したら、xが空文字列になるため、LP(x, y) = Sになることがわかると思う。

具体的に考えてみよう。 x = "apple"(xの長さは5)、y = ""(yの長さは0)とする。このとき、xの文字を5回削除したら、xはyと等しくなるから確かに、LP(x, y) = 5

ちなみに、xが空文字列、yが長さSの文字列であったとしても、xにS回文字を挿入したら、yと同じ文字列になるため、LP(x, y) = S

性質2) `LP(x,y)`は漸化式によってわかる

x = "book"、y = "desk"としたとき

(1)最後の文字が等しいときについて

LP("book", "desk") = LP("boo", "des")

これは、x[3](xの4文字目)とy[3](yの4文字目)が両方'k'で等しいため、最後の文字'k'がなくても編集距離は同じことによる

(2)削除について

LP("boo", "des") = LP("bo", "des") + 1

"boo"から'o'を削除したものが"bo"となるから、確かに、

LP("boo", "des") = LP("bo", "des") + 1が成り立つ

(3)挿入について

LP("boo", "des") = LP("boo", "de") + 1

"boo"に一文字's'を挿入したとき、LP("boo", "des") = LP("boos", "des") + 1

ここで(1)より、LP("boos", "des") = LP("boo", "de")となるから、

確かに、LP("boo", "des") = LP("boo", "de") + 1 が成り立つ

(4)置換について

LP("boo", "des") = LP("bo", "de") + 1

"boo"の3文字目の'o'を's'に置換したところ、LP("boo", "des") = LP("bos", "des") + 1

ここで(1)より、LP("bos", "des") = LP("bo", "de")となるから、

確かに、LP("boo", "des") = LP("bo", "de") + 1 が成り立つ

(1)(2)(3)(4)の漸化式を用いて、最小のレーベンシュタイン距離を求めたいから、

配列LPを確保して、j >= 1 かつ k >= 1における任意のLP[j][k]について、最後の文字が等しいかで場合分けして、

if xのj文字目 == yのj文字目
	LP[j][k] = min(LP[j-1][k]+1, LP[j][k-1]+1, LP[j-1][k-1])

if xのj文字目 != yのj文字目
	LP[j][k] = min(LP[j-1][k]+1, LP[j][k-1]+1, LP[j-1][k-1]+1)

としたら求まる

注) ここでLP[j][k]はxのj文字目までの文字列と、yのk文字目までの文字列のレーベンシュタイン距離を表す。

じゃあ実際に実装してみよう

4)実装方法をもとにしてできたコード

#include <iostream>
#include <string>
using namespace std;
int LP[1005][1005]={};

int main() {
  int j,k;
  string x,y;
  cin >> x >> y;
  for(j=1;j<=x.size();j++) LP[j][0] = j;
  for(k=1;k<=y.size();k++) LP[0][k] = k;

  //aをbに近づけたい!
  for(j=1;j<=x.size();j++) {
    for(k=1;k<=y.size();k++) {
      //a[j]を削除するか、a[j+1]にb[k]と同じ文字を挿入するか
      //上記２つの行為の回数で最小な方を採用
      int m = min(LP[j-1][k]+1, LP[j][k-1]+1);
      if(x[j-1] == y[k-1]) {
        //最後の文字が同じだから最後の文字がなくても編集距離は同じ
        m = min(m,LP[j-1][k-1]);
        LP[j][k] = m;
      }else {
        //最後の文字を置換する
        m = min(m,LP[j-1][k-1]+1);
        LP[j][k] = m;
      }
    }
  }
  cout << LP[x.size()][y.size()] << endl;
  return 0;
}