Levenshtein distance: Difference between revisions
lang -> syntaxhighlight
SqrtNegInf (talk | contribs) m (→{{header|Raku}}: no temp. variable) |
(lang -> syntaxhighlight) |
||
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}}
<lang> "kitten" Levenshtein "sitting"
Line 892:
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 930:
=={{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:
return 0;
}</
Take the above and add caching, we get (in [[C99]]):
<
#include <string.h>
Line 1,019:
return 0;
}</
=={{header|C sharp|C#}}==
This is a straightforward translation of the Wikipedia pseudocode.
<
namespace LevenshteinDistance
Line 1,072:
}
}
}</
{{out|Example output}}
<pre>
Line 1,083:
=={{header|C++}}==
<
#include <iostream>
using namespace std;
Line 1,137:
return 0;
}</
{{out|Example output}}
<pre>
Line 1,145:
===Generic ISO C++ version===
<
#include <iostream>
#include <numeric>
Line 1,184:
<< levenshtein_distance(s0, s1) << std::endl;
return 0;
}</
{{out}}
Line 1,194:
===Recursive Version===
<
(let [len1 (count str1)
len2 (count str2)]
Line 1,206:
(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:
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:
show("kitten", "sitting")
show("rosettacode", "raisethysword")
end start_up</
{{out}}
<pre>kitten => sitting: 3
Line 1,284:
=={{header|COBOL}}==
GnuCobol 2.2
<
identification division.
program-id. Levenshtein.
Line 1,347:
display trim(string-a) " -> " trim(string-b) " = " trim(distance)
.
</syntaxhighlight>
{{out|Output}}
<pre>
Line 1,356:
=={{header|CoffeeScript}}==
<
# more of less ported simple algorithm from JS
m = str1.length
Line 1,385:
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,404:
(leven la lb))))
(print (levenshtein "rosettacode" "raisethysword"))</
{{out}}
<pre>8</pre>
Line 1,410:
=={{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:
{{trans|Ruby 1st version}}
<
def self.distance(a, b)
Line 1,442:
Levenshtein.test
</syntaxhighlight>
{{out}}
<pre>
Line 1,451:
{{trans|Ruby 2nd version}}
<
n, m = str1.size, str2.size
max = n / 2
Line 1,482:
puts "distance(#{a}, #{b}) = #{levenshtein_distance(a, b)}"
end
</syntaxhighlight>
{{out}}
<pre>
Line 1,493:
===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:
===Iterative Version===
{{trans|Java}}
<
int distance(in string s1, in string s2) pure nothrow {
Line 1,534:
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:
lDist("kitten", "sitting").writeln;
lDist("rosettacode", "raisethysword").writeln;
}</
=={{header|Delphi}}==
{{Trans|C#}}
<
program Levenshtein_distanceTest;
Line 1,620:
readln;
end.
</syntaxhighlight>
Line 1,626:
=={{header|DWScript}}==
Based on Wikipedia version
<
var
i, j : Integer;
Line 1,648:
end;
PrintLn(LevenshteinDistance('kitten', 'sitting'));</
=={{header|Dyalect}}==
<
var n = s.Length()
var m = t.Length()
Line 1,695:
}
run("rosettacode", "raisethysword")</
{{out}}
Line 1,702:
=={{header|EchoLisp}}==
<
;; Recursive version adapted from Clojure
;; Added necessary memoization
Line 1,731:
(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:
=={{header|Elixir}}==
{{trans|Ruby}}
<
def distance(a, b) do
ta = String.downcase(a) |> to_charlist |> List.to_tuple
Line 1,777:
Enum.each(Enum.chunk(words, 2), fn [a,b] ->
IO.puts "distance(#{a}, #{b}) = #{Levenshtein.distance(a,b)}"
end)</
{{out}}
Line 1,788:
=={{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:
{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:
71> timer:tc(levenshtein,distance_cached,["kitten","sitting"]).
{213,3}
</syntaxhighlight>
=={{header|ERRE}}==
<
PROGRAM LEVENSHTEIN
Line 1,882:
!$ERASE D%
END PROGRAM
</syntaxhighlight>
{{out}}<pre>
'kitten' -> 'sitting' has distance 3
Line 1,890:
=={{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:
? levenshtein("kitten", "sitting")
? levenshtein("rosettacode", "raisethysword")</
{{out}}
<pre>3
Line 1,944:
=={{header|F_Sharp|F#}}==
=== Standard version ===
<
open System
Line 1,977:
Console.ReadKey () |> ignore
</syntaxhighlight>
=== Recursive Version ===
<
open System
Line 2,003:
printfn "dist(kitten, sitting) = %i" (levenshtein "kitten" "sitting")
</syntaxhighlight>
=={{header|Factor}}==
<
"kitten" "sitting" levenshtein .</
{{out}}
<pre>
Line 2,015:
=={{header|Forth}}==
{{trans|C}}
<
dup \ if either string is empty, difference
if \ is inserting all chars from the other
Line 2,037:
s" kitten" s" sitting" levenshtein . cr
s" rosettacode" s" raisethysword" levenshtein . cr</
=={{header|Fortran}}==
<
program demo_edit_distance
character(len=:),allocatable :: sources(:),targets(:)
Line 2,079:
end program demo_edit_distance
</syntaxhighlight>
{{out}}<pre>
kitten sitting 3 T
Line 2,092:
=={{header|FreeBASIC}}==
<
' Uses the "iterative with two matrix rows" algorithm
Line 2,140:
Print
Print "Press any key to quit"
Sleep</
{{out}}
Line 2,151:
=={{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}}==
Based on Wikipedia algorithm. Suitable for Pascal strings.
<
local fn LevenshteinDistance( aStr as Str255, bStr as Str255 ) as long
Line 2,206:
next
HandleEvents</
Output:
Line 2,233:
=={{header|Go}}==
WP algorithm:
<
import "fmt"
Line 2,270:
}
return d[len(s)][len(t)]
}</
{{out}}
<pre>
Line 2,276:
</pre>
{{trans|C}}
<
import "fmt"
Line 2,299:
fmt.Printf("distance between %s and %s: %d\n", s1, s2,
levenshtein(s1, s2))
}</
{{out}}
<pre>
Line 2,306:
=={{header|Groovy}}==
<
def dist = new int[str1.size() + 1][str2.size() + 1]
(0..str1.size()).each { dist[it][0] = it }
Line 2,324:
println "Checking distance(${key[0]}, ${key[1]}) == $dist"
assert distance(key[0], key[1]) == dist
}</
{{out}}
<pre>
Line 2,335:
===Implementation 1===
<
levenshtein s1 s2 = last $ foldl transform [0 .. length s1] s2
where
Line 2,343:
main :: IO ()
main = print (levenshtein "kitten" "sitting")</
{{Out}}
<pre>3</pre>
===Implementation 2===
<
levenshtein s1 [] = length s1
levenshtein [] s2 = length s2
Line 2,359:
main :: IO ()
main = print (levenshtein "kitten" "sitting")</
{{Out}}
<pre>3</pre>
=={{header|Icon}} and {{header|Unicon}}==
<
every process(!&input)
end
Line 2,384:
return d[n,m]-1
end</
{{out|Example}}
<pre>
Line 2,400:
Io> "rosettacode" levenshtein("raisethysword")
==> 8
Io> </
=={{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:
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:
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:
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:
=={{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:
System.out.println("distance(" + data[i] + ", " + data[i+1] + ") = " + distance(data[i], data[i+1]));
}
}</
{{out}}
<pre>distance(kitten, sitting) = 3
Line 2,485:
</pre>
{{trans|C}}
<
public static int levenshtein(String s, String t){
/* if either string is empty, difference is inserting all chars
Line 2,530:
+ levenshtein(sb1.reverse().toString(), sb2.reverse().toString()));
}
}</
{{out}}
<pre>distance between 'kitten' and 'sitting': 3
Line 2,538:
===Iterative space optimized (even bounded) ===
{{trans|Python}}
<
import static java.lang.Math.abs;
import static java.lang.Math.max;
Line 2,612:
}
}
</syntaxhighlight>
{{out}}
<pre>
Line 2,622:
===ES5===
Iterative:
<
var t = [], u, i, j, m = a.length, n = b.length;
if (!m) { return n; }
Line 2,652:
console.log('levenstein("' + a + '","' + b + '") was ' + d + ' should be ' + t);
}
});</
===ES6===
Line 2,658:
By composition of generic functions:
<
'use strict';
Line 2,800:
// MAIN ---
return JSON.stringify(main())
})();</
{{Out}}
<pre>[3, 3, 8, 8]</pre>
Line 2,817:
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:
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:
(["edocattesor", "drowsyhtesiar"] | demo),
(["this_algorithm_is_similar_to",
"Damerau-Levenshtein_distance"] | demo)</
{{Out}}
levenshteinDistance between kitten and sitting is 3
Line 2,886:
=={{header|Jsish}}==
From Javascript, ES5 entry.
<
function levenshtein(a, b) {
Line 2,930:
levenshtein('mississippi', 'swiss miss') ==> 8
=!EXPECTEND!=
*/</
{{out}}
<pre>prompt$ jsish -u levenshtein.jsi
Line 2,939:
'''Recursive''':
{{works with|Julia|1.0}}
<
ls, lt = length.((s, t))
ls == 0 && return lt
Line 2,950:
@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:
end
return dist[end]
end</
Let's see some benchmark:
<
println("\n# levendist(kitten, sitting)")
s, t = "kitten", "sitting"
Line 2,989:
@btime levendist(s, t)
println(" - Iterative:")
@btime levendist1(s, t)</
{{out}}
Line 3,007:
=={{header|Kotlin}}==
===Standard Version===
<
// Uses the "iterative with two matrix rows" algorithm referred to in the Wikipedia article.
Line 3,039:
println("'rosettacode' to 'raisethysword' => ${levenshtein("rosettacode", "raisethysword")}")
println("'sleep' to 'fleeting' => ${levenshtein("sleep", "fleeting")}")
}</
{{out}}
Line 3,049:
===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:
}
</syntaxhighlight>
{{out}}
<pre>
Line 3,083:
Suitable for short strings:
<
(defun levenshtein-simple
(('() str)
Line 3,097:
(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:
> (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:
=== Cached Implementation ===
<
(defun levenshtein-distance (str1 str2)
(let (((tuple distance _) (levenshtein-distance
Line 3,143:
(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:
> (levenshtein-distance "rosettacode" "raisethysword")
8
</syntaxhighlight>
=={{header|Liberty BASIC}}==
<
'08/19/10
'from http://www.merriampark.com/ld.htm#VB
Line 3,206:
Next i
LevenshteinDistance = d(n, m)
End Function </
=={{header|Limbo}}==
{{trans|Go}}
<
include "sys.m"; sys: Sys;
Line 3,257:
return a + 1;
}
</syntaxhighlight>
{{output}}
Line 3,268:
=={{header|LiveCode}}==
{{trans|Go}}
<
//Code By Neurox66
function Levenshtein pString1 pString2
Line 3,292:
put Levenshtein("kitten","sitting")
put Levenshtein("rosettacode","raisethysword")
</syntaxhighlight>
{{out}}
<pre>3
Line 3,299:
=={{header|Lobster}}==
{{trans|C}}
<
def makeNxM(n: int, m: int, v: int) -> [[int]]:
Line 3,334:
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:
print(leven("kitten", "sitting"))
print(leven("rosettacode", "raisethysword"))</
{{out}}
<pre>3
Line 3,362:
=={{header|M2000 Interpreter}}==
<
Module Checkit {
\\ Iterative with two matrix rows
Line 3,429:
}
Checkit2
</syntaxhighlight>
=={{header|Maple}}==
<
> with(StringTools):
> Levenshtein("kitten","sitting");
Line 3,439:
> Levenshtein("rosettacode","raisethysword");
8
</syntaxhighlight>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
EditDistance["rosettacode","raisethysword"]</
{{out}}
<pre>3
Line 3,449:
=={{header|MATLAB}}==
<
function score = levenshtein(s1, s2)
% score = levenshtein(s1, s2)
Line 3,480:
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:
end function
print "kitten".editDistance("sitting")</
'''Output:'''
Line 3,536:
=={{header|Modula-2}}==
<
FROM InOut IMPORT WriteString, WriteCard, WriteLn;
FROM Strings IMPORT Length;
Line 3,588:
ShowDistance("kitten", "sitting");
ShowDistance("rosettacode", "raisethysword");
END LevenshteinDistance.</
{{out}}
<pre>kitten -> sitting: 3
Line 3,595:
=={{header|NetRexx}}==
{{trans|ooRexx}}
<
options replace format comments java crossref symbols nobinary
Line 3,647:
return d[m + 1, n + 1]
</syntaxhighlight>
'''Output:'''
<pre>
Line 3,656:
=={{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:
{{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:
echo levenshteinDistance("kitten","sitting")
echo levenshteinDistance("rosettacode","raisethysword")</
=={{header|Objeck}}==
{{trans|C#}}
<
function : Main(args : String[]) ~ Nil {
if(args->Size() = 2) {
Line 3,728:
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:
return r;
}
@end</
=={{header|OCaml}}==
Translation of the pseudo-code of the Wikipedia article:
<
min a (min b c)
Line 3,810:
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:
let () =
test "kitten" "sitting";
test "rosettacode" "raisethysword";</
{{out}}
<pre>
Line 3,837:
=={{header|ooRexx}}==
<
say "kitten -> sitting:" levenshteinDistance("kitten", "sitting")
say "rosettacode -> raisethysword:" levenshteinDistance("rosettacode", "raisethysword")
Line 3,884:
return d[m + 1, n + 1 ]
</syntaxhighlight>
Output:
<pre>
Line 3,894:
{{trans|JavaScript}}
{{Works with|PARI/GP|2.7.4 and above}}
<
\\ Levenshtein distance between two words
\\ 6/21/16 aev
Line 3,918:
levensDist("X","oX");
}
</
{{Output}}
Line 3,932:
=={{header|Pascal}}==
A fairly direct translation of the wikipedia pseudo code:
<
uses
Line 3,969:
s2 := 'raisethysword';
writeln('The Levenshtein distance between "', s1, '" and "', s2, '" is: ', LevenshteinDistance(s1, s2));
end.</
{{out}}
<pre>
Line 3,978:
=={{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:
}
print leven('rosettacode', 'raisethysword'), "\n";</
Iterative solution:
<
sub leven {
Line 4,028:
}
print leven('rosettacode', 'raisethysword'), "\n";</
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
Line 4,072:
<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:
=== 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:
<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}}==
<
echo levenshtein('kitten','sitting');
echo levenshtein('rosettacode', 'raisethysword');
</syntaxhighlight>
{{out}}
Line 4,116:
==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:
end,
Dist = D[M,N].</
===Tabled recursive version===
<
levenshtein_rec(S,T) = Dist =>
Dist1 = 0,
Line 4,161:
Dist1 := A + 1
end,
Dist = Dist1.</
===Mode-directed tabling===
{{trans|Prolog}}
<
levenshtein_mode(S,T) = Dist =>
lev(S, T, Dist).
Line 4,174:
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:
nl
end,
nl.</
{{out}}
Line 4,227:
===Benchmark on larger strings===
Benchmarking the methods with larger strings of random lengths (between 1 and 2000).
<
_ = random2(),
Len = 2000,
Line 4,250:
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:
=={{header|PicoLisp}}==
Translation of the pseudo-code in the Wikipedia article:
<
(let D
(cons
Line 4,287:
(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:
(cadr Y) ) )
B
D ) ) )</
{{out|Output (both cases)}}
<pre>: (levenshtein (chop "kitten") (chop "sitting"))
Line 4,315:
=={{header|PL/I}}==
===version 1===
<
lsht: Proc Options(main);
Call test('kitten' ,'sitting');
Line 4,370:
Return(ld);
End;
End;</
{{out}}
<pre> 1st string = >kitten<
Line 4,396:
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:
Return(ld(sl,tl));
End;
End;</
Output is the same as for version 1.
Line 4,446:
{{works with|8080 PL/M Compiler}} ... under CP/M (or an emulator)
{{Trans|Action!}}
<
/* TRANS:ATED FROM THE ACTION! SAMPLE */
Line 4,545:
CALL TEST( .( 'ACTION', 33, '$' ), .'PL/M$' );
EOF</
{{out}}
<pre>
Line 4,556:
=={{header|PowerShell}}==
This version does not allow empty strings.
<
function Get-LevenshteinDistance
{
Line 4,616:
$outputObject
}
</syntaxhighlight>
<
Get-LevenshteinDistance "kitten" "sitting"
Get-LevenshteinDistance rosettacode raisethysword
</syntaxhighlight>
{{Out}}
<pre>
Line 4,630:
=={{header|Processing}}==
<
println(distance("kitten", "sitting"));
}
Line 4,647:
}
return costs[b.length()];
}</
==={{header|Processing Python mode}}===
<
println(distance("kitten", "sitting"))
Line 4,667:
costs[j] = cj
return costs[len(b)]</
=={{header|Prolog}}==
Line 4,673:
Works with SWI-Prolog.<br>
Based on Wikipedia's pseudocode.
<
length(S, M),
M1 is M+1,
Line 4,733:
init_n(N, L) :-
nth0(0, L, N).</
{{out|Output examples}}
<pre> ?- levenshtein("kitten", "sitting", R).
Line 4,763:
=={{header|PureBasic}}==
Based on Wikipedia's pseudocode.
<
Protected m, n, i, j, min, k, l
m = Len(A_string$)
Line 4,791:
;- 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:
print(levenshteinDistance("kitten","sitting"))
print(levenshteinDistance("rosettacode","raisethysword"))</
{{out}}
<pre>3
Line 4,820:
===Iterative 2===
Implementation of the Wikipedia algorithm, optimized for memory
<
if len(s1) > len(s2):
s1,s2 = s2,s1
Line 4,837:
print(minimumEditDistance("kitten","sitting"))
print(minimumEditDistance("rosettacode","raisethysword"))</
{{out}}
<pre>3
Line 4,844:
===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:
ld('kitten','kittenaaaaaaaaaaaaaaaaa',3), # False
ld('kittenaaaaaaaaaaaaaaaaa','kitten',3) # False
)</
{{out}}
<pre>0 1 2 3 4 8 17 17
Line 4,893:
====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:
>>> 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:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>Levenshtein minimum edit distances:
Line 5,068:
=={{header|Racket}}==
A memoized recursive implementation.
<
(define (levenshtein a b)
Line 5,087:
(levenshtein "kitten" "sitting")
(levenshtein "rosettacode" "raisethysword")</
{{out}}
<pre>3
Line 5,096:
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.
<
my @s = *, |$s.comb;
my @t = *, |$t.comb;
Line 5,118:
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
Line 5,127:
===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:
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:
===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:
say 'Levenshtein distance = ' d.m.n; say ''
Return d.m.n
</syntaxhighlight>
{{output}}
<pre>
Line 5,280:
===version 3===
Alternate algorithm from Wikipedia <strike>(but does not include a driver for testing)</strike>.
<
/*rexx*/
Line 5,326:
End
return v1.tl
</syntaxhighlight>
{{output}}
<pre>
Line 5,356:
===version 4 (recursive)===
Recursive algorithm from Wikipedia with memoization
<
/*rexx*/
Line 5,399:
End
Return ld.sl.tl
</syntaxhighlight>
{{output}}
<pre>
Line 5,428:
=={{header|Ring}}==
<
# Project : Levenshtein distance
Line 5,468:
levenshteindistance = d[n][m]
return levenshteindistance
</syntaxhighlight>
Output:
<pre>
Line 5,481:
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:
end
Levenshtein.test</
{{out}}
<pre>
Line 5,512:
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:
%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:
levenshteinDistance = d(n, m)
[ex]
end function</
8</pre>
Line 5,586:
Implementation of the wikipedia algorithm.
{{works with|Rust|1.45}}
<
println!("{}", levenshtein_distance("kitten", "sitting"));
println!("{}", levenshtein_distance("saturday", "sunday"));
Line 5,617:
}
matrix[word2_length-1][word1_length-1]
}</
{{out}}
<pre>3
Line 5,625:
=={{header|Scala}}==
===Translated Wikipedia algorithm.===
<
def distance(s1: String, s2: String): Int = {
Line 5,648:
printDistance("rosettacode", "raisethysword")
}</
{{out}}
<pre>kitten -> sitting : 3
Line 5,654:
===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:
printDistance("sleep", "fleeting")
}</
=={{header|Scheme}}==
Line 5,693:
Recursive version from wikipedia article.
<
(define (levenshtein s t)
(define (%levenshtein s sl t tl)
Line 5,707:
(string->list t)
(string-length t)))
</syntaxhighlight>
{{out}}
Line 5,718:
=={{header|Seed7}}==
<
const func integer: levenshteinDistance (in string: s, in string: t) is func
Line 5,749:
writeln("kitten -> sitting: " <& levenshteinDistance("kitten", "sitting"));
writeln("rosettacode -> raisethysword: " <& levenshteinDistance("rosettacode", "raisethysword"));
end func;</
{{out}}
Line 5,759:
=={{header|SenseTalk}}==
SenseTalk has a built-in TextDifference function for this.
<
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.
<
import <Utilities/Sequence.sl>;
import <Utilities/Math.sl>;
Line 5,789:
min(min(v1[n] + 1, v0[n + 1] + 1), v0[n] + (0 when s = t[n] else 1))),
n + 1);
</syntaxhighlight>
=={{header|Sidef}}==
===Recursive===
<
s || return t.len
Line 5,807:
__FUNC__(s1, t )
)
}</
===Iterative===
<
var d = [@(0 .. t.len), s.len.of {[_]}...]
for i,j in (^s ~X ^t) {
Line 5,820:
}
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:
END
</syntaxhighlight>
{{out}}
<pre>
Line 5,875:
{{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:
Version using entire matrix:
<
let (t, s) = (w1.characters, w2.characters)
Line 5,896:
}
return mat.last!.last!
}</
Version using only two rows at a time:
<
let (t, s) = (w1.characters, w2.characters)
Line 5,915:
}
return last.last!
}</
===Single array version===
{{trans|C++}}
<
let m = string1.count
let n = string2.count
Line 5,945:
}
print(levenshteinDistance(string1: "rosettacode", string2: "raisethysword"))</
{{out}}
Line 5,953:
=={{header|Tcl}}==
<
# Edge cases
if {![set n [string length $t]]} {
Line 5,981:
# 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:
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:
11846 ? "Damerau Distance=";Result
11850 ENDPROC
</syntaxhighlight>
{{out}}
<pre>kitten, sitting: 3
Line 6,066:
=={{header|TUSCRIPT}}==
<
$$ MODE TUSCRIPT
distance=DISTANCE ("kitten", "sitting")
PRINT distance
</syntaxhighlight>
Output:
<pre>
Line 6,078:
=={{header|TypeScript}}==
{{Trans|JavaScript}}
<
function levenshtein(a: string, b: string): number {
const m: number = a.length,
Line 6,094:
}
</syntaxhighlight>
=={{header|Vala}}==
<
public static int compute (owned string s, owned string t, bool case_sensitive = false) {
var n = s.length;
Line 6,123:
}
}
</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:
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:
PrintLevenshtein "rosettacode", "raisethysword"
PrintLevenshtein "saturday", "sunday"
PrintLevenshtein "sleep", "fleeting"</
{{out}}
<pre>
Line 6,231:
{{works with|VBA|6.5}}
{{works with|VBA|7.1}}
<
If x < y Then
min = x
Line 6,291:
Debug.Print "'sleep' to 'fleeting' => "; levenshtein("sleep", "fleeting")
End Sub
</syntaxhighlight>
{{out}}
<pre>'kitten' to 'sitting' => 3
Line 6,299:
=={{header|Visual Basic .NET}}==
<
Dim Matrix(String1.Length, String2.Length) As Integer
Dim Key As Integer
Line 6,318:
Next
Return Matrix(String1.Length - 1, String2.Length - 1)
End Function</
=={{header|Wren}}==
{{trans|Go}}
<
var ls = s.count
var lt = t.count
Line 6,346:
}
System.print(levenshtein.call("kitten", "sitting"))</
{{out}}
Line 6,355:
=={{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:
}
costs[-1]
}</
<
T("yo",""), T("","yo"), T("abc","abc")) ){
println(a," --> ",b,": ",levenshtein(a,b));
}</
{{out}}
<pre>
Line 6,387:
=={{header|ZX Spectrum Basic}}==
<
20 INPUT "first word:",n$
30 INPUT "second word:",m$
Line 6,400:
120 NEXT i
130 NEXT j
140 PRINT "The Levenshtein distance between """;n$;""", """;m$;""" is ";d(m+1,n+1);"."</
{{out}}
<pre>
|