Damerau–Levenshtein distance implementation

levDist.coffee

# Damerau–Levenshtein distance (Wikipedia) implementation
# Found in http://stackoverflow.com/questions/11919065/sort-an-array-by-the-levenshtein-distance-with-best-performance-in-javascript
# Answer by user http://stackoverflow.com/users/305319/james-westgate

levDist = (s, t) ->
  d = [] #2d matrix
  
  # Step 1
  n = s.length
  m = t.length
  return m  if n is 0
  return n  if m is 0
  
  #Create an array of arrays in javascript (a descending loop is quicker)
  i = n

  while i >= 0
    d[i] = []
    i--
  
  # Step 2
  i = n

  while i >= 0
    d[i][0] = i
    i--
  j = m

  while j >= 0
    d[0][j] = j
    j--
  
  # Step 3
  i = 1

  while i <= n
    s_i = s.charAt(i - 1)
    
    # Step 4
    j = 1

    while j <= m
      
      #Check the jagged ld total so far
      return n  if i is j and d[i][j] > 4
      t_j = t.charAt(j - 1)
      cost = (if (s_i is t_j) then 0 else 1) # Step 5
      
      #Calculate the minimum
      mi = d[i - 1][j] + 1
      b = d[i][j - 1] + 1
      c = d[i - 1][j - 1] + cost
      mi = b  if b < mi
      mi = c  if c < mi
      d[i][j] = mi # Step 6
      
      #Damerau transposition
      d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost)  if i > 1 and j > 1 and s_i is t.charAt(j - 2) and s.charAt(i - 2) is t_j
      j++
    i++
  
  # Step 7
  d[n][m]