Levenshtein distance function problem

[chemistRE]

Hello, I translated Levenshtein distance function from c# to autoit, but for some reason from time to time it does not worck as expected. Could anyone please give me a hint what is wrong with this code.

expandcollapse popup

#include <Math.au3>

Func _LevDis($s, $t)
Local $m, $n, $iMaxM, $iMaxN

$n = StringLen($s)
$m = StringLen($t)
$ss = StringSplit($s, "")
$tt = StringSplit($t, "")
$iMaxN = Number(Execute($n + 1))
$iMaxM = Number(Execute($m + 1))
Dim $d[$iMaxN][$iMaxM]

If $n = 0 Then
Return $m
ElseIf $m = 0 Then
Return $n
EndIf

For $i = 0 To $n
$d[$i][0] = $i
Next
For $j = 0 To $m
$d[0][$j] = $j
Next

For $i = 1 To $n
For $j = 1 To $m
$jj = Execute($j - 1)
$ii = Execute($i - 1)
$cost = Null
If $tt[$jj] = $ss[$ii] Then
$cost = 0
Else
$cost = 1
EndIf
$d[$i][$j] = _Min(_Min(Execute($d[$ii][$j] + 1), _
Execute($d[$i][$jj] + 1)), Execute($d[$ii][$jj] + $cost))
Next
Next
Return $d[$n][$m]
EndFunc

ConsoleWrite("Answer is:")
ConsoleWrite(_LevDis("max", "maxim"))
ConsoleWrite(" Done.")

Edited October 8, 2012 by chemistRE

[guinness]

There are plenty of examples about this in the Forum e.g.

Next time please search the Forum. Thanks.

[chemistRE]

Thank you for the reply.

I searched the forum, i just wanted to understand what is wrong with exactly this function.

[guinness]

I would firstly refrain from using Execute if it isn't required and then secondly compare the code to Malkey's (see the link.)

Also Null isn't an actual keyword in AutoIt V3.3.8.1.

[chemistRE]

I compared the functions and found my mistake, the function works great now.

Thank you.

This is the working function:

expandcollapse popup

#include <Math.au3>

Func _LevDis($s, $t)
Local $m, $n, $iMaxM, $iMaxN

$n = StringLen($s)
$m = StringLen($t)
$ss = StringSplit($s, "")
$tt = StringSplit($t, "")
$iMaxN = $n + 1
$iMaxM = $m + 1
Dim $d[$iMaxN + 1][$iMaxM + 1]
$d[0][0] = 0

If $n = 0 Then
Return $m
ElseIf $m = 0 Then
Return $n
EndIf

For $i = 1 To $n
$d[$i][0] = $d[$i - 1][0] + 1
Next
For $j = 1 To $m
$d[0][$j] = $d[0][$j - 1] + 1
Next

For $i = 1 To $n
For $j = 1 To $m
$jj = $j - 1
$ii = $i - 1
Local $cost
If (StringMid($s, $i, 1) = StringMid($t, $j, 1)) Then
$cost = 0
Else
$cost = 1
EndIf
$d[$i][$j] = _Min(_Min($d[$ii][$j] + 1, _
$d[$i][$jj] + 1), $d[$ii][$jj] + $cost)
Next
Next
Return $d[$n][$m]
EndFunc

ConsoleWrite("Answer is:")
ConsoleWrite(_LevDis("max", "maxim"))
ConsoleWrite(" Done.")

[guinness]

Great. Nice function by the way.