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

Published on 12 May 2024 09:40 PM
#Fortran

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

Source code in the fortran programming language

program demo_edit_distance
character(len=:),allocatable :: sources(:),targets(:)
integer,allocatable          :: answers(:),expected(:)

sources=[character(len=20)   :: "kitten",  "rosettacode",   "Saturday", "sleep",    "qwerty", "Fortran" ]
targets=[character(len=20)   :: "sitting", "raisethysword", "Sunday",   "fleeting", "qweryt", "Fortran" ]
expected=[                       3,         8,               3,          5,          2,        0        ]
! calculate answers
answers=edit_distance(sources,targets)
! print inputs, answers, and confirmation
do i=1, size(sources)
   write(*,'(*(g0,1x))') sources(i), targets(i), answers(i), answers(i) == expected(i)
enddo
! a longer test
write(*,*)edit_distance("here's a bunch of words", "to wring out this code")==18

contains

pure elemental integer function edit_distance (source,target)
!! The Levenshtein distance function returns how many edits (deletions,
!! insertions, transposition) are required to turn one string into another.
character(len=*), intent(in) :: source, target
integer                      :: len_source, len_target, i, j, cost
integer                      :: matrix(0:len_trim(source), 0:len_trim(target))
   len_source = len_trim(source)
   len_target = len_trim(target)
   matrix(:,0) = [(i,i=0,len_source)]
   matrix(0,:) = [(j,j=0,len_target)]
   do i = 1, len_source
      do j = 1, len_target
         cost=merge(0,1,source(i:i)==target(j:j))
         matrix(i,j) = min(matrix(i-1,j)+1, matrix(i,j-1)+1, matrix(i-1,j-1)+cost)
      enddo
   enddo
   edit_distance = matrix(len_source,len_target)
end function edit_distance

end program demo_edit_distance

You may also check:How to resolve the algorithm Sorting algorithms/Bubble sort step by step in the Eiffel programming language
You may also check:How to resolve the algorithm Prime conspiracy step by step in the PARI/GP programming language
You may also check:How to resolve the algorithm SEDOLs step by step in the Ruby programming language
You may also check:How to resolve the algorithm Farey sequence step by step in the Lua programming language
You may also check:How to resolve the algorithm Guess the number/With feedback step by step in the Mirah programming language