Related to:Misspelling Type: Find neighbor states function Description: The Levenshtein distance(LD) is a metric for measuring the amount of difference between two sequences (i.e., the so called edit distance). The Levenshtein distance between two strings is given by the minimum number of operations needed to transform one string into the other, where an operation is an insertion, deletion, or substitution of a single character. The greater the Levenshtein distance, the more different the strings are.Levenshtein distance is named after the Russian scientist Vladimir Levenshtein, who devised the algorithm in 1965.

Examples: If s is "test" and t is "test", then LD(s,t) = 0, because no transformations are needed. The strings are already identical.If s is "test" and t is "tent", then LD(s,t) = 1, because one substitution (change "s" to "n") is sufficient to transform s into t.

Applications:Spell checking , Speech recognition, DNA analysis, Plagiarism detection

Pseudo code: int LD(String s, String t) {
m = s.length
n = t.length int[m][n]
d = empty int table for i from 0 to m
d[i, 0] := i for j from 0 to n d[0, j] := j
for j from 1 to n
for i from 1 to m
if s[i] = t[j] then d[i, j] := d[i-1, j-1] else d[i, j] := minimum(d[i-1, j] + 1,d[i, j-1] + 1,d[i-1, j-1] + 1)
return d[m, n]}

Python code for the Levenshtein distance can be found here

Related to:MisspellingType:Find neighbor states functionDescription:The Levenshtein distance(LD) is a metric for measuring the amount of difference between two sequences (i.e., the so called edit distance). The Levenshtein distance between two strings is given by the minimum number of operations needed to transform one string into the other, where an operation is an insertion, deletion, or substitution of a single character.The greater the Levenshtein distance, the more different the strings are.Levenshtein distance is named after the Russian scientist Vladimir Levenshtein, who devised the algorithm in 1965.

If s is "test" and t is "test", then LD(s,t) = 0, because no transformations are needed. The strings are already identical.If s is "test" and t is "tent", then LD(s,t) = 1, because one substitution (change "s" to "n") is sufficient to transform s into t.Examples:

Applications:Spell checking , Speech recognition, DNA analysis, Plagiarism detectionPseudo code:int LD(String s, String t) {

m = s.length

n = t.length int[m][n]

d = empty int table for i from 0 to m

d[i, 0] := i for j from 0 to n d[0, j] := j

for j from 1 to n

for i from 1 to m

if s[i] = t[j] then d[i, j] := d[i-1, j-1] else d[i, j] := minimum(d[i-1, j] + 1,d[i, j-1] + 1,d[i-1, j-1] + 1)

return d[m, n]}

Python codefor the Levenshtein distance can be found here