レーベンシュタイン距離 (Levenshtein distance) / 編集距離 (edit distance)
(include/emthrm/dynamic_programming/levenshtein_distance.hpp)

• View this file on GitHub
• Last update: 2022-12-15 22:18:37+09:00
• Include: #include "emthrm/dynamic_programming/levenshtein_distance.hpp"

任意の文字を削除・挿入・置換することによって、二つの文字列を一致させるために必要な操作回数の最小値である。

時間計算量

$O(NM)$

仕様

名前	戻り値
template <typename T> int levenshtein_distance(const T& a, const T& b);	$A$ と $B$ のレーベンシュタイン距離

参考文献

• В. И. Левенштейн: Двоичные коды с исправлением выпадений, вставок и замещений символов, Докл. АН СССР, Vol. 163, No. 4, pp. 845–848 (1965).
• https://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2

TODO

• Method of Four Russians
  • https://en.wikipedia.org/wiki/Method_of_Four_Russians#:~:text=In%20computer%20science%2C%20the%20Method,bounded%20number%20of%20possible%20values.
  • https://qiita.com/okateim/items/a1b0523c1c862009e81f
  • https://echizen-tm.hatenadiary.org/entry/20120520/1337516536

Submissons

https://onlinejudge.u-aizu.ac.jp/solutions/problem/DPL_1_E/review/4112291/emthrm/C++14

Verified with

• 動的計画法/レーベンシュタイン距離 (test/dynamic_programming/levenshtein_distance.test.cpp)

Code

#ifndef EMTHRM_DYNAMIC_PROGRAMMING_LEVENSHTEIN_DISTANCE_HPP_
#define EMTHRM_DYNAMIC_PROGRAMMING_LEVENSHTEIN_DISTANCE_HPP_

#include <algorithm>
#include <numeric>
#include <vector>

namespace emthrm {

template <typename T>
int levenshtein_distance(const T& a, const T& b) {
  const int n = a.size(), m = b.size();
  std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1));
  for (int i = n; i >= 1; --i) {
    dp[i][0] = i;
  }
  std::iota(dp[0].begin(), dp[0].end(), 0);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      dp[i][j] = std::min({dp[i - 1][j] + 1,
                           dp[i][j - 1] + 1,
                           dp[i - 1][j - 1] + (a[i - 1] != b[j - 1])});
    }
  }
  return dp[n][m];
}

}  // namespace emthrm

#endif  // EMTHRM_DYNAMIC_PROGRAMMING_LEVENSHTEIN_DISTANCE_HPP_

#line 1 "include/emthrm/dynamic_programming/levenshtein_distance.hpp"



#include <algorithm>
#include <numeric>
#include <vector>

namespace emthrm {

template <typename T>
int levenshtein_distance(const T& a, const T& b) {
  const int n = a.size(), m = b.size();
  std::vector<std::vector<int>> dp(n + 1, std::vector<int>(m + 1));
  for (int i = n; i >= 1; --i) {
    dp[i][0] = i;
  }
  std::iota(dp[0].begin(), dp[0].end(), 0);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      dp[i][j] = std::min({dp[i - 1][j] + 1,
                           dp[i][j - 1] + 1,
                           dp[i - 1][j - 1] + (a[i - 1] != b[j - 1])});
    }
  }
  return dp[n][m];
}

}  // namespace emthrm

Back to top page