Skip to content

Instantly share code, notes, and snippets.

@ytomino
Created March 6, 2011 07:06
Show Gist options
  • Save ytomino/857096 to your computer and use it in GitHub Desktop.
Save ytomino/857096 to your computer and use it in GitHub Desktop.
function Levenshtein_Distance (Left, Right : String) return Natural is
D : array (Left'First - 1 .. Left'Last, Right'First - 1 .. Right'Last) of Integer;
begin
for I1 in D'Range (1) loop
D (I1, D'First (2)) := I1;
end loop;
for I2 in D'Range (2) loop
D (D'First (1), I2) := I2;
end loop;
for I1 in Left'Range loop
for I2 in Right'Range loop
declare
Cost : Integer;
begin
if Left (I1) = Right (I2) then
Cost := 0;
else
Cost := 1;
end if;
D (I1, I2) := Integer'Min (Integer'Min (
D (I1 - 1, I2) + 1, -- insert
D (I1, I2 - 1) + 1), -- delete
D (I1 - 1, I2 - 1) + Cost);
end;
end loop;
end loop;
return D (Left'Last, Right'Last);
end Levenshtein_Distance;
function Levenshtein_Distance (Left, Right : String) return Natural;
pragma Pure (Levenshtein_Distance);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment