Levenshtein Distance Algorithm
Definition:​
The Levenshtein Distance Algorithm, also known as Edit Distance, calculates the minimum number of single-character operations (insertions, deletions, or substitutions) required to transform one string into another. Developed by Vladimir Levenshtein in 1965, it is widely used in spell checking, DNA sequence analysis, and natural language processing.
Characteristics:​
-
Dynamic Programming:
- Builds solution matrix
- Optimal substructure
- Bottom-up approach
-
Edit Operations:
- Character insertions
- Character deletions
- Character substitutions
-
Distance Calculation:
- Minimum operations count
- Operation costs tracking
- Path reconstruction
-
Similarity Measurement:
- String comparison
- Fuzzy matching
- Distance normalization
Time Complexity:​
-
Standard Version:
- Where m, n are string lengths
- Dynamic programming approach
- Matrix construction
-
Space-Optimized:
- Using two rows only
- Rolling array technique
- Constant space per row
Space Complexity:​
- Standard Version:
- Full matrix storage
- Backtracking support
- Operation history
C++ Implementation:​
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class LevenshteinDistance {
private:
// Structure to store edit operation details
struct EditOperation {
enum Type { MATCH, SUBSTITUTE, INSERT, DELETE } type;
char from;
char to;
int cost;
EditOperation(Type t, char f, char t2, int c)
: type(t), from(f), to(t2), cost(c) {}
};
// Store the edit path for backtracking
vector<EditOperation> editPath;
// Custom costs for operations
int insertCost = 1;
int deleteCost = 1;
int substituteCost = 1;
public:
// Set custom costs for operations
void setCosts(int ins, int del, int sub) {
insertCost = ins;
deleteCost = del;
substituteCost = sub;
}
// Calculate basic Levenshtein distance
int calculateDistance(const string& str1, const string& str2) {
int m = str1.length();
int n = str2.length();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
// Initialize first row and column
for (int i = 0; i <= m; i++) {
dp[i][0] = i * deleteCost;
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j * insertCost;
}
// Fill the matrix
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (str1[i-1] == str2[j-1]) {
dp[i][j] = dp[i-1][j-1]; // Match
} else {
dp[i][j] = min({
dp[i-1][j] + deleteCost, // Deletion
dp[i][j-1] + insertCost, // Insertion
dp[i-1][j-1] + substituteCost // Substitution
});
}
}
}
return dp[m][n];
}
// Calculate distance and store edit path
int calculateDistanceWithPath(const string& str1,
const string& str2) {
editPath.clear();
int m = str1.length();
int n = str2.length();
vector<vector<int>> dp(m + 1, vector<int>(n + 1));
vector<vector<EditOperation::Type>> operations(
m + 1, vector<EditOperation::Type>(n + 1));
// Initialize
for (int i = 0; i <= m; i++) {
dp[i][0] = i * deleteCost;
operations[i][0] = EditOperation::DELETE;
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j * insertCost;
operations[0][j] = EditOperation::INSERT;
}
// Fill matrix and track operations
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (str1[i-1] == str2[j-1]) {
dp[i][j] = dp[i-1][j-1];
operations[i][j] = EditOperation::MATCH;
} else {
dp[i][j] = min({
dp[i-1][j] + deleteCost,
dp[i][j-1] + insertCost,
dp[i-1][j-1] + substituteCost
});
if (dp[i][j] == dp[i-1][j] + deleteCost) {
operations[i][j] = EditOperation::DELETE;
} else if (dp[i][j] == dp[i][j-1] + insertCost) {
operations[i][j] = EditOperation::INSERT;
} else {
operations[i][j] = EditOperation::SUBSTITUTE;
}
}
}
}
// Reconstruct edit path
int i = m, j = n;
while (i > 0 || j > 0) {
switch (operations[i][j]) {
case EditOperation::MATCH:
editPath.push_back(EditOperation(
EditOperation::MATCH,
str1[i-1], str2[j-1], 0));
i--; j--;
break;
case EditOperation::SUBSTITUTE:
editPath.push_back(EditOperation(
EditOperation::SUBSTITUTE,
str1[i-1], str2[j-1], substituteCost));
i--; j--;
break;
case EditOperation::INSERT:
editPath.push_back(EditOperation(
EditOperation::INSERT,
'\0', str2[j-1], insertCost));
j--;
break;
case EditOperation::DELETE:
editPath.push_back(EditOperation(
EditOperation::DELETE,
str1[i-1], '\0', deleteCost));
i--;
break;
}
}
reverse(editPath.begin(), editPath.end());
return dp[m][n];
}
// Get normalized distance (0 to 1)
double getNormalizedDistance(const string& str1,
const string& str2) {
int distance = calculateDistance(str1, str2);
return static_cast<double>(distance) /
max(str1.length(), str2.length());
}
// Get edit path as string
string getEditPathDescription() {
string description;
for (const auto& op : editPath) {
switch (op.type) {
case EditOperation::MATCH:
description += "Match '" + string(1, op.from) +
"'\n";
break;
case EditOperation::SUBSTITUTE:
description += "Substitute '" + string(1, op.from) +
"' with '" + string(1, op.to) +
"' (cost " + to_string(op.cost) +
")\n";
break;
case EditOperation::INSERT:
description += "Insert '" + string(1, op.to) +
"' (cost " + to_string(op.cost) +
")\n";
break;
case EditOperation::DELETE:
description += "Delete '" + string(1, op.from) +
"' (cost " + to_string(op.cost) +
")\n";
break;
}
}
return description;
}
};
// Demonstration class
class LevenshteinDemo {
public:
static void demonstrateAlgorithm() {
LevenshteinDistance algo;
string str1 = "kitten";
string str2 = "sitting";
cout << "String 1: " << str1 << endl;
cout << "String 2: " << str2 << endl;
// Basic distance calculation
int distance = algo.calculateDistance(str1, str2);
cout << "\nLevenshtein distance: " << distance << endl;
// Normalized distance
double normalized = algo.getNormalizedDistance(str1, str2);
cout << "Normalized distance: " << normalized << endl;
// Detailed edit path
distance = algo.calculateDistanceWithPath(str1, str2);
cout << "\nEdit operations:\n" <<
algo.getEditPathDescription() << endl;
// Custom costs demonstration
cout << "\nWith custom costs (Insert:2, Delete:2, Substitute:1):"
<< endl;
algo.setCosts(2, 2, 1);
distance = algo.calculateDistance(str1, str2);
cout << "Modified distance: " << distance << endl;
}
};
int main() {
LevenshteinDemo::demonstrateAlgorithm();
return 0;
}
Key Features:​
-
Dynamic Programming Implementation:
- Optimal subproblem solution
- Memoization of results
- Path reconstruction
-
Flexible Operations:
- Customizable operation costs
- Multiple distance metrics
- Edit path tracking
-
Optimization Options:
- Space-efficient versions
- Early termination
- Path reconstruction
Applications:​
-
Text Processing:
- Spell checking
- Auto-correction
- Fuzzy search
-
Bioinformatics:
- DNA sequence alignment
- Protein comparison
- Mutation analysis
-
Natural Language Processing:
- Text similarity
- Language correction
- Speech recognition
-
Information Retrieval:
- Search engines
- Pattern matching
- Document comparison
Advanced Features:​
-
Algorithm Variants:
- Damerau-Levenshtein distance
- Weighted operations
- Limited-window versions
-
Implementation Optimizations:
- Memory-efficient versions
- Parallel processing
- Block matrix computation
Comparison with Other Algorithms:​
-
Advantages:
- Intuitive distance metric
- Flexible operation costs
- Path reconstruction
-
Trade-offs:
- Computational complexity
- Memory requirements
- Implementation complexity
Performance Characteristics:​
-
Best Case:
- O(min(m,n)) for identical strings
- Early termination possible
- Optimal substructure
-
Average Case:
- O(mn) operations
- Predictable performance
- Consistent behavior
-
Worst Case:
- O(mn) operations required
- Full matrix computation
- Maximum path length
Summary:​
The Levenshtein Distance Algorithm provides a robust and flexible approach to measuring string similarity and calculating edit distances. Its dynamic programming implementation ensures optimal solutions while supporting various customizations and optimizations.
The algorithm's strength lies in its ability to handle different types of string transformations with customizable costs, making it adaptable to various applications. The implementation supports both basic distance calculation and detailed edit path reconstruction, providing comprehensive information about the transformation process.
The practical applications span multiple domains, from text processing and spell checking to bioinformatics and natural language processing. Its ability to quantify string similarity makes it a fundamental tool in many modern applications requiring fuzzy string matching or error tolerance.
The algorithm's versatility in handling different requirements through customizable operation costs and various implementation options makes it adaptable to different use cases while maintaining its fundamental efficiency in measuring string similarity and edit distances.