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.

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

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 example is incorrect. Please fix the code and remove this message.
Details: This task explicitly requires the computation of indications of the delta operations. It also asks for the indications to be printed. Was this intended as a solution for the separate Levenshtein distance task?

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