Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Levenshtein distance in vim
function! Levenshtein(first, second)
let f = []
let mn = 0
let fj = 0
let ca = 0
let fj1 = 0
for i in range(len(a:second) + 1)
let f = add(f, i)
endfor
for i in range(len(a:first))
let ca = strpart(a:first, i, 1)
let j = 1
let fj1 = f[0]
let f[0] = f[0] + 1
for x in range(len(a:second))
let cb = strpart(a:second, x, 1)
let mn = min([f[j] + 1, f[j - 1] + 1])
if cb != ca
let mn = min([mn, fj1 + 1])
else
let mn = min([mn, fj1])
endif
let fj1 = f[j]
let f[j] = mn
let j += 1
endfor
endfor
return f[len(f)-1]
endfunction
function! TestLevenshtein(first, second, expectedResult)
let result = Levenshtein(a:first, a:second)
if result != a:expectedResult
echo 'Expected "' . a:expectedResult . '" for words "' . a:first . '" and "' . a:second . '", but got "' . result . '"'
endif
endfunction
call TestLevenshtein('', '', 0)
call TestLevenshtein('yo', '', 2)
call TestLevenshtein('', 'yo', 2)
call TestLevenshtein('yo', 'yo', 0)
call TestLevenshtein('tier', 'tor', 2)
call TestLevenshtein('saturday', 'sunday', 3)
call TestLevenshtein('mist', 'dist', 1)
call TestLevenshtein('tier', 'tor', 2)
call TestLevenshtein('kitten', 'sitting', 3)
call TestLevenshtein('stop', 'tops', 2)
call TestLevenshtein('rosettacode', 'raisethysword', 8)
call TestLevenshtein('mississippi', 'swiss miss', 8)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.