Levenshtein distance in vim

levenshtein.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)