levenshtein Function

private pure function levenshtein(a, b) result(dist)

Levenshtein edit distance between two (capped) strings.

Arguments

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

Return Value integer


Called by

proc~~levenshtein~~CalledByGraph proc~levenshtein levenshtein proc~suggest suggest proc~suggest->proc~levenshtein proc~apply_one_pair apply_one_pair proc~apply_one_pair->proc~suggest proc~dispatch_group dispatch_group proc~dispatch_group->proc~suggest proc~parse_group_body parse_group_body proc~dispatch_group->proc~parse_group_body proc~parse_from_lines parse_from_lines proc~parse_from_lines->proc~dispatch_group proc~parse_group_body->proc~apply_one_pair proc~parse_file parse_file proc~parse_file->proc~parse_from_lines proc~schema_parse_lines nml_schema_t%schema_parse_lines proc~schema_parse_lines->proc~parse_from_lines proc~read_config_from_string_impl read_config_from_string_impl proc~read_config_from_string_impl->proc~schema_parse_lines proc~schema_parse nml_schema_t%schema_parse proc~schema_parse->proc~parse_file

Variables

Type Visibility Attributes Name Initial
character(len=MAX_SUGGEST_LEN), private :: aa
character(len=MAX_SUGGEST_LEN), private :: bb
integer, private, allocatable :: cur(:)
integer, private :: i
integer, private :: j
integer, private :: la
integer, private :: lb
integer, private, allocatable :: prev(:)

Source Code

   pure function levenshtein(a, b) result(dist)
      !! Levenshtein edit distance between two (capped) strings.
      character(len=*), intent(in) :: a, b
      integer :: dist
      integer :: la, lb, i, j
      integer, allocatable :: prev(:), cur(:)
      character(len=MAX_SUGGEST_LEN) :: aa, bb

      aa = a
      bb = b
      la = min(len_trim(a), MAX_SUGGEST_LEN)
      lb = min(len_trim(b), MAX_SUGGEST_LEN)
      allocate (prev(0:lb), cur(0:lb))
      do j = 0, lb
         prev(j) = j
      end do
      do i = 1, la
         cur(0) = i
         do j = 1, lb
            if (aa(i:i) == bb(j:j)) then
               cur(j) = prev(j - 1)
            else
               cur(j) = 1 + min(prev(j), cur(j - 1), prev(j - 1))
            end if
         end do
         prev = cur
      end do
      dist = prev(lb)
   end function levenshtein