レーベンシュタイン距離(編集距離)を計算(C++)

レーベンシュタイン距離とは?

• 文字列s1とs2がどれだけ異なっているかを示す指標。
• 1文字の置き換え、削除、追加をコスト1としたとき、s1からs2に変換するための最小コストがレーベンシュタイン距離です。
• 編集距離とも呼ばれるので、以降はそう呼びます(「レーベンシュタイン距離」は長ったらしいため)。
• s1⇒s2とs2⇒s1の変換にかかるコストは等しい。
• 参考(wikipedia)：レーベンシュタイン距離 - Wikipedia

例：「rise」と「kid」の編集距離を計算

初期状態

空文字は"□"で表示しておきます。

現在	r	i	s	e
ゴール	k	i	d	□

手順1：「r」を「k」に変換

現在	k	i	s	e
ゴール	k	i	d	□

手順2：「s」を「d」に変換

現在	k	i	d	e
ゴール	k	i	d	□

手順3：「e」を削除

現在	k	i	d	□
ゴール	k	i	d	□

よって、「rise」と「kid」のレーベンシュタイン距離は3です。

プログラム的な求め方

• 以下ではプログラム的な求め方をしていきます。
• アルゴリズムとしては、動的計画法(DP法)を使うことになります。

DP法のテーブルを用意

まずは、計算結果を格納するためのテーブルを用意します。
空文字「□」も含む点に注意しましょう。

各セルには「縦軸の文字」と「横軸の文字」の編集距離を保存します。
(1) : 「□(空文字)」と「k」の編集距離
(2) : 「ris」と「ki」の編集距離

セルの初期化

空文字と任意の文字xの編集距離はxの文字数と等しいため、該当する箇所は初期化しておきます。

セルの更新

セルの更新方法を説明しますが、文字が短いと説明が分かりにくいので、赤星(「ris」⇒「ki」)を使って説明します(グレーで塗りつぶしたところは同様の方法で更新します)。

更新する際は左、上、左上のセルの値を参照します。というのも、「ris」⇒「ki」(「ki」⇒「ris」でも同じ)は以下の3種類の変換で実現できるからです。

(1)

「ris」⇒「k」の処理(＊)＋「i」を加える。

スタート	r	i	s
＊の処理後	k	□	□
「i」を加える	k	i	□

(2)

「ki」⇒「ri」の処理(＊)＋「s」を加える (「ki」⇒「ris」と「ris」⇒「ki」は同じ処理とみなせます)

スタート	k	i	□
＊の処理後	r	i	□
「s」を加える	r	i	s

(3)

一度少し抽象化して考えますが、例えば、〇と△は任意長の文字列としたとき、

• 「〇a」と「△a」の距離：「〇」と「△」の距離と等しい。
• 「〇a」と「△b」の距離：「〇」と「△」の距離 + 1(「a」⇒「b」の距離)。

となります。つまり、「末尾の文字の変換」+「それ以外の文字の処理」でも変換は可能ということです。
今回は「ris」と「ki」の変換なので、「ri」⇒「k」変換＋「s」⇒「i」変換の処理と同等と考えることができます。

セルの更新

この(1)~(3)の処理における距離は、左・上・左上のセルの値を参照することで計算量を減らしながら求めることができます。
(1)~(3)で求まる距離は、
(1)3 + 1 = 4
(2)1 + 1 = 2
(3)2 + 1(末尾文字sとiは等しくないため)
となります。これらの最小値が「ris」⇒「ki」の編集距離となるため2を挿入します。

最終結果

• あとは同じ方法でグレーで塗りつぶした箇所の編集距離を求めます。
• 知りたいのは、「rise」⇒「kid」の距離なので、右下の値を取得すればOKです。

C++で実装

ソースコード

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {

  // 文字列の作成
  string s1 = "rise", s2 = "kid";

  // テーブルの高さと幅を決定
  int h = s1.size() + 1;
  int w = s2.size() + 1;

  // DP法のテーブルを作成
  vector<vector<int>> table(h, vector<int>(w, 0));

  // 初期化
  for (int i = 0; i < h; i++) {
    table[i][0] = i;
  }
  for (int j = 0; j < w; j++) {
    table[0][j] = j;
  }

  // 動的計画法でテーブルを更新
  for (int i = 1; i < h; i++) {
    for (int j = 1; j < w; j++) {
      // 更新したい位置を基準として、「左+1」、「上+1」の値を求める
      int v1 = table[i][j-1]+1;
      int v2 = table[i-1][j]+1;

      // 「左上+cの値を求める」
      int c = (s1[i-1] != s2[j-1]) ? 1 : 0; 
      int v3 = table[i-1][j-1] + c;

      // v1~3の最小値を求め、代入する
      int v_min = min(min(v1, v2), v3);
      table[i][j] = v_min;
    }
  }

  // テーブルを表示
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cout << table[i][j] << " ";
    }
    cout << endl;
  }

  // 編集距離を表示
  cout << "編集距離：" << table[h-1][w-1] << endl; 
}

実行結果

0 1 2 3 
1 1 2 3 
2 2 1 2 
3 3 2 2 
4 4 3 3 
編集距離：3

参考

qiita.com