Suggest edit — weighted edit distance

Title

Name

Note

---
title: "weighted edit distance"
type: concept
related: [Edit Distance With Dp]
source: https://www.jemoka.com/posts/kbhweighted_edit_distance/
confidence: high
status: active
---

For instance, in spellcheck, you are more likely to confuse say \(a\) and \(e\) than \(a\) and \(b\). Therefore, sometimes we want to weight our edit distance with DP to account for these &ldquo;common&rdquo; paths to make certain corrections more &ldquo;jarring&rdquo;.
For two strings, let&rsquo;s define:
\(X\) of length \(n\) \(Y\) of length \(m\) we define some \(D(i,j)\) as the edit distance between substring \(X[1:i]\) and \(Y[1:j]\).
Let:
\(D(i,0) = i, \forall i\) \(D(0,j) = j, \forall j\) for i in range(1,M): for j in range(1,N): # deletion: ignoring one char of previous string d1 = D(i-1,j) + 1 # (cost) # insertion: insertion into string before using rest of j d2 = D(i,j-1) + 1 # (cost) # keep same if char is same or substitute current d3 = D(i-1,j-1) + (0 if X[i] == Y[j] else 2) # cache D(i,j) = min(d1, d2, d3)