Howdy, Stranger!

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

Sign In with Facebook Sign In with Google Sign In with OpenID

Categories

We have migrated to a new platform! Please note that you will need to reset your password to log in (your credentials are still in-tact though). Please contact lee@programmersheaven.com if you have questions.
Welcome to the new platform of Programmer's 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 its 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)

lazerspewpewlazerspewpew 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 your first morse code string');
readln(s);

writeln('Please enter the second morse code string to have the MSE calculated');
readln(t);
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.

Comments

  • lazerspewpewlazerspewpew Posts: 11Member
    Anyone?

    even if you can point me in the direction of something that might help..?
  • AtexAtex 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]
  • lazerspewpewlazerspewpew Posts: 11Member
    Thanks I'll give that a try..

    Could anyone else check that over please?
  • lazerspewpewlazerspewpew 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 your first morse code string');
    readln(s);
    writeln('Please enter the second morse code string to have the MSE calculated');
    readln(t);
    [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
  • AtexAtex 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);
    readln;
    end.[/color][/code]

  • lazerspewpewlazerspewpew Posts: 11Member
    Thanks so much for your reply, that works great.

    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!


Sign In or Register to comment.