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

Published on 12 May 2024 09:40 PM
#Elixir

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

Source code in the elixir programming language

defmodule Levenshtein do
  def distance(a, b) do
    ta = String.downcase(a) |> to_charlist |> List.to_tuple
    tb = String.downcase(b) |> to_charlist |> List.to_tuple
    m = tuple_size(ta)
    n = tuple_size(tb)
    costs = Enum.reduce(0..m, %{},   fn i,acc -> Map.put(acc, {i,0}, i) end)
    costs = Enum.reduce(0..n, costs, fn j,acc -> Map.put(acc, {0,j}, j) end)
    Enum.reduce(0..n-1, costs, fn j, acc ->
      Enum.reduce(0..m-1, acc, fn i, map ->
        d = if elem(ta, i) == elem(tb, j) do
              map[ {i,j} ]
            else
              Enum.min([ map[ {i  , j+1} ] + 1,         # deletion
                         map[ {i+1, j  } ] + 1,         # insertion
                         map[ {i  , j  } ] + 1 ])       # substitution
            end
        Map.put(map, {i+1, j+1}, d)
      end)
    end)
    |> Map.get({m,n})
  end
end

words = ~w(kitten sitting saturday sunday rosettacode raisethysword)
Enum.each(Enum.chunk(words, 2), fn [a,b] ->
  IO.puts "distance(#{a}, #{b}) = #{Levenshtein.distance(a,b)}"
end)

You may also check:How to resolve the algorithm Loops/N plus one half step by step in the Delphi programming language
You may also check:How to resolve the algorithm Date format step by step in the Joy programming language
You may also check:How to resolve the algorithm 99 bottles of beer step by step in the Astro programming language
You may also check:How to resolve the algorithm Averages/Mean angle step by step in the Icon and Unicon programming language
You may also check:How to resolve the algorithm Array concatenation step by step in the Neko programming language