concept · INFO-CS-ADS-179Edit Distance Problem
Understand how dynamic programming calculates the minimum number of insertions, deletions, and substitutions needed to transform one string into another.
Explanation
Overview
Edit Distance, commonly called Levenshtein Distance, measures the minimum number of single-character operations required to transform one string into another. The standard version allows insertion, deletion, and substitution, each with a cost of one.
Key concepts
Insertion; Deletion; Substitution; String prefix states; Minimum-cost optimization
Variables
X: The original string.; Y: The target string.; i: The number of characters considered from X.; j: The number of characters considered from Y.; dp[i][j]: The minimum edit cost for transforming the first i characters of X into the first j characters of Y.
Complexity
tabulation: O(mn) time and O(mn) space.; spaceOptimized: O(mn) time and O(min(m,n)) space.; variables: m and n are the lengths of the source and target strings.
Example
source: kitten; target: sitting; operations: Replace k with s.; Replace e with i.; editDistance: 3; explanation: Three operations are sufficient to transform kitten into sitting, and no solution can use fewer operations under the standard cost model.
Pseudocode
function editDistance(X, Y):
m = length(X)
n = length(Y)
dp = 2D array of size (m + 1) × (n + 1)
for i = 0 to m:
dp[i][0] = i
for j = 0 to n:
dp[0][j] = j
for i = 1 to m:
for j = 1 to n:
if X[i - 1] == Y[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
return dp[m][n]
Applications
Spell checking.; Autocomplete and text correction.; DNA sequence comparison.; Plagiarism and similarity analysis.; Natural language processing.
Variables
I
The number of characters considered from X.
J
The number of characters considered from Y.
Dp[i][j]
The minimum edit cost for transforming the first i characters of X into the first j characters of Y.
Example or application
Operations
Replace k with s.
Replace e with i.
Insert g at the end.
Explanation
Three operations are sufficient to transform kitten into sitting, and no solution can use fewer operations under the standard cost model.
Definition
Edit Distance, commonly called Levenshtein Distance, measures the minimum number of single-character operations required to transform one string into another. The standard version allows insertion, deletion, and substitution, each with a cost of one.
Mathematical Representation
If X[i-1] = Y[j-1], dp[i][j] = dp[i-1][j-1]; otherwise dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).
Approaches
Recursive
Considers insertion, deletion, and substitution possibilities for the final characters.
Memoization
Stores the minimum edit cost for each pair of string prefixes.
Tabulation
Builds a two-dimensional table using smaller prefix transformations.
Space Optimized
Stores only the previous and current rows when only the distance is required.
Pseudocode
function editDistance(X, Y):
m = length(X)
n = length(Y)
dp = 2D array of size (m + 1) × (n + 1)
for i = 0 to m:
dp[i][0] = i
for j = 0 to n:
dp[0][j] = j
for i = 1 to m:
for j = 1 to n:
if X[i - 1] == Y[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
return dp[m][n]
Complexity
Tabulation
O(mn) time and O(mn) space.
Space Optimized
O(mn) time and O(min(m,n)) space.
Variables
m and n are the lengths of the source and target strings.
Advantages
Provides a quantitative measure of string similarity.
Finds the minimum number of standard edit operations.
Can reconstruct an optimal sequence of edits.
Can be extended to weighted edit costs.
Limitations
The standard algorithm requires O(mn) time.
Large strings can require substantial memory.
The result depends on the allowed operations and their assigned costs.
A small edit distance does not always imply that two texts have the same meaning.
Applications
Spell checking.
Autocomplete and text correction.
DNA sequence comparison.
Plagiarism and similarity analysis.
Natural language processing.
Practice Question
What is the standard Levenshtein edit distance between CAT and CUT?
Practice Answer
1, because only A needs to be substituted with U.
Learning Objectives
Explain the central idea and purpose of edit distance problem.
Identify the assumptions, inputs, and conditions relevant to edit distance problem.
Evaluate an application of edit distance problem for correctness and practical resource requirements.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Dynamic Programming Applications
Suggest a correction or source · More in Algorithms & Data Structures