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

Published on 12 May 2024 09:40 PM
#Euphoria

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

Source code in the euphoria programming language

function min(sequence s)
    atom m
    m = s[1]
    for i = 2 to length(s) do
        if s[i] < m then
            m = s[i]
        end if
    end for
    return m
end function

function levenshtein(sequence s1, sequence s2)
    integer n, m
    sequence d
    n = length(s1) + 1
    m = length(s2) + 1

    if n = 1  then
        return m-1
    elsif m = 1 then
        return n-1
    end if

    d = repeat(repeat(0, m), n)
    for i = 1 to n do
        d[i][1] = i-1
    end for

    for j = 1 to m do
        d[1][j] = j-1
    end for

    for i = 2 to n do
        for j = 2 to m do
            d[i][j] = min({
                d[i-1][j] + 1,
                d[i][j-1] + 1,
                d[i-1][j-1] + (s1[i-1] != s2[j-1])
            })
        end for
    end for

    return d[n][m]
end function

? levenshtein("kitten", "sitting")
? levenshtein("rosettacode", "raisethysword")

You may also check:How to resolve the algorithm Trabb Pardo–Knuth algorithm step by step in the RPL programming language
You may also check:How to resolve the algorithm Sum of squares step by step in the Scala programming language
You may also check:How to resolve the algorithm Motzkin numbers step by step in the Rust programming language
You may also check:How to resolve the algorithm Eban numbers step by step in the CLU programming language
You may also check:How to resolve the algorithm Sleep step by step in the Ruby programming language