Levenshtein distance: Difference between revisions

{{trans|Python}}

 

I s1.len > s2.len

(s1, s2) = (s2, s1)

 

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

LEVENS CSECT

USING LEVENS,R13 base register

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

 

=={{header|Ada}}==

 

procedure Main is

=={{header|Aime}}==

{{trans|C}}

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

{

<br>

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

BEGIN

 

===Iteration===

Translation of the "fast" C-version

to findLevenshteinDistance for s1 against s2

script o

 

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}

end zip3</syntaxhighlight>

{{Out}}

 

=={{header|Arc}}==

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

 

(withs l1 len.str1

l2 len.str2

=={{header|Arturo}}==

 

 

{{out}}

=={{header|AutoHotkey}}==

{{trans|Go}}

If s =

return StrLen(t)

Slavishly copied from the very clear AutoHotKey example.

 

 

BEGIN {

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

 

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

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

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

=={{header|BQN}}==

Recursive slow version:

𝕨 𝕊"": ≠𝕨;

""𝕊 𝕩: ≠𝕩;

}</syntaxhighlight>

Fast version:

{{out|Example use}}

3

"Saturday" Levenshtein "Sunday"

{{trans|C}}

Recursive method, but with memoization.

lev cache

. ( lev

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>

 

}</syntaxhighlight>

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

#include <string.h>

 

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

This is a straightforward translation of the Wikipedia pseudocode.

 

namespace LevenshteinDistance

 

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

#include <iostream>

using namespace std;

 

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

#include <iostream>

#include <numeric>

 

===Recursive Version===

(let [len1 (count str1)

len2 (count str2)]

 

===Iterative version===

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

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

 

=={{header|CLU}}==

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

if a<b

=={{header|COBOL}}==

GnuCobol 2.2

identification division.

program-id. Levenshtein.

 

=={{header|CoffeeScript}}==

# more of less ported simple algorithm from JS

m = str1.length

 

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

 

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

 

{{trans|Ruby 1st version}}

def self.distance(a, b)

 

{{trans|Ruby 2nd version}}

n, m = str1.size, str2.size

max = n / 2

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

 

===Iterative Version===

{{trans|Java}}

 

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

===Memoized Recursive Version===

{{trans|Python}}

 

uint lDist(T)(in const(T)[] s, in const(T)[] t) nothrow {

=={{header|Delphi}}==

{{Trans|C#}}

program Levenshtein_distanceTest;

 

=={{header|DWScript}}==

Based on Wikipedia version

var

i, j : Integer;

=={{header|Dyalect}}==

 

var n = s.Length()

var m = t.Length()

 

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

 

=={{header|EchoLisp}}==

;; Recursive version adapted from Clojure

;; Added necessary memoization

This code is translated from Haskell version.

 

 

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

Executing:

 

{{out}}

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

=={{header|Elixir}}==

{{trans|Ruby}}

def distance(a, b) do

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

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

</syntaxhighlight>

Below is a comparison of the runtimes, measured in microseconds, between the two implementations.

68> timer:tc(levenshtein,distance,["rosettacode","raisethysword"]).

{774799,8} % {Time, Result}

 

=={{header|ERRE}}==

PROGRAM LEVENSHTEIN

 

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

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

=== Standard version ===

open System

 

 

=== Recursive Version ===

open System

 

 

=={{header|Factor}}==

"kitten" "sitting" levenshtein .</syntaxhighlight>

{{out}}

=={{header|Forth}}==

{{trans|C}}

dup \ if either string is empty, difference

if \ is inserting all chars from the other

 

=={{header|Fortran}}==

program demo_edit_distance

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

 

=={{header|FreeBASIC}}==

 

' Uses the "iterative with two matrix rows" algorithm

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

 

 

 

print

next

 

 

<pre>

1st string = kitten

Levenshtein distance = 0

 

</pre>

 

=={{header|Go}}==

WP algorithm:

 

import "fmt"

</pre>

{{trans|C}}

 

import "fmt"

 

=={{header|Groovy}}==

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

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

 

===Implementation 1===

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

where

 

===Implementation 2===

levenshtein s1 [] = length s1

levenshtein [] s2 = length s2

 

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

every process(!&input)

end

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

==> 8

Io> </syntaxhighlight>

 

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

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

)</syntaxhighlight>

{{out|Example use}}

3

'kitten' levdist 'sitting'

3</syntaxhighlight>

Time and space use:

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

0.000113 6016

=={{header|Java}}==

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

 

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

</pre>

{{trans|C}}

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

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

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

{{trans|Python}}

import static java.lang.Math.abs;

import static java.lang.Math.max;

===ES5===

Iterative:

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

if (!m) { return n; }

 

By composition of generic functions:

'use strict';

 

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:

s as $s | t as $t | {} | ld($s;$t) | .[0];</syntaxhighlight>

'''Task'''

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

=={{header|Jsish}}==

From Javascript, ES5 entry.

 

function levenshtein(a, b) {

'''Recursive''':

{{works with|Julia|1.0}}

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

ls == 0 && return lt

'''Iterative''':

{{works with|Julia|0.6}}

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

if ls > lt

 

Let's see some benchmark:

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

s, t = "kitten", "sitting"

=={{header|Kotlin}}==

===Standard Version===

 

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

 

===Functional/Folding Version===

fun levenshtein(s: String, t: String,

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

Suitable for short strings:

 

(defun levenshtein-simple

(('() str)

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

 

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

0

=== Cached Implementation ===

 

(defun levenshtein-distance (str1 str2)

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

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

 

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

'08/19/10

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

=={{header|Limbo}}==

{{trans|Go}}

 

include "sys.m"; sys: Sys;

=={{header|LiveCode}}==

{{trans|Go}}

//Code By Neurox66

function Levenshtein pString1 pString2

=={{header|Lobster}}==

{{trans|C}}

 

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

 

=={{header|Lua}}==

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

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

 

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

Module Checkit {

\\ Iterative with two matrix rows

 

=={{header|Maple}}==

> with(StringTools):

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

 

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

EditDistance["rosettacode","raisethysword"]</syntaxhighlight>

{{out}}

 

=={{header|MATLAB}}==

function score = levenshtein(s1, s2)

% score = levenshtein(s1, s2)

=={{header|MiniScript}}==

In the Mini Micro environment, this function is part of the stringUtil library module, and can be used like so:

print "kitten".editDistance("sitting")</syntaxhighlight>

 

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

n = self.len

m = s2.len

 

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

FROM InOut IMPORT WriteString, WriteCard, WriteLn;

FROM Strings IMPORT Length;

=={{header|NetRexx}}==

{{trans|ooRexx}}

options replace format comments java crossref symbols nobinary

 

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

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

echo levenshteinDistance("rosettacode","raisethysword")</syntaxhighlight>

 

=={{header|Objeck}}==

{{trans|C#}}

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

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

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

Translation of the C# code into a NSString category

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

@end

=={{header|OCaml}}==

Translation of the pseudo-code of the Wikipedia article:

min a (min b c)

 

=== A recursive functional version ===

This could be made faster with memoization

let rec dist i j = match (i,j) with

| (i,0) -> i

 

=={{header|ooRexx}}==

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

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

{{trans|JavaScript}}

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

\\ Levenshtein distance between two words

\\ 6/21/16 aev

=={{header|Pascal}}==

A fairly direct translation of the wikipedia pseudo code:

 

uses

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

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

 

=={{header|PHP}}==

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

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

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

 

===Tabled recursive version===

levenshtein_rec(S,T) = Dist =>

Dist1 = 0,

===Mode-directed tabling===

{{trans|Prolog}}

levenshtein_mode(S,T) = Dist =>

lev(S, T, Dist).

 

===Test===

S = [

===Benchmark on larger strings===

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

_ = random2(),

Len = 2000,

=={{header|PicoLisp}}==

Translation of the pseudo-code in the Wikipedia article:

(let D

(cons

(get D J I) ) ) ) ) ) ) ) )</syntaxhighlight>

or, using 'map' to avoid list indexing:

(let D

(cons

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

===version 1===

lsht: Proc Options(main);

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

Levenshtein distance = 3</pre>

===version 2 recursive with memoization===

ld3: Proc Options(main);

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

{{works with|8080 PL/M Compiler}} ... under CP/M (or an emulator)

{{Trans|Action!}}

/* TRANS:ATED FROM THE ACTION! SAMPLE */

 

=={{header|PowerShell}}==

This version does not allow empty strings.

function Get-LevenshteinDistance

{

}

</syntaxhighlight>

Get-LevenshteinDistance "kitten" "sitting"

Get-LevenshteinDistance rosettacode raisethysword

 

=={{header|Processing}}==

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

}

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

 

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

 

Works with SWI-Prolog.<br>

Based on Wikipedia's pseudocode.

length(S, M),

M1 is M+1,

=={{header|PureBasic}}==

Based on Wikipedia's pseudocode.

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

m = Len(A_string$)

===Iterative 1===

Faithful implementation of "Iterative with full matrix" from Wikipedia

m = len(str1)

n = len(str2)

===Iterative 2===

Implementation of the Wikipedia algorithm, optimized for memory

if len(s1) > len(s2):

s1,s2 = s2,s1

===Iterative 3===

Iterative space optimized (even bounded)

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

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

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

{{Works with|Python|3.7}}

 

from itertools import (accumulate, chain, islice)

=={{header|Racket}}==

A memoized recursive implementation.

 

(define (levenshtein a b)

 

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;

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"

===version 2===

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

/*rexx*/

 

===version 3===

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

/*rexx*/

 

===version 4 (recursive)===

Recursive algorithm from Wikipedia with memoization

/*rexx*/

 

 

=={{header|Ring}}==

# Project : Levenshtein distance

 

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)

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

 

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

print levenshteinDistance("rosettacode", "raisethysword")

end

Implementation of the wikipedia algorithm.

{{works with|Rust|1.45}}

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

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

=={{header|Scala}}==

===Translated Wikipedia algorithm.===

 

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

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

 

Recursive version from wikipedia article.

 

(define (levenshtein s t)

(define (%levenshtein s sl t tl)

 

=={{header|Seed7}}==

 

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

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

=={{header|Sidef}}==

===Recursive===

 

s || return t.len

t || return s.len

 

 

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

 

===Iterative===

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

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

 

Calling the function:

say lev(%c'rosettacode', %c'raisethysword'); # prints: 8</syntaxhighlight>

 

=={{header|Simula}}==

 

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

{{works with|Smalltalk/X}}

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

'rosettacode' levenshteinTo: 'raisethysword' s:1 k:1 c:1 i:1 d:1 -> 8</syntaxhighlight>

 

Version using entire matrix:

 

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

Version using only two rows at a time:

 

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

===Single array version===

{{trans|C++}}

let m = string1.count

let n = string2.count

 

=={{header|Tcl}}==

# Edge cases

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

}</syntaxhighlight>

{{out|Usage}}

 

=={{header|TSE SAL}}==

INTEGER PROC FNMathGetDamerauLevenshteinDistanceI( STRING s1, STRING s2 )

INTEGER L1 = Length( s1 )

 

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

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

11 CLS

 

=={{header|TUSCRIPT}}==

$$ MODE TUSCRIPT

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

=={{header|TypeScript}}==

{{Trans|JavaScript}}

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

const m: number = a.length,

}

 

</syntaxhighlight>

 

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

 

=={{header|VBScript}}==

 

Function Min(a,b)

{{works with|VBA|6.5}}

{{works with|VBA|7.1}}

If x < y Then

min = x

</syntaxhighlight>

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

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

End Function</syntaxhighlight>

 

=={{header|Wren}}==

{{trans|Go}}

var ls = s.count

var lt = t.count

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]

}</syntaxhighlight>

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

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

 

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

20 INPUT "first word:",n$

30 INPUT "second word:",m$