Levenshtein distance: Difference between revisions

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

This is a straightforward translation of the Wikipedia pseudocode.

<lang csharp>using System;

namespace LevenshteinDistance

{

class Program

{

static int LevenshteinDistance(string s, string t)

{

int n = s.Length;

int m = t.Length;

int[,] d = new int[n + 1, m + 1];

if (n == 0)

{

return m;

}

if (m == 0)

{

return n;

}

for (int i = 0; i <= n; i++)

d[i, 0] = i;

for (int j = 0; j <= m; j++)

d[0, j] = j;

for (int j = 1; j <= m; j++)

for (int i = 1; i <= n; i++)

if (s[i - 1] == t[j - 1])

d[i, j] = d[i - 1, j - 1]; //no operation

else

d[i, j] = Math.Min(Math.Min(

d[i - 1, j] + 1, //a deletion

d[i, j - 1] + 1), //an insertion

d[i - 1, j - 1] + 1 //a substitution

);

return d[n, m];

}

static void Main(string[] args)

{

if (args.Length == 2)

Console.WriteLine("{0} -> {1} = {2}",

args[0], args[1], LevenshteinDistance(args[0], args[1]));

else

Console.WriteLine("Usage:-\n\nLevenshteinDistance <string1> <string2>");

}

}

}</lang>

{{out|Example output}}

<pre>

> LevenshteinDistance kitten sitting

kitten -> sitting = 3

> LevenshteinDistance rosettacode raisethysword

rosettacode -> raisethysword = 8

</pre>

=={{header|Clojure}}==

===Recursive Version===

<lang lisp>(defn levenshtein [str1 str2]

(let [len1 (count str1)

len2 (count str2)]

(cond (zero? len1) len2

(zero? len2) len1

:else

(let [cost (if (= (first str1) (first str2)) 0 1)]

(min (inc (levenshtein (rest str1) str2))

(inc (levenshtein str1 (rest str2)))

(+ cost

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

(println (levenshtein "rosettacode" "raisethysword"))</lang>

{{out}}

<pre>8</pre>

===Iterative version===

<lang lisp>(defn levenshtein [w1 w2]

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

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

(inc (last cur-row))

(+ (nth prev-row (dec col-idx)) (if same-char?

0

1))))]

(loop [row-idx 1

max-rows (inc (count w2))

prev-row (range (inc (count w1)))]

(if (= row-idx max-rows)

(last prev-row)

(let [ch2 (nth w2 (dec row-idx))

next-prev-row (reduce (fn [cur-row i]

(let [same-char? (= (nth w1 (dec i)) ch2)]

(conj cur-row (cell-value same-char?

prev-row

cur-row

i))))

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

(recur (inc row-idx) max-rows next-prev-row))))))</lang>

=={{header|Perl 6}}==

{{works with|rakudo|2015-09-16}}

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 the $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.

<lang perl6>sub levenshtein_distance ( Str $s, Str $t --> Int ) {

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

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

my @d;

@d[$_; 0] = $_ for ^@s.end;

@d[ 0; $_] = $_ for ^@t.end;

for 1..@s.end X 1..@t.end -> ($i, $j) {

@d[$i; $j] = @s[$i] eq @t[$j]

?? @d[$i-1; $j-1] # No operation required when eq

!! ( @d[$i-1; $j ], # Deletion

@d[$i ; $j-1], # Insertion

@d[$i-1; $j-1], # Substitution

).min + 1;

}

return @d[*-1][*-1];

}

my @a = [<kitten sitting>], [<saturday sunday>], [<rosettacode raisethysword>];

for @a -> [$s, $t] {

say "levenshtein_distance('$s', '$t') == ", levenshtein_distance($s, $t);

}</lang>

{{out}}

<pre>levenshtein_distance('kitten', 'sitting') == 3

levenshtein_distance('saturday', 'sunday') == 3

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