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

Published on 12 May 2024 09:40 PM

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

Source code in the limbo programming language

implement Levenshtein;

include "sys.m"; sys: Sys;
	print: import sys;
include "draw.m";


Levenshtein: module {
	init: fn(nil: ref Draw->Context, args: list of string);
	# Export distance so that this module can be used as either a
	# standalone program or as a library:
	distance: fn(s, t: string): int;
};

init(nil: ref Draw->Context, args: list of string)
{
	sys = load Sys Sys->PATH;
	if(!(len args % 2)) {
		sys->fprint(sys->fildes(2), "Provide an even number of arguments!\n");
		raise "fail:usage";
	}
	args = tl args;

	while(args != nil) {
		(s, t) := (hd args, hd tl args);
		args = tl tl args;
		print("%s <-> %s => %d\n", s, t, distance(s, t));
	}
}

distance(s, t: string): int
{
	if(s == "")
		return len t;
	if(t == "")
		return len s;
	if(s[0] == t[0])
		return distance(s[1:], t[1:]);
	a := distance(s[1:], t);
	b := distance(s, t[1:]);
	c := distance(s[1:], t[1:]);
	if(a > b)
		a = b;
	if(a > c)
		a = c;
	return a + 1;
}


  

You may also check:How to resolve the algorithm Regular expressions step by step in the NewLISP programming language
You may also check:How to resolve the algorithm Send email step by step in the LiveCode programming language
You may also check:How to resolve the algorithm Fibonacci sequence step by step in the Metafont programming language
You may also check:How to resolve the algorithm Arithmetic/Integer step by step in the Chef programming language
You may also check:How to resolve the algorithm Sorting algorithms/Pancake sort step by step in the UNIX Shell programming language