Levenshtein distance: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
|||
Line 31: | Line 31: | ||
{{trans|Python}} |
{{trans|Python}} |
||
<syntaxhighlight lang=11l>F minimumEditDistance(=s1, =s2) |
<syntaxhighlight lang="11l">F minimumEditDistance(=s1, =s2) |
||
I s1.len > s2.len |
I s1.len > s2.len |
||
(s1, s2) = (s2, s1) |
(s1, s2) = (s2, s1) |
||
Line 57: | Line 57: | ||
=={{header|360 Assembly}}== |
=={{header|360 Assembly}}== |
||
<syntaxhighlight lang=360asm>* Levenshtein distance - 22/04/2020 |
<syntaxhighlight lang="360asm">* Levenshtein distance - 22/04/2020 |
||
LEVENS CSECT |
LEVENS CSECT |
||
USING LEVENS,R13 base register |
USING LEVENS,R13 base register |
||
Line 241: | Line 241: | ||
=={{header|Action!}}== |
=={{header|Action!}}== |
||
{{Improve||The output shown does not appear to match the PrintF calls in the code}} |
{{Improve||The output shown does not appear to match the PrintF calls in the code}} |
||
<syntaxhighlight lang=action> |
<syntaxhighlight lang="action"> |
||
DEFINE STRING="CHAR ARRAY" ; sys.act |
DEFINE STRING="CHAR ARRAY" ; sys.act |
||
DEFINE width="15" ; max characters 14 |
DEFINE width="15" ; max characters 14 |
||
Line 327: | Line 327: | ||
=={{header|Ada}}== |
=={{header|Ada}}== |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="ada">with Ada.Text_IO; |
||
procedure Main is |
procedure Main is |
||
Line 367: | Line 367: | ||
=={{header|Aime}}== |
=={{header|Aime}}== |
||
{{trans|C}} |
{{trans|C}} |
||
<syntaxhighlight lang=aime>integer |
<syntaxhighlight lang="aime">integer |
||
dist(data s, t, integer i, j, list d) |
dist(data s, t, integer i, j, list d) |
||
{ |
{ |
||
Line 421: | Line 421: | ||
<br> |
<br> |
||
Non-recursive algorithm - although Algol 68 supports recursion, Action! doesn't. |
Non-recursive algorithm - although Algol 68 supports recursion, Action! doesn't. |
||
<syntaxhighlight lang=algol68># Calculate Levenshtein distance between strings - translated from the Action! sample # |
<syntaxhighlight lang="algol68"># Calculate Levenshtein distance between strings - translated from the Action! sample # |
||
BEGIN |
BEGIN |
||
Line 482: | Line 482: | ||
===Iteration=== |
===Iteration=== |
||
Translation of the "fast" C-version |
Translation of the "fast" C-version |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="applescript">set dist to findLevenshteinDistance for "sunday" against "saturday" |
||
to findLevenshteinDistance for s1 against s2 |
to findLevenshteinDistance for s1 against s2 |
||
script o |
script o |
||
Line 543: | 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: |
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: |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="applescript">-- levenshtein :: String -> String -> Int |
||
on levenshtein(sa, sb) |
on levenshtein(sa, sb) |
||
set {s1, s2} to {characters of sa, characters of sb} |
set {s1, s2} to {characters of sa, characters of sb} |
||
Line 698: | Line 698: | ||
end zip3</syntaxhighlight> |
end zip3</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="applescript">{3, 3, 8, 8}</syntaxhighlight> |
||
=={{header|Arc}}== |
=={{header|Arc}}== |
||
Line 704: | Line 704: | ||
O(n * m) time, linear space, using lists instead of vectors |
O(n * m) time, linear space, using lists instead of vectors |
||
<syntaxhighlight lang=lisp>(def levenshtein (str1 str2) |
<syntaxhighlight lang="lisp">(def levenshtein (str1 str2) |
||
(withs l1 len.str1 |
(withs l1 len.str1 |
||
l2 len.str2 |
l2 len.str2 |
||
Line 723: | Line 723: | ||
=={{header|Arturo}}== |
=={{header|Arturo}}== |
||
<syntaxhighlight lang=rebol>print levenshtein "kitten" "sitting"</syntaxhighlight> |
<syntaxhighlight lang="rebol">print levenshtein "kitten" "sitting"</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 731: | Line 731: | ||
=={{header|AutoHotkey}}== |
=={{header|AutoHotkey}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="autohotkey">levenshtein(s, t){ |
||
If s = |
If s = |
||
return StrLen(t) |
return StrLen(t) |
||
Line 755: | Line 755: | ||
Slavishly copied from the very clear AutoHotKey example. |
Slavishly copied from the very clear AutoHotKey example. |
||
<syntaxhighlight lang=awk>#!/usr/bin/awk -f |
<syntaxhighlight lang="awk">#!/usr/bin/awk -f |
||
BEGIN { |
BEGIN { |
||
Line 810: | Line 810: | ||
Alternative, much faster but also less readable lazy-evaluation version from http://awk.freeshell.org/LevenshteinEditDistance |
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): |
(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): |
||
<syntaxhighlight lang=awk>#!/usr/bin/awk -f |
<syntaxhighlight lang="awk">#!/usr/bin/awk -f |
||
function levdist(str1, str2, l1, l2, tog, arr, i, j, a, b, c) { |
function levdist(str1, str2, l1, l2, tog, arr, i, j, a, b, c) { |
||
Line 841: | Line 841: | ||
=={{header|BBC BASIC}}== |
=={{header|BBC BASIC}}== |
||
<syntaxhighlight lang=bbcbasic> PRINT "'kitten' -> 'sitting' has distance " ; |
<syntaxhighlight lang="bbcbasic"> PRINT "'kitten' -> 'sitting' has distance " ; |
||
PRINT ; FNlevenshtein("kitten", "sitting") |
PRINT ; FNlevenshtein("kitten", "sitting") |
||
PRINT "'rosettacode' -> 'raisethysword' has distance " ; |
PRINT "'rosettacode' -> 'raisethysword' has distance " ; |
||
Line 877: | Line 877: | ||
=={{header|BQN}}== |
=={{header|BQN}}== |
||
Recursive slow version: |
Recursive slow version: |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="bqn">Levenshtein ← { |
||
𝕨 𝕊"": ≠𝕨; |
𝕨 𝕊"": ≠𝕨; |
||
""𝕊 𝕩: ≠𝕩; |
""𝕊 𝕩: ≠𝕩; |
||
Line 885: | Line 885: | ||
}</syntaxhighlight> |
}</syntaxhighlight> |
||
Fast version: |
Fast version: |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="bqn">Levenshtein ← @⊸∾⊸{¯1⊑(↕≠𝕨)𝕨{(1⊸+⊸⌊`1⊸+⌊⊑⊸»+𝕨≠𝕗˙)𝕩}´⌽𝕩}</syntaxhighlight> |
||
{{out|Example use}} |
{{out|Example use}} |
||
<lang> "kitten" Levenshtein "sitting" |
<syntaxhighlight lang="text"> "kitten" Levenshtein "sitting" |
||
3 |
3 |
||
"Saturday" Levenshtein "Sunday" |
"Saturday" Levenshtein "Sunday" |
||
Line 897: | Line 897: | ||
{{trans|C}} |
{{trans|C}} |
||
Recursive method, but with memoization. |
Recursive method, but with memoization. |
||
<syntaxhighlight lang=bracmat>(levenshtein= |
<syntaxhighlight lang="bracmat">(levenshtein= |
||
lev cache |
lev cache |
||
. ( lev |
. ( lev |
||
Line 930: | Line 930: | ||
=={{header|C}}== |
=={{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>. |
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>. |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <string.h> |
#include <string.h> |
||
Line 976: | Line 976: | ||
}</syntaxhighlight> |
}</syntaxhighlight> |
||
Take the above and add caching, we get (in [[C99]]): |
Take the above and add caching, we get (in [[C99]]): |
||
<syntaxhighlight lang=c>#include <stdio.h> |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <string.h> |
#include <string.h> |
||
Line 1,023: | Line 1,023: | ||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
This is a straightforward translation of the Wikipedia pseudocode. |
This is a straightforward translation of the Wikipedia pseudocode. |
||
<syntaxhighlight lang=csharp>using System; |
<syntaxhighlight lang="csharp">using System; |
||
namespace LevenshteinDistance |
namespace LevenshteinDistance |
||
Line 1,083: | Line 1,083: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
<syntaxhighlight lang=c>#include <string> |
<syntaxhighlight lang="c">#include <string> |
||
#include <iostream> |
#include <iostream> |
||
using namespace std; |
using namespace std; |
||
Line 1,145: | Line 1,145: | ||
===Generic ISO C++ version=== |
===Generic ISO C++ version=== |
||
<syntaxhighlight lang=cpp>#include <algorithm> |
<syntaxhighlight lang="cpp">#include <algorithm> |
||
#include <iostream> |
#include <iostream> |
||
#include <numeric> |
#include <numeric> |
||
Line 1,194: | Line 1,194: | ||
===Recursive Version=== |
===Recursive Version=== |
||
<syntaxhighlight lang=lisp>(defn levenshtein [str1 str2] |
<syntaxhighlight lang="lisp">(defn levenshtein [str1 str2] |
||
(let [len1 (count str1) |
(let [len1 (count str1) |
||
len2 (count str2)] |
len2 (count str2)] |
||
Line 1,211: | Line 1,211: | ||
===Iterative version=== |
===Iterative version=== |
||
<syntaxhighlight lang=lisp>(defn levenshtein [w1 w2] |
<syntaxhighlight lang="lisp">(defn levenshtein [w1 w2] |
||
(letfn [(cell-value [same-char? prev-row cur-row col-idx] |
(letfn [(cell-value [same-char? prev-row cur-row col-idx] |
||
(min (inc (nth prev-row col-idx)) |
(min (inc (nth prev-row col-idx)) |
||
Line 1,234: | Line 1,234: | ||
=={{header|CLU}}== |
=={{header|CLU}}== |
||
<syntaxhighlight lang=clu>min = proc [T: type] (a, b: T) returns (T) |
<syntaxhighlight lang="clu">min = proc [T: type] (a, b: T) returns (T) |
||
where T has lt: proctype (T,T) returns (bool) |
where T has lt: proctype (T,T) returns (bool) |
||
if a<b |
if a<b |
||
Line 1,284: | Line 1,284: | ||
=={{header|COBOL}}== |
=={{header|COBOL}}== |
||
GnuCobol 2.2 |
GnuCobol 2.2 |
||
<syntaxhighlight lang=cobol> |
<syntaxhighlight lang="cobol"> |
||
identification division. |
identification division. |
||
program-id. Levenshtein. |
program-id. Levenshtein. |
||
Line 1,356: | Line 1,356: | ||
=={{header|CoffeeScript}}== |
=={{header|CoffeeScript}}== |
||
<syntaxhighlight lang=coffeescript>levenshtein = (str1, str2) -> |
<syntaxhighlight lang="coffeescript">levenshtein = (str1, str2) -> |
||
# more of less ported simple algorithm from JS |
# more of less ported simple algorithm from JS |
||
m = str1.length |
m = str1.length |
||
Line 1,388: | Line 1,388: | ||
=={{header|Common Lisp}}== |
=={{header|Common Lisp}}== |
||
<syntaxhighlight lang=lisp>(defun levenshtein (a b) |
<syntaxhighlight lang="lisp">(defun levenshtein (a b) |
||
(let* ((la (length a)) |
(let* ((la (length a)) |
||
(lb (length b)) |
(lb (length b)) |
||
Line 1,410: | Line 1,410: | ||
=={{header|Crystal}}== |
=={{header|Crystal}}== |
||
The standard library includes [https://crystal-lang.org/api/0.19.2/Levenshtein.html levenshtein] module |
The standard library includes [https://crystal-lang.org/api/0.19.2/Levenshtein.html levenshtein] module |
||
<syntaxhighlight lang=ruby>require "levenshtein" |
<syntaxhighlight lang="ruby">require "levenshtein" |
||
puts Levenshtein.distance("kitten", "sitting") |
puts Levenshtein.distance("kitten", "sitting") |
||
puts Levenshtein.distance("rosettacode", "raisethysword") |
puts Levenshtein.distance("rosettacode", "raisethysword") |
||
Line 1,419: | Line 1,419: | ||
{{trans|Ruby 1st version}} |
{{trans|Ruby 1st version}} |
||
<syntaxhighlight lang=ruby>module Levenshtein |
<syntaxhighlight lang="ruby">module Levenshtein |
||
def self.distance(a, b) |
def self.distance(a, b) |
||
Line 1,451: | Line 1,451: | ||
{{trans|Ruby 2nd version}} |
{{trans|Ruby 2nd version}} |
||
<syntaxhighlight lang=ruby>def levenshtein_distance(str1, str2) |
<syntaxhighlight lang="ruby">def levenshtein_distance(str1, str2) |
||
n, m = str1.size, str2.size |
n, m = str1.size, str2.size |
||
max = n / 2 |
max = n / 2 |
||
Line 1,493: | Line 1,493: | ||
===Standard Version=== |
===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: |
The standard library [http://www.digitalmars.com/d/2.0/phobos/std_algorithm.html#levenshteinDistance std.algorithm] module includes a Levenshtein distance function: |
||
<syntaxhighlight lang=d>void main() { |
<syntaxhighlight lang="d">void main() { |
||
import std.stdio, std.algorithm; |
import std.stdio, std.algorithm; |
||
Line 1,503: | Line 1,503: | ||
===Iterative Version=== |
===Iterative Version=== |
||
{{trans|Java}} |
{{trans|Java}} |
||
<syntaxhighlight lang=d>import std.stdio, std.algorithm; |
<syntaxhighlight lang="d">import std.stdio, std.algorithm; |
||
int distance(in string s1, in string s2) pure nothrow { |
int distance(in string s1, in string s2) pure nothrow { |
||
Line 1,538: | Line 1,538: | ||
===Memoized Recursive Version=== |
===Memoized Recursive Version=== |
||
{{trans|Python}} |
{{trans|Python}} |
||
<syntaxhighlight lang=d>import std.stdio, std.array, std.algorithm, std.functional; |
<syntaxhighlight lang="d">import std.stdio, std.array, std.algorithm, std.functional; |
||
uint lDist(T)(in const(T)[] s, in const(T)[] t) nothrow { |
uint lDist(T)(in const(T)[] s, in const(T)[] t) nothrow { |
||
Line 1,556: | Line 1,556: | ||
=={{header|Delphi}}== |
=={{header|Delphi}}== |
||
{{Trans|C#}} |
{{Trans|C#}} |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="delphi"> |
||
program Levenshtein_distanceTest; |
program Levenshtein_distanceTest; |
||
Line 1,626: | Line 1,626: | ||
=={{header|DWScript}}== |
=={{header|DWScript}}== |
||
Based on Wikipedia version |
Based on Wikipedia version |
||
<syntaxhighlight lang=delphi>function LevenshteinDistance(s, t : String) : Integer; |
<syntaxhighlight lang="delphi">function LevenshteinDistance(s, t : String) : Integer; |
||
var |
var |
||
i, j : Integer; |
i, j : Integer; |
||
Line 1,652: | Line 1,652: | ||
=={{header|Dyalect}}== |
=={{header|Dyalect}}== |
||
<syntaxhighlight lang=dyalect>func levenshtein(s, t) { |
<syntaxhighlight lang="dyalect">func levenshtein(s, t) { |
||
var n = s.Length() |
var n = s.Length() |
||
var m = t.Length() |
var m = t.Length() |
||
Line 1,702: | Line 1,702: | ||
=={{header|EchoLisp}}== |
=={{header|EchoLisp}}== |
||
<syntaxhighlight lang=lisp> |
<syntaxhighlight lang="lisp"> |
||
;; Recursive version adapted from Clojure |
;; Recursive version adapted from Clojure |
||
;; Added necessary memoization |
;; Added necessary memoization |
||
Line 1,736: | Line 1,736: | ||
This code is translated from Haskell version. |
This code is translated from Haskell version. |
||
<syntaxhighlight lang=ela>open list |
<syntaxhighlight lang="ela">open list |
||
levenshtein s1 s2 = last <| foldl transform [0 .. length s1] s2 |
levenshtein s1 s2 = last <| foldl transform [0 .. length s1] s2 |
||
Line 1,744: | Line 1,744: | ||
Executing: |
Executing: |
||
<syntaxhighlight lang=ela>(levenshtein "kitten" "sitting", levenshtein "rosettacode" "raisethysword")</syntaxhighlight> |
<syntaxhighlight lang="ela">(levenshtein "kitten" "sitting", levenshtein "rosettacode" "raisethysword")</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>(3, 8)</pre> |
<pre>(3, 8)</pre> |
||
Line 1,750: | Line 1,750: | ||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
{{trans|Ruby}} |
{{trans|Ruby}} |
||
<syntaxhighlight lang=elixir>defmodule Levenshtein do |
<syntaxhighlight lang="elixir">defmodule Levenshtein do |
||
def distance(a, b) do |
def distance(a, b) do |
||
ta = String.downcase(a) |> to_charlist |> List.to_tuple |
ta = String.downcase(a) |> to_charlist |> List.to_tuple |
||
Line 1,788: | Line 1,788: | ||
=={{header|Erlang}}== |
=={{header|Erlang}}== |
||
Here are two implementations. The first is the naive version, the second is a memoized version using Erlang's dictionary datatype. |
Here are two implementations. The first is the naive version, the second is a memoized version using Erlang's dictionary datatype. |
||
<syntaxhighlight lang=erlang> |
<syntaxhighlight lang="erlang"> |
||
-module(levenshtein). |
-module(levenshtein). |
||
-compile(export_all). |
-compile(export_all). |
||
Line 1,826: | Line 1,826: | ||
</syntaxhighlight> |
</syntaxhighlight> |
||
Below is a comparison of the runtimes, measured in microseconds, between the two implementations. |
Below is a comparison of the runtimes, measured in microseconds, between the two implementations. |
||
<syntaxhighlight lang=erlang> |
<syntaxhighlight lang="erlang"> |
||
68> timer:tc(levenshtein,distance,["rosettacode","raisethysword"]). |
68> timer:tc(levenshtein,distance,["rosettacode","raisethysword"]). |
||
{774799,8} % {Time, Result} |
{774799,8} % {Time, Result} |
||
Line 1,838: | Line 1,838: | ||
=={{header|ERRE}}== |
=={{header|ERRE}}== |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="erre"> |
||
PROGRAM LEVENSHTEIN |
PROGRAM LEVENSHTEIN |
||
Line 1,890: | Line 1,890: | ||
=={{header|Euphoria}}== |
=={{header|Euphoria}}== |
||
Code by Jeremy Cowgar from the [http://www.rapideuphoria.com/cgi-bin/asearch.exu?gen=on&keywords=Levenshtein Euphoria File Archive]. |
Code by Jeremy Cowgar from the [http://www.rapideuphoria.com/cgi-bin/asearch.exu?gen=on&keywords=Levenshtein Euphoria File Archive]. |
||
<syntaxhighlight lang=euphoria>function min(sequence s) |
<syntaxhighlight lang="euphoria">function min(sequence s) |
||
atom m |
atom m |
||
m = s[1] |
m = s[1] |
||
Line 1,944: | Line 1,944: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
=== Standard version === |
=== Standard version === |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="fsharp"> |
||
open System |
open System |
||
Line 1,980: | Line 1,980: | ||
=== Recursive Version === |
=== Recursive Version === |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="fsharp"> |
||
open System |
open System |
||
Line 2,006: | Line 2,006: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
<syntaxhighlight lang=factor>USING: lcs prettyprint ; |
<syntaxhighlight lang="factor">USING: lcs prettyprint ; |
||
"kitten" "sitting" levenshtein .</syntaxhighlight> |
"kitten" "sitting" levenshtein .</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,015: | Line 2,015: | ||
=={{header|Forth}}== |
=={{header|Forth}}== |
||
{{trans|C}} |
{{trans|C}} |
||
<syntaxhighlight lang=forth>: levenshtein ( a1 n1 a2 n2 -- n3) |
<syntaxhighlight lang="forth">: levenshtein ( a1 n1 a2 n2 -- n3) |
||
dup \ if either string is empty, difference |
dup \ if either string is empty, difference |
||
if \ is inserting all chars from the other |
if \ is inserting all chars from the other |
||
Line 2,040: | Line 2,040: | ||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="fortran"> |
||
program demo_edit_distance |
program demo_edit_distance |
||
character(len=:),allocatable :: sources(:),targets(:) |
character(len=:),allocatable :: sources(:),targets(:) |
||
Line 2,092: | Line 2,092: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
<syntaxhighlight lang=freebasic>' FB 1.05.0 Win64 |
<syntaxhighlight lang="freebasic">' FB 1.05.0 Win64 |
||
' Uses the "iterative with two matrix rows" algorithm |
' Uses the "iterative with two matrix rows" algorithm |
||
Line 2,151: | Line 2,151: | ||
=={{header|Frink}}== |
=={{header|Frink}}== |
||
Frink has a built-in function to calculate the Levenshtein edit distance between two strings: |
Frink has a built-in function to calculate the Levenshtein edit distance between two strings: |
||
<syntaxhighlight lang=frink>println[editDistance["kitten","sitting"]]</syntaxhighlight> |
<syntaxhighlight lang="frink">println[editDistance["kitten","sitting"]]</syntaxhighlight> |
||
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. |
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}}== |
=={{header|FutureBasic}}== |
||
Based on Wikipedia algorithm. Suitable for Pascal strings. |
Based on Wikipedia algorithm. Suitable for Pascal strings. |
||
<syntaxhighlight lang=futurebasic>window 1 |
<syntaxhighlight lang="futurebasic">window 1 |
||
local fn LevenshteinDistance( aStr as Str255, bStr as Str255 ) as long |
local fn LevenshteinDistance( aStr as Str255, bStr as Str255 ) as long |
||
Line 2,233: | Line 2,233: | ||
=={{header|Go}}== |
=={{header|Go}}== |
||
WP algorithm: |
WP algorithm: |
||
<syntaxhighlight lang=go>package main |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 2,276: | Line 2,276: | ||
</pre> |
</pre> |
||
{{trans|C}} |
{{trans|C}} |
||
<syntaxhighlight lang=go>package main |
<syntaxhighlight lang="go">package main |
||
import "fmt" |
import "fmt" |
||
Line 2,306: | Line 2,306: | ||
=={{header|Groovy}}== |
=={{header|Groovy}}== |
||
<syntaxhighlight lang=groovy>def distance(String str1, String str2) { |
<syntaxhighlight lang="groovy">def distance(String str1, String str2) { |
||
def dist = new int[str1.size() + 1][str2.size() + 1] |
def dist = new int[str1.size() + 1][str2.size() + 1] |
||
(0..str1.size()).each { dist[it][0] = it } |
(0..str1.size()).each { dist[it][0] = it } |
||
Line 2,335: | Line 2,335: | ||
===Implementation 1=== |
===Implementation 1=== |
||
<syntaxhighlight lang=haskell>levenshtein :: Eq a => [a] -> [a] -> Int |
<syntaxhighlight lang="haskell">levenshtein :: Eq a => [a] -> [a] -> Int |
||
levenshtein s1 s2 = last $ foldl transform [0 .. length s1] s2 |
levenshtein s1 s2 = last $ foldl transform [0 .. length s1] s2 |
||
where |
where |
||
Line 2,348: | Line 2,348: | ||
===Implementation 2=== |
===Implementation 2=== |
||
<syntaxhighlight lang=haskell>levenshtein :: Eq a => [a] -> [a] -> Int |
<syntaxhighlight lang="haskell">levenshtein :: Eq a => [a] -> [a] -> Int |
||
levenshtein s1 [] = length s1 |
levenshtein s1 [] = length s1 |
||
levenshtein [] s2 = length s2 |
levenshtein [] s2 = length s2 |
||
Line 2,364: | Line 2,364: | ||
=={{header|Icon}} and {{header|Unicon}}== |
=={{header|Icon}} and {{header|Unicon}}== |
||
<syntaxhighlight lang=unicon>procedure main() |
<syntaxhighlight lang="unicon">procedure main() |
||
every process(!&input) |
every process(!&input) |
||
end |
end |
||
Line 2,395: | Line 2,395: | ||
=={{header|Io}}== |
=={{header|Io}}== |
||
A <code>levenshtein</code> method is available on strings when the standard <code>Range</code> addon is loaded. |
A <code>levenshtein</code> method is available on strings when the standard <code>Range</code> addon is loaded. |
||
<lang>Io 20110905 |
<syntaxhighlight lang="text">Io 20110905 |
||
Io> Range ; "kitten" levenshtein("sitting") |
Io> Range ; "kitten" levenshtein("sitting") |
||
==> 3 |
==> 3 |
||
Line 2,404: | Line 2,404: | ||
=={{header|J}}== |
=={{header|J}}== |
||
One approach would be a literal transcription of the [[wp:Levenshtein_distance#Computing_Levenshtein_distance|wikipedia implementation]]: |
One approach would be a literal transcription of the [[wp:Levenshtein_distance#Computing_Levenshtein_distance|wikipedia implementation]]: |
||
<syntaxhighlight lang=j>levenshtein=:4 :0 |
<syntaxhighlight lang="j">levenshtein=:4 :0 |
||
D=. x +/&i.&>:&# y |
D=. x +/&i.&>:&# y |
||
for_i.1+i.#x do. |
for_i.1+i.#x do. |
||
Line 2,427: | Line 2,427: | ||
We can also do the usual optimization where we only represent one row of the distance matrix at a time: |
We can also do the usual optimization where we only represent one row of the distance matrix at a time: |
||
<syntaxhighlight lang=j>levdist =:4 :0 |
<syntaxhighlight lang="j">levdist =:4 :0 |
||
'a b'=. (x;y) /: (#x),(#y) |
'a b'=. (x;y) /: (#x),(#y) |
||
D=. >: iz =. i.#b |
D=. >: iz =. i.#b |
||
Line 2,436: | Line 2,436: | ||
)</syntaxhighlight> |
)</syntaxhighlight> |
||
{{out|Example use}} |
{{out|Example use}} |
||
<syntaxhighlight lang=j> 'kitten' levenshtein 'sitting' |
<syntaxhighlight lang="j"> 'kitten' levenshtein 'sitting' |
||
3 |
3 |
||
'kitten' levdist 'sitting' |
'kitten' levdist 'sitting' |
||
3</syntaxhighlight> |
3</syntaxhighlight> |
||
Time and space use: |
Time and space use: |
||
<syntaxhighlight lang=j> |
<syntaxhighlight lang="j"> |
||
timespacex '''kitten'' levenshtein ''sitting''' |
timespacex '''kitten'' levenshtein ''sitting''' |
||
0.000113 6016 |
0.000113 6016 |
||
Line 2,451: | Line 2,451: | ||
=={{header|Java}}== |
=={{header|Java}}== |
||
Based on the definition for Levenshtein distance given in the Wikipedia article: |
Based on the definition for Levenshtein distance given in the Wikipedia article: |
||
<syntaxhighlight lang=java>public class Levenshtein { |
<syntaxhighlight lang="java">public class Levenshtein { |
||
public static int distance(String a, String b) { |
public static int distance(String a, String b) { |
||
Line 2,485: | Line 2,485: | ||
</pre> |
</pre> |
||
{{trans|C}} |
{{trans|C}} |
||
<syntaxhighlight lang=java>public class Levenshtein{ |
<syntaxhighlight lang="java">public class Levenshtein{ |
||
public static int levenshtein(String s, String t){ |
public static int levenshtein(String s, String t){ |
||
/* if either string is empty, difference is inserting all chars |
/* if either string is empty, difference is inserting all chars |
||
Line 2,538: | Line 2,538: | ||
===Iterative space optimized (even bounded) === |
===Iterative space optimized (even bounded) === |
||
{{trans|Python}} |
{{trans|Python}} |
||
<syntaxhighlight lang=java> |
<syntaxhighlight lang="java"> |
||
import static java.lang.Math.abs; |
import static java.lang.Math.abs; |
||
import static java.lang.Math.max; |
import static java.lang.Math.max; |
||
Line 2,622: | Line 2,622: | ||
===ES5=== |
===ES5=== |
||
Iterative: |
Iterative: |
||
<syntaxhighlight lang=javascript>function levenshtein(a, b) { |
<syntaxhighlight lang="javascript">function levenshtein(a, b) { |
||
var t = [], u, i, j, m = a.length, n = b.length; |
var t = [], u, i, j, m = a.length, n = b.length; |
||
if (!m) { return n; } |
if (!m) { return n; } |
||
Line 2,658: | Line 2,658: | ||
By composition of generic functions: |
By composition of generic functions: |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="javascript">(() => { |
||
'use strict'; |
'use strict'; |
||
Line 2,817: | Line 2,817: | ||
67ms for rosettacode/raisethysword |
67ms for rosettacode/raisethysword |
||
71ms for edocattesor/drowsyhtesiar |
71ms for edocattesor/drowsyhtesiar |
||
<syntaxhighlight lang=jq> |
<syntaxhighlight lang="jq"> |
||
# lookup the distance between s and t in the nested cache, |
# lookup the distance between s and t in the nested cache, |
||
# which uses basic properties of the Levenshtein distance to save space: |
# which uses basic properties of the Levenshtein distance to save space: |
||
Line 2,870: | Line 2,870: | ||
s as $s | t as $t | {} | ld($s;$t) | .[0];</syntaxhighlight> |
s as $s | t as $t | {} | ld($s;$t) | .[0];</syntaxhighlight> |
||
'''Task''' |
'''Task''' |
||
<syntaxhighlight lang=jq>def demo: |
<syntaxhighlight lang="jq">def demo: |
||
"levenshteinDistance between \(.[0]) and \(.[1]) is \( levenshteinDistance(.[0]; .[1]) )"; |
"levenshteinDistance between \(.[0]) and \(.[1]) is \( levenshteinDistance(.[0]; .[1]) )"; |
||
Line 2,886: | Line 2,886: | ||
=={{header|Jsish}}== |
=={{header|Jsish}}== |
||
From Javascript, ES5 entry. |
From Javascript, ES5 entry. |
||
<syntaxhighlight lang=javascript>/* Levenshtein Distance, in Jsish */ |
<syntaxhighlight lang="javascript">/* Levenshtein Distance, in Jsish */ |
||
function levenshtein(a, b) { |
function levenshtein(a, b) { |
||
Line 2,939: | Line 2,939: | ||
'''Recursive''': |
'''Recursive''': |
||
{{works with|Julia|1.0}} |
{{works with|Julia|1.0}} |
||
<syntaxhighlight lang=julia>function levendist(s::AbstractString, t::AbstractString) |
<syntaxhighlight lang="julia">function levendist(s::AbstractString, t::AbstractString) |
||
ls, lt = length.((s, t)) |
ls, lt = length.((s, t)) |
||
ls == 0 && return lt |
ls == 0 && return lt |
||
Line 2,954: | Line 2,954: | ||
'''Iterative''': |
'''Iterative''': |
||
{{works with|Julia|0.6}} |
{{works with|Julia|0.6}} |
||
<syntaxhighlight lang=julia>function levendist1(s::AbstractString, t::AbstractString) |
<syntaxhighlight lang="julia">function levendist1(s::AbstractString, t::AbstractString) |
||
ls, lt = length(s), length(t) |
ls, lt = length(s), length(t) |
||
if ls > lt |
if ls > lt |
||
Line 2,977: | Line 2,977: | ||
Let's see some benchmark: |
Let's see some benchmark: |
||
<syntaxhighlight lang=julia>using BenchmarkTools |
<syntaxhighlight lang="julia">using BenchmarkTools |
||
println("\n# levendist(kitten, sitting)") |
println("\n# levendist(kitten, sitting)") |
||
s, t = "kitten", "sitting" |
s, t = "kitten", "sitting" |
||
Line 3,007: | Line 3,007: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
===Standard Version=== |
===Standard Version=== |
||
<syntaxhighlight lang=scala>// version 1.0.6 |
<syntaxhighlight lang="scala">// version 1.0.6 |
||
// Uses the "iterative with two matrix rows" algorithm referred to in the Wikipedia article. |
// Uses the "iterative with two matrix rows" algorithm referred to in the Wikipedia article. |
||
Line 3,049: | Line 3,049: | ||
===Functional/Folding Version=== |
===Functional/Folding Version=== |
||
<syntaxhighlight lang=scala> |
<syntaxhighlight lang="scala"> |
||
fun levenshtein(s: String, t: String, |
fun levenshtein(s: String, t: String, |
||
charScore : (Char, Char) -> Int = { c1, c2 -> if (c1 == c2) 0 else 1}) : Int { |
charScore : (Char, Char) -> Int = { c1, c2 -> if (c1 == c2) 0 else 1}) : Int { |
||
Line 3,083: | Line 3,083: | ||
Suitable for short strings: |
Suitable for short strings: |
||
<syntaxhighlight lang=lisp> |
<syntaxhighlight lang="lisp"> |
||
(defun levenshtein-simple |
(defun levenshtein-simple |
||
(('() str) |
(('() str) |
||
Line 3,101: | Line 3,101: | ||
You can copy and paste that function into an LFE REPL and run it like so: |
You can copy and paste that function into an LFE REPL and run it like so: |
||
<syntaxhighlight lang=lisp> |
<syntaxhighlight lang="lisp"> |
||
> (levenshtein-simple "a" "a") |
> (levenshtein-simple "a" "a") |
||
0 |
0 |
||
Line 3,116: | Line 3,116: | ||
=== Cached Implementation === |
=== Cached Implementation === |
||
<syntaxhighlight lang=lisp> |
<syntaxhighlight lang="lisp"> |
||
(defun levenshtein-distance (str1 str2) |
(defun levenshtein-distance (str1 str2) |
||
(let (((tuple distance _) (levenshtein-distance |
(let (((tuple distance _) (levenshtein-distance |
||
Line 3,147: | Line 3,147: | ||
As before, here's some usage in the REPL. Note that longer strings are now possible to compare without incurring long execution times: |
As before, here's some usage in the REPL. Note that longer strings are now possible to compare without incurring long execution times: |
||
<syntaxhighlight lang=lisp> |
<syntaxhighlight lang="lisp"> |
||
> (levenshtein-distance "a" "a") |
> (levenshtein-distance "a" "a") |
||
0 |
0 |
||
Line 3,161: | Line 3,161: | ||
=={{header|Liberty BASIC}}== |
=={{header|Liberty BASIC}}== |
||
<syntaxhighlight lang=lb>'Levenshtein Distance translated by Brandon Parker |
<syntaxhighlight lang="lb">'Levenshtein Distance translated by Brandon Parker |
||
'08/19/10 |
'08/19/10 |
||
'from http://www.merriampark.com/ld.htm#VB |
'from http://www.merriampark.com/ld.htm#VB |
||
Line 3,210: | Line 3,210: | ||
=={{header|Limbo}}== |
=={{header|Limbo}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
<syntaxhighlight lang=limbo>implement Levenshtein; |
<syntaxhighlight lang="limbo">implement Levenshtein; |
||
include "sys.m"; sys: Sys; |
include "sys.m"; sys: Sys; |
||
Line 3,268: | Line 3,268: | ||
=={{header|LiveCode}}== |
=={{header|LiveCode}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="livecode"> |
||
//Code By Neurox66 |
//Code By Neurox66 |
||
function Levenshtein pString1 pString2 |
function Levenshtein pString1 pString2 |
||
Line 3,299: | Line 3,299: | ||
=={{header|Lobster}}== |
=={{header|Lobster}}== |
||
{{trans|C}} |
{{trans|C}} |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="lobster">def levenshtein(s: string, t: string) -> int: |
||
def makeNxM(n: int, m: int, v: int) -> [[int]]: |
def makeNxM(n: int, m: int, v: int) -> [[int]]: |
||
Line 3,337: | Line 3,337: | ||
=={{header|Lua}}== |
=={{header|Lua}}== |
||
<syntaxhighlight lang=lua>function leven(s,t) |
<syntaxhighlight lang="lua">function leven(s,t) |
||
if s == '' then return t:len() end |
if s == '' then return t:len() end |
||
if t == '' then return s:len() end |
if t == '' then return s:len() end |
||
Line 3,362: | Line 3,362: | ||
=={{header|M2000 Interpreter}}== |
=={{header|M2000 Interpreter}}== |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="m2000 interpreter"> |
||
Module Checkit { |
Module Checkit { |
||
\\ Iterative with two matrix rows |
\\ Iterative with two matrix rows |
||
Line 3,432: | Line 3,432: | ||
=={{header|Maple}}== |
=={{header|Maple}}== |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="maple"> |
||
> with(StringTools): |
> with(StringTools): |
||
> Levenshtein("kitten","sitting"); |
> Levenshtein("kitten","sitting"); |
||
Line 3,442: | Line 3,442: | ||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="mathematica">EditDistance["kitten","sitting"] |
||
EditDistance["rosettacode","raisethysword"]</syntaxhighlight> |
EditDistance["rosettacode","raisethysword"]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 3,449: | Line 3,449: | ||
=={{header|MATLAB}}== |
=={{header|MATLAB}}== |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="matlab"> |
||
function score = levenshtein(s1, s2) |
function score = levenshtein(s1, s2) |
||
% score = levenshtein(s1, s2) |
% score = levenshtein(s1, s2) |
||
Line 3,485: | Line 3,485: | ||
=={{header|MiniScript}}== |
=={{header|MiniScript}}== |
||
In the Mini Micro environment, this function is part of the stringUtil library module, and can be used like so: |
In the Mini Micro environment, this function is part of the stringUtil library module, and can be used like so: |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="miniscript">import "stringUtil" |
||
print "kitten".editDistance("sitting")</syntaxhighlight> |
print "kitten".editDistance("sitting")</syntaxhighlight> |
||
In environments where the stringUtil module is not available, you'd have to define it yourself: |
In environments where the stringUtil module is not available, you'd have to define it yourself: |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="miniscript">string.editDistance = function(s2) |
||
n = self.len |
n = self.len |
||
m = s2.len |
m = s2.len |
||
Line 3,534: | Line 3,534: | ||
=={{header|Modula-2}}== |
=={{header|Modula-2}}== |
||
<syntaxhighlight lang=modula2>MODULE LevenshteinDistance; |
<syntaxhighlight lang="modula2">MODULE LevenshteinDistance; |
||
FROM InOut IMPORT WriteString, WriteCard, WriteLn; |
FROM InOut IMPORT WriteString, WriteCard, WriteLn; |
||
FROM Strings IMPORT Length; |
FROM Strings IMPORT Length; |
||
Line 3,593: | Line 3,593: | ||
=={{header|NetRexx}}== |
=={{header|NetRexx}}== |
||
{{trans|ooRexx}} |
{{trans|ooRexx}} |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="netrexx">/* NetRexx */ |
||
options replace format comments java crossref symbols nobinary |
options replace format comments java crossref symbols nobinary |
||
Line 3,654: | Line 3,654: | ||
=={{header|Nim}}== |
=={{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. |
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. |
||
<syntaxhighlight lang=nim>import std/editdistance |
<syntaxhighlight lang="nim">import std/editdistance |
||
echo editDistanceAscii("kitten", "sitting") |
echo editDistanceAscii("kitten", "sitting") |
||
Line 3,665: | Line 3,665: | ||
{{trans|Python}} |
{{trans|Python}} |
||
Here is a translation of the Python version. |
Here is a translation of the Python version. |
||
<syntaxhighlight lang=nim>import sequtils |
<syntaxhighlight lang="nim">import sequtils |
||
func min(a, b, c: int): int {.inline.} = min(a, min(b, c)) |
func min(a, b, c: int): int {.inline.} = min(a, min(b, c)) |
||
Line 3,693: | Line 3,693: | ||
=={{header|Objeck}}== |
=={{header|Objeck}}== |
||
{{trans|C#}} |
{{trans|C#}} |
||
<syntaxhighlight lang=objeck>class Levenshtein { |
<syntaxhighlight lang="objeck">class Levenshtein { |
||
function : Main(args : String[]) ~ Nil { |
function : Main(args : String[]) ~ Nil { |
||
if(args->Size() = 2) { |
if(args->Size() = 2) { |
||
Line 3,730: | Line 3,730: | ||
=={{header|Objective-C}}== |
=={{header|Objective-C}}== |
||
Translation of the C# code into a NSString category |
Translation of the C# code into a NSString category |
||
<syntaxhighlight lang=objc>@interface NSString (levenshteinDistance) |
<syntaxhighlight lang="objc">@interface NSString (levenshteinDistance) |
||
- (NSUInteger)levenshteinDistanceToString:(NSString *)string; |
- (NSUInteger)levenshteinDistanceToString:(NSString *)string; |
||
@end |
@end |
||
Line 3,768: | Line 3,768: | ||
=={{header|OCaml}}== |
=={{header|OCaml}}== |
||
Translation of the pseudo-code of the Wikipedia article: |
Translation of the pseudo-code of the Wikipedia article: |
||
<syntaxhighlight lang=ocaml>let minimum a b c = |
<syntaxhighlight lang="ocaml">let minimum a b c = |
||
min a (min b c) |
min a (min b c) |
||
Line 3,811: | Line 3,811: | ||
=== A recursive functional version === |
=== A recursive functional version === |
||
This could be made faster with memoization |
This could be made faster with memoization |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="ocaml">let levenshtein s t = |
||
let rec dist i j = match (i,j) with |
let rec dist i j = match (i,j) with |
||
| (i,0) -> i |
| (i,0) -> i |
||
Line 3,835: | Line 3,835: | ||
=={{header|ooRexx}}== |
=={{header|ooRexx}}== |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="oorexx"> |
||
say "kitten -> sitting:" levenshteinDistance("kitten", "sitting") |
say "kitten -> sitting:" levenshteinDistance("kitten", "sitting") |
||
say "rosettacode -> raisethysword:" levenshteinDistance("rosettacode", "raisethysword") |
say "rosettacode -> raisethysword:" levenshteinDistance("rosettacode", "raisethysword") |
||
Line 3,892: | Line 3,892: | ||
{{trans|JavaScript}} |
{{trans|JavaScript}} |
||
{{Works with|PARI/GP|2.7.4 and above}} |
{{Works with|PARI/GP|2.7.4 and above}} |
||
<syntaxhighlight lang=parigp> |
<syntaxhighlight lang="parigp"> |
||
\\ Levenshtein distance between two words |
\\ Levenshtein distance between two words |
||
\\ 6/21/16 aev |
\\ 6/21/16 aev |
||
Line 3,930: | Line 3,930: | ||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
A fairly direct translation of the wikipedia pseudo code: |
A fairly direct translation of the wikipedia pseudo code: |
||
<syntaxhighlight lang=pascal>Program LevenshteinDistanceDemo(output); |
<syntaxhighlight lang="pascal">Program LevenshteinDistanceDemo(output); |
||
uses |
uses |
||
Line 3,976: | Line 3,976: | ||
=={{header|Perl}}== |
=={{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. |
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. |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="perl">use List::Util qw(min); |
||
my %cache; |
my %cache; |
||
Line 4,004: | Line 4,004: | ||
Iterative solution: |
Iterative solution: |
||
<syntaxhighlight lang=perl>use List::Util qw(min); |
<syntaxhighlight lang="perl">use List::Util qw(min); |
||
sub leven { |
sub leven { |
||
Line 4,029: | Line 4,029: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--<syntaxhighlight lang= |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
||
Line 4,084: | Line 4,084: | ||
=== alternative === |
=== alternative === |
||
Modelled after the Processing code, uses a single/smaller array, passes the same tests as above. |
Modelled after the Processing code, uses a single/smaller array, passes the same tests as above. |
||
<!--<syntaxhighlight lang= |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<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: #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> |
<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,102: | Line 4,102: | ||
=={{header|PHP}}== |
=={{header|PHP}}== |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="php"> |
||
echo levenshtein('kitten','sitting'); |
echo levenshtein('kitten','sitting'); |
||
echo levenshtein('rosettacode', 'raisethysword'); |
echo levenshtein('rosettacode', 'raisethysword'); |
||
Line 4,114: | Line 4,114: | ||
===Iterative=== |
===Iterative=== |
||
Based on the iterative algorithm at Wikipedia. Picat is 1-based so some adjustments are needed. |
Based on the iterative algorithm at Wikipedia. Picat is 1-based so some adjustments are needed. |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="picat">levenshtein(S,T) = Dist => |
||
M = 1+S.length, |
M = 1+S.length, |
||
N = 1+T.length, |
N = 1+T.length, |
||
Line 4,142: | Line 4,142: | ||
===Tabled recursive version=== |
===Tabled recursive version=== |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="picat">table |
||
levenshtein_rec(S,T) = Dist => |
levenshtein_rec(S,T) = Dist => |
||
Dist1 = 0, |
Dist1 = 0, |
||
Line 4,163: | Line 4,163: | ||
===Mode-directed tabling=== |
===Mode-directed tabling=== |
||
{{trans|Prolog}} |
{{trans|Prolog}} |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="picat"> |
||
levenshtein_mode(S,T) = Dist => |
levenshtein_mode(S,T) = Dist => |
||
lev(S, T, Dist). |
lev(S, T, Dist). |
||
Line 4,176: | Line 4,176: | ||
===Test=== |
===Test=== |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="picat">go => |
||
S = [ |
S = [ |
||
Line 4,225: | Line 4,225: | ||
===Benchmark on larger strings=== |
===Benchmark on larger strings=== |
||
Benchmarking the methods with larger strings of random lengths (between 1 and 2000). |
Benchmarking the methods with larger strings of random lengths (between 1 and 2000). |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="picat">go2 => |
||
_ = random2(), |
_ = random2(), |
||
Len = 2000, |
Len = 2000, |
||
Line 4,268: | Line 4,268: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
Translation of the pseudo-code in the Wikipedia article: |
Translation of the pseudo-code in the Wikipedia article: |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="picolisp">(de levenshtein (A B) |
||
(let D |
(let D |
||
(cons |
(cons |
||
Line 4,287: | Line 4,287: | ||
(get D J I) ) ) ) ) ) ) ) )</syntaxhighlight> |
(get D J I) ) ) ) ) ) ) ) )</syntaxhighlight> |
||
or, using 'map' to avoid list indexing: |
or, using 'map' to avoid list indexing: |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="picolisp">(de levenshtein (A B) |
||
(let D |
(let D |
||
(cons |
(cons |
||
Line 4,313: | Line 4,313: | ||
=={{header|PL/I}}== |
=={{header|PL/I}}== |
||
===version 1=== |
===version 1=== |
||
<syntaxhighlight lang=pli>*process source xref attributes or(!); |
<syntaxhighlight lang="pli">*process source xref attributes or(!); |
||
lsht: Proc Options(main); |
lsht: Proc Options(main); |
||
Call test('kitten' ,'sitting'); |
Call test('kitten' ,'sitting'); |
||
Line 4,394: | Line 4,394: | ||
Levenshtein distance = 3</pre> |
Levenshtein distance = 3</pre> |
||
===version 2 recursive with memoization=== |
===version 2 recursive with memoization=== |
||
<syntaxhighlight lang=pli>*process source attributes xref or(!); |
<syntaxhighlight lang="pli">*process source attributes xref or(!); |
||
ld3: Proc Options(main); |
ld3: Proc Options(main); |
||
Dcl ld(0:30,0:30) Bin Fixed(31); |
Dcl ld(0:30,0:30) Bin Fixed(31); |
||
Line 4,444: | Line 4,444: | ||
{{works with|8080 PL/M Compiler}} ... under CP/M (or an emulator) |
{{works with|8080 PL/M Compiler}} ... under CP/M (or an emulator) |
||
{{Trans|Action!}} |
{{Trans|Action!}} |
||
<syntaxhighlight lang=pli>100H: /* CALCULATE THE LEVENSHTEIN DISTANCE BETWEEN STRINGS */ |
<syntaxhighlight lang="pli">100H: /* CALCULATE THE LEVENSHTEIN DISTANCE BETWEEN STRINGS */ |
||
/* TRANS:ATED FROM THE ACTION! SAMPLE */ |
/* TRANS:ATED FROM THE ACTION! SAMPLE */ |
||
Line 4,554: | Line 4,554: | ||
=={{header|PowerShell}}== |
=={{header|PowerShell}}== |
||
This version does not allow empty strings. |
This version does not allow empty strings. |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="powershell"> |
||
function Get-LevenshteinDistance |
function Get-LevenshteinDistance |
||
{ |
{ |
||
Line 4,615: | Line 4,615: | ||
} |
} |
||
</syntaxhighlight> |
</syntaxhighlight> |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="powershell"> |
||
Get-LevenshteinDistance "kitten" "sitting" |
Get-LevenshteinDistance "kitten" "sitting" |
||
Get-LevenshteinDistance rosettacode raisethysword |
Get-LevenshteinDistance rosettacode raisethysword |
||
Line 4,628: | Line 4,628: | ||
=={{header|Processing}}== |
=={{header|Processing}}== |
||
<syntaxhighlight lang=processing>void setup() { |
<syntaxhighlight lang="processing">void setup() { |
||
println(distance("kitten", "sitting")); |
println(distance("kitten", "sitting")); |
||
} |
} |
||
Line 4,649: | Line 4,649: | ||
==={{header|Processing Python mode}}=== |
==={{header|Processing Python mode}}=== |
||
<syntaxhighlight lang=python>def setup(): |
<syntaxhighlight lang="python">def setup(): |
||
println(distance("kitten", "sitting")) |
println(distance("kitten", "sitting")) |
||
Line 4,671: | Line 4,671: | ||
Works with SWI-Prolog.<br> |
Works with SWI-Prolog.<br> |
||
Based on Wikipedia's pseudocode. |
Based on Wikipedia's pseudocode. |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="prolog">levenshtein(S, T, R) :- |
||
length(S, M), |
length(S, M), |
||
M1 is M+1, |
M1 is M+1, |
||
Line 4,761: | Line 4,761: | ||
=={{header|PureBasic}}== |
=={{header|PureBasic}}== |
||
Based on Wikipedia's pseudocode. |
Based on Wikipedia's pseudocode. |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="purebasic">Procedure LevenshteinDistance(A_string$, B_String$) |
||
Protected m, n, i, j, min, k, l |
Protected m, n, i, j, min, k, l |
||
m = Len(A_string$) |
m = Len(A_string$) |
||
Line 4,794: | Line 4,794: | ||
===Iterative 1=== |
===Iterative 1=== |
||
Faithful implementation of "Iterative with full matrix" from Wikipedia |
Faithful implementation of "Iterative with full matrix" from Wikipedia |
||
<syntaxhighlight lang=python>def levenshteinDistance(str1, str2): |
<syntaxhighlight lang="python">def levenshteinDistance(str1, str2): |
||
m = len(str1) |
m = len(str1) |
||
n = len(str2) |
n = len(str2) |
||
Line 4,818: | Line 4,818: | ||
===Iterative 2=== |
===Iterative 2=== |
||
Implementation of the Wikipedia algorithm, optimized for memory |
Implementation of the Wikipedia algorithm, optimized for memory |
||
<syntaxhighlight lang=python>def minimumEditDistance(s1,s2): |
<syntaxhighlight lang="python">def minimumEditDistance(s1,s2): |
||
if len(s1) > len(s2): |
if len(s1) > len(s2): |
||
s1,s2 = s2,s1 |
s1,s2 = s2,s1 |
||
Line 4,842: | Line 4,842: | ||
===Iterative 3=== |
===Iterative 3=== |
||
Iterative space optimized (even bounded) |
Iterative space optimized (even bounded) |
||
<syntaxhighlight lang=python>def ld(a, b, mx=-1): |
<syntaxhighlight lang="python">def ld(a, b, mx=-1): |
||
def result(d): return d if mx < 0 else False if d > mx else True |
def result(d): return d if mx < 0 else False if d > mx else True |
||
Line 4,891: | Line 4,891: | ||
====Memoized recursion==== |
====Memoized recursion==== |
||
(Uses [http://docs.python.org/dev/library/functools.html?highlight=functools.lru_cache#functools.lru_cache this] cache from the standard library). |
(Uses [http://docs.python.org/dev/library/functools.html?highlight=functools.lru_cache#functools.lru_cache this] cache from the standard library). |
||
<syntaxhighlight lang=python>>>> from functools import lru_cache |
<syntaxhighlight lang="python">>>> from functools import lru_cache |
||
>>> @lru_cache(maxsize=4095) |
>>> @lru_cache(maxsize=4095) |
||
def ld(s, t): |
def ld(s, t): |
||
Line 4,907: | Line 4,907: | ||
====Non-recursive: reduce and scanl==== |
====Non-recursive: reduce and scanl==== |
||
{{Works with|Python|3.7}} |
{{Works with|Python|3.7}} |
||
<syntaxhighlight lang=python>'''Levenshtein distance''' |
<syntaxhighlight lang="python">'''Levenshtein distance''' |
||
from itertools import (accumulate, chain, islice) |
from itertools import (accumulate, chain, islice) |
||
Line 5,066: | Line 5,066: | ||
=={{header|Racket}}== |
=={{header|Racket}}== |
||
A memoized recursive implementation. |
A memoized recursive implementation. |
||
<syntaxhighlight lang=racket>#lang racket |
<syntaxhighlight lang="racket">#lang racket |
||
(define (levenshtein a b) |
(define (levenshtein a b) |
||
Line 5,094: | Line 5,094: | ||
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. |
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= |
<syntaxhighlight lang="raku" line>sub levenshtein-distance ( Str $s, Str $t --> Int ) { |
||
my @s = *, |$s.comb; |
my @s = *, |$s.comb; |
||
my @t = *, |$t.comb; |
my @t = *, |$t.comb; |
||
Line 5,125: | Line 5,125: | ||
===version 1=== |
===version 1=== |
||
As per the task's requirements, this version includes a driver to display the results. |
As per the task's requirements, this version includes a driver to display the results. |
||
<syntaxhighlight lang=rexx>/*REXX program calculates and displays the Levenshtein distance between two strings. */ |
<syntaxhighlight lang="rexx">/*REXX program calculates and displays the Levenshtein distance between two strings. */ |
||
call Levenshtein 'kitten' , "sitting" |
call Levenshtein 'kitten' , "sitting" |
||
call Levenshtein 'rosettacode' , "raisethysword" |
call Levenshtein 'rosettacode' , "raisethysword" |
||
Line 5,170: | Line 5,170: | ||
===version 2=== |
===version 2=== |
||
<strike>same as</strike> Similar to version 1 <strike>(but does not include a driver for testing)</strike>, reformatted and commented |
<strike>same as</strike> Similar to version 1 <strike>(but does not include a driver for testing)</strike>, reformatted and commented |
||
<syntaxhighlight lang=rexx> |
<syntaxhighlight lang="rexx"> |
||
/*rexx*/ |
/*rexx*/ |
||
Line 5,278: | Line 5,278: | ||
===version 3=== |
===version 3=== |
||
Alternate algorithm from Wikipedia <strike>(but does not include a driver for testing)</strike>. |
Alternate algorithm from Wikipedia <strike>(but does not include a driver for testing)</strike>. |
||
<syntaxhighlight lang=rexx> |
<syntaxhighlight lang="rexx"> |
||
/*rexx*/ |
/*rexx*/ |
||
Line 5,354: | Line 5,354: | ||
===version 4 (recursive)=== |
===version 4 (recursive)=== |
||
Recursive algorithm from Wikipedia with memoization |
Recursive algorithm from Wikipedia with memoization |
||
<syntaxhighlight lang=rexx> |
<syntaxhighlight lang="rexx"> |
||
/*rexx*/ |
/*rexx*/ |
||
Line 5,426: | Line 5,426: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
<syntaxhighlight lang=ring> |
<syntaxhighlight lang="ring"> |
||
# Project : Levenshtein distance |
# Project : Levenshtein distance |
||
Line 5,479: | Line 5,479: | ||
and for <code>k >= j</code> contains ''lev(i-1, k)''. The inner loop body restores the invariant for the |
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>. |
new value of <code>j</code>. |
||
<syntaxhighlight lang=ruby>module Levenshtein |
<syntaxhighlight lang="ruby">module Levenshtein |
||
def self.distance(a, b) |
def self.distance(a, b) |
||
Line 5,510: | Line 5,510: | ||
A variant can be found used in Rubygems [https://github.com/rubygems/rubygems/blob/master/lib/rubygems/text.rb] |
A variant can be found used in Rubygems [https://github.com/rubygems/rubygems/blob/master/lib/rubygems/text.rb] |
||
<syntaxhighlight lang=ruby>def levenshtein_distance(str1, str2) |
<syntaxhighlight lang="ruby">def levenshtein_distance(str1, str2) |
||
n = str1.length |
n = str1.length |
||
m = str2.length |
m = str2.length |
||
Line 5,547: | Line 5,547: | ||
=={{header|Run BASIC}}== |
=={{header|Run BASIC}}== |
||
<syntaxhighlight lang=runbasic>print levenshteinDistance("kitten", "sitting") |
<syntaxhighlight lang="runbasic">print levenshteinDistance("kitten", "sitting") |
||
print levenshteinDistance("rosettacode", "raisethysword") |
print levenshteinDistance("rosettacode", "raisethysword") |
||
end |
end |
||
Line 5,584: | Line 5,584: | ||
Implementation of the wikipedia algorithm. |
Implementation of the wikipedia algorithm. |
||
{{works with|Rust|1.45}} |
{{works with|Rust|1.45}} |
||
<syntaxhighlight lang=rust>fn main() { |
<syntaxhighlight lang="rust">fn main() { |
||
println!("{}", levenshtein_distance("kitten", "sitting")); |
println!("{}", levenshtein_distance("kitten", "sitting")); |
||
println!("{}", levenshtein_distance("saturday", "sunday")); |
println!("{}", levenshtein_distance("saturday", "sunday")); |
||
Line 5,623: | Line 5,623: | ||
=={{header|Scala}}== |
=={{header|Scala}}== |
||
===Translated Wikipedia algorithm.=== |
===Translated Wikipedia algorithm.=== |
||
<syntaxhighlight lang=scala>object Levenshtein0 extends App { |
<syntaxhighlight lang="scala">object Levenshtein0 extends App { |
||
def distance(s1: String, s2: String): Int = { |
def distance(s1: String, s2: String): Int = { |
||
Line 5,652: | Line 5,652: | ||
===Functional programmed, memoized=== |
===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)]. |
{{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)]. |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="scala">import scala.collection.mutable |
||
import scala.collection.parallel.ParSeq |
import scala.collection.parallel.ParSeq |
||
Line 5,691: | Line 5,691: | ||
Recursive version from wikipedia article. |
Recursive version from wikipedia article. |
||
<syntaxhighlight lang=scheme> |
<syntaxhighlight lang="scheme"> |
||
(define (levenshtein s t) |
(define (levenshtein s t) |
||
(define (%levenshtein s sl t tl) |
(define (%levenshtein s sl t tl) |
||
Line 5,716: | Line 5,716: | ||
=={{header|Seed7}}== |
=={{header|Seed7}}== |
||
<syntaxhighlight lang=seed7>$ include "seed7_05.s7i"; |
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; |
||
const func integer: levenshteinDistance (in string: s, in string: t) is func |
const func integer: levenshteinDistance (in string: s, in string: t) is func |
||
Line 5,757: | Line 5,757: | ||
=={{header|SenseTalk}}== |
=={{header|SenseTalk}}== |
||
SenseTalk has a built-in TextDifference function for this. |
SenseTalk has a built-in TextDifference function for this. |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="sensetalk"> |
||
put textDifference("kitten", "sitting") // --> 3 |
put textDifference("kitten", "sitting") // --> 3 |
||
put textDifference("rosettacode", "raisethysword") // --> 8 |
put textDifference("rosettacode", "raisethysword") // --> 8 |
||
Line 5,765: | Line 5,765: | ||
=={{header|SequenceL}}== |
=={{header|SequenceL}}== |
||
This implementation is based on the "Iterative with two matrix rows" version on Wikipedia. |
This implementation is based on the "Iterative with two matrix rows" version on Wikipedia. |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="sequencel"> |
||
import <Utilities/Sequence.sl>; |
import <Utilities/Sequence.sl>; |
||
import <Utilities/Math.sl>; |
import <Utilities/Math.sl>; |
||
Line 5,791: | Line 5,791: | ||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
===Recursive=== |
===Recursive=== |
||
<syntaxhighlight lang=ruby>func lev(s, t) is cached { |
<syntaxhighlight lang="ruby">func lev(s, t) is cached { |
||
s || return t.len |
s || return t.len |
||
Line 5,808: | Line 5,808: | ||
===Iterative=== |
===Iterative=== |
||
<syntaxhighlight lang=ruby>func lev(s, t) { |
<syntaxhighlight lang="ruby">func lev(s, t) { |
||
var d = [@(0 .. t.len), s.len.of {[_]}...] |
var d = [@(0 .. t.len), s.len.of {[_]}...] |
||
for i,j in (^s ~X ^t) { |
for i,j in (^s ~X ^t) { |
||
Line 5,821: | Line 5,821: | ||
Calling the function: |
Calling the function: |
||
<syntaxhighlight lang=ruby>say lev(%c'kitten', %c'sitting'); # prints: 3 |
<syntaxhighlight lang="ruby">say lev(%c'kitten', %c'sitting'); # prints: 3 |
||
say lev(%c'rosettacode', %c'raisethysword'); # prints: 8</syntaxhighlight> |
say lev(%c'rosettacode', %c'raisethysword'); # prints: 8</syntaxhighlight> |
||
=={{header|Simula}}== |
=={{header|Simula}}== |
||
<syntaxhighlight lang=simula>BEGIN |
<syntaxhighlight lang="simula">BEGIN |
||
INTEGER PROCEDURE LEVENSHTEINDISTANCE(S1, S2); TEXT S1, S2; |
INTEGER PROCEDURE LEVENSHTEINDISTANCE(S1, S2); TEXT S1, S2; |
||
Line 5,873: | Line 5,873: | ||
{{works with|Smalltalk/X}} |
{{works with|Smalltalk/X}} |
||
ST/X provides a customizable levenshtein method in the String class (weights for individual operations can be passed in): |
ST/X provides a customizable levenshtein method in the String class (weights for individual operations can be passed in): |
||
<syntaxhighlight lang=smalltalk>'kitten' levenshteinTo: 'sitting' s:1 k:1 c:1 i:1 d:1 -> 3 |
<syntaxhighlight lang="smalltalk">'kitten' levenshteinTo: 'sitting' s:1 k:1 c:1 i:1 d:1 -> 3 |
||
'rosettacode' levenshteinTo: 'raisethysword' s:1 k:1 c:1 i:1 d:1 -> 8</syntaxhighlight> |
'rosettacode' levenshteinTo: 'raisethysword' s:1 k:1 c:1 i:1 d:1 -> 8</syntaxhighlight> |
||
Line 5,880: | Line 5,880: | ||
Version using entire matrix: |
Version using entire matrix: |
||
<syntaxhighlight lang=swift>func levDis(w1: String, w2: String) -> Int { |
<syntaxhighlight lang="swift">func levDis(w1: String, w2: String) -> Int { |
||
let (t, s) = (w1.characters, w2.characters) |
let (t, s) = (w1.characters, w2.characters) |
||
Line 5,898: | Line 5,898: | ||
Version using only two rows at a time: |
Version using only two rows at a time: |
||
<syntaxhighlight lang=swift>func levDis(w1: String, w2: String) -> Int { |
<syntaxhighlight lang="swift">func levDis(w1: String, w2: String) -> Int { |
||
let (t, s) = (w1.characters, w2.characters) |
let (t, s) = (w1.characters, w2.characters) |
||
Line 5,917: | Line 5,917: | ||
===Single array version=== |
===Single array version=== |
||
{{trans|C++}} |
{{trans|C++}} |
||
<syntaxhighlight lang=swift>func levenshteinDistance(string1: String, string2: String) -> Int { |
<syntaxhighlight lang="swift">func levenshteinDistance(string1: String, string2: String) -> Int { |
||
let m = string1.count |
let m = string1.count |
||
let n = string2.count |
let n = string2.count |
||
Line 5,951: | Line 5,951: | ||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
||
<syntaxhighlight lang=tcl>proc levenshteinDistance {s t} { |
<syntaxhighlight lang="tcl">proc levenshteinDistance {s t} { |
||
# Edge cases |
# Edge cases |
||
if {![set n [string length $t]]} { |
if {![set n [string length $t]]} { |
||
Line 5,981: | Line 5,981: | ||
}</syntaxhighlight> |
}</syntaxhighlight> |
||
{{out|Usage}} |
{{out|Usage}} |
||
<syntaxhighlight lang=tcl>puts [levenshteinDistance "kitten" "sitting"]; # Prints 3</syntaxhighlight> |
<syntaxhighlight lang="tcl">puts [levenshteinDistance "kitten" "sitting"]; # Prints 3</syntaxhighlight> |
||
=={{header|TSE SAL}}== |
=={{header|TSE SAL}}== |
||
<syntaxhighlight lang= |
<syntaxhighlight lang="tsesal">// library: math: get: damerau: levenshtein <description></description> <version>1.0.0.0.23</version> <version control></version control> (filenamemacro=getmadle.s) [kn, ri, th, 08-09-2011 23:04:55] |
||
INTEGER PROC FNMathGetDamerauLevenshteinDistanceI( STRING s1, STRING s2 ) |
INTEGER PROC FNMathGetDamerauLevenshteinDistanceI( STRING s1, STRING s2 ) |
||
INTEGER L1 = Length( s1 ) |
INTEGER L1 = Length( s1 ) |
||
Line 6,021: | Line 6,021: | ||
=={{header|Turbo-Basic XL}}== |
=={{header|Turbo-Basic XL}}== |
||
<syntaxhighlight lang=turbobasic> |
<syntaxhighlight lang="turbobasic"> |
||
10 DIM Word_1$(20), Word_2$(20), DLDm(21, 21) |
10 DIM Word_1$(20), Word_2$(20), DLDm(21, 21) |
||
11 CLS |
11 CLS |
||
Line 6,064: | Line 6,064: | ||
=={{header|TUSCRIPT}}== |
=={{header|TUSCRIPT}}== |
||
<syntaxhighlight lang=tuscript> |
<syntaxhighlight lang="tuscript"> |
||
$$ MODE TUSCRIPT |
$$ MODE TUSCRIPT |
||
distance=DISTANCE ("kitten", "sitting") |
distance=DISTANCE ("kitten", "sitting") |
||
Line 6,076: | Line 6,076: | ||
=={{header|TypeScript}}== |
=={{header|TypeScript}}== |
||
{{Trans|JavaScript}} |
{{Trans|JavaScript}} |
||
<syntaxhighlight lang=typescript> |
<syntaxhighlight lang="typescript"> |
||
function levenshtein(a: string, b: string): number { |
function levenshtein(a: string, b: string): number { |
||
const m: number = a.length, |
const m: number = a.length, |
||
Line 6,095: | Line 6,095: | ||
=={{header|Vala}}== |
=={{header|Vala}}== |
||
<syntaxhighlight lang=vala>class LevenshteinDistance : Object { |
<syntaxhighlight lang="vala">class LevenshteinDistance : Object { |
||
public static int compute (owned string s, owned string t, bool case_sensitive = false) { |
public static int compute (owned string s, owned string t, bool case_sensitive = false) { |
||
var n = s.length; |
var n = s.length; |
||
Line 6,124: | Line 6,124: | ||
=={{header|VBA}}== |
=={{header|VBA}}== |
||
{{trans|Phix}}<syntaxhighlight lang=vb>Option Base 1 |
{{trans|Phix}}<syntaxhighlight lang="vb">Option Base 1 |
||
Function levenshtein(s1 As String, s2 As String) As Integer |
Function levenshtein(s1 As String, s2 As String) As Integer |
||
Dim n As Integer: n = Len(s1) + 1 |
Dim n As Integer: n = Len(s1) + 1 |
||
Line 6,169: | Line 6,169: | ||
=={{header|VBScript}}== |
=={{header|VBScript}}== |
||
<syntaxhighlight lang=vb>' Levenshtein distance - 23/04/2020 |
<syntaxhighlight lang="vb">' Levenshtein distance - 23/04/2020 |
||
Function Min(a,b) |
Function Min(a,b) |
||
Line 6,229: | Line 6,229: | ||
{{works with|VBA|6.5}} |
{{works with|VBA|6.5}} |
||
{{works with|VBA|7.1}} |
{{works with|VBA|7.1}} |
||
<syntaxhighlight lang=vb>Function min(x As Integer, y As Integer) As Integer |
<syntaxhighlight lang="vb">Function min(x As Integer, y As Integer) As Integer |
||
If x < y Then |
If x < y Then |
||
min = x |
min = x |
||
Line 6,299: | Line 6,299: | ||
=={{header|Visual Basic .NET}}== |
=={{header|Visual Basic .NET}}== |
||
<syntaxhighlight lang=vbnet> Function LevenshteinDistance(ByVal String1 As String, ByVal String2 As String) As Integer |
<syntaxhighlight lang="vbnet"> Function LevenshteinDistance(ByVal String1 As String, ByVal String2 As String) As Integer |
||
Dim Matrix(String1.Length, String2.Length) As Integer |
Dim Matrix(String1.Length, String2.Length) As Integer |
||
Dim Key As Integer |
Dim Key As Integer |
||
Line 6,322: | Line 6,322: | ||
=={{header|Wren}}== |
=={{header|Wren}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
<syntaxhighlight lang=ecmascript>var levenshtein = Fn.new { |s, t| |
<syntaxhighlight lang="ecmascript">var levenshtein = Fn.new { |s, t| |
||
var ls = s.count |
var ls = s.count |
||
var lt = t.count |
var lt = t.count |
||
Line 6,355: | Line 6,355: | ||
=={{header|zkl}}== |
=={{header|zkl}}== |
||
{{trans|D}} |
{{trans|D}} |
||
<syntaxhighlight lang=zkl>fcn levenshtein(s1,s2){ |
<syntaxhighlight lang="zkl">fcn levenshtein(s1,s2){ |
||
sz2,costs:=s2.len() + 1, List.createLong(sz2,0); // -->zero filled List |
sz2,costs:=s2.len() + 1, List.createLong(sz2,0); // -->zero filled List |
||
foreach i in (s1.len() + 1){ |
foreach i in (s1.len() + 1){ |
||
Line 6,373: | Line 6,373: | ||
costs[-1] |
costs[-1] |
||
}</syntaxhighlight> |
}</syntaxhighlight> |
||
<syntaxhighlight lang=zkl>foreach a,b in (T(T("kitten","sitting"), T("rosettacode","raisethysword"), |
<syntaxhighlight lang="zkl">foreach a,b in (T(T("kitten","sitting"), T("rosettacode","raisethysword"), |
||
T("yo",""), T("","yo"), T("abc","abc")) ){ |
T("yo",""), T("","yo"), T("abc","abc")) ){ |
||
println(a," --> ",b,": ",levenshtein(a,b)); |
println(a," --> ",b,": ",levenshtein(a,b)); |
||
Line 6,387: | Line 6,387: | ||
=={{header|ZX Spectrum Basic}}== |
=={{header|ZX Spectrum Basic}}== |
||
<syntaxhighlight lang=zxbasic>10 REM ZX Spectrum Basic - Levenshtein distance |
<syntaxhighlight lang="zxbasic">10 REM ZX Spectrum Basic - Levenshtein distance |
||
20 INPUT "first word:",n$ |
20 INPUT "first word:",n$ |
||
30 INPUT "second word:",m$ |
30 INPUT "second word:",m$ |