Levenshtein distance/Alignment: Difference between revisions
(+ D entry) |
(Simpler D entry) |
||
Line 19: | Line 19: | ||
immutable s1 = "rosettacode"; |
immutable s1 = "rosettacode"; |
||
immutable s2 = "raisethysword"; |
immutable s2 = "raisethysword"; |
||
const dd = levenshteinDistanceAndPath(s1, s2); |
|||
// EditOp Key: |
|||
// n = none. Current items are equal, no editing is necessary. |
|||
// s = substitute current target item with current source item. |
|||
// i = insert current item from the source into the target. |
|||
// r = remove current item from the target. |
|||
writeln("Levenshtein distance and edit operations:\n", dd, "\n"); |
|||
string s1b, s2b; |
string s1b, s2b; |
||
size_t pos1, pos2; |
size_t pos1, pos2; |
||
foreach (immutable c; |
foreach (immutable c; levenshteinDistanceAndPath(s1, s2)[1]) { |
||
final switch (c) with (EditOp) { |
final switch (c) with (EditOp) { |
||
case none, substitute: |
case none, substitute: |
||
Line 48: | Line 40: | ||
} |
} |
||
writeln( |
writeln(s1b, "\n", s2b); |
||
}</lang> |
}</lang> |
||
{{out}} |
{{out}} |
||
⚫ | |||
<pre>Levenshtein distance and edit operations: |
|||
const(Tuple!(uint, EditOp[]))(8, nisnnnisssnss) |
|||
Alignments: |
|||
⚫ | |||
raisethysword</pre> |
raisethysword</pre> |
||
Revision as of 18:09, 8 May 2013
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).
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
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>