[[
wikihub
]]
Search
⌘K
Explore
People
For Agents
Sign in
Explore
People
For Agents
Sign in
@jemoka / Jemoka Knowledge Base / wiki/concepts/minimum_edit_distance.md
Suggest edit
Cancel
Submit suggestion
Title
Name
Note
--- title: "minimum edit distance" type: concept related: [Edit Distance With Dp, Minimum Edit Distance] source: https://www.jemoka.com/posts/kbhminimum_edit_distance/ confidence: high status: active --- “minimum edit distance” is one approach to solving the problem of “how similar are these two strings”? minimum edit distance is defined by the smallest number of editing operations (insertion, deletion, substitution) needed to transform one string into another. There are two technical definitions. Both definitions are grounded upon “minimum number of operations it takes to transform a string into another, where” edit distance with DP DP costs \(O(nm)\), backtrace costs \(O(n+m)\). Standard Edit Distance insertion, deletion, and substitution cost 1 Levenshtein Distance insertion and deletion cost 1; substitution cost 2 Example For instance: “graffe”. Is… graf graft grail giraffe the closest? Common Use machine translation + speech recognition uses edit distance to evaluate output quality coreference and NER uses edit distance as a baseline check