Рет қаралды 70,357
What is the edit distance of two strings? It is the minimum cost of operations to convert the first string to the second string. The operations allowed are addition, deletion and transition. We find the sequence of edits required to change the first to the second to in the cheapest way possible.
This algorithm using dynamic programming is used in many real world applications. The edit distance of two strings helps auto correct and word suggestion algorithms. These applications run when we type texts and messages on phones or computers.
The edit distance is also called the levenshtein distance between two strings. It has applications in auto correction, genetic material study and many other string processing applications. The most common use is that of auto correct in text editors, which use a variation of the edit distance algorithm to find closest matching words from a dictionary.
This is a dynamic programming solution which converts a recursive approach to a matrix. This matrix allows us to store values which are accessed repeatedly, and hence converts the simple recursion to dynamic programming. Each cell in the dp matrix depends on adjacent cells and the original strings for it's value.
I am looking forward to talking about approximate string matching in the next videos. Cheers!
References:
web.stanford.e...
www.geeksforge...
en.wikipedia.o...
people.cs.pitt...
Code:
github.com/gkc...