8

我正在尝试创建或查找 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

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

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。对角线上方和左侧的单元格加上成本：d[i-1,j-1] + 成本。

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

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

4

1 回答 1

5

此页面（链接到您提到的资源）提供了 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]

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

于 2011-07-10T00:47:16.527 回答