Levenshtein distance/Alignment: Difference between revisions
m
→{{header|EasyLang}}
m (→{{header|Sidef}}: update) |
|||
| (7 intermediate revisions by 5 users not shown) | |||
Line 178:
raisethysword -> rosettacode: 8 edits
r(a,o)(i,)set(h,t)(y,a)(s,c)(w,)o(r,d)(d,e)
</pre>
=={{header|C#}}==
{{trans|Java}}
<syntaxhighlight lang="C#">
using System;
using System.Text;
public class LevenshteinAlignment
{
public static string[] Alignment(string a, string b)
{
a = a.ToLower();
b = b.ToLower();
int[,] costs = new int[a.Length + 1, b.Length + 1];
for (int j = 0; j <= b.Length; j++)
costs[0, j] = j;
for (int i = 1; i <= a.Length; i++)
{
costs[i, 0] = i;
for (int j = 1; j <= b.Length; j++)
{
costs[i, j] = Math.Min(1 + Math.Min(costs[i - 1, j], costs[i, j - 1]),
a[i - 1] == b[j - 1] ? costs[i - 1, j - 1] : costs[i - 1, j - 1] + 1);
}
}
StringBuilder aPathRev = new StringBuilder();
StringBuilder bPathRev = new StringBuilder();
for (int i = a.Length, j = b.Length; i != 0 && j != 0;)
{
if (costs[i, j] == (a[i - 1] == b[j - 1] ? costs[i - 1, j - 1] : costs[i - 1, j - 1] + 1))
{
aPathRev.Append(a[--i]);
bPathRev.Append(b[--j]);
}
else if (costs[i, j] == 1 + costs[i - 1, j])
{
aPathRev.Append(a[--i]);
bPathRev.Append('-');
}
else if (costs[i, j] == 1 + costs[i, j - 1])
{
aPathRev.Append('-');
bPathRev.Append(b[--j]);
}
}
return new string[] { Reverse(aPathRev.ToString()), Reverse(bPathRev.ToString()) };
}
private static string Reverse(string s)
{
char[] charArray = s.ToCharArray();
Array.Reverse(charArray);
return new string(charArray);
}
public static void Main(string[] args)
{
string[] result = Alignment("rosettacode", "raisethysword");
Console.WriteLine(result[0]);
Console.WriteLine(result[1]);
}
}
</syntaxhighlight>
{{out}}
<pre>
r-oset-tacode
raisethysword
</pre>
=={{header|C++}}==
<syntaxhighlight lang="c++">
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
std::string to_lower_case(const std::string& text) {
std::string result = text;
std::transform(result.begin(), result.end(), result.begin(),
[](char ch){ return std::tolower(ch); });
return result;
}
std::vector<std::string> levenshtein_alignment(std::string a, std::string b) {
a = to_lower_case(a);
b = to_lower_case(b);
std::vector<std::vector<int32_t>> costs{ a.length() + 1, std::vector<int32_t>( b.length() + 1, 0 ) };
for ( uint64_t j = 0; j <= b.length(); ++j )
costs[0][j] = j;
for ( uint64_t i = 1; i <= a.length(); ++i ) {
costs[i][0] = i;
for ( uint64_t j = 1; j <= b.length(); ++j ) {
costs[i][j] = std::min(std::min( costs[i - 1][j], costs[i][j - 1]) + 1,
a[i - 1] == b[j - 1] ? costs[i - 1][j - 1] : costs[i - 1][j - 1] + 1);
}
}
std::string a_path_reversed, b_path_reversed;
uint64_t i = a.length(), j = b.length();
while ( i != 0 && j != 0 ) {
if ( costs[i][j] == ( a[i - 1] == b[j - 1] ? costs[i - 1][j - 1] : costs[i - 1][j - 1] + 1 ) ) {
a_path_reversed += a[--i];
b_path_reversed += b[--j];
} else if ( costs[i][j] == costs[i - 1][j] + 1 ) {
a_path_reversed += a[--i];
b_path_reversed += "-";
} else if ( costs[i][j] == costs[i][j - 1] + 1 ) {
a_path_reversed += "-";
b_path_reversed += b[--j];
}
}
std::reverse(a_path_reversed.begin(), a_path_reversed.end());
std::reverse(b_path_reversed.begin(), b_path_reversed.end());
return std::vector<std::string>{ a_path_reversed, b_path_reversed };
}
int main() {
std::vector<std::string> result = levenshtein_alignment("place", "palace");
std::cout << result[0] << std::endl;
std::cout << result[1] << std::endl;
std::cout << std::endl;
result = levenshtein_alignment("rosettacode", "raisethysword");
std::cout << result[0] << std::endl;
std::cout << result[1] << std::endl;
}
</syntaxhighlight>
{{ out }}
<pre>
p-lace
palace
r-oset-tacode
raisethysword
</pre>
Line 213 ⟶ 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 246 ⟶ 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 1,123 ⟶ 1,406:
{{trans|Kotlin}}
{{libheader|Wren-str}}
<syntaxhighlight lang="
var levenshteinAlign = Fn.new { |a, b|
| |||