Levenshtein distance/Alignment: Difference between revisions

<br><br>

 

 

 

{{out}}

 

=={{header|C}}==

#include <stdlib.h>

#include <string.h>

leven("raisethysword", "rosettacode");

return 0;

{{out}}

<pre>

raisethysword -> rosettacode: 8 edits

r(a,o)(i,)set(h,t)(y,a)(s,c)(w,)o(r,d)(d,e)

</pre>

 

=={{header|D}}==

Using the standard library.

import std.stdio, std.algorithm;

 

 

writeln(s1b, "\n", s2b);

{{out}}

<pre>r_oset_tacode

raisethysword</pre>

 

=={{header|Eiffel}}==

distance (source, target: STRING): INTEGER

-- Minimum number of operations to turn `source' into `target'.

Result:= l_distance [source.count, target.count]

end

Result = 8

 

 

Also—the `ic' is this programmers shorthand for ITERATION_CURSOR. Therefore, in the nested loops, the `ic' is the iteration cursor following `i' and the `ij' is following `j' as indexes on the source, target, and l_distance.

 

=={{header|Go}}==

{{libheader|biogo}}

Alignment computed by the Needleman-Wunch algorithm, which is used in bioinformatics.

 

import (

}

fmt.Println(string(ma))

{{out}}

The lines after the alignment point out the 8 edits.

=={{header|Haskell}}==

The Wagner–Fischer matrix construction is adopted from [[Levenshtein_distance#Haskell]], however it is reversed in order to simplify it's traversing.

costs s1 s2 = reverse $ reverse <$> matrix

where

 

levenshteinDistance :: String -> String -> Int

 

 

Instead of indices the Wagner–Fischer matrix and strings are traversed by list truncation, as zippers.

 

alignment s1 s2 = go (costs s1 s2) (reverse s1) (reverse s2) ([],[])

where

nextRow = map tail

nextCol = tail

 

<pre>λ> alignment "palace" "place"

The alternative solution, which extensively produces all minimal alignments for given strings.

 

allAlignments :: String -> String -> [[(Char, Char)]]

allAlignments s1 s2 = go (length s2 - length s1) s1 s2

best = filter ((lev ==) . dist) $ allAlignments s1 s2

lev = levenshteinDistance s1 s2

 

 

("rosettacode","r-----a---t")</pre>

 

 

=={{header|Java}}==

 

public static String[] alignment(String a, String b) {

System.out.println(result[1]);

}

{{out}}

<pre>

{{trans|Java}}

 

a = lowercase(a)

b = lowercase(b)

 

foreach(println, levenshteinalign("rosettacode", "raisethysword"))

 

{{out}}

=={{header|Kotlin}}==

{{trans|Java}}

 

fun levenshteinAlign(a: String, b: String): Array<String> {

println(result[0])

println(result[1])

 

{{out}}

{{incorrect}}

{{works with|Mathematica|7}}

 

{{out}}<pre>8</pre>

=={{header|Nim}}==

{{trans|Kotlin}}

 

proc levenshteinAlign(a, b: string): tuple[a, b: string] =

result = levenshteinAlign("rosettacode","raisethysword")

echo result.a

 

{{out}}

 

=={{header|Perl}}==

use warnings;

 

}

{{out}}

<pre>ro-settac-o-de

=={{header|Phix}}==

{{trans|Kotlin}} plus the indicator from Go

{{out}}

<pre>

 

=={{header|Python}}==

 

def levenshtein(str1, str2):

 

levenshtein("place","palace")

{{out}}

<pre>

for a discussion of the code.

 

 

(define (memoize f)

(min (add1 (levenshtein (rest s) t))

(add1 (levenshtein s (rest t)))

'''Demonstration:'''

{{out}}

<pre>8</pre>

===Complete version===

Now we extend the code from http://blog.racket-lang.org/2012/08/dynamic-programming-versus-memoization.html to show also the alignment. The code is very similar, but it stores the partial results (number of edits and alignment of each substring) in a lev structure.

 

(struct lev (n s t))

(values (lev-n result)

(list->string (lev-s result))

'''Demonstration:'''

(levenshtein "rosettacode" "raisethysword")])

(printf "levenshtein: ~a edits\n" dist)

(displayln exp-s)

{{out}}

<pre>levenshtein: 8 edits

(formerly Perl 6)

{{trans|Perl}}

my @s = flat *, $σ.comb;

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

}

{{out}}

<pre>ro-settac-o-de

{{trans|Tcl}}

uses "lcs" from [[Longest common subsequence#Ruby|here]]

 

def levenshtein_align(a, b)

end

 

 

{{out}}

 

'''src/main.rs'''

 

 

=={{header|Scala}}==

{{Out}}Best seen running in your browser either by [https://scastie.scala-lang.org/I8BAESkNTjukVPzsWOUyPA ScalaFiddle (ES aka JavaScript, non JVM)] or [https://scastie.scala-lang.org/I8BAESkNTjukVPzsWOUyPA].

import scala.collection.parallel.ParSeq

 

println(alignment._2)

 

 

=={{header|Sidef}}==

{{trans|Perl}}

s.chars!.prepend!('^')

t.chars!.prepend!('^')

 

var A = []

 

for i (1 .. s.end) {

}

 

{{out}}

ro-settac-o-de

=={{header|Tcl}}==

{{tcllib|struct::list}}

proc levenshtein/align {a b} {

lassign [struct::list longestCommonSubsequence [split $a ""] [split $b ""]]\

}

 

{{out}}

<pre>

{{trans|Kotlin}}

{{libheader|Wren-str}}

 

var levenshteinAlign = Fn.new { |a, b|

for (j in 1..b.count) {

var temp = costs[i - 1][j - 1] + ((a[i - 1] == b[j - 1]) ? 0 : 1)

}

}

result = levenshteinAlign.call("rosettacode","raisethysword")

System.print(result[0])

 

{{out}}

=={{header|zkl}}==

{{trans|Java}}

a,b = a.toLower(), b.toLower();

costs := (a.len()+1).pump(List(),'wrap(a){ [1..b.len()].pump(List(a)) });

}

return(aPathRev.text.reverse(), bPathRev.text.reverse())

println(result[0]);

{{out}}

<pre>