Rosetta Code

Levenshtein distance/Alignment: Difference between revisions

Page Discussion

Levenshtein distance/Alignment (view source)

Revision as of 19:16, 29 March 2024

39,338 bytes added ,  1 month ago
m
→‎{{header|EasyLang}}
m (Mathematica code calculates distance, but does not give alignment)
 
(42 intermediate revisions by 19 users not shown)
Line 1:
{{draft task}}
 
The [[Levenshtein distance]] algorithm returns the number of atomic operations (insertion, deletion or edition) that must be performed on a string in order to obtain an other one, but it does not say anything about the actual operations used or their order.
Line 18:
You can either implement an algorithm, or use a dedicated library (thus showing us how it is named in your language).
<br><br>
 
=={{header|11l}}==
{{trans|Nim}}
 
<syntaxhighlight lang="11l">F levenshteinAlign(aa, bb)
V a = aa.lowercase()
V b = bb.lowercase()
V costs = [[0] * (b.len + 1)] * (a.len + 1)
L(j) 0 .. b.len
costs[0][j] = j
L(i) 1 .. a.len
costs[i][0] = i
L(j) 1 .. b.len
V tmp = costs[i - 1][j - 1] + Int(a[i - 1] != b[j - 1])
costs[i][j] = min(1 + min(costs[i - 1][j], costs[i][j - 1]), tmp)
 
V aPathRev = ‘’
V bPathRev = ‘’
V i = a.len
V j = b.len
L i != 0 & j != 0
V tmp = costs[i - 1][j - 1] + Int(a[i - 1] != b[j - 1])
I costs[i][j] == tmp
aPathRev ‘’= a[--i]
bPathRev ‘’= b[--j]
E I costs[i][j] == 1 + costs[i - 1][j]
aPathRev ‘’= a[--i]
bPathRev ‘’= ‘-’
E I costs[i][j] == 1 + costs[i][j - 1]
aPathRev ‘’= ‘-’
bPathRev ‘’= b[--j]
E
assert(0B, ‘Internal error’)
 
R (reversed(aPathRev), reversed(bPathRev))
 
V result = levenshteinAlign(‘place’, ‘palace’)
print(result[0])
print(result[1])
print()
 
result = levenshteinAlign(‘rosettacode’, ‘raisethysword’)
print(result[0])
print(result[1])</syntaxhighlight>
 
{{out}}
<pre>
p-lace
palace
 
r-oset-tacode
raisethysword
</pre>
 
=={{header|Arturo}}==
 
<syntaxhighlight lang="rebol">print join.with:"\n" levenshtein.align "place" "palace"
print join.with:"\n" levenshtein.align "rosettacode" "raisethysword"</syntaxhighlight>
 
{{out}}
 
<pre>p-lace
palace
r-oset-tacode
raisethysword</pre>
 
=={{header|C}}==
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <string.h>
Line 108 ⟶ 173:
leven("raisethysword", "rosettacode");
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>
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>
 
=={{header|D}}==
Using the standard library.
<langsyntaxhighlight lang="d">void main() {
import std.stdio, std.algorithm;
 
Line 144 ⟶ 354:
 
writeln(s1b, "\n", s2b);
}</langsyntaxhighlight>
{{out}}
<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}}==
<syntaxhighlight lang="eiffel">
distance (source, target: STRING): INTEGER
-- Minimum number of operations to turn `source' into `target'.
local
l_distance: ARRAY2 [INTEGER]
del, ins, subst: INTEGER
do
create l_distance.make (source.count, target.count)
⟳ ic:(1 |..| source.count) ¦ l_distance [ic, 1] := ic - 1 ⟲
⟳ ij:(1 |..| target.count) ¦ l_distance [1, ij] := ij - 1 ⟲
 
⟳ ic:(2 |..| source.count) ¦
⟳ jc:(2 |..| target.count) ¦
if source [ic] = target [jc] then -- same char
l_distance [ic, jc] := l_distance [ic - 1, jc - 1]
else -- diff char
del := l_distance [ic - 1, jc] -- delete?
ins := l_distance [ic, jc - 1] -- insert?
subst := l_distance [ic - 1, jc -1] -- substitute/swap?
l_distance [ic, jc] := del.min (ins.min (subst)) + 1
end
⟲
⟲
Result:= l_distance [source.count, target.count]
end
</syntaxhighlight>{{out}}
Result = 8
 
