Levenshtein distance: Difference between revisions

{{trans|Python}}

 

I s1.len > s2.len

(s1, s2) = (s2, s1)

 

print(minimumEditDistance(‘kitten’, ‘sitting’))

 

{{out}}

 

=={{header|360 Assembly}}==

LEVENS CSECT

USING LEVENS,R13 base register

XDEC DS CL12 temp fo xdeco

REGEQU

{{out}}

<pre>

 

=={{header|Action!}}==

DEFINE STRING="CHAR ARRAY" ; sys.act

DEFINE width="15" ; max characters 14

;PrintF("Damerau Levenshtein Distance=%U%E%E",result)

RETURN

{{out}}

<pre>kitten, sitting: 3

 

=={{header|Ada}}==

 

procedure Main is

("rosettacode -> raisethysword:" &

Integer'Image (Levenshtein_Distance ("rosettacode", "raisethysword")));

{{out}}

<pre>kitten -> sitting: 3

=={{header|Aime}}==

{{trans|C}}

dist(data s, t, integer i, j, list d)

{

 

0;

{{Out}}

<pre>`rosettacode' to `raisethysword' is 8

=={{header|ALGOL 68}}==

{{Trans|Action!}}

BEGIN

 

 

 

FI

 

STRING word 1, word 2;

word 1 :="kitten"; word 2 := "sitting";

word 1 := "rosettacode"; word 2 := "raisethysword";

word 1 := "qwerty"; word 2 := "qweryt";

{{out}}

<pre>

</pre>

 

===Iteration===

Translation of the "fast" C-version

to findLevenshteinDistance for s1 against s2

script o

end if

end if

 

===Composition of generic functions===

 

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}

map(result, items 1 thru ¬

minimum({length of xs, length of ys, length of zs}) of xs)

{{Out}}

 

=={{header|Arc}}==

O(n * m) time, linear space, using lists instead of vectors

 

(withs l1 len.str1

l2 len.str2

next))

(= row nrev.next)))

 

=={{header|Arturo}}==

 

 

{{out}}

=={{header|AutoHotkey}}==

{{trans|Go}}

If s =

return StrLen(t)

s1 := "kitten"

s2 := "sitting"

 

=={{header|AWK}}==

Slavishly copied from the very clear AutoHotKey example.

 

 

BEGIN {

}

 

 

Example output:

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) {

return arr[tog, j-1]

}

 

=={{header|BBC BASIC}}==

PRINT ; FNlevenshtein("kitten", "sitting")

PRINT "'rosettacode' -> 'raisethysword' has distance " ;

NEXT

NEXT j%

'''Output:'''

<pre>

=={{header|BQN}}==

Recursive slow version:

𝕨 𝕊"": ≠𝕨;

""𝕊 𝕩: ≠𝕩;

Tail←1⊸↓

𝕨 =○⊑◶⟨1+·⌊´ 𝕊○Tail ∾ Tail⊸𝕊 ∾ 𝕊⟜Tail, 𝕊○Tail⟩ 𝕩

Fast version:

{{out|Example use}}

3

"Saturday" Levenshtein "Sunday"

3

"rosettacode" Levenshtein "raisethysword"

 

=={{header|Bracmat}}==

{{trans|C}}

Recursive method, but with memoization.

lev cache

. ( lev

)

& new$hash:?cache

{{out|Demonstrating}}

<pre> levenshtein$(kitten,sitting)

levenshtein$(rosettacode,raisethysword)

8</pre>

 

=={{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>

 

 

return 0;

Take the above and add caching, we get (in [[C99]]):

#include <string.h>

 

return 0;

 

=={{header|C sharp|C#}}==

This is a straightforward translation of the Wikipedia pseudocode.

 

namespace LevenshteinDistance

}

}

{{out|Example output}}

<pre>

 

=={{header|C++}}==

#include <iostream>

using namespace std;

 

return 0;

{{out|Example output}}

<pre>

 

===Generic ISO C++ version===

#include <iostream>

#include <numeric>

<< levenshtein_distance(s0, s1) << std::endl;

return 0;

 

{{out}}

 

===Recursive Version===

(let [len1 (count str1)

len2 (count str2)]

(levenshtein (rest str1) (rest str2))))))))

 

