Levenshtein distance: Difference between revisions
Add SETL
SqrtNegInf (talk | contribs) m (→{{header|Raku}}: no temp. variable) |
Not a robot (talk | contribs) (Add SETL) |
||
(28 intermediate revisions by 17 users not shown) | |||
Line 31:
{{trans|Python}}
<
I s1.len > s2.len
(s1, s2) = (s2, s1)
Line 48:
print(minimumEditDistance(‘kitten’, ‘sitting’))
print(minimumEditDistance(‘rosettacode’, ‘raisethysword’))</
{{out}}
Line 57:
=={{header|360 Assembly}}==
<
LEVENS CSECT
USING LEVENS,R13 base register
Line 229:
XDEC DS CL12 temp fo xdeco
REGEQU
END LEVENS</
{{out}}
<pre>
Line 241:
=={{header|Action!}}==
{{Improve||The output shown does not appear to match the PrintF calls in the code}}
<
DEFINE STRING="CHAR ARRAY" ; sys.act
DEFINE width="15" ; max characters 14
Line 320:
;PrintF("Damerau Levenshtein Distance=%U%E%E",result)
RETURN
</syntaxhighlight>
{{out}}
<pre>kitten, sitting: 3
Line 327:
=={{header|Ada}}==
<
procedure Main is
Line 360:
("rosettacode -> raisethysword:" &
Integer'Image (Levenshtein_Distance ("rosettacode", "raisethysword")));
end Main;</
{{out}}
<pre>kitten -> sitting: 3
Line 367:
=={{header|Aime}}==
{{trans|C}}
<
dist(data s, t, integer i, j, list d)
{
Line 411:
0;
}</
{{Out}}
<pre>`rosettacode' to `raisethysword' is 8
Line 421:
<br>
Non-recursive algorithm - although Algol 68 supports recursion, Action! doesn't.
<
BEGIN
Line 470:
print((word 1," -> ",word 2,": "));
print(("Levenshtein Distance: ",whole(levenshtein distance(word 1,word 2),0),newline))
END</
{{out}}
<pre>
Line 482:
===Iteration===
Translation of the "fast" C-version
<
to findLevenshteinDistance for s1 against s2
script o
Line 536:
end if
end if
end min3</
===Composition of generic functions===
Line 543:
In the ancient tradition of "''Use library functions whenever feasible.''" (for better productivity), and also in the even older functional tradition of composing values (for better reliability) rather than sequencing actions:
<
on levenshtein(sa, sb)
set {s1, s2} to {characters of sa, characters of sb}
Line 696:
map(result, items 1 thru ¬
minimum({length of xs, length of ys, length of zs}) of xs)
end zip3</
{{Out}}
<
=={{header|Arc}}==
Line 704:
O(n * m) time, linear space, using lists instead of vectors
<
(withs l1 len.str1
l2 len.str2
Line 719:
next))
(= row nrev.next)))
row.l1))</
=={{header|Arturo}}==
<
{{out}}
Line 731:
=={{header|AutoHotkey}}==
{{trans|Go}}
<
If s =
return StrLen(t)
Line 749:
s1 := "kitten"
s2 := "sitting"
MsgBox % "distance between " s1 " and " s2 ": " levenshtein(s1, s2)</
=={{header|AWK}}==
Line 755:
Slavishly copied from the very clear AutoHotKey example.
<
BEGIN {
Line 800:
}
</syntaxhighlight>
Example output:
Line 810:
Alternative, much faster but also less readable lazy-evaluation version from http://awk.freeshell.org/LevenshteinEditDistance
(where the above takes e.g. 0m44.904s in gawk 4.1.3 for 5 edits (length 10 and 14 strings), this takes user 0m0.004s):
<
function levdist(str1, str2, l1, l2, tog, arr, i, j, a, b, c) {
Line 838:
return arr[tog, j-1]
}
</syntaxhighlight>
=={{header|BBC BASIC}}==
<
PRINT ; FNlevenshtein("kitten", "sitting")
PRINT "'rosettacode' -> 'raisethysword' has distance " ;
Line 868:
NEXT
NEXT j%
= d%(i%-1,j%-1)</
'''Output:'''
<pre>
Line 877:
=={{header|BQN}}==
Recursive slow version:
<
𝕨 𝕊"": ≠𝕨;
""𝕊 𝕩: ≠𝕩;
Line 883:
Tail←1⊸↓
𝕨 =○⊑◶⟨1+·⌊´ 𝕊○Tail ∾ Tail⊸𝕊 ∾ 𝕊⟜Tail, 𝕊○Tail⟩ 𝕩
}</
Fast version:
<
{{out|Example use}}
<syntaxhighlight lang="text"> "kitten" Levenshtein "sitting"
3
"Saturday" Levenshtein "Sunday"
3
"rosettacode" Levenshtein "raisethysword"
8</
=={{header|Bracmat}}==
{{trans|C}}
Recursive method, but with memoization.
<
lev cache
. ( lev
Line 921:
)
& new$hash:?cache
& lev$!arg);</
{{out|Demonstrating}}
<pre> levenshtein$(kitten,sitting)
Line 927:
levenshtein$(rosettacode,raisethysword)
8</pre>
=={{header|Bruijn}}==
{{trans|Haskell}}
Recursive and non-memoized method:
<syntaxhighlight lang="bruijn>
:import std/Combinator .
:import std/Char C
:import std/List .
:import std/Math .
levenshtein y [[[∅?1 ∀0 (∅?0 ∀1 (0 (1 [[[[go]]]])))]]]
go (C.eq? 3 1) (6 2 0) ++(lmin ((6 2 0) : ((6 5 0) : {}(6 2 4))))
:test ((levenshtein "rosettacode" "raisethysword") =? (+8)) ([[1]])
:test ((levenshtein "kitten" "sitting") =? (+3)) ([[1]])
</syntaxhighlight>
=={{header|C}}==
Recursive method. Deliberately left in an inefficient state to show the recursive nature of the algorithm; notice how it would have become the Wikipedia algorithm if we memoized the function against parameters <code>ls</code> and <code>lt</code>.
<
#include <string.h>
Line 974 ⟶ 991:
return 0;
}</
Take the above and add caching, we get (in [[C99]]):
<
#include <string.h>
Line 1,019 ⟶ 1,036:
return 0;
}</
=={{header|C sharp|C#}}==
This is a straightforward translation of the Wikipedia pseudocode.
<
namespace LevenshteinDistance
Line 1,072 ⟶ 1,089:
}
}
}</
{{out|Example output}}
<pre>
Line 1,083 ⟶ 1,100:
=={{header|C++}}==
<
#include <iostream>
using namespace std;
Line 1,137 ⟶ 1,154:
return 0;
}</
{{out|Example output}}
<pre>
Line 1,145 ⟶ 1,162:
===Generic ISO C++ version===
<
#include <iostream>
#include <numeric>
Line 1,184 ⟶ 1,201:
<< levenshtein_distance(s0, s1) << std::endl;
return 0;
}</
{{out}}
Line 1,194 ⟶ 1,211:
===Recursive Version===
<
(let [len1 (count str1)
len2 (count str2)]
Line 1,206 ⟶ 1,223:
(levenshtein (rest str1) (rest str2))))))))
(println (levenshtein "rosettacode" "raisethysword"))</
{{out}}
<pre>8</pre>
===Iterative version===
<
(letfn [(cell-value [same-char? prev-row cur-row col-idx]
(min (inc (nth prev-row col-idx))
Line 1,231 ⟶ 1,248:
i))))
[row-idx] (range 1 (count prev-row)))]
(recur (inc row-idx) max-rows next-prev-row))))))</
=={{header|CLU}}==
<
where T has lt: proctype (T,T) returns (bool)
if a<b
Line 1,277 ⟶ 1,294:
show("kitten", "sitting")
show("rosettacode", "raisethysword")
end start_up</
{{out}}
<pre>kitten => sitting: 3
Line 1,284 ⟶ 1,301:
=={{header|COBOL}}==
GnuCobol 2.2
<
identification division.
program-id. Levenshtein.
Line 1,347 ⟶ 1,364:
display trim(string-a) " -> " trim(string-b) " = " trim(distance)
.
</syntaxhighlight>
{{out|Output}}
<pre>
Line 1,356 ⟶ 1,373:
=={{header|CoffeeScript}}==
<
# more of less ported simple algorithm from JS
m = str1.length
Line 1,385 ⟶ 1,402:
console.log levenshtein("stop", "tops")
console.log levenshtein("yo", "")
console.log levenshtein("", "yo")</
=={{header|Common Lisp}}==
<
(let* ((la (length a))
(lb (length b))
Line 1,398 ⟶ 1,415:
((aref rec x y) (aref rec x y))
(t (setf (aref rec x y)
(+ (leven (1- x) (1- y)) (if (char= (
(leven la lb))))
(print (levenshtein "rosettacode" "raisethysword"))</
{{out}}
<pre>8</pre>
Line 1,410 ⟶ 1,426:
=={{header|Crystal}}==
The standard library includes [https://crystal-lang.org/api/0.19.2/Levenshtein.html levenshtein] module
<
puts Levenshtein.distance("kitten", "sitting")
puts Levenshtein.distance("rosettacode", "raisethysword")
</syntaxhighlight>
{{out}}
<pre>3
Line 1,419 ⟶ 1,435:
{{trans|Ruby 1st version}}
<
def self.distance(a, b)
Line 1,442 ⟶ 1,458:
Levenshtein.test
</syntaxhighlight>
{{out}}
<pre>
Line 1,451 ⟶ 1,467:
{{trans|Ruby 2nd version}}
<
n, m = str1.size, str2.size
max = n / 2
Line 1,482 ⟶ 1,498:
puts "distance(#{a}, #{b}) = #{levenshtein_distance(a, b)}"
end
</syntaxhighlight>
{{out}}
<pre>
Line 1,493 ⟶ 1,509:
===Standard Version===
The standard library [http://www.digitalmars.com/d/2.0/phobos/std_algorithm.html#levenshteinDistance std.algorithm] module includes a Levenshtein distance function:
<
import std.stdio, std.algorithm;
levenshteinDistance("kitten", "sitting").writeln;
}</
{{out}}
<pre>3</pre>
Line 1,503 ⟶ 1,519:
===Iterative Version===
{{trans|Java}}
<
int distance(in string s1, in string s2) pure nothrow {
Line 1,534 ⟶ 1,550:
foreach (p; [["kitten", "sitting"], ["rosettacode", "raisethysword"]])
writefln("distance(%s, %s): %d", p[0], p[1], distance(p[0], p[1]));
}</
===Memoized Recursive Version===
{{trans|Python}}
<
uint lDist(T)(in const(T)[] s, in const(T)[] t) nothrow {
Line 1,552 ⟶ 1,568:
lDist("kitten", "sitting").writeln;
lDist("rosettacode", "raisethysword").writeln;
}</
=={{header|Delphi}}==
{{Trans|C#}}
<syntaxhighlight lang="delphi">
program Levenshtein_distanceTest;
Line 1,620 ⟶ 1,636:
readln;
end.
</syntaxhighlight>
Line 1,626 ⟶ 1,642:
=={{header|DWScript}}==
Based on Wikipedia version
<
var
i, j : Integer;
Line 1,648 ⟶ 1,664:
end;
PrintLn(LevenshteinDistance('kitten', 'sitting'));</
=={{header|Dyalect}}==
<
var n = s.Length()
var m = t.Length()
Line 1,695 ⟶ 1,711:
}
run("rosettacode", "raisethysword")</
{{out}}
<pre>rosettacode -> raisethysword = 8</pre>
=={{header|EasyLang}}==
{{trans|AWK}}
<syntaxhighlight lang=easylang>
func dist s1$ s2$ .
if len s1$ = 0
return len s2$
.
if len s2$ = 0
return len s1$
.
c1$ = substr s1$ 1 1
c2$ = substr s2$ 1 1
s1rest$ = substr s1$ 2 len s1$
s2rest$ = substr s2$ 2 len s2$
#
if c1$ = c2$
return dist s1rest$ s2rest$
.
min = lower dist s1rest$ s2rest$ dist s1$ s2rest$
min = lower min dist s1rest$ s2rest$
return min + 1
.
print dist "kitten" "sitting"
print dist "rosettacode" "raisethysword"
</syntaxhighlight>
=={{header|EchoLisp}}==
<
;; Recursive version adapted from Clojure
;; Added necessary memoization
Line 1,731 ⟶ 1,774:
(levenshtein "rosettacode" "raisethysword") → 8
</syntaxhighlight>
=={{header|Ela}}==
This code is translated from Haskell version.
<
levenshtein s1 s2 = last <| foldl transform [0 .. length s1] s2
where transform (n::ns')@ns c = scanl calc (n+1) <| zip3 s1 ns ns'
where calc z (c', x, y) = minimum [y+1, z+1, x + toInt (c' <> c)]</
Executing:
<
{{out}}
<pre>(3, 8)</pre>
Line 1,750 ⟶ 1,793:
=={{header|Elixir}}==
{{trans|Ruby}}
<
def distance(a, b) do
ta = String.downcase(a) |> to_charlist |> List.to_tuple
Line 1,777 ⟶ 1,820:
Enum.each(Enum.chunk(words, 2), fn [a,b] ->
IO.puts "distance(#{a}, #{b}) = #{Levenshtein.distance(a,b)}"
end)</
{{out}}
Line 1,788 ⟶ 1,831:
=={{header|Erlang}}==
Here are two implementations. The first is the naive version, the second is a memoized version using Erlang's dictionary datatype.
<
-module(levenshtein).
-compile(export_all).
Line 1,824 ⟶ 1,867:
{L,dict:store({S,T},L,C3)}
end.
</syntaxhighlight>
Below is a comparison of the runtimes, measured in microseconds, between the two implementations.
<
68> timer:tc(levenshtein,distance,["rosettacode","raisethysword"]).
{774799,8} % {Time, Result}
Line 1,835 ⟶ 1,878:
71> timer:tc(levenshtein,distance_cached,["kitten","sitting"]).
{213,3}
</syntaxhighlight>
=={{header|ERRE}}==
<syntaxhighlight lang="erre">
PROGRAM LEVENSHTEIN
Line 1,882 ⟶ 1,925:
!$ERASE D%
END PROGRAM
</syntaxhighlight>
{{out}}<pre>
'kitten' -> 'sitting' has distance 3
Line 1,890 ⟶ 1,933:
=={{header|Euphoria}}==
Code by Jeremy Cowgar from the [http://www.rapideuphoria.com/cgi-bin/asearch.exu?gen=on&keywords=Levenshtein Euphoria File Archive].
<
atom m
m = s[1]
Line 1,936 ⟶ 1,979:
? levenshtein("kitten", "sitting")
? levenshtein("rosettacode", "raisethysword")</
{{out}}
<pre>3
Line 1,944 ⟶ 1,987:
=={{header|F_Sharp|F#}}==
=== Standard version ===
<syntaxhighlight lang="fsharp">
open System
Line 1,977 ⟶ 2,020:
Console.ReadKey () |> ignore
</syntaxhighlight>
=== Recursive Version ===
<syntaxhighlight lang="fsharp">
open System
Line 2,003 ⟶ 2,046:
printfn "dist(kitten, sitting) = %i" (levenshtein "kitten" "sitting")
</syntaxhighlight>
=={{header|Factor}}==
<
"kitten" "sitting" levenshtein .</
{{out}}
<pre>
Line 2,015 ⟶ 2,058:
=={{header|Forth}}==
{{trans|C}}
<
dup \ if either string is empty, difference
if \ is inserting all chars from the other
Line 2,037 ⟶ 2,080:
s" kitten" s" sitting" levenshtein . cr
s" rosettacode" s" raisethysword" levenshtein . cr</
=={{header|Fortran}}==
<syntaxhighlight lang="fortran">
program demo_edit_distance
character(len=:),allocatable :: sources(:),targets(:)
Line 2,079 ⟶ 2,122:
end program demo_edit_distance
</syntaxhighlight>
{{out}}
<pre>
kitten sitting 3 T
rosettacode raisethysword 8 T
Line 2,089 ⟶ 2,133:
T
</pre>
=={{header|FreeBASIC}}==
<
' Uses the "iterative with two matrix rows" algorithm
Line 2,140 ⟶ 2,183:
Print
Print "Press any key to quit"
Sleep</
{{out}}
Line 2,151 ⟶ 2,194:
=={{header|Frink}}==
Frink has a built-in function to calculate the Levenshtein edit distance between two strings:
<
It also has a function to calculate the Levenshtein-Damerau edit distance, <CODE>editDistanceDamerau[<I>str1</I>,<I>str2</I>]</CODE>. This is similar to the <CODE>editDistance</CODE> function but also allows ''swaps'' between two adjoining characters, which count as an edit distance of 1. This may make distances between some strings shorter, by say, treating transposition errors in a word as a less expensive operation than in the pure Levenshtein algorithm, and is generally more useful in more circumstances.
=={{header|FutureBasic}}==
Recursive version.
<syntaxhighlight lang
local fn LevenshteinDistance( s1 as CFStringRef, s2 as CFStringRef ) as NSInteger
NSInteger result
// If strings are equal, Levenshtein distance is 0
if ( fn StringIsEqual( s1, s2 ) ) then result = 0 : exit fn
// If either string is empty, then distance is the length of the other string.
if (
if ( len(s2) == 0) then result = len(s1) : exit fn
// The remaining recursive process uses first characters and remainder of each string.
CFStringRef s1First = fn StringSubstringToIndex( s1, 1 )
CFStringRef s2First = fn StringSubstringToIndex( s2, 1 )
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.
if fn StringIsEqual( s1First, s2First ) then result = fn LevenshteinDistance( s1Rest, s2Rest ) : exit fn
// Find the distances between sub strings.
NSInteger distA = fn LevenshteinDistance( s1Rest, s2 )
NSInteger distB = fn
NSInteger distC = fn LevenshteinDistance( s1Rest, s2Rest )
// Return the minimum distance between substrings.
NSInteger minDist = distA
if ( distB < minDist )
if ( distC < minDist ) then minDist = distC
result = minDist + 1 // Include change for the first character.
end fn = result
NSInteger i
testStr( 0, 0 ) = @"kitten" : testStr( 0, 1 ) = @"sitting"
testStr( 1,
testStr( 2,
testStr( 4, 0 ) = @"rave" : testStr( 4, 1 ) = @"ravel"
testStr( 5, 0 ) = @"black" : testStr( 5, 1 ) = @"slack"
testStr( 6, 0 ) = @"rave" : testStr( 6, 1 ) = @"grave"
for i = 0 to 6
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
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
1st string = kitten
Line 2,226 ⟶ 2,271:
Levenshtein distance = 0
1st string =
2nd string =
Levenshtein distance =
1st string = black
2nd string = slack
Levenshtein distance = 1
1st string = rave
2nd string = grave
Levenshtein distance = 1
</pre>
=={{header|Go}}==
WP algorithm:
<
import "fmt"
Line 2,270 ⟶ 2,323:
}
return d[len(s)][len(t)]
}</
{{out}}
<pre>
Line 2,276 ⟶ 2,329:
</pre>
{{trans|C}}
<
import "fmt"
Line 2,299 ⟶ 2,352:
fmt.Printf("distance between %s and %s: %d\n", s1, s2,
levenshtein(s1, s2))
}</
{{out}}
<pre>
Line 2,306 ⟶ 2,359:
=={{header|Groovy}}==
<
def dist = new int[str1.size() + 1][str2.size() + 1]
(0..str1.size()).each { dist[it][0] = it }
Line 2,324 ⟶ 2,377:
println "Checking distance(${key[0]}, ${key[1]}) == $dist"
assert distance(key[0], key[1]) == dist
}</
{{out}}
<pre>
Line 2,335 ⟶ 2,388:
===Implementation 1===
<
levenshtein s1 s2 = last $ foldl transform [0 .. length s1] s2
where
Line 2,343 ⟶ 2,396:
main :: IO ()
main = print (levenshtein "kitten" "sitting")</
{{Out}}
<pre>3</pre>
===Implementation 2===
<
levenshtein s1 [] = length s1
levenshtein [] s2 = length s2
Line 2,359 ⟶ 2,412:
main :: IO ()
main = print (levenshtein "kitten" "sitting")</
{{Out}}
<pre>3</pre>
=={{header|Icon}} and {{header|Unicon}}==
<
every process(!&input)
end
Line 2,384 ⟶ 2,437:
return d[n,m]-1
end</
{{out|Example}}
<pre>
Line 2,395 ⟶ 2,448:
=={{header|Io}}==
A <code>levenshtein</code> method is available on strings when the standard <code>Range</code> addon is loaded.
<syntaxhighlight lang="text">Io 20110905
Io> Range ; "kitten" levenshtein("sitting")
==> 3
Io> "rosettacode" levenshtein("raisethysword")
==> 8
Io> </
=={{header|IS-BASIC}}==
<syntaxhighlight lang="is-basic">100 PROGRAM "Levensht.bas"
110 LET S1$="kitten":LET S2$="sitting"
120 PRINT "The Levenshtein distance between """;S1$;""" and """;S2$;""" is:";LEVDIST(S1$,S2$)
130 DEF LEVDIST(S$,T$)
140 LET N=LEN(T$):LET M=LEN(S$)
150 NUMERIC D(0 TO M,0 TO N)
160 FOR I=0 TO M
170 LET D(I,0)=I
180 NEXT
190 FOR J=0 TO N
200 LET D(0,J)=J
210 NEXT
220 FOR J=1 TO N
230 FOR I=1 TO M
240 IF S$(I)=T$(J) THEN
250 LET D(I,J)=D(I-1,J-1)
260 ELSE
270 LET D(I,J)=MIN(D(I-1,J)+1,MIN(D(I,J-1)+1,D(I-1,J-1)+1))
280 END IF
290 NEXT
300 NEXT
310 LET LEVDIST=D(M,N)
320 END DEF</syntaxhighlight>
=={{header|J}}==
One approach would be a literal transcription of the [[wp:Levenshtein_distance#Computing_Levenshtein_distance|wikipedia implementation]]:
<
D=. x +/&i.&>:&# y
for_i.1+i.#x do.
Line 2,417 ⟶ 2,495:
end.
{:{:D
)</
First, we setup up an matrix of costs, with 0 or 1 for unexplored cells (1 being where the character pair corresponding to that cell position has two different characters). Note that the "cost to reach the empty string" cells go on the bottom and the right, instead of the top and the left, because this works better with J's "[http://www.jsoftware.com/help/dictionary/d420.htm insert]" operation (which we will call "reduce" in the next paragraph here. It could also be thought of as a right fold which has been constrained such the initial value is the identity value for the operation. Or, just think of it as inserting its operation between each item of its argument...).
Line 2,427 ⟶ 2,505:
We can also do the usual optimization where we only represent one row of the distance matrix at a time:
<
'a b'=. (x;y) /: (#x),(#y)
D=. >: iz =. i.#b
Line 2,434 ⟶ 2,512:
end.
{:D
)</
{{out|Example use}}
<
3
'kitten' levdist 'sitting'
3</
Time and space use:
<syntaxhighlight lang="j">
timespacex '''kitten'' levenshtein ''sitting'''
0.000113 6016
timespacex '''kitten'' levdist ''sitting'''
1.5e_5 4416</
So the levdist implementation is about 7 times faster for this example (which approximately corresponds to the length of the shortest string)
See the [[j:Essays/Levenshtein Distance|Levenshtein distance essay]] on the Jwiki for additional solutions.
Line 2,451 ⟶ 2,529:
=={{header|Java}}==
Based on the definition for Levenshtein distance given in the Wikipedia article:
<
public static int distance(String a, String b) {
Line 2,478 ⟶ 2,556:
System.out.println("distance(" + data[i] + ", " + data[i+1] + ") = " + distance(data[i], data[i+1]));
}
}</
{{out}}
<pre>distance(kitten, sitting) = 3
Line 2,485 ⟶ 2,563:
</pre>
{{trans|C}}
<
public static int levenshtein(String s, String t){
/* if either string is empty, difference is inserting all chars
Line 2,530 ⟶ 2,608:
+ levenshtein(sb1.reverse().toString(), sb2.reverse().toString()));
}
}</
{{out}}
<pre>distance between 'kitten' and 'sitting': 3
Line 2,538 ⟶ 2,616:
===Iterative space optimized (even bounded) ===
{{trans|Python}}
<
import static java.lang.Math.abs;
import static java.lang.Math.max;
Line 2,612 ⟶ 2,690:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 2,622 ⟶ 2,700:
===ES5===
Iterative:
<
var t = [], u, i, j, m = a.length, n = b.length;
if (!m) { return n; }
Line 2,652 ⟶ 2,730:
console.log('levenstein("' + a + '","' + b + '") was ' + d + ' should be ' + t);
}
});</
===ES6===
Line 2,658 ⟶ 2,736:
By composition of generic functions:
<
// ------------ LEVENSHTEIN EDIT DISTANCE ------------
// levenshtein :: String -> String -> Int
const levenshtein = sa =>
const go = (ns,
const calc = z
1 + y,
1 + z,
x + (
c1 === c
? 0
: 1
)
);
};
const [n, ...ns1] = ns;
return scanl(calc)(1 + n)(
zip3(cs)(ns)(ns1)
);
};
return
go,
enumFromTo(0)(cs.length)
)
);
};
//
const main = () => [
["kitten", "sitting"],
Line 2,695 ⟶ 2,785:
//
// enumFromTo :: Int -> Int -> [Int]
Line 2,736 ⟶ 2,795:
// last :: [a] -> a
const last = xs =>
// The last item of a list.
return 0 < n
};
// scanl :: (b -> a -> b) -> b -> [a] -> [b]
const scanl = f
// The series of interim values arising
// from a catamorphism.
startValue => xs =>
(a, x) => {
const v = f(a[0])(x);
return [v, a[1].concat(v)];
}, [startValue, [startValue]]
Line 2,782 ⟶ 2,823:
// A function over a pair, derived
// from a curried function.
const
: args
return f(
};
Line 2,794 ⟶ 2,835:
// zip3 :: [a] -> [b] -> [c] -> [(a, b, c)]
const zip3 = xs =>
ys => zs => xs.slice(
0,
)
.map((x, i) => [x, ys[i], zs[i]]);
// MAIN ---
return JSON.stringify(main());
})();</
{{Out}}
<pre>[3, 3, 8, 8]</pre>
Line 2,817 ⟶ 2,861:
67ms for rosettacode/raisethysword
71ms for edocattesor/drowsyhtesiar
<syntaxhighlight lang="jq">
# lookup the distance between s and t in the nested cache,
# which uses basic properties of the Levenshtein distance to save space:
Line 2,868 ⟶ 2,912:
def levenshteinDistance(s;t):
s as $s | t as $t | {} | ld($s;$t) | .[0];</
'''Task'''
<
"levenshteinDistance between \(.[0]) and \(.[1]) is \( levenshteinDistance(.[0]; .[1]) )";
Line 2,877 ⟶ 2,921:
(["edocattesor", "drowsyhtesiar"] | demo),
(["this_algorithm_is_similar_to",
"Damerau-Levenshtein_distance"] | demo)</
{{Out}}
levenshteinDistance between kitten and sitting is 3
Line 2,886 ⟶ 2,930:
=={{header|Jsish}}==
From Javascript, ES5 entry.
<
function levenshtein(a, b) {
Line 2,930 ⟶ 2,974:
levenshtein('mississippi', 'swiss miss') ==> 8
=!EXPECTEND!=
*/</
{{out}}
<pre>prompt$ jsish -u levenshtein.jsi
Line 2,939 ⟶ 2,983:
'''Recursive''':
{{works with|Julia|1.0}}
<
ls, lt = length.((s, t))
ls == 0 && return lt
Line 2,950 ⟶ 2,994:
@show levendist("kitten", "sitting") # 3
@show levendist("rosettacode", "raisethysword") # 8</
'''Iterative''':
{{works with|Julia|0.6}}
<
ls, lt = length(s), length(t)
if ls > lt
Line 2,974 ⟶ 3,018:
end
return dist[end]
end</
Let's see some benchmark:
<
println("\n# levendist(kitten, sitting)")
s, t = "kitten", "sitting"
Line 2,989 ⟶ 3,033:
@btime levendist(s, t)
println(" - Iterative:")
@btime levendist1(s, t)</
{{out}}
Line 3,007 ⟶ 3,051:
=={{header|Kotlin}}==
===Standard Version===
<
// Uses the "iterative with two matrix rows" algorithm referred to in the Wikipedia article.
Line 3,039 ⟶ 3,083:
println("'rosettacode' to 'raisethysword' => ${levenshtein("rosettacode", "raisethysword")}")
println("'sleep' to 'fleeting' => ${levenshtein("sleep", "fleeting")}")
}</
{{out}}
Line 3,049 ⟶ 3,093:
===Functional/Folding Version===
<
fun levenshtein(s: String, t: String,
charScore : (Char, Char) -> Int = { c1, c2 -> if (c1 == c2) 0 else 1}) : Int {
Line 3,069 ⟶ 3,113:
}
</syntaxhighlight>
{{out}}
<pre>
Line 3,083 ⟶ 3,127:
Suitable for short strings:
<
(defun levenshtein-simple
(('() str)
Line 3,097 ⟶ 3,141:
(levenshtein-simple str1-tail str2)
(levenshtein-simple str1-tail str2-tail))))))
</syntaxhighlight>
You can copy and paste that function into an LFE REPL and run it like so:
<
> (levenshtein-simple "a" "a")
0
Line 3,110 ⟶ 3,154:
> (levenshtein-simple "kitten" "sitting")
3
</syntaxhighlight>
It is not recommended to test strings longer than the last example using this implementation, as performance quickly degrades.
Line 3,116 ⟶ 3,160:
=== Cached Implementation ===
<
(defun levenshtein-distance (str1 str2)
(let (((tuple distance _) (levenshtein-distance
Line 3,143 ⟶ 3,187:
(len (+ 1 (lists:min (list l1 l2 l3)))))
(tuple len (dict:store (tuple str1 str2) len c3)))))))
</syntaxhighlight>
As before, here's some usage in the REPL. Note that longer strings are now possible to compare without incurring long execution times:
<
> (levenshtein-distance "a" "a")
0
Line 3,158 ⟶ 3,202:
> (levenshtein-distance "rosettacode" "raisethysword")
8
</syntaxhighlight>
=={{header|Liberty BASIC}}==
<
'08/19/10
'from http://www.merriampark.com/ld.htm#VB
Line 3,206 ⟶ 3,250:
Next i
LevenshteinDistance = d(n, m)
End Function </
=={{header|Limbo}}==
{{trans|Go}}
<
include "sys.m"; sys: Sys;
Line 3,257 ⟶ 3,301:
return a + 1;
}
</syntaxhighlight>
{{
<
% levenshtein kitten sitting rosettacode raisethysword
kitten <-> sitting => 3
rosettacode <-> raisethysword => 8
</
=={{header|LiveCode}}==
{{trans|Go}}
<syntaxhighlight lang="livecode">
//Code By Neurox66
function Levenshtein pString1 pString2
Line 3,292 ⟶ 3,336:
put Levenshtein("kitten","sitting")
put Levenshtein("rosettacode","raisethysword")
</syntaxhighlight>
{{out}}
<pre>3
Line 3,299 ⟶ 3,343:
=={{header|Lobster}}==
{{trans|C}}
<
def makeNxM(n: int, m: int, v: int) -> [[int]]:
Line 3,334 ⟶ 3,378:
assert 3 == levenshtein("kitten", "sitting")
assert 8 == levenshtein("rosettacode", "raisethysword")</
=={{header|Lua}}==
<
if s == '' then return t:len() end
if t == '' then return s:len() end
Line 3,356 ⟶ 3,400:
print(leven("kitten", "sitting"))
print(leven("rosettacode", "raisethysword"))</
{{out}}
<pre>3
Line 3,362 ⟶ 3,406:
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang="m2000 interpreter">
Module Checkit {
\\ Iterative with two matrix rows
Line 3,429 ⟶ 3,473:
}
Checkit2
</syntaxhighlight>
=={{header|Maple}}==
<syntaxhighlight lang="maple">
> with(StringTools):
> Levenshtein("kitten","sitting");
Line 3,439 ⟶ 3,483:
> Levenshtein("rosettacode","raisethysword");
8
</syntaxhighlight>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
EditDistance["rosettacode","raisethysword"]</
{{out}}
<pre>3
Line 3,449 ⟶ 3,493:
=={{header|MATLAB}}==
<syntaxhighlight lang="matlab">
function score = levenshtein(s1, s2)
% score = levenshtein(s1, s2)
Line 3,480 ⟶ 3,524:
score = current_row(end);
end
</syntaxhighlight>
Source : [https://github.com/benhamner/Metrics/blob/master/MATLAB/metrics/levenshtein.m]
=={{header|MiniScript}}==
In the Mini Micro environment, this function is part of the stringUtil library module, and can be used like so:
<
print "kitten".editDistance("sitting")</
In environments where the stringUtil module is not available, you'd have to define it yourself:
<
n = self.len
m = s2.len
Line 3,528 ⟶ 3,572:
end function
print "kitten".editDistance("sitting")</
{{out}}
<pre>3</pre>
=={{header|Modula-2}}==
<
FROM InOut IMPORT WriteString, WriteCard, WriteLn;
FROM Strings IMPORT Length;
Line 3,588 ⟶ 3,630:
ShowDistance("kitten", "sitting");
ShowDistance("rosettacode", "raisethysword");
END LevenshteinDistance.</
{{out}}
<pre>kitten -> sitting: 3
Line 3,595 ⟶ 3,637:
=={{header|NetRexx}}==
{{trans|ooRexx}}
<
options replace format comments java crossref symbols nobinary
Line 3,647 ⟶ 3,689:
return d[m + 1, n + 1]
</syntaxhighlight>
'''Output:'''
<pre>
Line 3,656 ⟶ 3,698:
=={{header|Nim}}==
Nim provides a function in module "std/editdistance" to compute the Levenshtein distance between two strings containing ASCII characters only or containing UTF-8 encoded Unicode runes.
<
echo editDistanceAscii("kitten", "sitting")
echo editDistanceAscii("rosettacode", "raisethysword")</
{{out}}
Line 3,667 ⟶ 3,709:
{{trans|Python}}
Here is a translation of the Python version.
<
func min(a, b, c: int): int {.inline.} = min(a, min(b, c))
Line 3,691 ⟶ 3,733:
echo levenshteinDistance("kitten","sitting")
echo levenshteinDistance("rosettacode","raisethysword")</
=={{header|Oberon-2}}==
{{trans|Modula-2}}
<syntaxhighlight lang="oberon2">MODULE LevesteinDistance;
IMPORT Out,Strings;
PROCEDURE Levestein(s,t:ARRAY OF CHAR):LONGINT;
CONST
maxlen = 15;
VAR
d:ARRAY maxlen,maxlen OF LONGINT;
lens,lent,i,j:LONGINT;
PROCEDURE Min(a,b:LONGINT):LONGINT;
BEGIN
IF a < b THEN RETURN a ELSE RETURN b END
END Min;
BEGIN
lens := Strings.Length(s);
lent := Strings.Length(t);
IF lens = 0 THEN RETURN lent
ELSIF lent = 0 THEN RETURN lens
ELSE
FOR i := 0 TO lens DO d[i,0] := i END;
FOR j := 0 TO lent DO d[0,j] := j END;
FOR i := 1 TO lens DO
FOR j := 1 TO lent DO
IF s[i-1] = t[j-1] THEN
d[i,j] := d[i-1,j-1]
ELSE
d[i,j] := Min((d[i-1,j] + 1),
Min(d[i,j-1] + 1, d[i-1,j-1] + 1));
END
END
END
END;
RETURN d[lens,lent];
END Levestein;
PROCEDURE ShowDistance(s,t:ARRAY OF CHAR);
BEGIN
Out.String(s);
Out.String(" -> ");
Out.String(t);
Out.String(": ");
Out.Int(Levestein(s,t),0);
Out.Ln
END ShowDistance;
BEGIN
ShowDistance("kitten", "sitting");
ShowDistance("rosettacode", "raisethysword");
END LevesteinDistance.
</syntaxhighlight>
{{out}}
<pre>kitten -> sitting: 3
rosettacode -> raisethysword: 8
</pre>
=={{header|Objeck}}==
{{trans|C#}}
<
function : Main(args : String[]) ~ Nil {
if(args->Size() = 2) {
Line 3,728 ⟶ 3,831:
return d[s->Size(), t->Size()];
}
}</
=={{header|Objective-C}}==
Translation of the C# code into a NSString category
<
- (NSUInteger)levenshteinDistanceToString:(NSString *)string;
@end
Line 3,766 ⟶ 3,869:
return r;
}
@end</
=={{header|OCaml}}==
Translation of the pseudo-code of the Wikipedia article:
<
min a (min b c)
Line 3,810 ⟶ 3,913:
test "kitten" "sitting";
test "rosettacode" "raisethysword";
;;</
=== A recursive functional version ===
This could be made faster with memoization
<
let rec dist i j = match (i,j) with
| (i,0) -> i
Line 3,829 ⟶ 3,932:
let () =
test "kitten" "sitting";
test "rosettacode" "raisethysword";</
{{out}}
<pre>
Line 3,837 ⟶ 3,940:
=={{header|ooRexx}}==
<syntaxhighlight lang="oorexx">
say "kitten -> sitting:" levenshteinDistance("kitten", "sitting")
say "rosettacode -> raisethysword:" levenshteinDistance("rosettacode", "raisethysword")
Line 3,884 ⟶ 3,987:
return d[m + 1, n + 1 ]
</syntaxhighlight>
Output:
<pre>
Line 3,894 ⟶ 3,997:
{{trans|JavaScript}}
{{Works with|PARI/GP|2.7.4 and above}}
<
\\ Levenshtein distance between two words
\\ 6/21/16 aev
Line 3,918 ⟶ 4,021:
levensDist("X","oX");
}
</
{{Output}}
Line 3,932 ⟶ 4,035:
=={{header|Pascal}}==
A fairly direct translation of the wikipedia pseudo code:
<
uses
Line 3,969 ⟶ 4,072:
s2 := 'raisethysword';
writeln('The Levenshtein distance between "', s1, '" and "', s2, '" is: ', LevenshteinDistance(s1, s2));
end.</
{{out}}
<pre>
Line 3,978 ⟶ 4,081:
=={{header|Perl}}==
Recursive algorithm, as in the C sample. You are invited to comment out the line where it says so, and see the speed difference. By the way, there's the <code>Memoize</code> standard module, but it requires setting quite a few parameters to work right for this example, so I'm just showing the simple minded caching scheme here.
<
my %cache;
Line 4,002 ⟶ 4,105:
}
print leven('rosettacode', 'raisethysword'), "\n";</
Iterative solution:
<
sub leven {
Line 4,028 ⟶ 4,131:
}
print leven('rosettacode', 'raisethysword'), "\n";</
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
Line 4,072 ⟶ 4,175:
<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: #000000;">0</span><span style="color: #0000FF;">}}</span>
<span style="color: #7060A8;">papply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">test</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span>
<!--</
{{out}}
<pre>
Line 4,086 ⟶ 4,189:
=== alternative ===
Modelled after the Processing code, uses a single/smaller array, passes the same tests as above.
<!--<
<span style="color: #008080;">function</span> <span style="color: #000000;">levenshtein</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: #004080;">sequence</span> <span style="color: #000000;">costs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</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><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
Line 4,101 ⟶ 4,204:
<span style="color: #008080;">return</span> <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: #008080;">end</span> <span style="color: #008080;">function</span>
<!--</
=={{header|PHP}}==
<syntaxhighlight lang="php">
echo levenshtein('kitten','sitting');
echo levenshtein('rosettacode', 'raisethysword');
</syntaxhighlight>
{{out}}
Line 4,114 ⟶ 4,217:
=={{header|Picat}}==
===Iterative===
Based on the iterative algorithm at Wikipedia. Picat is 1-based so some adjustments are needed.
<
M = 1+S.length,
N = 1+T.length,
Line 4,141 ⟶ 4,244:
end,
Dist = D[M,N].</
===Tabled recursive version===
<
levenshtein_rec(S,T) = Dist =>
Dist1 = 0,
Line 4,161 ⟶ 4,264:
Dist1 := A + 1
end,
Dist = Dist1.</
===Mode-directed tabling===
{{trans|Prolog}}
<syntaxhighlight lang="picat">
levenshtein_mode(S,T) = Dist =>
lev(S, T, Dist).
Line 4,174 ⟶ 4,277:
lev([_|L], [_|R], D) :- lev(L, R, H), D is H+1.
lev([_|L], R, D) :- lev(L, R, H), D is H+1.
lev(L, [_|R], D) :- lev(L, R, H), D is H+1.</
===Test===
<
S = [
Line 4,196 ⟶ 4,299:
nl
end,
nl.</
{{out}}
Line 4,227 ⟶ 4,330:
===Benchmark on larger strings===
Benchmarking the methods with larger strings of random lengths (between 1 and 2000).
<
_ = random2(),
Len = 2000,
Line 4,250 ⟶ 4,353:
Alpha = "abcdefghijklmnopqrstuvxyz",
Len = Alpha.length,
S := [Alpha[random(1,Len)] : _ in 1..random(1,MaxLen)].</
Here is sample run. The version using mode-directed tabling is clearly the fastest.
Line 4,270 ⟶ 4,373:
=={{header|PicoLisp}}==
Translation of the pseudo-code in the Wikipedia article:
<
(let D
(cons
Line 4,287 ⟶ 4,390:
(get D J (inc I))
(get D (inc J) I)
(get D J I) ) ) ) ) ) ) ) )</
or, using 'map' to avoid list indexing:
<
(let D
(cons
Line 4,308 ⟶ 4,411:
(cadr Y) ) )
B
D ) ) )</
{{out|Output (both cases)}}
<pre>: (levenshtein (chop "kitten") (chop "sitting"))
Line 4,315 ⟶ 4,418:
=={{header|PL/I}}==
===version 1===
<
lsht: Proc Options(main);
Call test('kitten' ,'sitting');
Line 4,370 ⟶ 4,473:
Return(ld);
End;
End;</
{{out}}
<pre> 1st string = >kitten<
Line 4,396 ⟶ 4,499:
Levenshtein distance = 3</pre>
===version 2 recursive with memoization===
<
ld3: Proc Options(main);
Dcl ld(0:30,0:30) Bin Fixed(31);
Line 4,440 ⟶ 4,543:
Return(ld(sl,tl));
End;
End;</
Output is the same as for version 1.
Line 4,446 ⟶ 4,549:
{{works with|8080 PL/M Compiler}} ... under CP/M (or an emulator)
{{Trans|Action!}}
<
/* TRANS:ATED FROM THE ACTION! SAMPLE */
Line 4,545 ⟶ 4,648:
CALL TEST( .( 'ACTION', 33, '$' ), .'PL/M$' );
EOF</
{{out}}
<pre>
Line 4,556 ⟶ 4,659:
=={{header|PowerShell}}==
This version does not allow empty strings.
<syntaxhighlight lang="powershell">
function Get-LevenshteinDistance
{
Line 4,616 ⟶ 4,719:
$outputObject
}
</syntaxhighlight>
<syntaxhighlight lang="powershell">
Get-LevenshteinDistance "kitten" "sitting"
Get-LevenshteinDistance rosettacode raisethysword
</syntaxhighlight>
{{Out}}
<pre>
Line 4,630 ⟶ 4,733:
=={{header|Processing}}==
<
println(distance("kitten", "sitting"));
}
Line 4,647 ⟶ 4,750:
}
return costs[b.length()];
}</
==={{header|Processing Python mode}}===
<
println(distance("kitten", "sitting"))
Line 4,667 ⟶ 4,770:
costs[j] = cj
return costs[len(b)]</
=={{header|Prolog}}==
Line 4,673 ⟶ 4,776:
Works with SWI-Prolog.<br>
Based on Wikipedia's pseudocode.
<
length(S, M),
M1 is M+1,
Line 4,733 ⟶ 4,836:
init_n(N, L) :-
nth0(0, L, N).</
{{out|Output examples}}
<pre> ?- levenshtein("kitten", "sitting", R).
Line 4,763 ⟶ 4,866:
=={{header|PureBasic}}==
Based on Wikipedia's pseudocode.
<
Protected m, n, i, j, min, k, l
m = Len(A_string$)
Line 4,791 ⟶ 4,894:
;- Testing
n = LevenshteinDistance("kitten", "sitting")
MessageRequester("Info","Levenshtein Distance= "+Str(n))</
=={{header|Python}}==
===Iterative 1===
Faithful implementation of "Iterative with full matrix" from Wikipedia
<
m = len(str1)
n = len(str2)
Line 4,813 ⟶ 4,916:
print(levenshteinDistance("kitten","sitting"))
print(levenshteinDistance("rosettacode","raisethysword"))</
{{out}}
<pre>3
Line 4,820 ⟶ 4,923:
===Iterative 2===
Implementation of the Wikipedia algorithm, optimized for memory
<
if len(s1) > len(s2):
s1,s2 = s2,s1
Line 4,837 ⟶ 4,940:
print(minimumEditDistance("kitten","sitting"))
print(minimumEditDistance("rosettacode","raisethysword"))</
{{out}}
<pre>3
Line 4,844 ⟶ 4,947:
===Iterative 3===
Iterative space optimized (even bounded)
<
def result(d): return d if mx < 0 else False if d > mx else True
Line 4,885 ⟶ 4,988:
ld('kitten','kittenaaaaaaaaaaaaaaaaa',3), # False
ld('kittenaaaaaaaaaaaaaaaaa','kitten',3) # False
)</
{{out}}
<pre>0 1 2 3 4 8 17 17
Line 4,893 ⟶ 4,996:
====Memoized recursion====
(Uses [http://docs.python.org/dev/library/functools.html?highlight=functools.lru_cache#functools.lru_cache this] cache from the standard library).
<
>>> @lru_cache(maxsize=4095)
def ld(s, t):
Line 4,905 ⟶ 5,008:
>>> print( ld("kitten","sitting"),ld("rosettacode","raisethysword") )
3 8</
====Non-recursive: reduce and scanl====
{{Works with|Python|3.7}}
<
from itertools import (accumulate, chain, islice)
Line 5,055 ⟶ 5,158:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>Levenshtein minimum edit distances:
Line 5,068 ⟶ 5,171:
=={{header|Racket}}==
A memoized recursive implementation.
<
(define (levenshtein a b)
Line 5,087 ⟶ 5,190:
(levenshtein "kitten" "sitting")
(levenshtein "rosettacode" "raisethysword")</
{{out}}
<pre>3
Line 5,096 ⟶ 5,199:
Implementation of the Wikipedia algorithm. Since column 0 and row 0 are used for base distances, the original algorithm would require us to compare "@s[$i-1] eq @t[$j-1]", and reference $m and $n separately. Prepending an unused value (undef) onto @s and @t makes their indices align with the $i,$j numbering of @d, and lets us use .end instead of $m,$n.
<syntaxhighlight lang="raku"
my @s = *, |$s.comb;
my @t = *, |$t.comb;
Line 5,118 ⟶ 5,221:
for <kitten sitting>, <saturday sunday>, <rosettacode raisethysword> -> ($s, $t) {
say "Levenshtein distance('$s', '$t') == ", levenshtein-distance($s, $t)
}</
{{out}}
<pre>Levenshtein distance('kitten', 'sitting') == 3
Levenshtein distance('saturday', 'sunday') == 3
Levenshtein distance('rosettacode', 'raisethysword') == 8</pre>
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
= <Show ('kitten') ('sitting')>
<Show ('rosettacode') ('raisethysword')>;
};
Show {
(e.A) (e.B) = <Prout e.A ' -> ' e.B ': ' <Lev (e.A) (e.B)>>;
};
Lev {
(e.A) (), <Lenw e.A>: s.L e.A = s.L;
() (e.B), <Lenw e.B>: s.L e.B = s.L;
(s.C e.A) (s.C e.B) = <Lev (e.A) (e.B)>;
(e.A) (e.B), e.A: s.HA e.LA, e.B: s.HB e.LB =
<+ 1 <Min <Lev (e.LA) (e.B)>
<Lev (e.A) (e.LB)>
<Lev (e.LA) (e.LB)>>>;
}
Min {
s.N = s.N;
s.M s.N e.X, <Compare s.M s.N>: {
'-' = <Min s.M e.X>;
s.X = <Min s.N e.X>;
};
};</syntaxhighlight>
{{out}}
<pre>kitten -> sitting: 3
rosettacode -> raisethysword: 8</pre>
=={{header|REXX}}==
===version 1===
As per the task's requirements, this version includes a driver to display the results.
<
call Levenshtein 'kitten' , "sitting"
call Levenshtein 'rosettacode' , "raisethysword"
Line 5,146 ⟶ 5,280:
end /*k*/
end /*j*/ /* [↑] best choice.*/
say ' Levenshtein distance = ' @.oL.tL; say; return</
{{out|output|text= when using the internal default inputs:}}
<pre>
Line 5,172 ⟶ 5,306:
===version 2===
<strike>same as</strike> Similar to version 1 <strike>(but does not include a driver for testing)</strike>, reformatted and commented
<
/*rexx*/
Line 5,226 ⟶ 5,360:
say 'Levenshtein distance = ' d.m.n; say ''
Return d.m.n
</syntaxhighlight>
{{output}}
<pre>
Line 5,280 ⟶ 5,414:
===version 3===
Alternate algorithm from Wikipedia <strike>(but does not include a driver for testing)</strike>.
<
/*rexx*/
Line 5,326 ⟶ 5,460:
End
return v1.tl
</syntaxhighlight>
{{output}}
<pre>
Line 5,356 ⟶ 5,490:
===version 4 (recursive)===
Recursive algorithm from Wikipedia with memoization
<
/*rexx*/
Line 5,399 ⟶ 5,533:
End
Return ld.sl.tl
</syntaxhighlight>
{{output}}
<pre>
Line 5,428 ⟶ 5,562:
=={{header|Ring}}==
<
# Project : Levenshtein distance
Line 5,468 ⟶ 5,602:
levenshteindistance = d[n][m]
return levenshteindistance
</syntaxhighlight>
Output:
<pre>
Line 5,474 ⟶ 5,608:
distance(saturday, sunday) = 3
distance(rosettacode, raisethysword) = 8
</pre>
=={{header|RPL}}==
{{works with|HP|28}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪ DUP2 SIZE SWAP SIZE → a b lb la
≪ '''IF''' la lb * NOT '''THEN''' la lb +
'''ELSE'''
a 2 la SUB b 2 lb SUB DUP2 <span style="color:blue">LEV</span>
'''IF''' a 1 1 SUB b 1 1 SUB == '''THEN'''
ROT ROT DROP2
'''ELSE'''
a ROT <span style="color:blue">LEV</span> ROT b <span style="color:blue">LEV</span>
MIN MIN 1 +
'''END END'''
≫ ≫ '<span style="color:blue">LEV</span>' STO
|
<span style="color:blue">LEV</span> ''( "a" "b" → distance )''
if |a|=0 or [b|=0 then return resp. [b| or |a|
else
put tail(a), tail(b) and lev(tail(a),tail(b)) in stack
if a[1]=b[1} then
clean stack and return lev(tail(a),tail(b))
else
put lev(a,tail(b)) and lev(tail(a),b) in stack
return min of the 3 values in stack and add 1
|}
"kitten" "sitting" <span style="color:blue">LEV</span>
"Summer" "Winter" <span style="color:blue">LEV</span>
"Levenshtein" "Levenshtein" <span style="color:blue">LEV</span>
{{out}}
<pre>
3: 3
2: 4
1: 0
</pre>
===Iterative implementation (Wagner-Fischer algorithm)===
index of arrays and strings start with 1 in RPL, so the main trick in translating the algorithm given by Wikipedia was to manage the offsets properly. The distance between "rosettacode" and "raisethysword" is within the reach of a calculator (emulated or not), unlike the above recursive approach.
{{works with|HP|48}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪
DUP2 { } + + ≪ SIZE ≫ DOLIST 1 ADD 0 CON → a b d
≪ 1 a SIZE '''FOR''' h
'd' h 1 + 1 2 →LIST h PUT '''NEXT'''
1 b SIZE '''FOR''' j
'd' 1 j 1 + 2 →LIST j PUT '''NEXT'''
1 b SIZE '''FOR''' j
1 a SIZE '''FOR''' h
a h DUP SUB b j DUP SUB ≠
'd' h j 2 →LIST GET +
'd' h j 1 + 2 →LIST GET 1 +
'd' h 1 + j 2 →LIST GET 1 +
MIN MIN 'd' h 1 + j 1 + 2 →LIST ROT PUT
'''NEXT NEXT'''
'd' DUP SIZE GET
≫ ≫ '<span style="color:blue">LEV2</span>' STO
|
<span style="color:blue">LEV2</span> ''( "a" "b" → distance )''
declare int d[0..m, 0..n] and set each element in d to zero
for h from 1 to m: <span style="color:grey>// h replaces i, which is √-1 in RPL</span>
d[h, 0] := i <span style="color:grey>// RPL array indexes start with 1</span>
for j from 1 to n:
d[0, j] := j
for j from 1 to n:
for h from 1 to m:
substitutionCost := ( s[h] <> t[j] )
d[h, j] := minimum(d[h-1, j-1] + substitutionCost,
d[h-1, j] + 1,
d[h, j-1] + 1)
return d[m, n]
|}
"rosettacode" "raisethysword" <span style="color:blue">LEV2</span>
{{out}}
<pre>
1: 8
</pre>
Line 5,481 ⟶ 5,705:
and for <code>k >= j</code> contains ''lev(i-1, k)''. The inner loop body restores the invariant for the
new value of <code>j</code>.
<
def self.distance(a, b)
Line 5,503 ⟶ 5,727:
end
Levenshtein.test</
{{out}}
<pre>
Line 5,512 ⟶ 5,736:
A variant can be found used in Rubygems [https://github.com/rubygems/rubygems/blob/master/lib/rubygems/text.rb]
<
n = str1.length
m = str2.length
Line 5,545 ⟶ 5,769:
%w{kitten sitting saturday sunday rosettacode raisethysword}.each_slice(2) do |a, b|
puts "distance(#{a}, #{b}) = #{levenshtein_distance(a, b)}"
end</
same output
=={{header|Run BASIC}}==
<
print levenshteinDistance("rosettacode", "raisethysword")
end
Line 5,580 ⟶ 5,804:
levenshteinDistance = d(n, m)
[ex]
end function</
8</pre>
Line 5,586 ⟶ 5,810:
Implementation of the wikipedia algorithm.
{{works with|Rust|1.45}}
<
println!("{}", levenshtein_distance("kitten", "sitting"));
println!("{}", levenshtein_distance("saturday", "sunday"));
Line 5,617 ⟶ 5,841:
}
matrix[word2_length-1][word1_length-1]
}</
{{out}}
<pre>3
Line 5,625 ⟶ 5,849:
=={{header|Scala}}==
===Translated Wikipedia algorithm.===
<
def distance(s1: String, s2: String): Int = {
Line 5,648 ⟶ 5,872:
printDistance("rosettacode", "raisethysword")
}</
{{out}}
<pre>kitten -> sitting : 3
Line 5,654 ⟶ 5,878:
===Functional programmed, memoized===
{{Out}}Best seen running in your browser either by [https://scalafiddle.io/sf/zj7bHC7/0 (ES aka JavaScript, non JVM)] or [https://scastie.scala-lang.org/qHhDWl68QgWv1uwOYzzNqw Scastie (remote JVM)].
<
import scala.collection.parallel.ParSeq
Line 5,687 ⟶ 5,911:
printDistance("sleep", "fleeting")
}</
=={{header|Scheme}}==
Line 5,693 ⟶ 5,917:
Recursive version from wikipedia article.
<
(define (levenshtein s t)
(define (%levenshtein s sl t tl)
Line 5,707 ⟶ 5,931:
(string->list t)
(string-length t)))
</syntaxhighlight>
{{out}}
Line 5,718 ⟶ 5,942:
=={{header|Seed7}}==
<
const func integer: levenshteinDistance (in string: s, in string: t) is func
Line 5,749 ⟶ 5,973:
writeln("kitten -> sitting: " <& levenshteinDistance("kitten", "sitting"));
writeln("rosettacode -> raisethysword: " <& levenshteinDistance("rosettacode", "raisethysword"));
end func;</
{{out}}
Line 5,759 ⟶ 5,983:
=={{header|SenseTalk}}==
SenseTalk has a built-in TextDifference function for this.
<syntaxhighlight lang="sensetalk">
put textDifference("kitten", "sitting") // --> 3
put textDifference("rosettacode", "raisethysword") // --> 8
</syntaxhighlight>
=={{header|SequenceL}}==
This implementation is based on the "Iterative with two matrix rows" version on Wikipedia.
<syntaxhighlight lang="sequencel">
import <Utilities/Sequence.sl>;
import <Utilities/Math.sl>;
Line 5,789 ⟶ 6,013:
min(min(v1[n] + 1, v0[n + 1] + 1), v0[n] + (0 when s = t[n] else 1))),
n + 1);
</syntaxhighlight>
=={{header|SETL}}==
<syntaxhighlight lang="setl">program levenshtein_distance;
tests := {['kitten', 'sitting'], ['rosettacode', 'raisethysword']};
loop for dest = tests(src) do
print(src + ' -> ' + dest + ': ' + str levenshtein(src, dest));
end loop;
proc levenshtein(s, t);
d := {};
loop for i in [1..#s] do
d(i,0) := i;
end loop;
loop for j in [1..#t] do
d(0,j) := j;
end loop;
loop for j in [1..#t] do
loop for i in [1..#s] do
d(i,j) := min/[
(d(i-1,j) ? 0) + 1,
(d(i,j-1) ? 0) + 1,
(d(i-1,j-1) ? 0) + if s(i) = t(j) then 0 else 1 end
];
end loop;
end loop;
return d(#s, #t);
end proc;
end program;</syntaxhighlight>
{{out}}
<pre>kitten -> sitting: 3
rosettacode -> raisethysword: 8</pre>
=={{header|Sidef}}==
===Recursive===
<
s || return t.len
t || return s.len
var s1 = s.
var t1 = t.
s[0] == t[0] ? __FUNC__(s1, t1)
Line 5,807 ⟶ 6,061:
__FUNC__(s1, t )
)
}</
===Iterative===
<
var d = [@(0 .. t.len), s.len.of {[_]}...]
for i,j in (^s ~X ^t) {
Line 5,820 ⟶ 6,074:
}
d[-1][-1]
}</
Calling the function:
<
say lev(%c'rosettacode', %c'raisethysword'); # prints: 8</
=={{header|Simula}}==
<
INTEGER PROCEDURE LEVENSHTEINDISTANCE(S1, S2); TEXT S1, S2;
Line 5,863 ⟶ 6,117:
END
</syntaxhighlight>
{{out}}
<pre>
Line 5,875 ⟶ 6,129:
{{works with|Smalltalk/X}}
ST/X provides a customizable levenshtein method in the String class (weights for individual operations can be passed in):
<
'rosettacode' levenshteinTo: 'raisethysword' s:1 k:1 c:1 i:1 d:1 -> 8</
=={{header|Swift}}==
Line 5,882 ⟶ 6,136:
Version using entire matrix:
<
let (t, s) = (w1.characters, w2.characters)
Line 5,896 ⟶ 6,150:
}
return mat.last!.last!
}</
Version using only two rows at a time:
<
let (t, s) = (w1.characters, w2.characters)
Line 5,915 ⟶ 6,169:
}
return last.last!
}</
===Single array version===
{{trans|C++}}
<
let m = string1.count
let n = string2.count
Line 5,945 ⟶ 6,199:
}
print(levenshteinDistance(string1: "rosettacode", string2: "raisethysword"))</
{{out}}
Line 5,953 ⟶ 6,207:
=={{header|Tcl}}==
<
# Edge cases
if {![set n [string length $t]]} {
Line 5,981 ⟶ 6,235:
# The score is at the end of the last-computed row
return [lindex $p end]
}</
{{out|Usage}}
<
=={{header|TSE SAL}}==
<
INTEGER PROC FNMathGetDamerauLevenshteinDistanceI( STRING s1, STRING s2 )
INTEGER L1 = Length( s1 )
Line 6,020 ⟶ 6,274:
s2 = "altruistic"
Warn( "Minimum amount of steps to convert ", s1, " to ", s2, " = ", FNMathGetDamerauLevenshteinDistanceI( s1, s2 ) ) // gives e.g. 6
END</
=={{header|Turbo-Basic XL}}==
<
10 DIM Word_1$(20), Word_2$(20), DLDm(21, 21)
11 CLS
Line 6,059 ⟶ 6,313:
11846 ? "Damerau Distance=";Result
11850 ENDPROC
</syntaxhighlight>
{{out}}
<pre>kitten, sitting: 3
Line 6,066 ⟶ 6,320:
=={{header|TUSCRIPT}}==
<
$$ MODE TUSCRIPT
distance=DISTANCE ("kitten", "sitting")
PRINT distance
</syntaxhighlight>
Output:
<pre>
Line 6,078 ⟶ 6,332:
=={{header|TypeScript}}==
{{Trans|JavaScript}}
<
function levenshtein(a: string, b: string): number {
const m: number = a.length,
Line 6,094 ⟶ 6,348:
}
</syntaxhighlight>
=={{header|uBasic/4tH}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="ubasic-4th">
' Uses the "iterative with two matrix rows" algorithm
' referred to in the Wikipedia article.
' create two integer arrays of distances
Dim @u(128) ' previous
Dim @v(128) ' current
Print "'kitten' to 'sitting' => ";
Print FUNC(_Levenshtein ("kitten", "sitting"))
Print "'rosettacode' to 'raisethysword' => ";
Print FUNC(_Levenshtein ("rosettacode", "raisethysword"))
Print "'sleep' to 'fleeting' => ";
Print FUNC(_Levenshtein ("sleep", "fleeting"))
End
_Levenshtein
Param (2)
Local (3)
' degenerate cases
If Comp(a@, b@) = 0 Then Return (0)
If Len(a@) = 0 Then Return (Len(b@))
If Len(b@) = 0 Then Return (Len(a@))
' initialize v0
For c@ = 0 To Len(b@)
@u(c@) = c@
Next
For c@ = 0 To Len(a@) - 1
' calculate @v() from @u()
@v(0) = c@ + 1
For d@ = 0 To Len(b@) - 1
e@ = IIf(Peek (a@, c@) = Peek (b@, d@), 0, 1)
@v(d@ + 1) = min(@v(d@) + 1, Min(@u(d@ + 1) + 1, @u(d@) + e@))
Next
' copy @v() to @u() for next iteration
For d@ = 0 To Len(b@)
@u(d@) = @v(d@)
Next
Next
Return (@v(Len(b@)))
</syntaxhighlight>
=={{header|Uiua}}==
<syntaxhighlight lang="uiua">
Lev ← |1 memo(
±/↧≡◇⧻.
⨬(
/↥≡◇⧻ # If either is zero, return length of other
| /≍≡◇⊢. # Both start with same letter?
⨬(
# NO: 1 + min(Lev of (tail a, tail b), (tail a, b), (a, tail b))
+1/↧≡Lev[⊃(⍚↘1|⍜⊢⍚↘1|⍜(⊡1|⍚↘1))]
|
Lev ⍚↘1 # YES: = Lev of (tail a, tail b)
)
)
)
Lev {"kitten" "sitting"}
Lev {"rosettacode" "raisethysword"}
</syntaxhighlight>
{{out}}
<pre>
3
8
</pre>
=={{header|Vala}}==
<
public static int compute (owned string s, owned string t, bool case_sensitive = false) {
var n = s.length;
Line 6,123 ⟶ 6,453:
}
}
</syntaxhighlight>
=={{header|VBA}}==
{{trans|Phix}}<
Function levenshtein(s1 As String, s2 As String) As Integer
Dim n As Integer: n = Len(s1) + 1
Line 6,166 ⟶ 6,496:
Debug.Print levenshtein("kitten", "sitting")
Debug.Print levenshtein("rosettacode", "raisethysword")
End Sub</
<pre> 3
8 </pre>
=={{header|VBScript}}==
<
Function Min(a,b)
Line 6,214 ⟶ 6,544:
PrintLevenshtein "rosettacode", "raisethysword"
PrintLevenshtein "saturday", "sunday"
PrintLevenshtein "sleep", "fleeting"</
{{out}}
<pre>
Line 6,231 ⟶ 6,561:
{{works with|VBA|6.5}}
{{works with|VBA|7.1}}
<
If x < y Then
min = x
Line 6,291 ⟶ 6,621:
Debug.Print "'sleep' to 'fleeting' => "; levenshtein("sleep", "fleeting")
End Sub
</syntaxhighlight>
{{out}}
<pre>
'kitten' to 'sitting' => 3
'sitting' to 'kitten' => 3
'rosettacode' to 'raisethysword' => 8
'sleep' to 'fleeting' => 5
</pre>
=={{header|Visual Basic .NET}}==
<
Dim Matrix(String1.Length, String2.Length) As Integer
Dim Key As Integer
Line 6,318 ⟶ 6,650:
Next
Return Matrix(String1.Length - 1, String2.Length - 1)
End Function</
=={{header|V (Vlang)}}==
<syntaxhighlight lang="Zig">
import strings
fn main() {
println(strings.levenshtein_distance("kitten", "sitting"))
println(strings.levenshtein_distance("rosettacode", "raisethysword"))
}
</syntaxhighlight>
{{out}}
<pre>
3
8
</pre>
=={{header|Wren}}==
{{trans|Go}}
<
var ls = s.count
var lt = t.count
Line 6,346 ⟶ 6,694:
}
System.print(levenshtein.call("kitten", "sitting"))</
{{out}}
Line 6,352 ⟶ 6,700:
3
</pre>
=={{header|Zig}}==
{{trans|C}}
'''Works with:''' 0.11.x, 0.12.0-dev.1381+61861ef39
For 0.10.x, replace @min(a, b, c) with std.math.min3(a, b, c).
Recursive method without memoization.
<syntaxhighlight lang="zig">const std = @import("std");
fn levenshtein(s: []const u8, t: []const u8) usize {
// If either string is empty, difference is inserting all chars
// from the other
if (s.len == 0) return t.len;
if (t.len == 0) return s.len;
// If last letters are the same, the difference is whatever is
// required to edit the rest of the strings
if (s[s.len - 1] == t[t.len - 1])
return levenshtein(s[0 .. s.len - 1], t[0 .. t.len - 1]);
// Else try:
// changing last letter of s to that of t; or
// remove last letter of s; or
// remove last letter of t,
// any of which is 1 edit plus editing the rest of the strings
const a = levenshtein(s[0 .. s.len - 1], t[0 .. t.len - 1]);
const b = levenshtein(s, t[0 .. t.len - 1]);
const c = levenshtein(s[0 .. s.len - 1], t);
return @min(a, b, c) + 1;
}
pub fn main() std.fs.File.WriteError!void {
const stdout = std.io.getStdOut();
const stdout_w = stdout.writer();
const s1 = "rosettacode";
const s2 = "raisethysword";
try stdout_w.print("distance between '{s}' and '{s}': {d}\n", .{ s1, s2, levenshtein(s1, s2) });
return;
}</syntaxhighlight>
=={{header|zkl}}==
{{trans|D}}
<
sz2,costs:=s2.len() + 1, List.createLong(sz2,0); // -->zero filled List
foreach i in (s1.len() + 1){
Line 6,372 ⟶ 6,764:
}
costs[-1]
}</
<
T("yo",""), T("","yo"), T("abc","abc")) ){
println(a," --> ",b,": ",levenshtein(a,b));
}</
{{out}}
<pre>
Line 6,387 ⟶ 6,779:
=={{header|ZX Spectrum Basic}}==
<
20 INPUT "first word:",n$
30 INPUT "second word:",m$
Line 6,400 ⟶ 6,792:
120 NEXT i
130 NEXT j
140 PRINT "The Levenshtein distance between """;n$;""", """;m$;""" is ";d(m+1,n+1);"."</
{{out}}
<pre>
|