Levenshtein distance/Alignment: Difference between revisions

{{trans|Nim}}

 

V a = aa.lowercase()

V b = bb.lowercase()

result = levenshteinAlign(‘rosettacode’, ‘raisethysword’)

print(result[0])

 

{{out}}

=={{header|Arturo}}==

 

 

{{out}}

 

=={{header|C}}==

#include <stdlib.h>

#include <string.h>

leven("raisethysword", "rosettacode");

return 0;

{{out}}

<pre>

=={{header|D}}==

Using the standard library.

import std.stdio, std.algorithm;

 

 

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

{{out}}

<pre>r_oset_tacode

 

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

 

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

 

 

Translation of java:

 

assert. x <:&# y

D=. x +/&i.&>:&# y

end.

A,:&|.B

 

Task examples:

 

p-lace

palace

r-oset-tacode

raisethysword

 

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

<span style="color: #008080;">function</span> <span style="color: #000000;">LevenshteinAlignment</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;">integer</span> <span style="color: #000000;">la</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>

<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"rosettacode"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"raisethysword"</span><span style="color: #0000FF;">)</span>

<span style="color: #000000;">test</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"place"</span><span style="color: #0000FF;">,</span> <span style="color: #008000;">"palace"</span><span style="color: #0000FF;">)</span>

{{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!('^')

}

 

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

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>