【C++】Wagner-Fischerアルゴリズムで文字列照合!レーベンシュタイン距離の求め方

本記事では、Wagner-Fischer(ワグナー・フィッシャー)アルゴリズムを使って2つの文字列を比較する方法を解説します。このアルゴリズムを利用すると、片方の文字列をもう片方に一致させるために必要な最小の編集回数を求めることができます。

これは動的計画法(ダイナミックプログラミング)を用いた代表的な手法で、2つの文字列間のレーベンシュタイン距離(編集距離)を計算します。レーベンシュタイン距離とは、1文字の「挿入」「削除」「置換」を繰り返して一方の文字列を他方に変換するときの、最小の操作回数のことです。

入力：2つの文字列 "Support" と "Suppose"
出力：必要な最小変更回数：2

アルゴリズムの流れ

Wagner_Fischer(str1, str2)

入力：2つの文字列 str1 と str2
出力：必要な最小変更回数

l1 := str1 の長さ、l2 := str2 の長さ
(l1+1)×(l2+1) のサイズの表 d を定義する
d の1行目に 0〜l1 の連番を、1列目に 0〜l2 の連番を設定する
j を 1 から l1 まで繰り返す:
    i を 1 から l2 まで繰り返す:
        もし str1[i-1] = str2[j-1] ならば
            tracker := 0
        そうでなければ
            tracker := 1
        temp := d[i-1][j]+1 と d[i][j-1]+1 のうち小さい方
        d[i][j] := temp と (d[i-1][j-1]+tracker) のうち小さい方
d[l2][l1] を返す

ポイントは、比較する文字が一致した場合はコスト0(tracker = 0)、一致しなかった場合はコスト1(tracker = 1)として、左・上・左上の3方向のセルを参照しながら最小コストを埋めていく点です。

C++によるサンプルコード

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

int d[100][100];

int min(int a, int b) {
    return (a < b) ? a : b;
}

int main() {
    int i, j, str1_len, str2_len, temp, tracker;
    string str1 = "Support";
    string str2 = "Suppose";

    str1_len = str1.length();
    str2_len = str2.length();

    // 表の初期化（1行目と1列目）
    for (i = 0; i <= str1_len; i++)
        d[0][i] = i;
    for (j = 0; j <= str2_len; j++)
        d[j][0] = j;

    // 動的計画法で表を埋める
    for (j = 1; j <= str1_len; j++) {
        for (i = 1; i <= str2_len; i++) {
            if (str1[i-1] == str2[j-1]) {
                tracker = 0;
            } else {
                tracker = 1;
            }
            temp = min((d[i-1][j] + 1), (d[i][j-1] + 1));
            d[i][j] = min(temp, (d[i-1][j-1] + tracker));
        }
    }

    cout << "Levenshtein distance: " << d[str2_len][str1_len];
}

実行結果

Levenshtein distance: 2

結果の解説

"Suppose" を "Support" に変換するには、6文字目の s → r という置換と、7文字目の e → t という置換の、合計2回の編集操作が必要です。そのため、レーベンシュタイン距離は 2 となります。

このようにWagner-Fischerアルゴリズムでは、2つの文字列の長さに対応する二次元の表を作成し、左上から順に各セルの最小コストを計算することで、効率よく編集距離を求められます。計算量は O(m×n)（m、n はそれぞれの文字列の長さ）です。

まとめ

Wagner-Fischerアルゴリズムは、テキストエディタの差分検出、DNA配列の解析、スペルチェックなど、文字列同士の類似度を評価したいさまざまな場面で応用されています。C++では上記のように二次元配列と二重ループだけで簡潔に実装できるので、ぜひ実際に動かして挙動を確かめてみてください。