CoffeeScript 中的编辑距离公式？

Question

我正在尝试创建或查找 Levenshtein Distance 公式（又名编辑距离）的 CoffeeScript 实现。这是我到目前为止所拥有的，任何帮助将不胜感激。

levenshtein = (s1,s2) ->
    n = s1.length
    m = s2.length
    if n < m
        return levenshtein(s2, s1) 
    if not s1 
        return s2.length
    previous_row = [s2.length + 1]
    for c1, i in s1
        current_row = [i + 1]
        for c2, j in s2
            insertions = previous_row[j + 1] + 1
            deletions = current_row[j] + 1
            substitutions = previous_row[j] # is this unnescessary?-> (c1 != c2)
            current_row.push(Math.min(insertions,deletions,substitutions))
        previous_row = current_row
    return previous_row[previous_row.length-1]
#End Levenshetein Function

顺便说一句：我知道这段代码在很多层面上都是错误的，我很高兴收到任何和所有建设性的批评。只是想改进，并找出这个公式！

CodeEdit1：修补了 Trevor 指出的错误，上面的当前代码包括这些更改

更新：我要问的问题是 - 我们如何在 CoffeeScript 中进行 Levenshtein？

以下是编辑距离算法的“步骤”，可帮助您了解我想要实现的目标。

步骤 1
将 n 设为 s 的长度。 将 m 设置为 t 的长度。 如果 n = 0，则返回 m 并退出。 如果 m = 0，则返回 n 并退出。 构造一个包含 0..m 行和 0..n 列的矩阵。

2
将第一行初始化为 0..n。 将第一列初始化为 0..m。

3 检查 s 的每个字符（i 从 1 到 n）。

4 检查 t（j 从 1 到 m）的每个字符。

5 如果 s[i] 等于 t[j]，则成本为 0。 如果 s[i] 不等于 t[j]，则成本为 1。

6 将矩阵的单元格 d[i,j] 设置为等于以下最小值： 一个。紧邻上方的单元格加 1：d[i-1,j] + 1。 b.紧邻左侧的单元格加 1：d[i,j-1] + 1。 c.左上方对角的单元格加上成本：d[i-1,j-1] + 成本。

7 迭代步骤 (3, 4, 5, 6) 完成后，在单元格 d[n,m] 中找到距离。

来源：http://www.merriampark.com/ld.htm

Answer 1

此页面（从您提到的资源链接到）提供了 Levenshtein 距离算法的 JavaScript 实现。基于此和您发布的代码，这是我的 CoffeeScript 版本：

LD = (s, t) ->
  n = s.length
  m = t.length
  return m if n is 0
  return n if m is 0

  d       = []
  d[i]    = [] for i in [0..n]
  d[i][0] = i  for i in [0..n]
  d[0][j] = j  for j in [0..m]

  for c1, i in s
    for c2, j in t
      cost = if c1 is c2 then 0 else 1
      d[i+1][j+1] = Math.min d[i][j+1]+1, d[i+1][j]+1, d[i][j] + cost

  d[n][m]

它似乎可以通过简单测试，但如果有任何问题，请告诉我。