{{out}}

<pre>8</pre>

 

===Iterative version===

(letfn [(cell-value [same-char? prev-row cur-row col-idx]

(min (inc (nth prev-row col-idx))

i))))

[row-idx] (range 1 (count prev-row)))]

 

=={{header|CLU}}==

where T has lt: proctype (T,T) returns (bool)

if a<b

show("kitten", "sitting")

show("rosettacode", "raisethysword")

{{out}}

<pre>kitten => sitting: 3

=={{header|COBOL}}==

GnuCobol 2.2

identification division.

program-id. Levenshtein.

display trim(string-a) " -> " trim(string-b) " = " trim(distance)

.

{{out|Output}}

<pre>

 

=={{header|CoffeeScript}}==

# more of less ported simple algorithm from JS

m = str1.length

console.log levenshtein("stop", "tops")

console.log levenshtein("yo", "")

 

=={{header|Common Lisp}}==

(let* ((la (length a))

(lb (length b))

((aref rec x y) (aref rec x y))

(t (setf (aref rec x y)

(leven la lb))))

 

{{out}}

<pre>8</pre>

=={{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")

{{out}}

<pre>3

 

{{trans|Ruby 1st version}}

def self.distance(a, b)

Levenshtein.test

{{out}}

<pre>

 

{{trans|Ruby 2nd version}}

n, m = str1.size, str2.size

max = n / 2

puts "distance(#{a}, #{b}) = #{levenshtein_distance(a, b)}"

end

{{out}}

<pre>

===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>

===Iterative Version===

{{trans|Java}}

 

int distance(in string s1, in string s2) pure nothrow {

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 {

lDist("kitten", "sitting").writeln;

lDist("rosettacode", "raisethysword").writeln;

 

=={{header|Delphi}}==

{{Trans|C#}}

program Levenshtein_distanceTest;

 

readln;

end.

 

 

=={{header|DWScript}}==

Based on Wikipedia version

var

i, j : Integer;

end;

 

 

=={{header|Dyalect}}==

 

var n = s.Length()

var m = t.Length()

}

 

{{out}}

 

<pre>rosettacode -> raisethysword = 8</pre>

 

=={{header|EchoLisp}}==

;; Recursive version adapted from Clojure

;; Added necessary memoization

 

(levenshtein "rosettacode" "raisethysword") → 8

 

=={{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'

 

Executing:

 

{{out}}

<pre>(3, 8)</pre>

=={{header|Elixir}}==

{{trans|Ruby}}

def distance(a, b) do

ta = String.downcase(a) |> to_charlist |> List.to_tuple

Enum.each(Enum.chunk(words, 2), fn [a,b] ->

IO.puts "distance(#{a}, #{b}) = #{Levenshtein.distance(a,b)}"

 

{{out}}

=={{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).

{L,dict:store({S,T},L,C3)}

end.

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}

71> timer:tc(levenshtein,distance_cached,["kitten","sitting"]).

{213,3}

 

=={{header|ERRE}}==

PROGRAM LEVENSHTEIN

 

!$ERASE D%

END PROGRAM

{{out}}<pre>

'kitten' -> 'sitting' has distance 3

=={{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]

 

? levenshtein("kitten", "sitting")

{{out}}

<pre>3

=={{header|F_Sharp|F#}}==

=== Standard version ===

open System

 

 

Console.ReadKey () |> ignore

 

=== Recursive Version ===

open System

 

let levenshtein (s1:string) (s2:string) : int =

 

printfn "dist(kitten, sitting) = %i" (levenshtein "kitten" "sitting")

 

=={{header|Factor}}==

{{out}}

<pre>

=={{header|Forth}}==

{{trans|C}}

dup \ if either string is empty, difference

if \ is inserting all chars from the other

 

s" kitten" s" sitting" levenshtein . cr

 

=={{header|Fortran}}==

program demo_edit_distance

character(len=:),allocatable :: sources(:),targets(:)

 

end program demo_edit_distance

kitten sitting 3 T

rosettacode raisethysword 8 T

T

</pre>

 

=={{header|FreeBASIC}}==

 

' Uses the "iterative with two matrix rows" algorithm

Print

Print "Press any key to quit"

 

{{out}}

=={{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}}==

 

 

 

 

next

 

<pre>

1st string = kitten

Levenshtein distance = 0

 

</pre>

 

=={{header|Go}}==

WP algorithm:

 

import "fmt"

}

return d[len(s)][len(t)]

{{out}}

<pre>

</pre>

{{trans|C}}

 

import "fmt"

fmt.Printf("distance between %s and %s: %d\n", s1, s2,

levenshtein(s1, s2))

{{out}}

<pre>

 

=={{header|Groovy}}==

def dist = new int[str1.size() + 1][str2.size() + 1]

(0..str1.size()).each { dist[it][0] = it }

println "Checking distance(${key[0]}, ${key[1]}) == $dist"

assert distance(key[0], key[1]) == dist

{{out}}

<pre>

 

=={{header|Haskell}}==

levenshtein s1 s2 = last $ foldl transform [0 .. length s1] s2

where

 

main :: IO ()

{{Out}}

<pre>3</pre>

 

=={{header|Icon}} and {{header|Unicon}}==

every process(!&input)

end

 

return d[n,m]-1

{{out|Example}}

<pre>

=={{header|Io}}==

A <code>levenshtein</code> method is available on strings when the standard <code>Range</code> addon is loaded.

Io> Range ; "kitten" levenshtein("sitting")

==> 3

Io> "rosettacode" levenshtein("raisethysword")

==> 8

 

=={{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.

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...).

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

end.

{:D

{{out|Example use}}

3

'kitten' levdist 'sitting'

Time and space use:

timespacex '''kitten'' levenshtein ''sitting'''

0.000113 6016

timespacex '''kitten'' levdist ''sitting'''

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.

=={{header|Java}}==

Based on the definition for Levenshtein distance given in the Wikipedia article:

 

public static int distance(String a, String b) {

System.out.println("distance(" + data[i] + ", " + data[i+1] + ") = " + distance(data[i], data[i+1]));

}

{{out}}

<pre>distance(kitten, sitting) = 3

</pre>

{{trans|C}}

public static int levenshtein(String s, String t){

/* if either string is empty, difference is inserting all chars

+ levenshtein(sb1.reverse().toString(), sb2.reverse().toString()));

}

{{out}}

<pre>distance between 'kitten' and 'sitting': 3

===Iterative space optimized (even bounded) ===

{{trans|Python}}

import static java.lang.Math.abs;

import static java.lang.Math.max;

}

}

{{out}}

<pre>

===ES5===

Iterative:

var t = [], u, i, j, m = a.length, n = b.length;

if (!m) { return n; }

console.log('levenstein("' + a + '","' + b + '") was ' + d + ' should be ' + t);

}

 

===ES6===

 

By composition of generic functions:

'use strict';

 

// MAIN ---

return JSON.stringify(main())

{{Out}}

<pre>[3, 3, 8, 8]</pre>

67ms for rosettacode/raisethysword

71ms for edocattesor/drowsyhtesiar

# lookup the distance between s and t in the nested cache,

# which uses basic properties of the Levenshtein distance to save space:

 

def levenshteinDistance(s;t):

'''Task'''

"levenshteinDistance between \(.[0]) and \(.[1]) is \( levenshteinDistance(.[0]; .[1]) )";

(["edocattesor", "drowsyhtesiar"] | demo),

(["this_algorithm_is_similar_to",

{{Out}}

levenshteinDistance between kitten and sitting is 3

=={{header|Jsish}}==

From Javascript, ES5 entry.

 

function levenshtein(a, b) {

levenshtein('mississippi', 'swiss miss') ==> 8

=!EXPECTEND!=

{{out}}

<pre>prompt$ jsish -u levenshtein.jsi

'''Recursive''':

{{works with|Julia|1.0}}

ls, lt = length.((s, t))

ls == 0 && return lt

 

@show levendist("kitten", "sitting") # 3

 

'''Iterative''':

{{works with|Julia|0.6}}

ls, lt = length(s), length(t)

if ls > lt

end

return dist[end]

 

Let's see some benchmark:

println("\n# levendist(kitten, sitting)")

s, t = "kitten", "sitting"

@btime levendist(s, t)

println(" - Iterative:")

 

{{out}}

=={{header|Kotlin}}==

===Standard Version===

 

// Uses the "iterative with two matrix rows" algorithm referred to in the Wikipedia article.

println("'rosettacode' to 'raisethysword' => ${levenshtein("rosettacode", "raisethysword")}")

println("'sleep' to 'fleeting' => ${levenshtein("sleep", "fleeting")}")

 

{{out}}

 

===Functional/Folding Version===

fun levenshtein(s: String, t: String,

charScore : (Char, Char) -> Int = { c1, c2 -> if (c1 == c2) 0 else 1}) : Int {

 

}

{{out}}

<pre>

Suitable for short strings:

 

(defun levenshtein-simple

(('() str)

(levenshtein-simple str1-tail str2)

(levenshtein-simple str1-tail str2-tail))))))

 

You can copy and paste that function into an LFE REPL and run it like so:

 

> (levenshtein-simple "a" "a")

0

> (levenshtein-simple "kitten" "sitting")

3

 

It is not recommended to test strings longer than the last example using this implementation, as performance quickly degrades.

=== Cached Implementation ===

 

(defun levenshtein-distance (str1 str2)

(let (((tuple distance _) (levenshtein-distance

(len (+ 1 (lists:min (list l1 l2 l3)))))

(tuple len (dict:store (tuple str1 str2) len c3)))))))

 

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

> (levenshtein-distance "rosettacode" "raisethysword")

8

 

=={{header|Liberty BASIC}}==

'08/19/10

'from http://www.merriampark.com/ld.htm#VB

Next i

LevenshteinDistance = d(n, m)

 

=={{header|Limbo}}==

{{trans|Go}}

 

include "sys.m"; sys: Sys;

return a + 1;

}

 

% levenshtein kitten sitting rosettacode raisethysword

kitten <-> sitting => 3

rosettacode <-> raisethysword => 8

 

=={{header|LiveCode}}==

{{trans|Go}}

//Code By Neurox66

function Levenshtein pString1 pString2

put Levenshtein("kitten","sitting")

put Levenshtein("rosettacode","raisethysword")

{{out}}

<pre>3

=={{header|Lobster}}==

{{trans|C}}

 

def makeNxM(n: int, m: int, v: int) -> [[int]]:

 

assert 3 == levenshtein("kitten", "sitting")

 

=={{header|Lua}}==

if s == '' then return t:len() end

if t == '' then return s:len() end

 

print(leven("kitten", "sitting"))

{{out}}

<pre>3

 

=={{header|M2000 Interpreter}}==

Module Checkit {

\\ Iterative with two matrix rows

}

Checkit2

 

=={{header|Maple}}==

> with(StringTools):

> Levenshtein("kitten","sitting");

> Levenshtein("rosettacode","raisethysword");

8

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

{{out}}

<pre>3

 

=={{header|MATLAB}}==

function score = levenshtein(s1, s2)

% score = levenshtein(s1, s2)

score = current_row(end);

end

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:

 

In environments where the stringUtil module is not available, you'd have to define it yourself:

n = self.len

m = s2.len

end function

 

 

<pre>3</pre>

 

=={{header|Modula-2}}==

FROM InOut IMPORT WriteString, WriteCard, WriteLn;

FROM Strings IMPORT Length;

ShowDistance("kitten", "sitting");

ShowDistance("rosettacode", "raisethysword");

{{out}}

<pre>kitten -> sitting: 3

=={{header|NetRexx}}==

{{trans|ooRexx}}

options replace format comments java crossref symbols nobinary

 

 

return d[m + 1, n + 1]

'''Output:'''

<pre>

=={{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")

 

{{out}}

{{trans|Python}}

Here is a translation of the Python version.

 

func min(a, b, c: int): int {.inline.} = min(a, min(b, c))

 

echo levenshteinDistance("kitten","sitting")

 

=={{header|Objeck}}==

{{trans|C#}}

function : Main(args : String[]) ~ Nil {

if(args->Size() = 2) {

return d[s->Size(), t->Size()];

}

 

=={{header|Objective-C}}==

Translation of the C# code into a NSString category

- (NSUInteger)levenshteinDistanceToString:(NSString *)string;

@end

return r;

}

 

=={{header|OCaml}}==

Translation of the pseudo-code of the Wikipedia article:

min a (min b c)

 

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

let () =

test "kitten" "sitting";

{{out}}

<pre>

 

=={{header|ooRexx}}==

say "kitten -> sitting:" levenshteinDistance("kitten", "sitting")

say "rosettacode -> raisethysword:" levenshteinDistance("rosettacode", "raisethysword")

 

return d[m + 1, n + 1 ]

Output:

<pre>

{{trans|JavaScript}}

{{Works with|PARI/GP|2.7.4 and above}}

\\ Levenshtein distance between two words

\\ 6/21/16 aev

levensDist("X","oX");

}

{{Output}}

=={{header|Pascal}}==

A fairly direct translation of the wikipedia pseudo code:

 

uses

s2 := 'raisethysword';

writeln('The Levenshtein distance between "', s1, '" and "', s2, '" is: ', LevenshteinDistance(s1, s2));

{{out}}

<pre>

=={{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;

}

 

 

Iterative solution:

 

 

sub leven {

}

 

 

=={{header|Phix}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #0000FF;">{</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">""</span><span style="color: #0000FF;">,</span> <span style="color: #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>

=== 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>

<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');

 

{{out}}

 

=={{header|Picat}}==

Based on the iterative algorithm at Wikipedia. Picat is 1-based so some adjustments are needed.

M = 1+S.length,

N = 1+T.length,

end,

 

 

===Tabled recursive version===

levenshtein_rec(S,T) = Dist =>

Dist1 = 0,

Dist1 := A + 1

end,

 

===Mode-directed tabling===

{{trans|Prolog}}

levenshtein_mode(S,T) = Dist =>

lev(S, T, Dist).

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 = [

nl

end,

 

{{out}}

===Benchmark on larger strings===

Benchmarking the methods with larger strings of random lengths (between 1 and 2000).

_ = random2(),

Len = 2000,

Alpha = "abcdefghijklmnopqrstuvxyz",

Len = Alpha.length,

 

Here is sample run. The version using mode-directed tabling is clearly the fastest.

=={{header|PicoLisp}}==

Translation of the pseudo-code in the Wikipedia article:

(let D

(cons

(get D J (inc I))

(get D (inc J) I)

or, using 'map' to avoid list indexing:

(let D

(cons

(cadr Y) ) )

B

{{out|Output (both cases)}}

<pre>: (levenshtein (chop "kitten") (chop "sitting"))

=={{header|PL/I}}==

===version 1===

lsht: Proc Options(main);

Call test('kitten' ,'sitting');

Return(ld);

End;

{{out}}

<pre> 1st string = >kitten<

Levenshtein distance = 3</pre>

===version 2 recursive with memoization===

ld3: Proc Options(main);

Dcl ld(0:30,0:30) Bin Fixed(31);

Return(ld(sl,tl));

End;

Output is the same as for version 1.

 

=={{header|PowerShell}}==

This version does not allow empty strings.

function Get-LevenshteinDistance

{

$outputObject

}

Get-LevenshteinDistance "kitten" "sitting"

Get-LevenshteinDistance rosettacode raisethysword

{{Out}}

<pre>

 

=={{header|Processing}}==

println(distance("kitten", "sitting"));

}

}

return costs[b.length()];

 

==={{header|Processing Python mode}}===

 

println(distance("kitten", "sitting"))

 

costs[j] = cj

 

 

=={{header|Prolog}}==

Works with SWI-Prolog.<br>

Based on Wikipedia's pseudocode.

length(S, M),

M1 is M+1,

 

init_n(N, L) :-

{{out|Output examples}}

<pre> ?- levenshtein("kitten", "sitting", R).

=={{header|PureBasic}}==

Based on Wikipedia's pseudocode.

Protected m, n, i, j, min, k, l

m = Len(A_string$)

;- Testing

n = LevenshteinDistance("kitten", "sitting")

 

=={{header|Python}}==

===Iterative 1===

Faithful implementation of "Iterative with full matrix" from Wikipedia

m = len(str1)

n = len(str2)

 

print(levenshteinDistance("kitten","sitting"))

{{out}}

<pre>3

===Iterative 2===

Implementation of the Wikipedia algorithm, optimized for memory

if len(s1) > len(s2):

s1,s2 = s2,s1

print(minimumEditDistance("kitten","sitting"))

{{out}}

<pre>3

===Iterative 3===

Iterative space optimized (even bounded)

def result(d): return d if mx < 0 else False if d > mx else True

ld('kitten','kittenaaaaaaaaaaaaaaaaa',3), # False

ld('kittenaaaaaaaaaaaaaaaaa','kitten',3) # False

{{out}}

<pre>0 1 2 3 4 8 17 17

====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):

 

>>> print( ld("kitten","sitting"),ld("rosettacode","raisethysword") )

 

====Non-recursive: reduce and scanl====

{{Works with|Python|3.7}}

 

from itertools import (accumulate, chain, islice)

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>Levenshtein minimum edit distances:

=={{header|Racket}}==

A memoized recursive implementation.

 

(define (levenshtein a b)

 

(levenshtein "kitten" "sitting")

{{out}}

<pre>3

=={{header|Raku}}==

(formerly Perl 6)

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;

}

 

}

 

{{out}}

<pre>Levenshtein distance('kitten', 'sitting') == 3

Levenshtein distance('saturday', 'sunday') == 3

Levenshtein distance('rosettacode', 'raisethysword') == 8</pre>

 

=={{header|REXX}}==

===version 1===

As per the task's requirements, this version includes a driver to display the results.

call Levenshtein 'kitten' , "sitting"

call Levenshtein 'rosettacode' , "raisethysword"

end /*k*/

end /*j*/ /* [↑] best choice.*/

{{out|output|text=&nbsp; when using the internal default inputs:}}

<pre>

===version 2===

<strike>same as</strike> Similar to version 1 <strike>(but does not include a driver for testing)</strike>, reformatted and commented

/*rexx*/

 

say 'Levenshtein distance = ' d.m.n; say ''

Return d.m.n

{{output}}

<pre>

===version 3===

Alternate algorithm from Wikipedia <strike>(but does not include a driver for testing)</strike>.

/*rexx*/

 

End

return v1.tl

{{output}}

<pre>

===version 4 (recursive)===

Recursive algorithm from Wikipedia with memoization

/*rexx*/

 

End

Return ld.sl.tl

{{output}}

<pre>

 

=={{header|Ring}}==

# Project : Levenshtein distance

 

levenshteindistance = d[n][m]

return levenshteindistance

Output:

<pre>

distance(saturday, sunday) = 3

distance(rosettacode, raisethysword) = 8

</pre>

 

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)

end

 

{{out}}

<pre>

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

%w{kitten sitting saturday sunday rosettacode raisethysword}.each_slice(2) do |a, b|

puts "distance(#{a}, #{b}) = #{levenshtein_distance(a, b)}"

same output

 

=={{header|Run BASIC}}==

print levenshteinDistance("rosettacode", "raisethysword")

end

levenshteinDistance = d(n, m)

[ex]

8</pre>

 

Implementation of the wikipedia algorithm.

{{works with|Rust|1.45}}

println!("{}", levenshtein_distance("kitten", "sitting"));

println!("{}", levenshtein_distance("saturday", "sunday"));

}

matrix[word2_length-1][word1_length-1]

{{out}}

<pre>3

=={{header|Scala}}==

===Translated Wikipedia algorithm.===

 

def distance(s1: String, s2: String): Int = {

printDistance("rosettacode", "raisethysword")

 

{{out}}

<pre>kitten -> sitting : 3

===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

 

printDistance("sleep", "fleeting")

 

 

=={{header|Scheme}}==

Recursive version from wikipedia article.

 

(define (levenshtein s t)

(define (%levenshtein s sl t tl)

(string->list t)

(string-length t)))

 

{{out}}

 

=={{header|Seed7}}==

 

const func integer: levenshteinDistance (in string: s, in string: t) is func

writeln("kitten -> sitting: " <& levenshteinDistance("kitten", "sitting"));

writeln("rosettacode -> raisethysword: " <& levenshteinDistance("rosettacode", "raisethysword"));

 

{{out}}

=={{header|SenseTalk}}==

SenseTalk has a built-in TextDifference function for this.

put textDifference("kitten", "sitting") // --> 3

put textDifference("rosettacode", "raisethysword") // --> 8

 

 

=={{header|SequenceL}}==

This implementation is based on the "Iterative with two matrix rows" version on Wikipedia.

import <Utilities/Sequence.sl>;

import <Utilities/Math.sl>;

min(min(v1[n] + 1, v0[n + 1] + 1), v0[n] + (0 when s = t[n] else 1))),

n + 1);

 

=={{header|Sidef}}==

===Recursive===

 

s || return t.len

t || return s.len

 

 

s[0] == t[0] ? __FUNC__(s1, t1)

__FUNC__(s1, t )

)

 

===Iterative===

var d = [@(0 .. t.len), s.len.of {[_]}...]

for i,j in (^s ~X ^t) {

}

d[-1][-1]

 

Calling the function:

 

=={{header|Simula}}==

 

INTEGER PROCEDURE LEVENSHTEINDISTANCE(S1, S2); TEXT S1, S2;

 

END

{{out}}

<pre>

{{works with|Smalltalk/X}}

ST/X provides a customizable levenshtein method in the String class (weights for individual operations can be passed in):

 

=={{header|Swift}}==

Version using entire matrix:

 

let (t, s) = (w1.characters, w2.characters)

}

return mat.last!.last!

 

Version using only two rows at a time:

 

let (t, s) = (w1.characters, w2.characters)

}

return last.last!

 

===Single array version===

{{trans|C++}}

let m = string1.count

let n = string2.count

}

 

 

{{out}}

 

=={{header|Tcl}}==

# Edge cases

if {![set n [string length $t]]} {

# 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 )

s2 = "altruistic"

Warn( "Minimum amount of steps to convert ", s1, " to ", s2, " = ", FNMathGetDamerauLevenshteinDistanceI( s1, s2 ) ) // gives e.g. 6

 

=={{header|Turbo-Basic XL}}==

10 DIM Word_1$(20), Word_2$(20), DLDm(21, 21)

11 CLS

11846 ? "Damerau Distance=";Result

11850 ENDPROC

{{out}}

<pre>kitten, sitting: 3

 

=={{header|TUSCRIPT}}==

$$ MODE TUSCRIPT

distance=DISTANCE ("kitten", "sitting")

PRINT distance

Output:

<pre>

=={{header|TypeScript}}==

{{Trans|JavaScript}}

function levenshtein(a: string, b: string): number {

const m: number = a.length,

}

 

 

=={{header|Vala}}==

public static int compute (owned string s, owned string t, bool case_sensitive = false) {

var n = s.length;

}

}

 

=={{header|VBA}}==

Function levenshtein(s1 As String, s2 As String) As Integer

Dim n As Integer: n = Len(s1) + 1

Debug.Print levenshtein("kitten", "sitting")

Debug.Print levenshtein("rosettacode", "raisethysword")

<pre> 3

8 </pre>

 

=={{header|VBScript}}==

 

Function Min(a,b)

PrintLevenshtein "rosettacode", "raisethysword"

PrintLevenshtein "saturday", "sunday"

{{out}}

<pre>

{{works with|VBA|6.5}}

{{works with|VBA|7.1}}

If x < y Then

min = x

Debug.Print "'sleep' to 'fleeting' => "; levenshtein("sleep", "fleeting")

End Sub

{{out}}

'sitting' to 'kitten' => 3

'rosettacode' to 'raisethysword' => 8

 

=={{header|Visual Basic .NET}}==

Dim Matrix(String1.Length, String2.Length) As Integer

Dim Key As Integer

Next

Return Matrix(String1.Length - 1, String2.Length - 1)

 

=={{header|Wren}}==

{{trans|Go}}

var ls = s.count

var lt = t.count

}

 

 

{{out}}

3

</pre>

 

=={{header|zkl}}==

{{trans|D}}

sz2,costs:=s2.len() + 1, List.createLong(sz2,0); // -->zero filled List

foreach i in (s1.len() + 1){

}

costs[-1]

T("yo",""), T("","yo"), T("abc","abc")) ){

println(a," --> ",b,": ",levenshtein(a,b));

{{out}}

<pre>

 

=={{header|ZX Spectrum Basic}}==

20 INPUT "first word:",n$

30 INPUT "second word:",m$

120 NEXT i

130 NEXT j

{{out}}

<pre>