Levenshtein distance/Alignment: Difference between revisions
→{{header|jq}}
(Add C# implementation) |
|||
| (4 intermediate revisions by 2 users not shown) | |||
Line 358:
<pre>r_oset_tacode
raisethysword</pre>
=={{header|EasyLang}}==
{{trans|FreeBASIC}}
<syntaxhighlight>
global dparr[] dpcols .
proc dpnew a b . .
len dparr[] a * b
dpcols = b
.
func dp r c .
return dparr[r * dpcols + c + 1]
.
proc dps r c v . .
dparr[r * dpcols + c + 1] = v
.
proc align a$ b$ . ar$ br$ .
dpnew (len a$ + 1) (len b$ + 1)
for i = 1 to len a$
dps i 0 i
.
for j = 0 to len b$
dps 0 j j
.
for i = 1 to len a$
for j = 1 to len b$
if substr a$ i 1 = substr b$ j 1
dps i j dp (i - 1) (j - 1)
else
dps i j lower (lower dp (i - 1) j dp i (j - 1)) dp (i - 1) (j - 1) + 1
.
.
.
ar$ = "" ; br$ = ""
i = len a$ ; j = len b$
while i <> 0 and j <> 0
if substr a$ i 1 = substr b$ j 1 or dp i j = dp (i - 1) (j - 1) + 1
ar$ = substr a$ i 1 & ar$
i -= 1
br$ = substr b$ j 1 & br$
j -= 1
elif dp i j = dp (i - 1) j + 1
ar$ = substr a$ i 1 & ar$
i -= 1
br$ = "-" & br$
else
ar$ = "-" & ar$
br$ = substr b$ j 1 & br$
j -= 1
.
.
.
align "rosettacode" "raisethysword" ar$ br$
print ar$ ; print br$
</syntaxhighlight>
{{out}}
<pre>
r-oset-tacode
raisethysword
</pre>
=={{header|Eiffel}}==
Line 391 ⟶ 450:
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}}==
Line 644 ⟶ 782:
r-oset-tacode
raisethysword
</pre>
=={{header|jq}}==
'''Adapted from [[#Wren|Wren]]'''
'''Works with jq, the C implementation of jq'''
'''Works with gojq, the Go implementation of jq'''
'''Works with jaq, the Rust implementation of jq'''
<syntaxhighlight lang="jq">
def reverseString: explode | reverse | implode;
def levenshteinAlign($x; $y):
def min($a;$b): [$a,$b]|min;
($x|length + 1) as $a1
| ($y|length + 1) as $b1
| ($x | ascii_downcase) as $a
| ($y | ascii_downcase) as $b
| [range(0; $b1) | 0] as $zeros
| {costs: [range(0; $a1) | $zeros]}
| reduce range(0; $b1) as $j (.; .costs[0][$j] = $j)
| reduce range(1; $a1) as $i (.;
.costs[$i][0] = $i
| reduce range(1; $b1) as $j (.;
(.costs[$i - 1][$j - 1] + (if $a[$i - 1: $i] == $b[$j - 1: $j] then 0 else 1 end)) as $temp
| .costs[$i][$j] = min( $temp; 1 + min(.costs[$i - 1][$j]; .costs[$i][$j - 1] )) ))
# walk back through matrix to figure out path
| .aPathRev = ""
| .bPathRev = ""
| .i = ($a|length)
| .j = ($b|length)
| until (.i == 0 or .j == 0;
(.costs[.i - 1][.j - 1] + (if $a[.i - 1: .i] == $b[.j - 1: .j] then 0 else 1 end)) as $temp
| .costs[.i][.j] as $cij
| if $cij == $temp
then .i += -1
| .aPathRev += $a[.i: .i+1]
| .j += -1
| .bPathRev += $b[.j: .j+1]
elif $cij == 1 + .costs[.i-1][.j]
then .i += -1
| .aPathRev += $a[.i:.i+1]
| .bPathRev += "-"
elif $cij == 1 + .costs[.i][.j-1]
then .aPathRev += "-"
| .j += -1
| .bPathRev += $b[.j: .j+1]
end)
| [.aPathRev, .bPathRev ] | map(reverseString);
levenshteinAlign("place"; "palace"),
levenshteinAlign("rosettacode";"raisethysword")
</syntaxhighlight>
{{output}}
<pre>
[
"p-lace",
"palace"
]
[
"r-oset-tacode",
"raisethysword"
]
</pre>
| |||