Levenshtein distance/Alignment

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.

Levenshtein distance/Alignment is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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";
   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;
   size_t pos1, pos2;

   foreach (immutable c; dd[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("Alignments:\n", s1b, "\n", s2b);

}</lang>

Output:

Levenshtein distance and edit operations:
const(Tuple!(uint, EditOp[]))(8, nisnnnisssnss)

Alignments:
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

Translation of: Perl

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