#### Howdy, Stranger!

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

#### Categories

Welcome to the new platform of Programmers Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use it's exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

# 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);