edit_distance(3f) - [M_strings:DESCRIBE] returns a naive edit distance using
the Levenshtein distance algorithm
(LICENSE:PD)
pure elemental function edit_distance(str1,str2) result (distance)
character(len=*),intent(in) :: str1, str2
integer :: distance
The Levenshtein distance function returns how many edits (deletions, insertions, transposition) are required to turn one string into another.
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
John S. Urban
Public Domain
| Type | Intent | Optional | Attributes | Name | ||
|---|---|---|---|---|---|---|
| character(len=*), | intent(in) | :: | a | |||
| character(len=*), | intent(in) | :: | b |
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