AdaPower Logged in as Guest
Ada Tools and Resources

Ada 95 Reference Manual
Ada Source Code Treasury
Bindings and Packages
Ada FAQ


Join >
Home >
Articles >
Getting Started >
Ada FAQ >
Source Treasury >
Books & Tutorials >
Packages for Reuse >
Latest Additions >
Ada Projects >
Press Releases >
Ada Audio / Video >
Home Pages >
Links >
Contact >
About >
Login >
Back
A Generic Minimal Edit Distance Algorithm (Ehud Lamm)

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


(c) 1998-2004 All Rights Reserved David Botton