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
sequences.
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);
begin
put(Med(Strand'("AATCCGGAT"),Strand'("AATCCCGAT")));
end;
Download Spec
Download Body
|
