edit_distance Function

public pure elemental function edit_distance(a, b)

NAME

edit_distance(3f) - [M_strings:DESCRIBE] returns a naive edit distance using
the Levenshtein distance algorithm
(LICENSE:PD)

SYNOPSIS

pure elemental function edit_distance(str1,str2) result (distance)

 character(len=*),intent(in)   :: str1, str2
 integer :: distance

DESCRIPTION

The Levenshtein distance function returns how many edits (deletions, insertions, transposition) are required to turn one string into another.

EXAMPLES

Sample Program:

program demo_edit_distance
use M_strings, only : edit_distance
   write(*,*)edit_distance('kittens','sitting')==3
   write(*,*)edit_distance('geek','gesek')==1
   write(*,*)edit_distance('Saturday','Sunday')==3
end program demo_edit_distance

Expected output

 T
 T
 T

AUTHOR

John S. Urban

LICENSE

Public Domain

Arguments

Type IntentOptional Attributes Name
character(len=*), intent(in) :: a
character(len=*), intent(in) :: b

Return Value integer


Contents

Source Code


Source Code

pure elemental integer function edit_distance (a,b)
character(len=*), intent(in) :: a, b
integer                      :: len_a, len_b, i, j, cost
! matrix for calculating Levenshtein distance
!integer                      :: matrix(0:len_trim(a), 0:len_trim(b)) ! not supported by all compilers yet
integer,allocatable          :: matrix(:,:)
   len_a = len_trim(a)
   len_b = len_trim(b)
   !-------------------------------------- ! required by older compilers instead of above declaration
   if(allocated(matrix))deallocate(matrix)
   allocate(matrix(0:len_a,0:len_b))
   !--------------------------------------
   matrix(:,0) = [(i,i=0,len_a)]
   matrix(0,:) = [(j,j=0,len_b)]
   do i = 1, len_a
      do j = 1, len_b
         cost=merge(0,1,a(i:i)==b(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_a,len_b)
end function edit_distance