http://www.merriampark.com/ldc.htm
The algorithm is explaned in detial here:
http://www.merriampark.com/ld.htm
(I find it rather ironic how similar those urls are)
Anyways can someone tell me if this is efficient or not? I'm still a little fuzzy on what you can do with references (arrays in this case).
Here it is:
levenshtein_distance( s, t ) { n := strlen(s) m := strlen(t) if( n != 0 and m != 0 ) { m++ n++ d0 = 0 ; Because A_index starts at 1, we emulate a for loop by hardcoding the first repetition Loop, %n% d%A_Index% := A_Index ; I would emulate the first repetition here, but it just sets d0 = 0 Loop, %m% { temp1 := A_Index * n d%temp1% := A_Index } B_Index := 0 Loop, %n% { B_Index++ Loop, %m% { temp1 := B_Index temp2 := A_Index StringMid, tempA, s, temp1, 1 StringMid, tempB, t, temp2, 1 ;MsgBox, Comparing %tempA% and %tempB% if( tempA == tempB ) cost := 0 else cost := 1 temp1 := A_Index * n + B_Index temp2 := (A_Index - 1) * n + B_Index temp3 := A_Index * n + B_Index - 1 temp4 := (A_Index - 1) * n + B_Index - 1 d%temp1% := minimum( d%temp2%+1 , d%temp3%+1 , d%temp4%+cost ) } ;Loop, m } ;Loop, n temp1 := n*m - 1 distance := d%temp1% return distance } ;if else return -1 } minimum( a, b, c ) { min := a if(b<min) min := b if(c<min) min := c return min } MsgBox,% levenshtein_distance( "Ben", "Hen" )
Thanks!!