Vim - Levenshtein Distance

string.vim

function! lib#string#levenshtein_distance(str1, str2)
  let str1_chars = split(a:str1, '\zs') | let str1_len = len(str1_chars)
  let str2_chars = split(a:str2, '\zs') | let str2_len = len(str2_chars)

  let matrix = []
  let y = 0
  while y <= str2_len
    let row = range(0, str1_len)
    let row[0] = y
    call add(matrix, row)
    let y += 1
  endwhile

  let y = 1
  while y <= str2_len
    let x = 1
    while x <= str1_len
      let cost = !(str1_chars[x - 1] ==# str2_chars[y - 1])
      let matrix[y][x] = min([
            \ matrix[y][x - 1] + 1,
            \ matrix[y - 1][x] + 1,
            \ matrix[y - 1][x - 1] + cost,
            \ ])
      let x += 1
    endwhile
    let y += 1
  endwhile

  return matrix[str2_len][str1_len]
endfunction