Optimizing the Levenshtein Distance for Measuring Text Similarity - KDnuggets

The Levenshtein distance is a text similarity metric that measures the distance between 2 words. It has a number of applications, including text autocompletion and autocorrection. For either of these use cases, the word entered by a user is compared to words in a dictionary to find the closest match, at which point a suggestion(s) is made. The dictionary may contain thousands of words, and thus the response of the application for comparing 2 words will likely take a few milliseconds. The Levenshtein distance is usually calculated by preparing a matrix of size (M 1)x(N 1)--where M and N are the lengths of the 2 words--and looping through said matrix using 2 for loops, performing some calculations within each iteration.