51 lines
2.1 KiB
Text
51 lines
2.1 KiB
Text
local fn LevenshteinDistance( s1 as CFStringRef, s2 as CFStringRef ) as NSInteger
|
|
NSInteger result
|
|
|
|
// If strings are equal, Levenshtein distance is 0
|
|
if ( fn StringIsEqual( s1, s2 ) ) then result = 0 : exit fn
|
|
|
|
// If either string is empty, then distance is the length of the other string.
|
|
if ( len(s1) == 0) then result = len(s2) : exit fn
|
|
if ( len(s2) == 0) then result = len(s1) : exit fn
|
|
|
|
// The remaining recursive process uses first characters and remainder of each string.
|
|
CFStringRef s1First = fn StringSubstringToIndex( s1, 1 )
|
|
CFStringRef s2First = fn StringSubstringToIndex( s2, 1 )
|
|
CFStringRef s1Rest = mid( s1, 1, len(s1) -1 )
|
|
CFStringRef s2Rest = mid( s2, 1, len(s2) -1 )
|
|
|
|
// If leading characters are the same, then distance is that between the rest of the strings.
|
|
if fn StringIsEqual( s1First, s2First ) then result = fn LevenshteinDistance( s1Rest, s2Rest ) : exit fn
|
|
|
|
// Find the distances between sub strings.
|
|
NSInteger distA = fn LevenshteinDistance( s1Rest, s2 )
|
|
NSInteger distB = fn LevenshteinDistance( s1, s2Rest )
|
|
NSInteger distC = fn LevenshteinDistance( s1Rest, s2Rest )
|
|
|
|
// Return the minimum distance between substrings.
|
|
NSInteger minDist = distA
|
|
if ( distB < minDist ) then minDist = distB
|
|
if ( distC < minDist ) then minDist = distC
|
|
result = minDist + 1 // Include change for the first character.
|
|
end fn = result
|
|
|
|
|
|
NSInteger i
|
|
CFStringRef testStr( 6, 2 )
|
|
|
|
testStr( 0, 0 ) = @"kitten" : testStr( 0, 1 ) = @"sitting"
|
|
testStr( 1, 0 ) = @"rosettacode" : testStr( 1, 1 ) = @"raisethysword"
|
|
testStr( 2, 0 ) = @"Saturday" : testStr( 2, 1 ) = @"Sunday"
|
|
testStr( 3, 0 ) = @"FutureBasic" : testStr( 3, 1 ) = @"FutureBasic"
|
|
testStr( 4, 0 ) = @"rave" : testStr( 4, 1 ) = @"ravel"
|
|
testStr( 5, 0 ) = @"black" : testStr( 5, 1 ) = @"slack"
|
|
testStr( 6, 0 ) = @"rave" : testStr( 6, 1 ) = @"grave"
|
|
|
|
for i = 0 to 6
|
|
print @"1st string = "; testStr( i, 0 )
|
|
print @"2nd string = "; testStr( i, 1 )
|
|
print @"Levenshtein distance = "; fn LevenshteinDistance( testStr( i, 0 ), testStr( i, 1 ) )
|
|
print
|
|
next
|
|
|
|
HandleEvents
|