A Generic Minimal Edit Distance Algorithm

Finding how different two strings are, is important in many domains. One
domain which receives a lot of attention is molecular biology - where it
is, for example, important to quantify the differences between DNA
The following routine calculates the _Minimal Edit Distnace_ which is the
minimal number of edit operations needed to transform one string into the
other. The edit operations are the insertion or deletion of one character,
or the replacing of a character with a different character.
In this version all operations have the same cost, but it is possible to
enhance the routine to differentiate between the different operations.

Minimal edit distance can also be useful for (approximate) string
searching, and other uses.

This is an example of use:

with Minimal_Edit_Distance;
with Ada.Integer_Text_Io;
use  Ada.Integer_Text_Io;

procedure Try_MED is

      type base is ('A','C','G','T');
      type strand is array(Positive range <>) of base;

      function MED is new Minimal_Edit_Distance(base,Positive,Strand);

Download Spec
Download Body

Contributed by: Ehud Lamm
Contributed on: December 2, 1999
License: Public Domain