Levenshtein distance/Alignment: Difference between revisions
→{{header|Racket}}: Why was this posted as a potential solution? |
Go solution |
||
Line 141: | Line 141: | ||
<pre>r_oset_tacode |
<pre>r_oset_tacode |
||
raisethysword</pre> |
raisethysword</pre> |
||
=={{header|Go}}== |
|||
{{libheader|biogo}} |
|||
Alignment computed by the Needleman-Wunch algorithm, which is used in bioinformatics. |
|||
<lang go>package main |
|||
import ( |
|||
"fmt" |
|||
"code.google.com/p/biogo/align" |
|||
ab "code.google.com/p/biogo/alphabet" |
|||
"code.google.com/p/biogo/feat" |
|||
"code.google.com/p/biogo/seq/linear" |
|||
) |
|||
func main() { |
|||
// Alphabets for things like DNA are predefined in biogo, but we |
|||
// define our own here. |
|||
lc := ab.Must(ab.NewAlphabet("-abcdefghijklmnopqrstuvwxyz", |
|||
feat.Undefined, '-', 0, true)) |
|||
// Construct scoring matrix for Needleman-Wunch algorithm. |
|||
// We leave zeros on the diagonal for the Levenshtein distance of an |
|||
// exact match and put -1s everywhere else for the Levenshtein distance |
|||
// of an edit. |
|||
nw := make(align.NW, lc.Len()) |
|||
for i := range nw { |
|||
r := make([]int, lc.Len()) |
|||
nw[i] = r |
|||
for j := range r { |
|||
if j != i { |
|||
r[j] = -1 |
|||
} |
|||
} |
|||
} |
|||
// define input sequences |
|||
a := &linear.Seq{Seq: ab.BytesToLetters([]byte("rosettacode"))} |
|||
a.Alpha = lc |
|||
b := &linear.Seq{Seq: ab.BytesToLetters([]byte("raisethysword"))} |
|||
b.Alpha = lc |
|||
// perform alignment |
|||
aln, err := nw.Align(a, b) |
|||
// format and display result |
|||
if err != nil { |
|||
fmt.Println(err) |
|||
return |
|||
} |
|||
fa := align.Format(a, b, aln, '-') |
|||
fmt.Printf("%s\n%s\n", fa[0], fa[1]) |
|||
}</lang> |
|||
{{out}} |
|||
<pre> |
|||
r-oset-tacode |
|||
raisethysword |
|||
</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
Revision as of 23:02, 5 January 2014
The Levenshtein distance algorithm returns the number of atomic operations (insertion, deletion or edition) that must be performed on a string in order to obtain an other one, but it does not say anything about the actual operations used or their order.
An alignment is a notation used to describe the operations used to turn a string into an other. At some point in the strings, the minus character ('-') is placed in order to signify that a character must be added at this very place. For instance, an alignment between the words 'place' and 'palace' is:
P-LACE PALACE
For this task, write a function that shows the alignment of two strings for the corresponding levenshtein distance. As an example, use the words "rosettacode" and "raisethysword".
You can either implement an algorithm, or use a dedicated library (thus showing us how it is named in your language).
C
<lang c>#include <stdio.h>
- include <stdlib.h>
- include <string.h>
typedef struct edit_s edit_t, *edit; struct edit_s { char c1, c2; int n; edit next; };
void leven(char *a, char *b) { int i, j, la = strlen(a), lb = strlen(b); edit *tbl = malloc(sizeof(edit) * (1 + la)); tbl[0] = calloc((1 + la) * (1 + lb), sizeof(edit_t)); for (i = 1; i <= la; i++) tbl[i] = tbl[i-1] + (1+lb);
for (i = la; i >= 0; i--) { char *aa = a + i; for (j = lb; j >= 0; j--) { char *bb = b + j; if (!*aa && !*bb) continue;
edit e = &tbl[i][j]; edit repl = &tbl[i+1][j+1]; edit dela = &tbl[i+1][j]; edit delb = &tbl[i][j+1];
e->c1 = *aa; e->c2 = *bb; if (!*aa) { e->next = delb; e->n = e->next->n + 1; continue; } if (!*bb) { e->next = dela; e->n = e->next->n + 1; continue; }
e->next = repl; if (*aa == *bb) { e->n = e->next->n; continue; }
if (e->next->n > delb->n) { e->next = delb; e->c1 = 0; } if (e->next->n > dela->n) { e->next = dela; e->c1 = *aa; e->c2 = 0; } e->n = e->next->n + 1; } }
edit p = tbl[0]; printf("%s -> %s: %d edits\n", a, b, p->n);
while (p->next) { if (p->c1 == p->c2) printf("%c", p->c1); else { putchar('('); if (p->c1) putchar(p->c1); putchar(','); if (p->c2) putchar(p->c2); putchar(')'); }
p = p->next; } putchar('\n');
free(tbl[0]); free(tbl); }
int main(void) { leven("raisethysword", "rosettacode"); return 0; }</lang>
- Output:
raisethysword -> rosettacode: 8 edits r(a,o)(i,)set(h,t)(y,a)(s,c)(w,)o(r,d)(d,e)
D
Using the standard library. <lang d>void main() {
import std.stdio, std.algorithm;
immutable s1 = "rosettacode"; immutable s2 = "raisethysword";
string s1b, s2b; size_t pos1, pos2;
foreach (immutable c; levenshteinDistanceAndPath(s1, s2)[1]) { final switch (c) with (EditOp) { case none, substitute: s1b ~= s1[pos1++]; s2b ~= s2[pos2++]; break; case insert: s1b ~= "_"; s2b ~= s2[pos2++]; break; case remove: s1b ~= s1[pos1++]; s2b ~= "_"; break; } }
writeln(s1b, "\n", s2b);
}</lang>
- Output:
r_oset_tacode raisethysword
Go
Alignment computed by the Needleman-Wunch algorithm, which is used in bioinformatics. <lang go>package main
import (
"fmt"
"code.google.com/p/biogo/align" ab "code.google.com/p/biogo/alphabet" "code.google.com/p/biogo/feat" "code.google.com/p/biogo/seq/linear"
)
func main() {
// Alphabets for things like DNA are predefined in biogo, but we // define our own here. lc := ab.Must(ab.NewAlphabet("-abcdefghijklmnopqrstuvwxyz", feat.Undefined, '-', 0, true)) // Construct scoring matrix for Needleman-Wunch algorithm. // We leave zeros on the diagonal for the Levenshtein distance of an // exact match and put -1s everywhere else for the Levenshtein distance // of an edit. nw := make(align.NW, lc.Len()) for i := range nw { r := make([]int, lc.Len()) nw[i] = r for j := range r { if j != i { r[j] = -1 } } } // define input sequences a := &linear.Seq{Seq: ab.BytesToLetters([]byte("rosettacode"))} a.Alpha = lc b := &linear.Seq{Seq: ab.BytesToLetters([]byte("raisethysword"))} b.Alpha = lc // perform alignment aln, err := nw.Align(a, b) // format and display result if err != nil { fmt.Println(err) return } fa := align.Format(a, b, aln, '-') fmt.Printf("%s\n%s\n", fa[0], fa[1])
}</lang>
- Output:
r-oset-tacode raisethysword
Perl
<lang perl>use strict; use warnings;
use List::Util qw(min);
sub levenshtein_distance_alignment {
my @s = ('^', split //, shift); my @t = ('^', split //, shift); my @A; @{$A[$_][0]}{qw(d s t)} = ($_, join(, @s[1 .. $_]), ('~' x $_)) for 0 .. $#s; @{$A[0][$_]}{qw(d s t)} = ($_, ('-' x $_), join , @t[1 .. $_]) for 0 .. $#t; for my $i (1 .. $#s) { for my $j (1 .. $#t) {
if ($s[$i] ne $t[$j]) { $A[$i][$j]{d} = 1 + ( my $min = min $A[$i-1][$j]{d}, $A[$i][$j-1]{d}, $A[$i-1][$j-1]{d} ); @{$A[$i][$j]}{qw(s t)} = $A[$i-1][$j]{d} == $min ? ($A[$i-1][$j]{s}.$s[$i], $A[$i-1][$j]{t}.'-') : $A[$i][$j-1]{d} == $min ? ($A[$i][$j-1]{s}.'-', $A[$i][$j-1]{t}.$t[$j]) : ($A[$i-1][$j-1]{s}.$s[$i], $A[$i-1][$j-1]{t}.$t[$j]); }
else {
@{$A[$i][$j]}{qw(d s t)} = ( $A[$i-1][$j-1]{d}, $A[$i-1][$j-1]{s}.$s[$i], $A[$i-1][$j-1]{t}.$t[$j] );
} } } return @{$A[-1][-1]}{'s', 't'};
}
print join "\n", levenshtein_distance_alignment "rosettacode", "raisethysword";</lang>
- Output:
ro-settac-o-de raisethysword-
Perl 6
<lang Perl 6>sub align ( Str $σ, Str $t ) {
my @s = *, $σ.comb; my @t = *, $t.comb; my @A; @A[$_][ 0]<d s t> = $_, @s[1..$_].join, '-' x $_ for ^@s; @A[ 0][$_]<d s t> = $_, '-' x $_, @t[1..$_].join for ^@t; for 1 ..^ @s X 1..^ @t -> \i, \j {
if @s[i] ne @t[j] {
@A[i][j]<d> = 1 + my $min =
min @A[i-1][j]<d>, @A[i][j-1]<d>, @A[i-1][j-1]<d>;
@A[i][j] =
@A[i-1][j]<d> == $min ?? (@A[i-1][j] Z~ @s[i], '-') !!
@A[i][j-1]<d> == $min ?? (@A[i][j-1] Z~ '-', @t[j]) !!
(@A[i-1][j-1] Z~ @s[i], @t[j]);
} else {
@A[i][j]<d s t> = @A[i-1][j-1]<d s t> Z~ , @s[i], @t[j];
}
} return @A[*-1][*-1];
}
.say for align |<rosettacode raisethysword>;</lang>
- Output:
ro-settac-o-de raisethysword-
Racket
This solution only computes the distance. See http://blog.racket-lang.org/2012/08/dynamic-programming-versus-memoization.html for a discussion of the code.
<lang racket>#lang racket
(define (memoize f)
(local ([define table (make-hash)]) (lambda args (dict-ref! table args (λ () (apply f args))))))
(define levenshtein
(memoize (lambda (s t) (cond [(and (empty? s) (empty? t)) 0] [(empty? s) (length t)] [(empty? t) (length s)] [else (if (equal? (first s) (first t)) (levenshtein (rest s) (rest t)) (min (add1 (levenshtein (rest s) t)) (add1 (levenshtein s (rest t))) (add1 (levenshtein (rest s) (rest t)))))]))))</lang>
Demonstration: <lang racket>(levenshtein (string->list "rosettacode")
(string->list "raisethysword"))</lang>