Code: Select all

`'Levenshtein Distance Algorithm for FreeBASIC`

'Based on the C implementation of Lorenzo Seidenari here: http://www.merriampark.com/ldc.htm

'This code is assumed to be available under the Public Domain.

declare function levenshtein_distance( s as string, t as string ) as integer

declare function lev_minimum( a as integer, b as integer, c as integer ) as integer

'Just a simple test of the algorithm

? levenshtein_distance( command(1), command(2) )

function levenshtein_distance( s as string, t as string ) as integer

dim as integer k, i, j, n, m, cost, distance

dim as integer ptr d

n = len(s)

m = len(t)

if (n <> 0) AND (m <> 0) then

d = allocate( sizeof(integer) * (m+1) * (n+1) )

m += 1

n += 1

k = 0

while k < n

d[k]=k

k += 1

wend

k = 0

while k < m

d[k*n]=k

k += 1

wend

i = 1

while i < n

j = 1

while j<m

if (s[i-1] = t[j-1]) then

cost = 0

else

cost = 1

end if

d[j*n+i] = lev_minimum(d[(j-1)*n+i]+1, d[j*n+i-1]+1, d[(j-1)*n+i-1]+cost)

j += 1

wend

i += 1

wend

distance = d[n*m-1]

deallocate d

return distance

else

return -1

end if

end function

function lev_minimum( a as integer, b as integer, c as integer ) as integer

var min = a

if (b<min) then min = b

if (c<min) then min = c

return min

end function