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:
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);
Contributed by: Ehud Lamm
Contributed on: December 2, 1999
License: Public Domain