coffeescript - CoffeeScript 中的 Levenshtein 距离公式？

Question

我正在尝试创建或找到 Levenshtein 距离公式的 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

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

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

更新:我要问的问题是 - 我们如何在 CoffeeScript 中做 Levenshtein？

以下是 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。
湾紧靠左边的单元格加 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

This page (链接到您提到的资源)提供了 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]

它似乎经得起轻度测试，但如果有任何问题，请告诉我。