0
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\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$
    – theonlygusti
    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$
    – David Richerby
    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$
    – theonlygusti
    Nov 23, 2017 at 17:22

0

Reset to default

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.