minmum string edit distance (levenstein distance) - Programmers Heaven

#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

# minmum string edit distance (levenstein distance)

Posts: 11Member
Hi - I posted a question on here about this subject a while ago and atex pointed me in the direction of the pseudocode which helped alot.

From this I have created the following code, a program which is designed to ask users to input morse code using only ' ' , '.' and '-' then calculate the levenstein distance..

[code]program Levenstein;

{\$apptype console}

uses
SysUtils;

const Nocols=15;
Norows=15;
type
MyTable = array [0..Nocols, 0..Norows] of integer;

var
s,t:string;
x:integer;

function Tdistance(s:string; t:string):integer;

var
d:MyTable;
n,m,i,j,cost:integer;

begin
n:=length(s);
m:=length(t);
if (n=0) then begin
result:=m;
Exit
end;

if (m=0) then begin
result:=n;
Exit
end;

for i := 0 to n do
d [i,0] := i;
for j :=0 to m do
d [j,0] := j;

for i:=1 to n do
for j:=1 to m do

if s[i]=t[j] then cost := 0
else cost := 1;

d[i,j] :=minimum (d[i-1,j] + 1, d[i, j-1] + 1, d[i-1,j-1] + cost);
end;

begin
writeln('Welcome to the minimum string edit distance program');

writeln('Please enter the second morse code string to have the MSE calculated');
x:=Tdistance(s,t);
end.
[/code]

So I have 2 questions...
1) As my programming is so rusty [color=Grey](bad)[/color].. i have forgotten how to display results (stored here as x). The result will be the number in the bottom right hand corner of the array as that is the minimum string edit distance.

2) I also need some help with the function 'minimun'. It needs to chose the option (delete, insert or substitute) which has the least 'cost'

Thanks for any help.

• Posts: 11Member
Anyone?

even if you can point me in the direction of something that might help..?
• Posts: 268Member
Not sure if this is the right thing, but IMO that what's the pseudocode means:[code][color=Blue]function minimum(a,b,c:integer):integer;
function min_(d,e:integer):integer;
begin if d<e then min_:=d else min_:=e;end;
begin minimum:=min_(min_(a,b),c);end;
[/color][/code]
• Posts: 11Member
Thanks I'll give that a try..

Could anyone else check that over please?
• Posts: 11Member
Hi I have the program compiling but it crashes.. i KNOW it is something to do with the lines highlighted..

[code]function Tdistance(s:string; t:string):integer;

var
d:MyTable;
n,m,i,j,cost:integer;

begin
[color=Red]n:=length(s);
m:=length(t)[/color];
if (n=0) then begin
result:=m;
Exit
end;

if (m=0) then begin
result:=n;
Exit
end;

for i := 0 to n do
d [i,0] := i;
for j :=0 to m do
d [j,0] := j;

for i:=1 to n do
for j:=1 to m do

if s[i]=t[j] then cost := 0
else cost := 1;

d[i,j] :=minimum (d[i-1,j] + 1, d[i, j-1] + 1, d[i-1,j-1] + cost);
result:=d[n,m];
end;

begin
writeln('Welcome to the minimum string edit distance program');
writeln('Please enter the second morse code string to have the MSE calculated');
[color=Red]x:=Tdistance(s,t);[/color]
end.[/code]

Its something to do with the way the result is stored in the variable x but i cant get it to work

Thanks
• Posts: 268Member
[code][color=Blue]{\$mode tp}
{\$apptype console}
const maxrows=15;
maxcols=15;
display_table=true;

type str15=string[maxrows];
table=array[0..maxrows,0..maxcols] of integer;

function minimum(a,b,c:integer):integer;
function min_(d,e:integer):integer;
begin if d0) and (bl>0));
writeln;
x:=levenshtein_distance(a,b);
writeln(#13#10,'Distance: ',x);
end.[/color][/code]

• Posts: 11Member

In order to help further my understand im going to have a study of the code, look at what you have modified to try and understand it better.

I hope you won't mind if I ask you a question again regarding the changes made. Really, really appreciate your help. Thanks. Lazerspewpew!