Levenshtein distance: Difference between revisions

 

 

Implements a Levenshtein distance function, or uses a library function, to show the Levenshtein distance between   "kitten"   and   "sitting".

 

;Related task:

*   [[Longest common subsequence]]

<br><br>

 

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

 

FOR I=0 TO MatrixSize-1 DO matrix(I)=0 OD

FOR J=1 TO N DO

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

{{Trans|JavaScript}}

(ES6 version)

on levenshtein(sa, sb)

set {s1, s2} to {characters of sa, characters of sb}

end script

end levenshtein

 

on run

script test

end |λ|

end script

 

 

 

-- enumFromTo :: Int -> Int -> [Int]

end if

end enumFromTo

 

-- fromEnum :: Enum a => a -> Int

end if

end fromEnum

 

-- foldl :: (a -> b -> a) -> a -> [b] -> a

end tell

end foldl

 

-- map :: (a -> b) -> [a] -> [b]

end tell

end map

 

-- minimum :: Ord a => [a] -> a

return m

end minimum

 

-- mReturn :: First-class m => (a -> b) -> m (a -> b)

end if

end mReturn

 

-- scanl :: (b -> a -> b) -> b -> [a] -> [b]

end tell

end scanl

 

-- zip3 :: [a] -> [b] -> [c] -> [(a, b, c)]

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

'rosettacode' -> 'raisethysword' has distance 8

</pre>

 

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

// Martin Ettl, 2012-10-05

 

{

 

if( m==0 ) return n;

if( n==0 ) return m;

 

 

for( size_t k=0; k<=n; k++ ) costs[k] = k;

 

{

costs[0] = i+1;

{

costs[j+1] = (costs[j]<t?costs[j]:t)+1;

corner = upper;

}

}

 

}

 

int main()

{

 

{{out|Example output}}

<pre>

distance between rosettacode and raisethysword : 8

</pre>

 

 

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

 

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

Based on Wikipedia version

var

i, j : Integer;

end;

 

 

=={{header|Dyalect}}==

 

if n == 0 {

return m

d[i][0] = i

}

for j in 0..m {

d[0][j] = j

}

}

d[n][m]

}

func run(x, y) {

print("\(x) -> \(y) = \(levenshtein(x, y))")

}

 

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

m = tuple_size(ta)

n = tuple_size(tb)

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

</pre>

 

open System

 

 

Console.ReadKey () |> ignore

 

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

 

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

 

Then we reduce the rows of that matrix using an operation that treats those two rows as columns and reduces the rows of this derived matrix with an operation that gives the (unexplored cell + the minumum of the other cells) followed by (the cell adjacent to the previously unexplored cell.

{{out|Example use}}

3

Time and space use:

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;

int[] cost = new int[lb+1];

for (int i=1; i<=la; i+=1) {

cost[0] = i;

}

}

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

 

// levenshtein :: String -> String -> Int

);

};

 

 

 

 

 

 

};

 

 

 

}, (_, i) => m + i);

 

 

 

{{Out}}

 

=={{header|jq}}==

The main point of interest about the following implementation is that it shows how the naive recursive algorithm can be tweaked within a completely functional framework to yield an efficient implementation.

 

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

levenshteinDistance between rosettacode and raisethysword is 8

levenshteinDistance between edocattesor and drowsyhtesiar is 8

 

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

{{trans|ooRexx}}

options replace format comments java crossref symbols nobinary

 

 

return d[m + 1, n + 1]

'''Output:'''

<pre>

 

=={{header|Nim}}==

 

 

{{out}}

 

{{trans|Python}}

 

var (s1, s2) = (s1, s2)

 

newDistances.add(distances[i1])

else:

 

distances = newDistances

 

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

{{out}}

<pre>

</pre>

 

=={{header|PHP}}==

echo levenshtein('kitten','sitting');

echo levenshtein('rosettacode', 'raisethysword');

 

{{out}}

<pre>3

8</pre>

 

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

?- levenshtein("rosettacode", "raisethysword", R).

R = 8.

</pre>

 

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

if len(s1) > len(s2):

s1,s2 = s2,s1

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

{{out}}

<pre>3

8</pre>

 

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

 

===Functional===

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

my @s = *, |$s.comb;

my @t = *, |$t.comb;

}

 

}

 

 

{{out}}

 

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

Parse Arg s,t

/* for all i and j, d[i,j] will hold the Levenshtein distance between */

Say ' 2nd string = ' t

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

 

===version 3===

Parse Arg s,t

If s==t Then Return 0;

End

End

 

===version 4 (recursive)===

Recursive algorithm from Wikipedia with memoization

call test 'rosettacode' ,'raisethysword'

call test 'Sunday' ,'Saturday'

call test '','abc'

Exit

 

test: Procedure

Say ''

Return

 

LevenshteinDistance: Procedure Expose ld.

/* test if last characters of the strings match */

cost=substr(s,sl,1)<>substr(t,tl,1)

and delete char from both */

ld.sl.tl=min(LevenshteinDistance(s,sl-1,t,tl )+1,,

End

End

 

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

 

=={{header|Rust}}==

Implementation of the wikipedia algorithm.

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

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

println!("{}", levenshtein_distance("rosettacode", "raisethysword"));

}

fn levenshtein_distance(word1: &str, word2: &str) -> usize {

let w1 = word1.chars().collect::<Vec<_>>();

let w2 = word2.chars().collect::<Vec<_>>();

let word1_length = w1.len() + 1;

let word2_length = w2.len() + 1;

for j in 1..word2_length {

for i in 1..word1_length {

, matrix[j-1][i-1])

};

}

}

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!

 

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

11600 PROC _DLD_

11610 Result=0 : M=LEN(Word_1$) : N=LEN(Word_2$)

11640 FOR J=1 TO N

11650 FOR I=1 TO M

11846 ? "Damerau Distance=";Result

11850 ENDPROC

{{out}}

<pre>kitten, sitting: 3

 

=={{header|TUSCRIPT}}==

$$ MODE TUSCRIPT

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

PRINT distance

Output:

<pre>

3

</pre>

 

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