mirror of
https://hub.njuu.cf/TheAlgorithms/C-Plus-Plus.git
synced 2023-10-11 13:05:55 +08:00
164 lines
5.8 KiB
C++
164 lines
5.8 KiB
C++
|
/**
|
||
|
* @file
|
||
|
* @brief Implementation of [Minimum Edit Distance](https://en.wikipedia.org/wiki/Edit_distance) using Dynamic Programing
|
||
|
*
|
||
|
* @details
|
||
|
*
|
||
|
* Given two strings str1 & str2 and we have to calculate the minimum
|
||
|
* number of operations (Insert, Remove, Replace) required to convert
|
||
|
* str1 to str2.
|
||
|
*
|
||
|
* ### Algorithm
|
||
|
*
|
||
|
* We will solve this problem using Naive recursion. But as we are
|
||
|
* approaching with a DP solution. So, we will take a DP array to
|
||
|
* store the solution of all sub-problems so that we don't have to
|
||
|
* perform recursion again and again. Now to solve the problem, We
|
||
|
* can traverse all characters from either right side of the strings
|
||
|
* or left side. Suppose we will do it from the right side. So, there
|
||
|
* are two possibilities for every pair of characters being traversed.
|
||
|
* 1. If the last characters of two strings are the same, Ignore
|
||
|
* the characters and get the count for the remaining string.
|
||
|
* So, we get the solution for lengths m-1 and n-1 in a DP array.
|
||
|
*
|
||
|
* 2. Else, (If last characters are not the same), we will consider all
|
||
|
* three operations (Insert, Remove, Replace) on the last character of
|
||
|
* the first string and compute the minimum cost for all three operations
|
||
|
* and take the minimum of three values in the DP array.
|
||
|
* For Insert: Recur for m and n-1
|
||
|
* For Remove: Recur for for m-1 and n
|
||
|
* For Replace: Recur for for m-1 and n-1
|
||
|
*
|
||
|
* @author [Nirjas Jakilim](github.com/nirzak)
|
||
|
*/
|
||
|
|
||
|
#include <cassert> /// for assert
|
||
|
#include <iostream> /// for IO operations
|
||
|
#include <vector> /// for std::vector
|
||
|
/**
|
||
|
* @namespace dynamic_programming
|
||
|
* @brief Dynamic Programming algorithms
|
||
|
*/
|
||
|
|
||
|
namespace dynamic_programming {
|
||
|
|
||
|
/**
|
||
|
* @namespace Minimum Edit Distance
|
||
|
* @brief Implementation of [Minimum Edit Distance](https://en.wikipedia.org/wiki/Edit_distance) algorithm
|
||
|
*/
|
||
|
|
||
|
namespace minimum_edit_distance {
|
||
|
|
||
|
/**
|
||
|
* @brief Takes input of the cost of
|
||
|
* three operations: Insert, Replace and Delete
|
||
|
* and return the minimum cost among them.
|
||
|
* @param x used to pass minimum cost of Insert operations
|
||
|
* @param y used to pass minimum cost of Replace operations
|
||
|
* @param z used to pass minimum cost of Delete operations
|
||
|
* @returns x if `x` is the minimum value
|
||
|
* @returns y if `y` is the minimum value
|
||
|
* @returns z if `z` is the minimum value
|
||
|
*/
|
||
|
uint64_t min(uint64_t x, uint64_t y, uint64_t z) {
|
||
|
if (x <= y && x <= z) {
|
||
|
return x; /// returns x, if x is the minimum value
|
||
|
}
|
||
|
if (y <= x && y <= z) {
|
||
|
return y; /// returns y, if y is the minimum value
|
||
|
}
|
||
|
else {
|
||
|
return z; /// returns z if z is the minimum value
|
||
|
}
|
||
|
}
|
||
|
|
||
|
/**
|
||
|
* @brief Calculates and stores the result
|
||
|
* of all the sub-problems, so that we don't have to recur to compute
|
||
|
* the minimum cost of a particular operation if it is already
|
||
|
* computed and stored in the `dp` vector.
|
||
|
* @param dp vector to store the computed minimum costs
|
||
|
* @param str1 to pass the 1st string
|
||
|
* @param str2 to pass the 2nd string
|
||
|
* @param m the length of str1
|
||
|
* @param n the length of str2
|
||
|
* @returns dp[m][n] the minimum cost of operations
|
||
|
* needed to convert str1 to str2
|
||
|
*/
|
||
|
uint64_t editDistDP(std::string str1, std::string str2, uint64_t m, uint64_t n) {
|
||
|
/// Create a table to store results of subproblems
|
||
|
std::vector<std::vector<uint64_t>>dp(m+1, std::vector<uint64_t>(n+1)); /// creasting 2D vector dp to store the results of subproblems
|
||
|
|
||
|
/// Fill d[][] in bottom up manner
|
||
|
for (uint64_t i = 0; i <= m; i++) {
|
||
|
for (uint64_t j = 0; j <= n; j++) {
|
||
|
/// If first string is empty, only option is to
|
||
|
/// insert all characters of second string
|
||
|
if (i == 0) {
|
||
|
dp[i][j] = j; /// Minimum operations = j
|
||
|
}
|
||
|
|
||
|
/// If second string is empty, only option is to
|
||
|
/// remove all characters of second string
|
||
|
else if (j == 0) {
|
||
|
dp[i][j] = i; /// Minimum operations = i
|
||
|
}
|
||
|
|
||
|
/// If last characters are same, ignore last char
|
||
|
/// and recur for remaining string
|
||
|
else if (str1[i - 1] == str2[j - 1]) {
|
||
|
dp[i][j] = dp[i - 1][j - 1];
|
||
|
}
|
||
|
|
||
|
/// If the last character is different, consider all
|
||
|
/// possibilities and find the minimum
|
||
|
else {
|
||
|
dp[i][j] = 1 + min(dp[i][j - 1], // Insert
|
||
|
dp[i - 1][j], // Remove
|
||
|
dp[i - 1][j - 1]); // Replace
|
||
|
}
|
||
|
}
|
||
|
}
|
||
|
|
||
|
return dp[m][n]; /// returning the minimum cost of operations needed to convert str1 to str2
|
||
|
}
|
||
|
} // namespace minimum_edit_distance
|
||
|
} // namespace dynamic_programming
|
||
|
|
||
|
/**
|
||
|
* @brief Self-test implementations
|
||
|
* @returns void
|
||
|
*/
|
||
|
static void test() {
|
||
|
// 1st test
|
||
|
std::string str1 = "INTENTION"; // Sample input of 1st string
|
||
|
std::string str2 = "EXECUTION"; // Sample input of 2nd string
|
||
|
uint64_t expected_output1 = 5; // Expected minimum cost
|
||
|
uint64_t output1 = dynamic_programming::minimum_edit_distance::editDistDP(
|
||
|
str1, str2, str1.length(), str2.length()); // calling the editDistDP function and storing the result on output1
|
||
|
assert(output1 == expected_output1); // comparing the output with the expected output
|
||
|
std::cout << "Minimum Number of Operations Required: " << output1
|
||
|
<< std::endl;
|
||
|
|
||
|
// 2nd test
|
||
|
std::string str3 = "SATURDAY";
|
||
|
std::string str4 = "SUNDAY";
|
||
|
uint64_t expected_output2 = 3;
|
||
|
uint64_t output2 = dynamic_programming::minimum_edit_distance::editDistDP(
|
||
|
str3, str4, str3.length(), str4.length());
|
||
|
assert(output2 == expected_output2);
|
||
|
std::cout << "Minimum Number of Operations Required: " << output2
|
||
|
<< std::endl;
|
||
|
}
|
||
|
|
||
|
/**
|
||
|
* @brief main function
|
||
|
* @param argc commandline argument count (ignored)
|
||
|
* @param argv commandline array of arguments (ignored)
|
||
|
* @returns 0 on exit
|
||
|
*/
|
||
|
int main(int argc, char *argv[]) {
|
||
|
test(); // run self-test implementations
|
||
|
return 0;
|
||
|
}
|