How to resolve the algorithm Levenshtein distance step by step in the Delphi programming language

Published on 12 May 2024 09:40 PM
#Delphi

How to resolve the algorithm Levenshtein distance step by step in the Delphi 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 Delphi programming language

Source code in the delphi programming language

program Levenshtein_distanceTest;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils,
  Math;

function Levenshtein_distance(s, t: string): integer;
var
  d: array of array of integer;
  i, j, cost: integer;
begin
  SetLength(d, Length(s) + 1);
  for i := Low(d) to High(d) do
  begin
    SetLength(d[i], Length(t) + 1);
  end;

  for i := Low(d) to High(d) do
  begin
    d[i, 0] := i;
    for j := Low(d[i]) to High(d[i]) do
    begin
      d[0, j] := j;
    end;
  end;

  for i := Low(d) + 1 to High(d) do
  begin
    for j := Low(d[i]) + 1 to High(d[i]) do
    begin
      if s[i] = t[j] then
      begin
        cost := 0;
      end
      else
      begin
        cost := 1;
      end;

      d[i, j] := Min(Min(d[i - 1, j] + 1,      //deletion
        d[i, j - 1] + 1),     //insertion
        d[i - 1, j - 1] + cost  //substitution
      );
    end;
  end;
  Result := d[Length(s), Length(t)];
end;

procedure Println(s, t: string);
begin
  Writeln('> LevenshteinDistance "', s, '" "', t, '"');
  Writeln(s, ' -> ', t, ' = ', Levenshtein_distance(s, t), #10);
end;

begin
  Println('kitten', 'sitting');
  Println('rosettacode', 'raisethysword');
  readln;
end.

You may also check:How to resolve the algorithm Anagrams step by step in the Ruby programming language
You may also check:How to resolve the algorithm Multiplication tables step by step in the Jsish programming language
You may also check:How to resolve the algorithm Peano curve step by step in the VBA programming language
You may also check:How to resolve the algorithm Same fringe step by step in the PicoLisp programming language
You may also check:How to resolve the algorithm Semordnilap step by step in the Racket programming language