Levenshtein Distance (レーベンシュタイン距離)
(dp/levenshtein_distance.hpp)

• View this file on GitHub
• Last update: 2025-01-29 15:54:05+09:00
• Include: #include "dp/levenshtein_distance.hpp"

Edit Distance (編集距離) とも呼ばれ, 1 文字の挿入, 1 文字の削除, 1 文字の置換を行うことで $s$ を $t$ に一致させるための操作回数を表す

DP のイメージは LCS と似ており, 編集前の $s$ における各文字が $t$ のどの文字と対応するかを考えながら計算を進める

LCS では dp 配列の更新が $s_i = t_j$ となるような対応付けを行うときのみ発生していたため, dp[n][j] や dp[i][m] からの更新は発生しなかったが, Levenshtein Distance の場合は dp[n][j] から $s$ に 1 文字挿入を行うことで dp[n][j + 1] を更新できるため, i = n や j = m からも遷移を計算する必要がある

使い方

std::string s, t;
auto d = levenshtein_distance(s, t);

参考文献

• Wikipedia, レーベンシュタイン距離
  • 擬似コードはもらう DP で書かれており, このライブラリは配る DP で書かれていることに注意

Verified with

• verify/dp/levenshtein_distance.test.cpp

Code

#pragma once

#include <vector>
#include <string>

template <class T>
int levenshtein_distance(std::vector<T>& a, std::vector<T>& b, const int inf = 1000000000) {
    const int n = (int)(a.size()), m = (int)(b.size());
    std::vector dp(n + 1, std::vector<int>(m + 1, inf));
    // initialize
    dp[0][0] = 0;
    // もらう DP だと dp[i][0], dp[0][j] について初期化が必要
    // for (int i = 0; i < n + 1; i++) dp[i][0] = i;
    // for (int j = 0; j < m + 1; j++) dp[0][j] = j;
    // dp
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            // a += ?
            if (j + 1 <= m and dp[i][j + 1] > dp[i][j] + 1) {
                dp[i][j + 1] = dp[i][j] + 1;
            }
            // b += ?
            if (i + 1 <= n and dp[i + 1][j] > dp[i][j] + 1) {
                dp[i + 1][j] = dp[i][j] + 1;
            }
            // a[i] = b[i]
            if (i + 1 <= n and j + 1 <= m) {
                int cost = a[i] == b[j] ? 0 : 1;
                if (dp[i + 1][j + 1] > dp[i][j] + cost) {
                    dp[i + 1][j + 1] = dp[i][j] + cost;
                }
            }
        }
    }
    return dp[n][m];
}

int levenshtein_distance(std::string& s, std::string& t, const int inf = 1000000000) {
    const int n = (int)(s.size()), m = (int)(t.size());
    std::vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) a[i] = s[i];
    for (int j = 0; j < m; j++) b[j] = t[j];
    return levenshtein_distance(a, b, inf);
}

#line 2 "dp/levenshtein_distance.hpp"

#include <vector>
#include <string>

template <class T>
int levenshtein_distance(std::vector<T>& a, std::vector<T>& b, const int inf = 1000000000) {
    const int n = (int)(a.size()), m = (int)(b.size());
    std::vector dp(n + 1, std::vector<int>(m + 1, inf));
    // initialize
    dp[0][0] = 0;
    // もらう DP だと dp[i][0], dp[0][j] について初期化が必要
    // for (int i = 0; i < n + 1; i++) dp[i][0] = i;
    // for (int j = 0; j < m + 1; j++) dp[0][j] = j;
    // dp
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            // a += ?
            if (j + 1 <= m and dp[i][j + 1] > dp[i][j] + 1) {
                dp[i][j + 1] = dp[i][j] + 1;
            }
            // b += ?
            if (i + 1 <= n and dp[i + 1][j] > dp[i][j] + 1) {
                dp[i + 1][j] = dp[i][j] + 1;
            }
            // a[i] = b[i]
            if (i + 1 <= n and j + 1 <= m) {
                int cost = a[i] == b[j] ? 0 : 1;
                if (dp[i + 1][j + 1] > dp[i][j] + cost) {
                    dp[i + 1][j + 1] = dp[i][j] + cost;
                }
            }
        }
    }
    return dp[n][m];
}

int levenshtein_distance(std::string& s, std::string& t, const int inf = 1000000000) {
    const int n = (int)(s.size()), m = (int)(t.size());
    std::vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) a[i] = s[i];
    for (int j = 0; j < m; j++) b[j] = t[j];
    return levenshtein_distance(a, b, inf);
}

Back to top page