PDA

View Full Version : The Levenshtein distance implemetation in Simba



CynicRus
04-14-2014, 09:20 AM
Hey, this is implementation of this (http://en.wikipedia.org/wiki/Levenshtein_distance) algorithm:


program new;

const
cuthalf = 100;

var
buf: array [0.. ((cuthalf * 2) - 1)] of integer;

function min3(a, b, c: integer): integer;
begin
Result := a;
if b < Result then
Result := b;
if c < Result then
Result := c;
end;

function LevenshteinDistance(s, t: string): integer;
var
i, j, m, n: integer;
cost: integer;
flip: boolean;
begin
s := copy(s, 1, cuthalf - 1);
t := copy(t, 1, cuthalf - 1);
m := length(s);
n := length(t);
if m = 0 then
Result := n
else if n = 0 then
Result := m
else
begin
flip := false;
for i := 0 to n do
buf[i] := i;
for i := 1 to m do
begin
if flip then
buf[0] := i
else
buf[cuthalf] := i;
for j := 1 to n do
begin
if s[i] = t[j] then
cost := 0
else
cost := 1;
if flip then
buf[j] := min3((buf[cuthalf + j] + 1), (buf[j - 1] + 1), (buf[cuthalf + j - 1] + cost))
else
buf[cuthalf + j] := min3((buf[j] + 1), (buf[cuthalf + j - 1] + 1), (buf[j - 1] + cost));
end;
flip := not flip;
end;
if flip then
Result := buf[cuthalf + n]
else
Result := buf[n];
end;
end;

begin
WriteLn(IntToStr(LevenshteinDistance('stfing1', 'string2')));
end.


Output:

Compiled successfully in 328 ms.
2
Successfully executed.


Written in Simba:)
Just 4 fun.

Cheers,
Cynic.

Janilabo
04-14-2014, 11:22 AM
Looking good - nice job man!
..and thanks for sharing it, CynicRus. :sasmokin:

Flight
04-14-2014, 11:44 AM
This is pretty clever, nicely done.

slacky
04-14-2014, 06:15 PM
Just as a heads up, Levenshtein distance is already built in to Simba, a long with a normalized version as well.

> LevDistance (https://github.com/MerlijnWajer/Simba/blob/master/Units/MMLAddon/stringutil.pas#L206)(...)
> NormLevDistance (https://github.com/MerlijnWajer/Simba/blob/master/Units/MMLAddon/stringutil.pas#L260)(...)