Levenshtein distance: Difference between revisions

=={{header|MiniScript}}==

In the Mini Micro environment, this function is part of the stringUtil library module, and can be used like so:

<lang MiniScript>import "stringUtil"

print "kitten".editDistance("sitting")</lang>

In environments where the stringUtil module is not available, you'd have to define it yourself:

<lang MiniScript>string.editDistance = function(s2)

n = self.len

m = s2.len

if n == 0 then return m

if m == 0 then return n

s1chars = self.split("")

s2chars = s2.split("")

d = range(0, m)

lastCost = 0

for i in range(1, n)

s1char = s1chars[i-1]

lastCost = i

jMinus1 = 0

for j in range(1, m)

if s1char == s2chars[jMinus1] then cost = 0 else cost = 1

// set nextCost to the minimum of the following three possibilities:

a = d[j] + 1

b = lastCost + 1

c = cost + d[jMinus1]

if a < b then

if c < a then nextCost = c else nextCost = a

else

if c < b then nextCost = c else nextCost = b

end if

d[jMinus1] = lastCost

lastCost = nextCost

jMinus1 = j

end for

d[m] = lastCost

end for

return nextCost

end function

print "kitten".editDistance("sitting")</lang>

'''Output:'''

<pre>3</pre>