[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / raw/concept/kbhweighted_edit_distance.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "weighted edit distance" source: https://www.jemoka.com/posts/kbhweighted_edit_distance/ --- 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 “common” paths to make certain corrections more “jarring”. For two strings, let’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)