Levenshtein distance is a string metric, the simplest weighting factor, that measures the differences between two strings and counts the number of changes needed to make. It is the simplest weighting factor because each of the three operations (insertion, deletion, substitution) has a cost of 1.

University of Michigan - Ann Arbor

In NLP, we need to find out how similar the two strings are to each other. Minimum edit distance finds out the dissimilarity of two strings and counts the minimum number of modifications to transform a string to another. Levenshtein distance is the method that is used to measure the minimum edit distance.

Minimum Edit Distance

An on-going but a helpful book resource about NLP
https://web.stanford.edu/~jurafsky/slp3/

Speech and Language Processing (3rd ed. draft) 

Levenshtein Distance

Dynamic programming is an algorithm technique that recursively solves subproblems of a problem and finds the optimal solution from the optimal solution of the subproblems. Some of the algorithms in NLP uses dynamic programming, such as the Viterbi algorithm, CKY algorithm for parsing, and the Minimum Edit Distance Algorithm. 

Learn Before

Related