Levenshtein distance/Alignment: Difference between revisions
Content added Content deleted
(Add C# implementation) |
(Added FreeBASIC) |
||
Line 391: | Line 391: | ||
Also—the `ic' is this programmers shorthand for ITERATION_CURSOR. Therefore, in the nested loops, the `ic' is the iteration cursor following `i' and the `ij' is following `j' as indexes on the source, target, and l_distance. |
Also—the `ic' is this programmers shorthand for ITERATION_CURSOR. Therefore, in the nested loops, the `ic' is the iteration cursor following `i' and the `ij' is following `j' as indexes on the source, target, and l_distance. |
||
=={{header|FreeBASIC}}== |
|||
<syntaxhighlight lang="vbnet">#define min(a, b) iif((a) < (b), (a), (b)) |
|||
Sub LevenshteinAlignment(s1 As String, s2 As String) |
|||
Dim As String align1 = "", align2 = "" |
|||
Dim As Integer i, j, len1, len2 |
|||
len1 = Len(s1): |
|||
len2 = Len(s2) |
|||
Dim As Integer dp(len1+1, len2+1) |
|||
For i = 0 To len1 |
|||
dp(i, 0) = i |
|||
Next i |
|||
For j = 0 To len2 |
|||
dp(0, j) = j |
|||
Next j |
|||
For i = 1 To len1 |
|||
For j = 1 To len2 |
|||
If Mid(s1, i, 1) = Mid(s2, j, 1) Then |
|||
dp(i, j) = dp(i-1, j-1) |
|||
Else |
|||
dp(i, j) = min(min(dp(i-1, j), dp(i, j-1)), dp(i-1, j-1)) + 1 |
|||
End If |
|||
Next j |
|||
Next i |
|||
i = len1: j = len2 |
|||
While i > 0 And j > 0 |
|||
If Mid(s1, i, 1) = Mid(s2, j, 1) Then |
|||
align1 = Mid(s1, i, 1) + align1 |
|||
align2 = Mid(s2, j, 1) + align2 |
|||
i -= 1: j -= 1 |
|||
Elseif dp(i, j) = dp(i-1, j-1) + 1 Then |
|||
align1 = Mid(s1, i, 1) + align1 |
|||
align2 = Mid(s2, j, 1) + align2 |
|||
i -= 1: j -= 1 |
|||
Elseif dp(i, j) = dp(i-1, j) + 1 Then |
|||
align1 = Mid(s1, i, 1) + align1 |
|||
align2 = "-" + align2 |
|||
i -= 1 |
|||
Else |
|||
align1 = "-" + align1 |
|||
align2 = Mid(s2, j, 1) + align2 |
|||
j -= 1 |
|||
End If |
|||
Wend |
|||
While i > 0 |
|||
align1 = Mid(s1, i, 1) + align1 |
|||
align2 = "-" + align2 |
|||
i -= 1 |
|||
Wend |
|||
While j > 0 |
|||
align1 = "-" + align1 |
|||
align2 = Mid(s2, j, 1) + align2 |
|||
j -= 1 |
|||
Wend |
|||
Print "Levenshtein Distance: "; dp(len1, len2) |
|||
Print align1 |
|||
Print align2 |
|||
Print |
|||
End Sub |
|||
LevenshteinAlignment("rosettacode", "raisethysword") |
|||
LevenshteinAlignment("place", "palace") |
|||
Sleep</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Levenshtein Distance: 8 |
|||
r-oset-tacode |
|||
raisethysword |
|||
Levenshtein Distance: 1 |
|||
p-lace |
|||
palace</pre> |
|||
=={{header|Go}}== |
=={{header|Go}}== |