The ⟳ ¦ ⟲ represents the "symbolic form" of an Eiffel across loop. In the case above, the first two ⟳ (loops) initialize the first column and the first row, and then two nested ⟳ (loops) to walk the distance computation.
 
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}}==
{{libheader|biogo}}
Alignment computed by the Needleman-Wunch algorithm, which is used in bioinformatics.
<langsyntaxhighlight lang="go">package main
 
import (
Line 207 ⟶ 588:
}
fmt.Println(string(ma))
}</langsyntaxhighlight>
{{out}}
The lines after the alignment point out the 8 edits.
Line 215 ⟶ 596:
|| |||| ||
</pre>
 
=={{header|Haskell}}==
The Wagner–Fischer matrix construction is adopted from [[Levenshtein_distance#Haskell]], however it is reversed in order to simplify it's traversing.
<syntaxhighlight lang="haskell">costs :: String -> String -> [[Int]]
costs s1 s2 = reverse $ reverse <$> matrix
where
matrix = scanl transform [0 .. length s1] s2
transform ns@(n:ns1) c = scanl calc (n + 1) $ zip3 s1 ns ns1
where
calc z (c1, x, y) = minimum [ y + 1, z + 1
, x + fromEnum (c1 /= c)]
 
levenshteinDistance :: String -> String -> Int
levenshteinDistance s1 s2 = head.head $ costs s1 s2</syntaxhighlight>
 
 
=== A sample alignment ===
The alignment is built in the same way as it is done in [[Levenshtein_distance/Alignment#Java]].
Instead of indices the Wagner–Fischer matrix and strings are traversed by list truncation, as zippers.
 
<syntaxhighlight lang="haskell">alignment :: String -> String -> (String, String)
alignment s1 s2 = go (costs s1 s2) (reverse s1) (reverse s2) ([],[])
where
go c _ _ r | isEmpty c = r
go _ [] s r = ('-' <$ s, reverse s) <> r
go _ s [] r = (reverse s, '-' <$ s) <> r
go c s1@(h1:t1) s2@(h2:t2) (r1, r2) =
let temp = (get.nextCol.nextRow $ c) + if h1 == h2 then 0 else 1
in case get c of
x | x == temp -> go (nextRow.nextCol $ c) t1 t2 (h1:r1, h2:r2)
| x == 1 + (get.nextCol $ c) -> go (nextCol c) s1 t2 ('-':r1, h2:r2)
| x == 1 + (get.nextRow $ c) -> go (nextRow c) t1 s2 (h1:r1, '-':r2)
 
-- Functions which treat table as zipper
get ((h:_):_) = h
nextRow = map tail
nextCol = tail
isEmpty c = null c || null (head c)</syntaxhighlight>
 
<pre>λ> alignment "palace" "place"
("palace","p-lace")
 
λ> alignment "rosettacode" "raisethysword"
("r-oset-tacode","raisethysword")
 
λ> alignment "rosettacode" "rat"
("rosettacode","r-----a---t")</pre>
 
=== All alignments ===
The alternative solution, which extensively produces all minimal alignments for given strings.
 
<syntaxhighlight lang="haskell">-- Produces all possible alignments for two strings.
allAlignments :: String -> String -> [[(Char, Char)]]
allAlignments s1 s2 = go (length s2 - length s1) s1 s2
where
go _ s [] = [(\x -> (x, '-')) <$> s]
go _ [] s = [(\x -> ('-' ,x)) <$> s]
go n s1@(h1:t1) s2@(h2:t2) = (h1, h2) <:> go n t1 t2
++ case compare n 0 of
LT -> (h1, '-') <:> go (n+1) t1 s2
EQ -> []
GT -> ('-', h2) <:> go (n-1) s1 t2
 
x <:> l = fmap (x :) l
 
-- Returns a lazy list of all optimal alignments.
levenshteinAlignments :: String -> String -> [(String, String)]
levenshteinAlignments s1 s2 = unzip <$> best
where
best = filter ((lev ==) . dist) $ allAlignments s1 s2
lev = levenshteinDistance s1 s2
dist = length . filter (uncurry (/=))</syntaxhighlight>
 
 
<pre>λ> mapM_ print $ levenshteinAlignments "rosettacode" "raisethysword"
("ro-settac-ode","raisethysword")
("ro-setta-code","raisethysword")
("ro-sett-acode","raisethysword")
("ro-set-tacode","raisethysword")
("r-osettac-ode","raisethysword")
("r-osetta-code","raisethysword")
("r-osett-acode","raisethysword")
("r-oset-tacode","raisethysword")
 
λ> mapM_ print $ levenshteinAlignments "rosettacode" "rat"
("rosettacode","ra--t------")
("rosettacode","ra---t-----")
("rosettacode","r-a-t------")
("rosettacode","r-a--t-----")
("rosettacode","r--at------")
("rosettacode","r--a-t-----")
("rosettacode","r---at-----")
("rosettacode","r-----at---")
("rosettacode","r-----a-t--")
("rosettacode","r-----a--t-")
("rosettacode","r-----a---t")</pre>
 
 
=={{header|J}}==
 
Translation of java:
 
<syntaxhighlight lang="j">levalign=:4 :0
assert. x <:&# y
D=. x +/&i.&>:&# y
for_i. 1+i.#x do.
for_j. 1+i.#y do.
if. ((<:i){x)=(<:j){y do.
D=. (D {~<<:i,j) (<i,j)} D
else.
min=. 1+<./D{~(i,j) <@:-"1#:1 2 3
D=. min (<i,j)} D
end.
end.
end.
A=. B=. ''
ij=. x ,&# y
while. */ij do.
'd00 d01 d10 d11'=. D{~ ij <@:-"1#:i.4
'x1 y1'=. (ij-1){each x;y
if. d00 = d11+x1~:y1 do.
A=. A,x1 [ B=. B,y1 [ ij=. ij-1
elseif. d00 = 1+d10 do.
A=. A,x1 [ B=. B,'-'[ ij=. ij-1 0
elseif. d00 = 1+d01 do.
A=. A,'-'[ B=. B,y1 [ ij=. ij-0 1
end.
end.
A,:&|.B
)</syntaxhighlight>
 
Task examples:
 
<syntaxhighlight lang="j"> 'place' levalign 'palace'
p-lace
palace
'rosettacode' levalign 'raisethysword'
r-oset-tacode
raisethysword
</syntaxhighlight>
 
=={{header|Java}}==
<langsyntaxhighlight lang="java">public class LevenshteinAlignment {
 
public static String[] alignment(String a, String b) {
Line 256 ⟶ 777:
System.out.println(result[1]);
}
}</langsyntaxhighlight>
{{out}}
<pre>
r-oset-tacode
raisethysword
</pre>
 
=={{header|Julia}}==
{{works with|Julia|0.6}}
{{trans|Java}}
 
<syntaxhighlight lang="julia">function levenshteinalign(a::AbstractString, b::AbstractString)
a = lowercase(a)
b = lowercase(b)
len_a = length(a)
len_b = length(b)
 
costs = Matrix{Int}(len_a + 1, len_b + 1)
costs[1, :] .= 0:len_b
@inbounds for i in 2:(len_a + 1)
costs[i, 1] = i
for j in 2:(len_b + 1)
tmp = ifelse(a[i-1] == b[j-1], costs[i-1, j-1], costs[i-1, j-1] + 1)
costs[i, j] = min(1 + min(costs[i-1, j], costs[i, j-1]), tmp)
end
end
 
apathrev = IOBuffer()
bpathrev = IOBuffer()
local i = len_a + 1
local j = len_b + 1
@inbounds while i != 1 && j != 1
tmp = ifelse(a[i-1] == b[j-1], costs[i-1, j-1], costs[i-1, j-1] + 1)
if costs[i, j] == tmp
i -= 1
j -= 1
print(apathrev, a[i])
print(bpathrev, b[j])
elseif costs[i, j] == 1 + costs[i-1, j]
i -= 1
print(apathrev, a[i])
print(bpathrev, '-')
elseif costs[i, j] == 1 + costs[i, j-1]
j -= 1
print(apathrev, '-')
print(bpathrev, b[j])
end
end
 
return reverse(String(take!(apathrev))), reverse(String(take!(bpathrev)))
end
 
foreach(println, levenshteinalign("rosettacode", "raisethysword"))
foreach(println, levenshteinalign("place", "palace"))</syntaxhighlight>
 
{{out}}
<pre>r-oset-tacode
raisethysword
p-lace
palace</pre>
 
=={{header|Kotlin}}==
{{trans|Java}}
<syntaxhighlight lang="scala">// version 1.1.3
 
fun levenshteinAlign(a: String, b: String): Array<String> {
val aa = a.toLowerCase()
val bb = b.toLowerCase()
val costs = Array(a.length + 1) { IntArray(b.length + 1) }
for (j in 0..b.length) costs[0][j] = j
for (i in 1..a.length) {
costs[i][0] = i
for (j in 1..b.length) {
val temp = costs[i - 1][j - 1] + (if (aa[i - 1] == bb[j - 1]) 0 else 1)
costs[i][j] = minOf(1 + minOf(costs[i - 1][j], costs[i][j - 1]), temp)
}
}
 
// walk back through matrix to figure out path
val aPathRev = StringBuilder()
val bPathRev = StringBuilder()
var i = a.length
var j = b.length
while (i != 0 && j != 0) {
val temp = costs[i - 1][j - 1] + (if (aa[i - 1] == bb[j - 1]) 0 else 1)
when (costs[i][j]) {
temp -> {
aPathRev.append(aa[--i])
bPathRev.append(bb[--j])
}
 
1 + costs[i-1][j] -> {
aPathRev.append(aa[--i])
bPathRev.append('-')
}
 
1 + costs[i][j-1] -> {
aPathRev.append('-')
bPathRev.append(bb[--j])
}
}
}
return arrayOf(aPathRev.reverse().toString(), bPathRev.reverse().toString())
}
 
fun main(args: Array<String>) {
var result = levenshteinAlign("place", "palace")
println(result[0])
println(result[1])
println()
result = levenshteinAlign("rosettacode","raisethysword")
println(result[0])
println(result[1])
}</syntaxhighlight>
 
{{out}}
<pre>
p-lace
palace
 
r-oset-tacode
raisethysword
Line 265 ⟶ 903:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
{{incorrect}}
{{works with|Mathematica|7}}
<lang Mathematica>DamerauLevenshteinDistance["rosettacode", "raisethysword"]</lang>
<syntaxhighlight lang="mathematica">DamerauLevenshteinDistance["rosettacode", "raisethysword"]</syntaxhighlight>
 
{{out}}<pre>8</pre>
 
=={{header|Nim}}==
{{trans|Kotlin}}
<syntaxhighlight lang="nim">import algorithm, sequtils, strutils
 
proc levenshteinAlign(a, b: string): tuple[a, b: string] =
let a = a.toLower()
let b = b.toLower()
var costs = newSeqWith(a.len + 1, newSeq[int](b.len + 1))
for j in 0..b.len: costs[0][j] = j
for i in 1..a.len:
costs[i][0] = i
for j in 1..b.len:
let tmp = costs[i - 1][j - 1] + ord(a[i - 1] != b[j - 1])
costs[i][j] = min(1 + min(costs[i - 1][j], costs[i][j - 1]), tmp)
 
# Walk back through matrix to figure out path.
var aPathRev, bPathRev: string
var i = a.len
var j = b.len
while i != 0 and j != 0:
let tmp = costs[i - 1][j - 1] + ord(a[i - 1] != b[j - 1])
if costs[i][j] == tmp:
dec i
dec j
aPathRev.add a[i]
bPathRev.add b[j]
elif costs[i][j] == 1 + costs[i-1][j]:
dec i
aPathRev.add a[i]
bPathRev.add '-'
elif costs[i][j] == 1 + costs[i][j-1]:
dec j
aPathRev.add '-'
bPathRev.add b[j]
else:
quit "Internal error"
 
result = (reversed(aPathRev).join(), reversed(bPathRev).join())
 
when isMainModule:
 
var result = levenshteinAlign("place", "palace")
echo result.a
echo result.b
echo ""
 
result = levenshteinAlign("rosettacode","raisethysword")
echo result.a
echo result.b</syntaxhighlight>
 
{{out}}
<pre>p-lace
palace
 
r-oset-tacode
raisethysword</pre>
 
=={{header|Perl}}==
<langsyntaxhighlight lang="perl">use strict;
use warnings;
 
Line 304 ⟶ 1,001:
}
print join "\n", levenshtein_distance_alignment "rosettacode", "raisethysword";</langsyntaxhighlight>
{{out}}
<pre>ro-settac-o-de
raisethysword-</pre>
 
=={{header|Perl 6Phix}}==
{{trans|Kotlin}} plus the indicator from Go
{{incorrect}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
{{trans|Perl}}
<span style="color: #008080;">function</span> <span style="color: #000000;">LevenshteinAlignment</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
<lang Perl 6>sub align ( Str $σ, Str $t ) {
<span style="color: #004080;">integer</span> <span style="color: #000000;">la</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
my @s = *, $σ.comb;
<span style="color: #000000;">lb</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span>
my @t = *, $t.comb;
<span style="color: #004080;">sequence</span> <span style="color: #000000;">costs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lb</span><span style="color: #0000FF;">),</span><span style="color: #000000;">la</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">lb</span> <span style="color: #008080;">do</span>
my @A;
<span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">j</span>
@A[$_][ 0]<d s t> = $_, @s[1..$_].join, '-' x $_ for ^@s;
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
@A[ 0][$_]<d s t> = $_, '-' x $_, @t[1..$_].join for ^@t;
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">la</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
for 1 ..^ @s X 1..^ @t -> (\i, \j) {
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">lb</span> <span style="color: #008080;">do</span>
if @s[i] ne @t[j] {
<span style="color: #004080;">integer</span> <span style="color: #000000;">tmp1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">+</span><span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]),</span>
@A[i][j]<d> = 1 + my $min =
<span style="color: #000000;">tmp2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
min @A[i-1][j]<d>, @A[i][j-1]<d>, @A[i-1][j-1]<d>;
<span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tmp2</span><span style="color: #0000FF;">)</span>
@A[i][j]<s t> =
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
@A[i-1][j]<d> == $min ?? (@A[i-1][j]<s t> Z~ @s[i], '-') !!
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
@A[i][j-1]<d> == $min ?? (@A[i][j-1]<s t> Z~ '-', @t[j]) !!
<span style="color: #000080;font-style:italic;">-- walk back through matrix to figure out the path</span>
(@A[i-1][j-1]<s t> Z~ @s[i], @t[j]);
<span style="color: #004080;">string</span> <span style="color: #000000;">arev</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span><span style="color: #0000FF;">,</span>
} else {
<span style="color: #000000;">brev</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
@A[i][j]<d s t> = @A[i-1][j-1]<d s t> Z~ '', @s[i], @t[j];
<span style="color: #004080;">integer</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">la</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">j</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lb</span>
}
<span style="color: #008080;">while</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">and</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
}
<span style="color: #004080;">integer</span> <span style="color: #000000;">tmp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">switch</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">do</span>
return @A[*-1][*-1]<s t>;
<span style="color: #008080;">case</span> <span style="color: #000000;">tmp</span><span style="color: #0000FF;">:</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">;</span> <span style="color: #000000;">arev</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
}
<span style="color: #000000;">j</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">;</span> <span style="color: #000000;">brev</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">case</span> <span style="color: #000000;">1</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]:</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">;</span> <span style="color: #000000;">arev</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
.say for align |<rosettacode raisethysword>;</lang>
<span style="color: #000000;">brev</span> <span style="color: #0000FF;">&=</span> <span style="color: #008000;">'-'</span>
<span style="color: #008080;">case</span> <span style="color: #000000;">1</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">costs</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]:</span> <span style="color: #000000;">arev</span> <span style="color: #0000FF;">&=</span> <span style="color: #008000;">'-'</span>
<span style="color: #000000;">j</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">;</span> <span style="color: #000000;">brev</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">switch</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">arev</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">reverse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">brev</span><span style="color: #0000FF;">)}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">LevenshteinAlignment</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_add</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)),</span><span style="color: #7060A8;">sq_mul</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sq_ne</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">),</span><span style="color: #008000;">'|'</span><span style="color: #0000FF;">-</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n%s\n%s\n\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"rosettacode"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"raisethysword"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"place"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"palace"</span><span style="color: #0000FF;">)</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>ro-settac-o-de
r-oset-tacode
raisethysword-</pre>
raisethysword
|| |||| ||
 
p-lace
palace
|
</pre>
 
=={{header|Python}}==
<syntaxhighlight lang="python">from difflib import ndiff
 
def levenshtein(str1, str2):
result = ""
pos, removed = 0, 0
for x in ndiff(str1, str2):
if pos<len(str1) and str1[pos] == x[2]:
pos += 1
result += x[2]
if x[0] == "-":
removed += 1
continue
else:
if removed > 0:
removed -=1
else:
result += "-"
print(result)
 
levenshtein("place","palace")
levenshtein("rosettacode","raisethysword")</syntaxhighlight>
{{out}}
<pre>
p-lace
ro-settac-o-de
</pre>
 
=={{header|Racket}}==
Line 347 ⟶ 1,095:
for a discussion of the code.
 
<langsyntaxhighlight lang="racket">#lang racket
 
(define (memoize f)
Line 366 ⟶ 1,114:
(min (add1 (levenshtein (rest s) t))
(add1 (levenshtein s (rest t)))
(add1 (levenshtein (rest s) (rest t)))))]))))</langsyntaxhighlight>
'''Demonstration:'''
<langsyntaxhighlight lang="racket">(levenshtein (string->list "rosettacode")
(string->list "raisethysword"))</langsyntaxhighlight>
{{out}}
<pre>8</pre>
Line 375 ⟶ 1,123:
===Complete version===
Now we extend the code from http://blog.racket-lang.org/2012/08/dynamic-programming-versus-memoization.html to show also the alignment. The code is very similar, but it stores the partial results (number of edits and alignment of each substring) in a lev structure.
<langsyntaxhighlight Racketlang="racket">#lang racket
 
(struct lev (n s t))
Line 418 ⟶ 1,166:
(values (lev-n result)
(list->string (lev-s result))
(list->string (lev-t result)))))</langsyntaxhighlight>
'''Demonstration:'''
<langsyntaxhighlight lang="racket">(let-values ([(dist exp-s exp-t)
(levenshtein "rosettacode" "raisethysword")])
(printf "levenshtein: ~a edits\n" dist)
(displayln exp-s)
(displayln exp-t))</langsyntaxhighlight>
{{out}}
<pre>levenshtein: 8 edits
r-oset-taco-de
raisethysword-</pre>
 
=={{header|Raku}}==
(formerly Perl 6)
{{trans|Perl}}
<syntaxhighlight lang="raku" line>sub align ( Str $σ, Str $t ) {
my @s = flat *, $σ.comb;
my @t = flat *, $t.comb;
my @A;
@A[$_][ 0]<d s t> = $_, @s[1..$_].join, '-' x $_ for ^@s;
@A[ 0][$_]<d s t> = $_, '-' x $_, @t[1..$_].join for ^@t;
for 1 ..^ @s X 1..^ @t -> (\i, \j) {
if @s[i] ne @t[j] {
@A[i][j]<d> = 1 + my $min =
min @A[i-1][j]<d>, @A[i][j-1]<d>, @A[i-1][j-1]<d>;
@A[i][j]<s t> =
@A[i-1][j]<d> == $min ?? (@A[i-1][j]<s t> Z~ @s[i], '-') !!
@A[i][j-1]<d> == $min ?? (@A[i][j-1]<s t> Z~ '-', @t[j]) !!
(@A[i-1][j-1]<s t> Z~ @s[i], @t[j]);
} else {
@A[i][j]<d s t> = @A[i-1][j-1]<d s t> Z~ '', @s[i], @t[j];
}
}
return @A[*-1][*-1]<s t>;
}
.say for align 'rosettacode', 'raisethysword';</syntaxhighlight>
{{out}}
<pre>ro-settac-o-de
raisethysword-</pre>
 
Line 433 ⟶ 1,213:
{{trans|Tcl}}
uses "lcs" from [[Longest common subsequence#Ruby|here]]
<langsyntaxhighlight lang="ruby">require 'lcs'
 
def levenshtein_align(a, b)
Line 468 ⟶ 1,248:
end
 
puts levenshtein_align("rosettacode", "raisethysword")</langsyntaxhighlight>
 
{{out}}
Line 475 ⟶ 1,255:
raisethysword-
</pre>
 
=={{header|Rust}}==
'''Cargo.toml'''
<pre>[dependencies]
edit-distance = "^1.0.0"</pre>
 
'''src/main.rs'''
<syntaxhighlight lang="rust">extern crate edit_distance;
 
edit_distance("rosettacode", "raisethysword");</syntaxhighlight>
 
=={{header|Scala}}==
{{Out}}Best seen running in your browser either by [https://scastie.scala-lang.org/I8BAESkNTjukVPzsWOUyPA ScalaFiddle (ES aka JavaScript, non JVM)] or [https://scastie.scala-lang.org/I8BAESkNTjukVPzsWOUyPA].
<syntaxhighlight lang="scala">import scala.collection.mutable
import scala.collection.parallel.ParSeq
 
object LevenshteinAlignment extends App {
val vlad = new Levenshtein("rosettacode", "raisethysword")
val alignment = vlad.revLevenstein()
 
class Levenshtein(s1: String, s2: String) {
val memoizedCosts = mutable.Map[(Int, Int), Int]()
 
def revLevenstein(): (String, String) = {
def revLev: (Int, Int, String, String) => (String, String) = {
case (_, 0, revS1, revS2) => (revS1, revS2)
case (0, _, revS1, revS2) => (revS1, revS2)
case (i, j, revS1, revS2) =>
if (memoizedCosts(i, j) == (memoizedCosts(i - 1, j - 1)
+ (if (s1(i - 1) != s2(j - 1)) 1 else 0)))
revLev(i - 1, j - 1, s1(i - 1) + revS1, s2(j - 1) + revS2)
else if (memoizedCosts(i, j) == 1 + memoizedCosts(i - 1, j))
revLev(i - 1, j, s1(i - 1) + revS1, "-" + revS2)
else
revLev(i, j - 1, "-" + revS1, s2(j - 1) + revS2)
}
 
revLev(s1.length, s2.length, "", "")
}
 
private def levenshtein: Int = {
def lev: ((Int, Int)) => Int = {
case (k1, k2) =>
memoizedCosts.getOrElseUpdate((k1, k2), (k1, k2) match {
case (i, 0) => i
case (0, j) => j
case (i, j) =>
ParSeq(1 + lev((i - 1, j)),
1 + lev((i, j - 1)),
lev((i - 1, j - 1))
+ (if (s1(i - 1) != s2(j - 1)) 1 else 0)).min
})
}
 
lev((s1.length, s2.length))
}
 
levenshtein
}
 
println(alignment._1)
println(alignment._2)
 
}</syntaxhighlight>
 
=={{header|Sidef}}==
{{trans|Perl}}
<langsyntaxhighlight lang="ruby">func align(s, t) {
s.chars!.prepend!('^')
t.chars!.prepend!('^')
 
var A = []
for {|i in ^s {| A[i][0]{@|<d s t>} = (i, s.ftslice(1, ).first(i).join, '~' * i) } << ^s
for {|i in ^t {| A[0][i]{@|<d s t>} = (i, '-' * i, t.ftslice(1, ).first(i).join) } << ^t
 
for i (1 .. s.end.times) { |i|
for j (1 .. t.end.times) { |j|
if (s[i] != t[j]) {
A[i][j]{:d} = 1+(
var min = Math.min(A[i-1][j]{:d}, A[i][j-1]{:d}, A[i-1][j-1]{:d})
)
A[i][j]{@|<s t>} = @|(A[i-1][j]{:d} == min
? [A[i-1][j]{:s}+s[i], A[i-1][j]{:t}+'-']
: (A[i][j-1]{:d} == min
? [A[i][j-1]{:s}+'-', A[i][j-1]{:t}+t[j]]
: [A[i-1][j-1]{:s}+s[i], A[i-1][j-1]{:t}+t[j]]))...
}
else {
A[i][j]{@|<d s t>} = (
A[i-1][j-1]{:d},
A[i-1][j-1]{:s}+s[i],
Line 507 ⟶ 1,351:
}
}
return [A[-1][-1]{@|<s t>}]
}
 
align("rosettacode", "raisethysword").each { .say }</langsyntaxhighlight>
{{out}}
ro-settac-o-de
<pre>
raisethysword-
ro-settac-o-de
raisethysword-
</pre>
 
=={{header|Tcl}}==
{{tcllib|struct::list}}
<langsyntaxhighlight lang="tcl">package require struct::list
proc levenshtein/align {a b} {
lassign [struct::list longestCommonSubsequence [split $a ""] [split $b ""]]\
Line 554 ⟶ 1,396:
}
 
puts [levenshtein/align "rosettacode" "raisethysword"]</langsyntaxhighlight>
{{out}}
<pre>
r-oset-taco-de
raisethysword-
</pre>
 
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-str}}
<syntaxhighlight lang="wren">import "./str" for Str
 
var levenshteinAlign = Fn.new { |a, b|
a = Str.lower(a)
b = Str.lower(b)
var costs = List.filled(a.count+1, null)
for (i in 0..a.count) costs[i] = List.filled(b.count+1, 0)
for (j in 0..b.count) costs[0][j] = j
for (i in 1..a.count) {
costs[i][0] = i
for (j in 1..b.count) {
var temp = costs[i - 1][j - 1] + ((a[i - 1] == b[j - 1]) ? 0 : 1)
costs[i][j] = temp.min(1 + costs[i - 1][j].min(costs[i][j - 1]))
}
}
// walk back through matrix to figure out path
var aPathRev = ""
var bPathRev = ""
var i = a.count
var j = b.count
while (i != 0 && j != 0) {
var temp = costs[i - 1][j - 1] + ((a[i - 1] == b[j - 1]) ? 0 : 1)
var cij = costs[i][j]
if (cij == temp) {
i = i - 1
aPathRev = aPathRev + a[i]
j = j - 1
bPathRev = bPathRev + b[j]
} else if (cij == 1 + costs[i-1][j]) {
i = i - 1
aPathRev = aPathRev + a[i]
bPathRev = bPathRev + "-"
} else if (cij == 1 + costs[i][j-1]) {
aPathRev = aPathRev + "-"
j = j - 1
bPathRev = bPathRev+ b[j]
}
}
return [aPathRev[-1..0], bPathRev[-1..0]]
}
 
var result = levenshteinAlign.call("place", "palace")
System.print(result[0])
System.print(result[1])
System.print()
result = levenshteinAlign.call("rosettacode","raisethysword")
System.print(result[0])
System.print(result[1])</syntaxhighlight>
 
{{out}}
<pre>
p-lace
palace
 
r-oset-tacode
raisethysword
</pre>
 
=={{header|zkl}}==
{{trans|Java}}
<langsyntaxhighlight lang="zkl">fcn alignment(a,b){
a,b = a.toLower(), b.toLower();
costs := (a.len()+1).pump(List(),'wrap(a){ [1..b.len()].pump(List(a)) });
Line 587 ⟶ 1,490:
}
return(aPathRev.text.reverse(), bPathRev.text.reverse())
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">result := alignment("rosettacode", "raisethysword");
println(result[0]);
println(result[1]);</langsyntaxhighlight>
{{out}}
<pre>
Chkas
1,983

edits

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