Rosetta Code

Levenshtein distance: Difference between revisions

Page Discussion

Levenshtein distance (view source)

Revision as of 21:05, 12 November 2022

896 bytes added ,  1 year ago
m
→‎{{header|FutureBasic}}
m (syntax highlighting fixup automation)
Line 2,155:
 
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">window 1▼
Based on Wikipedia algorithm. Suitable for Pascal strings.
local fn LevenshteinDistance( aStrs1 as Str255CFStringRef, bStrs2 as Str255CFStringRef ) as longNSInteger▼
▲<syntaxhighlight lang="futurebasic">window 1
NSInteger result
 
▲local fn LevenshteinDistance( aStr as Str255, bStr as Str255 ) as long
dim as long m, n, i, j, min, k, l
dim as long distance( 255, 255 )
// If strings are equal, Levenshtein distance is 0
m = len$(aStr)
if ( fn StringIsEqual( s1, s2 ) ) then result = 0 : exit fn
n = len$(bStr)
// If either string is empty, then distance is the length of the other string.
for i = 0 to m▼
if ( distancelen(s1) i,== 0 ) then result = ilen(s2) : exit fn
if ( len(s2) == 0) then result = len(s1) : exit fn
next
// The remaining recursive process uses first characters and remainder of each string.
for j = 0 to n
CFStringRef s1First = fn StringSubstringToIndex( s1, 1 )
distance( 0, j ) = j
CFStringRef s2First = fn StringSubstringToIndex( s2, 1 )
next
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.
for j = 1 to n
if fn StringIsEqual( s1First, s2First ) then result = fn LevenshteinDistance( s1Rest, s2Rest ) : exit fn
for i = 1 to m
if mid$( aStr, i, 1 ) == mid$( bStr, j, 1 )
// Find the distances between sub strings.
distance( i, j ) = distance( i-1, j-1 )
NSInteger distA = fn LevenshteinDistance( s1Rest, s2 )
else
NSInteger distB = fn min = distanceLevenshteinDistance( i-1s1, j ) +s2Rest 1)
NSInteger distC = fn LevenshteinDistance( s1Rest, s2Rest )
k = distance( i, j - 1 ) + 1
l = distance( i-1, j-1 ) + 1
// Return the minimum distance between substrings.
if k < min then min = k
NSInteger minDist = distA
if l < min then min = l
if ( distB < minDist ) distance(then i, j )minDist = mindistB
if ( distC < minDist ) then minDist = distC
end if
result = minDist + 1 // Include change for the first character.
next
end fn = result
next
end fn = distance( m, n )
 
dim as long i
dim as Str255 testStr( 5, 2 )
 
NSInteger i
testStr( 0, 0 ) = "kitten" : testStr( 0, 1 ) = "sitting"▼
testStr( 1, 0 ) = "rosettacode" :CFStringRef testStr( 16, 12 ) = "raisethysword"
testStr( 2, 0 ) = "Saturday" : testStr( 2, 1 ) = "Sunday"▼
testStr( 3, 0 ) = "FutureBasic" : testStr( 3, 1 ) = "FutureBasic"▼
testStr( 4, 0 ) = "here's a bunch of words"
testStr( 4, 1 ) = "to wring out this code"
 
▲testStr( 0, 0 ) = @"kitten" : testStr( 0, 1 ) = @"sitting"
for i = 0 to 4
testStr( 1, print0 "1st string) = @";rosettacode" : testStr( i1, 01 ) = @"raisethysword"
testStr( 2, print0 "2nd string) = @";Saturday" : testStr( i2, 1 ) = @"Sunday"
print "Levenshtein distance ="; fn LevenshteinDistance( testStr( i3, 0 ), = @"FutureBasic" : testStr( i3, 1 ) )= @"FutureBasic"
▲testStr( 34, 0 ) = @"FutureBasicrave" : testStr( 34, 1 ) = @"FutureBasicravel"
▲testStr( 25, 0 ) = @"Saturdayblack" : testStr( 25, 1 ) = @"Sundayslack"
testStr( 6, 0 ) = @"rave" : testStr( 6, 1 ) = @"grave"
 
▲ for i = 0 to m6
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
 
NSLog( @"%@", fn WindowPrintViewString( 1 ) )
HandleEvents</syntaxhighlight>▼
 
HandleEvents
Output:
▲HandleEvents</syntaxhighlight>
 
{{output}}
<pre>
1st string = kitten
Line 2,226 ⟶ 2,229:
Levenshtein distance = 0
 
1st string = here's a bunch of wordsrave
2nd string = to wring out this coderavel
Levenshtein distance = 181
 
1st string = black
2nd string = slack
Levenshtein distance = 1
 
1st string = rave
2nd string = grave
Levenshtein distance = 1
</pre>
 
KenS
723

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/333480"