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

プログラミング 競技プログラミング Aizu Online Judge アルゴリズム

こんにちは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を確保して、任意のLP[j][k](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])
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;
}

 

5)レーベンシュタイン距離の実用例(個人的見解)

類似内容の発見に使えそうだよね。

文書作成ソフトとかで、"play"じゃなくて間違って"plai"と打ったときに、レーベンシュタイン距離が近いため、"play"と正しい候補が出てくる的なことを個人的にイメージした。本当にレーベンシュタイン距離が使われていたらうれしいな。

 

ということでまた