編集距離（レーベンシュタイン距離）とは？C++での再帰的実装をわかりやすく解説

編集距離とは

2つの文字列が与えられたとき、1つ目の文字列（初期文字列）を2つ目の文字列（最終文字列）へ変換するために必要な最小の編集回数を求める問題を、編集距離（エディットディスタンス）と呼びます。本記事では、この問題を再帰的なアルゴリズムで解く考え方と、C++による実装例を紹介します。

ここで許される「編集」操作は、次の3種類です。

• 挿入 … 文字を1つ追加する
• 削除 … 文字を1つ取り除く
• 置換 … 既存の文字を別の文字に書き換える

入力と出力

比較対象となる2つの文字列を入力とし、変換に必要な編集回数を出力します。

入力：
比較する2つの文字列
string 1: Programming
string 2: Programs

出力：
Enter the initial string: Programming
Enter the final string: Programs
The number of changes required to convert Programming to Programs is 4

アルゴリズム

再帰関数 editCount(initStr, finalStr, initLen, finalLen) を用いて解きます。

入力：初期文字列・最終文字列と、それぞれの長さ
出力：初期文字列を最終文字列に変換するために必要な編集回数

Begin
    if initLen = 0, then
        return finalLen
    if finalLen = 0, then
        return initLen

    if initStr[initLen - 1] = finalStr[finalLen - 1], then
        return editCount(initStr, finalStr, initLen - 1, finalLen - 1)
    answer := 1 + min of (editCount(initStr, finalStr, initLen, finalLen - 1),
        editCount(initStr, finalStr, initLen - 1, finalLen),
        editCount(initStr, finalStr, initLen - 1, finalLen - 1))
    return answer
End

処理の流れを整理すると、次のようになります。

• 初期文字列が空なら、最終文字列の長さ（＝全文字の挿入）が答えになる
• 最終文字列が空なら、初期文字列の長さ（＝全文字の削除）が答えになる
• 末尾の文字が一致していれば、その文字は編集不要として、残りの部分の答えを再帰的に求める
• 一致していなければ、「挿入」「削除」「置換」の3操作それぞれについて再帰的に解き、最小値に1を加えたものが答えになる

C++による実装例

#include<iostream>
using namespace std;

// 3つの値の中で最小のものを返す関数
int min(int x, int y, int z) {
    if(x < y) {
        if(x < z)
            return x;
        else
            return z;
    } else {
        if(y < z)
            return y;
        else
            return z;
    }
}

// 初期文字列を最終文字列に変換するために必要な編集回数を再帰的に求める
int editCount(string initStr, string finalStr, int initLen, int finalLen) {
    // 初期文字列が空の場合：最終文字列の全文字を挿入する必要がある
    if (initLen == 0)
        return finalLen;

    // 最終文字列が空の場合：初期文字列の全文字を削除する必要がある
    if (finalLen == 0)
        return initLen;

    // 末尾の文字が一致する場合は、その前の文字同士を再帰的に比較
    if (initStr[initLen-1] == finalStr[finalLen-1])
        return editCount(initStr, finalStr, initLen-1, finalLen-1);

    // 末尾の文字が一致しない場合は、挿入・削除・置換の3操作を再帰的に試す
    return 1 + min (
        editCount(initStr, finalStr, initLen, finalLen-1),   // 挿入
        editCount(initStr, finalStr, initLen-1, finalLen),   // 削除
        editCount(initStr, finalStr, initLen-1, finalLen-1)  // 置換
    );
}

int main() {
    string initStr;
    string finalStr;

    cout << "Enter the initial string: "; cin >> initStr;
    cout << "Enter the final string: "; cin >> finalStr;
    cout << "The number of changes required to convert " << initStr << " to " << finalStr;
    cout << " is " << editCount( initStr, finalStr, initStr.size(), finalStr.size()) << endl;
}

実行結果

Enter the initial string: Programming
Enter the final string: Programs
The number of changes required to convert Programming to Programs is 4

「Programming」を「Programs」に変換するには、末尾の「ming」→「ms」の部分で4回の編集が必要であることが分かります。

計算量の注意点

この再帰的な解法はシンプルで理解しやすい反面、同じ部分問題を何度も計算するため、文字列が長くなると最悪で指数時間（O(3ⁿ)）かかるという弱点があります。実用上は、動的計画法（DP）を用いて O(m×n) の時間で解くのが一般的です。再帰にメモ化（結果のキャッシュ）を追加するだけでも、大幅な高速化が期待できます。