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

顺便说一句:我知道这个代码在很多层面都是错误的,我很高兴接受任何建设性的批评.只是想改进,并找出这个公式!

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]等于最小值:a.紧接在上面的单元加上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]

它似乎坚持光测试,但让我知道是否有任何问题.