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

{{Improve||The output shown does not appear to match the PrintF calls in the code}}

DEFINE STRING="CHAR ARRAY" ; sys.act

DEFINE width="15" ; max characters 14

;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

<br>

Non-recursive algorithm - although Algol 68 supports recursion, Action! doesn't.

BEGIN

print((word 1," -> ",word 2,": "));

print(("Levenshtein Distance: ",whole(levenshtein distance(word 1,word 2),0),newline))

{{out}}

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

<lang> "kitten" Levenshtein "sitting"

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)

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

(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}}

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

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

{{out}}<pre>

kitten sitting 3 T

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

Based on Wikipedia algorithm. Suitable for Pascal strings.

local fn LevenshteinDistance( aStr as Str255, bStr as Str255 ) as long

next

Output:

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

===Implementation 1===

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

where

main :: IO ()

{{Out}}

<pre>3</pre>

===Implementation 2===

levenshtein s1 [] = length s1

levenshtein [] s2 = length s2

main :: IO ()

{{Out}}

<pre>3</pre>

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

every process(!&input)

end

return d[n,m]-1

{{out|Example}}

<pre>

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;

}

{{output}}

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

'''Output:'''

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

==Iterative==

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

M = 1+S.length,

N = 1+T.length,

end,