How to resolve the algorithm Levenshtein distance step by step in the Oberon-2 programming language

Published on 12 May 2024 09:40 PM
#Oberon-2

How to resolve the algorithm Levenshtein distance step by step in the Oberon-2 programming language

Table of Contents

Problem Statement

In information theory and computer science, the Levenshtein distance is a metric for measuring the amount of difference between two sequences (i.e. an edit distance). The Levenshtein distance between two strings is defined as the minimum number of edits needed to transform one string into the other, with the allowable edit operations being insertion, deletion, or substitution of a single character.

The Levenshtein distance between "kitten" and "sitting" is 3, since the following three edits change one into the other, and there isn't a way to do it with fewer than three edits:

The Levenshtein distance between   "rosettacode",   "raisethysword"   is   8. The distance between two strings is same as that when both strings are reversed.

Implements a Levenshtein distance function, or uses a library function, to show the Levenshtein distance between   "kitten"   and   "sitting".

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Levenshtein distance step by step in the Oberon-2 programming language

Source code in the oberon-2 programming language

MODULE LevesteinDistance;

  IMPORT Out,Strings;
    
  PROCEDURE Levestein(s,t:ARRAY OF CHAR):LONGINT;   
    CONST
      maxlen = 15;
    VAR
      d:ARRAY maxlen,maxlen OF LONGINT;
      lens,lent,i,j:LONGINT;
      
    PROCEDURE Min(a,b:LONGINT):LONGINT;
    BEGIN
      IF a < b THEN RETURN a ELSE RETURN b END
    END Min;
    
  BEGIN
    lens := Strings.Length(s);
    lent := Strings.Length(t);
    IF lens = 0 THEN RETURN lent
    ELSIF lent = 0 THEN RETURN lens
    ELSE
      FOR i := 0 TO lens DO d[i,0] := i END;
      FOR j := 0 TO lent DO d[0,j] := j END;
      FOR i := 1 TO lens DO
	FOR j := 1 TO lent DO
	  IF s[i-1] = t[j-1] THEN
	    d[i,j] := d[i-1,j-1]
	  ELSE
	    d[i,j] := Min((d[i-1,j] + 1),
			  Min(d[i,j-1] + 1, d[i-1,j-1] + 1));
	  END
	END
      END
    END;
    RETURN d[lens,lent];
  END Levestein;

  PROCEDURE ShowDistance(s,t:ARRAY OF CHAR);
  BEGIN
    Out.String(s);
    Out.String(" -> ");
    Out.String(t);
    Out.String(": ");
    Out.Int(Levestein(s,t),0);
    Out.Ln
  END ShowDistance;
  
BEGIN
  ShowDistance("kitten", "sitting");
  ShowDistance("rosettacode", "raisethysword");
END LevesteinDistance.

You may also check:How to resolve the algorithm Arithmetic evaluation step by step in the FreeBASIC programming language
You may also check:How to resolve the algorithm Environment variables step by step in the Java programming language
You may also check:How to resolve the algorithm Function definition step by step in the Quackery programming language
You may also check:How to resolve the algorithm A+B step by step in the Dragon programming language
You may also check:How to resolve the algorithm One of n lines in a file step by step in the Wren programming language