Please can someone explain how Levenshtein edit distance works?

I've stepped through the algorithm in code and in excel, but I don't understand how this actually succeeds in finding an edit distance.

Specifically, I don't understand how these algorithms are able to find the number of substitutions, deletions, and insertions. How does the matrix method correspond to this?

I really want to be able to grasp this process intuitively but haven't found any resources that teach it in a way I understand.

  • $\begingroup$ Try to understand the recursive algorithm, or a dynamic programming version of the algorithm. Excel is not really warranted for doing algorithms. $\endgroup$
    – Pål GD
    Nov 23, 2017 at 15:51
  • $\begingroup$ @PålGD I'm really looking for a way to intuitively grasp what the edit distance is and how it's given by this alg $\endgroup$ Nov 23, 2017 at 16:15
  • 1
    $\begingroup$ "I ... haven't found any resources that teach it in a way I understand." I worry that, unless you're more specific about what you don't understand, your response to any answer is also likely to be "That also isn't a resource that teaches it in a way I understand." $\endgroup$ Nov 23, 2017 at 17:20
  • $\begingroup$ @DavidRicherby I'm just hoping someone who does intuitively grasp it and has good ways of visualising it can explain how they think of it $\endgroup$ Nov 23, 2017 at 17:22


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.