I am trying to create or find a CoffeeScript implementation of the Levenshtein Distance formula, aka Edit Distance. Here is what I have so far, any help at all would be much appreciated.
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
Btw: I know this code is wrong on many levels, I am happy to receive any and all constructive criticism. Just looking to improve, and figure out this formula!
CodeEdit1: Patched up the errors Trevor pointed out, current code above includes those changes
Update: The question I am asking is - how do we do Levenshtein in CoffeeScript?
Here is the 'steps' for the Levenshtein Distance Algorithm to help you see what I am trying to accomplish.
Steps
1
Set n to be the length of s.
Set m to be the length of t.
If n = 0, return m and exit.
If m = 0, return n and exit.
Construct a matrix containing 0..m rows and 0..n columns.
2
Initialize the first row to 0..n.
Initialize the first column to 0..m.
3 Examine each character of s (i from 1 to n).
4 Examine each character of t (j from 1 to m).
5 If s[i] equals t[j], the cost is 0. If s[i] doesn't equal t[j], the cost is 1.
6 Set cell d[i,j] of the matrix equal to the minimum of: a. The cell immediately above plus 1: d[i-1,j] + 1. b. The cell immediately to the left plus 1: d[i,j-1] + 1. c. The cell diagonally above and to the left plus the cost: d[i-1,j-1] + cost.
7 After the iteration steps (3, 4, 5, 6) are complete, the distance is found in cell d[n,m].
source:http://www.merriampark.com/ld.htm
This page (linked to from the resource you mentioned) offers a JavaScript implementation of the Levenshtein distance algorithm. Based on both that and the code you posted, here's my CoffeeScript version:
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]
It seems to hold up to light testing, but let me know if there are any problems.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With