C++で実装するレーベンシュタイン距離計算アルゴリズム

レーベンシュタイン距離（Levenshtein Distance）とは、2つの文字列の間で、一方の文字列をもう一方へ変換するために必要な最小の編集回数を表す指標です。ここでいう編集操作には、1文字の挿入・削除・置換の3つが含まれます。

例：「cat」と「mat」のレーベンシュタイン距離は1です。

cat → mat（'c' を 'm' に置換）

この記事では、動的計画法を用いてレーベンシュタイン距離を計算するC++プログラムを紹介します。レーベンシュタイン距離は、スペルチェック、DNA配列解析、類似テキスト検索など、幅広い分野で活用されている重要なアルゴリズムです。

アルゴリズムの手順

開始
    文字列を入力として受け取り、それぞれの長さを求める
    i = 0 から l1 まで:
        dist[0][i] = i
    j = 0 から l2 まで:
        dist[j][0] = j
    j = 1 から l1 まで:
        i = 1 から l2 まで:
            もし s1[i-1] == s2[j-1] ならば
                track = 0
            そうでなければ
                track = 1
            t = MIN((dist[i-1][j]+1), (dist[i][j-1]+1))
            dist[i][j] = MIN(t, (dist[i-1][j-1]+track))
        繰り返し終了
    繰り返し終了
    レーベンシュタイン距離を出力: dist[l2][l1]
終了

アルゴリズムのポイント

このアルゴリズムは動的計画法に基づいています。2次元配列 dist を使い、各セルには部分文字列同士の距離が格納されていきます。各セルの値は、次の3つの候補の中から最小値を選んで決定されます。

• 削除：dist[i-1][j] + 1
• 挿入：dist[i][j-1] + 1
• 置換または一致：dist[i-1][j-1] + track

track は、比較中の2文字が一致すれば 0、一致しなければ 1 となります。計算が完了すると、表の右下にある dist[l2][l1] が最終的なレーベンシュタイン距離になります。

C++による実装例

#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;
#define MIN(x,y) ((x) < (y) ? (x) : (y)) // 2つの値の最小値を計算するマクロ
int main() {
    int i,j,l1,l2,t,track;
    int dist[50][50];
    // 比較対象の文字列を定義
    char s1[] = "tutorials";
    char s2[] = "point";
    // 文字列 s1 と s2 の長さを取得して格納
    l1 = strlen(s1);
    l2 = strlen(s2);
    for(i=0;i<=l1;i++) {
        dist[0][i] = i;
    }
    for(j=0;j<=l2;j++) {
        dist[j][0] = j;
    }
    for (j=1;j<=l1;j++) {
        for(i=1;i<=l2;i++) {
            if(s1[i-1] == s2[j-1]) {
                track = 0;
            } else {
                track = 1;
            }
            t = MIN((dist[i-1][j]+1),(dist[i][j-1]+1));
            dist[i][j] = MIN(t,(dist[i-1][j-1]+track));
        }
    }
    cout<<"The Levinstein distance is:"<<dist[l2][l1];
    return 0;
}

実行結果

The Levinstein distance is:8

このプログラムでは、「tutorials」（9文字）と「point」（5文字）という2つの文字列を比較しており、結果としてレーベンシュタイン距離は 8 となりました。つまり、「tutorials」を「point」に変換するためには、最低でも8回の編集操作が必要だということです。ソースコード内の文字列は自由に変更できるので、任意の2つの文字列同士の距離を簡単に計算できます。