Get_close_matches in Fortran

Looking for an implementation of Python’s get_close_matches, but in Fortran.


1 Like

I don’t know of one. Here is a code from the Fortran Wiki (slightly adapted) that does wildcard matches.

module match_mod
implicit none
public :: match_wild
elemental LOGICAL FUNCTION match_wild(pattern, string)
! compare given string for match to pattern which may
! contain wildcard characters:
! "?" matching any one character, and
! "*" matching any zero or more characters.
! Both strings may have trailing spaces which are ignored.
! Authors: Clive Page, userid: cgp  domain:, 2003 (original code)
!          Rolf Sander, 2005 (bug fixes and pattern preprocessing)
! Minor bug fixed by Clive Page, 2005 Nov 29, bad comment fixed 2005 Dec 2.
! Serious bug fixed by  Robert H McClanahan, 2011 April 11th
!    This program is free software; you can redistribute it and/or modify
!    it under the terms of the GNU General Public License as published by
!    the Free Software Foundation; either version 2 of the License, or
!    (at your option) any later version.
!    This program is distributed in the hope that it will be useful,
!    but WITHOUT ANY WARRANTY; without even the implied warranty of
!    GNU General Public License for more details.
!    You should have received a copy of the GNU General Public License
!    along with this program; if not, write to the Free Software
!    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
!    02110-1301  USA

   CHARACTER(LEN=*), INTENT(IN) :: pattern ! pattern may contain * and ?
   CHARACTER(LEN=*), INTENT(IN) :: string  ! string to be compared
   INTEGER :: lenp, lenp2, lens, n, p2, p, s
   INTEGER :: n_question, n_asterisk
   LOGICAL :: found

   CHARACTER(LEN=LEN(pattern)) :: pattern2
   lens = LEN_TRIM(string)
   lenp = LEN_TRIM(pattern)

! If the pattern is empty, always return true
   IF (lenp == 0) THEN
     match_wild = .TRUE.

! The pattern must be preprocessed. All consecutive occurrences of
! one or more question marks ('?') and asterisks ('*') are sorted and
! compressed. The result is stored in pattern2.

   p  = 1 ! current position in pattern
   p2 = 1 ! current position in pattern2
     IF ((pattern(p:p) == '?').OR.(pattern(p:p) == '*')) THEN
! a special character was found in the pattern
       n_question = 0
       n_asterisk = 0
       DO WHILE (p <= lenp)
         ! count the consecutive question marks and asterisks
         IF ((pattern(p:p) /= '?').AND.(pattern(p:p) /= '*')) EXIT
         IF (pattern(p:p) == '?') n_question = n_question + 1
         IF (pattern(p:p) == '*') n_asterisk = n_asterisk + 1
         p = p + 1
       IF (n_question>0) THEN ! first, all the question marks
         pattern2(p2:p2+n_question-1) = REPEAT('?',n_question)
         p2 = p2 + n_question
       IF (n_asterisk>0) THEN ! next, the asterisk (only one!)
         pattern2(p2:p2) = '*'
         p2 = p2 + 1
! just a normal character
       pattern2(p2:p2) = pattern(p:p)
       p2 = p2 + 1
       p = p + 1
     IF (p > lenp) EXIT
!!   lenp2 = p2 - 1
   lenp2 = len_trim(pattern2)

! The modified wildcard in pattern2 is compared to the string:

   p2 = 1
   s = 1
   match_wild = .FALSE.
     IF (pattern2(p2:p2) == '?') THEN
! accept any char in string
       p2 = p2 + 1
       s = s + 1

     ELSEIF (pattern2(p2:p2) == "*") THEN
       p2 = p2 + 1
       IF (p2 > lenp2) THEN
! anything goes in rest of string
         match_wild = .TRUE.
         EXIT ! .TRUE.
! search string for char at p2
         n = INDEX(string(s:), pattern2(p2:p2))
         IF (n == 0) EXIT  ! .FALSE.
         s = n + s - 1

     ELSEIF (pattern2(p2:p2) == string(s:s)) THEN
! single char match
       p2 = p2 + 1
       s = s + 1
! non-match
!       EXIT ! .FALSE.
! Previous line buggy because failure to match one character in the pattern
! does not mean that a match won't be found later. Back up through pattern string
! until first wildcard character is found and start over with the exact character
! match. If the end of the string is reached, then return .FALSE.
!      04/11/2011 Robert McClanahan    Robert.McClanahan   <<at>>   AECC.COM
       found = .FALSE.
       DO WHILE (p2 > 0 .AND. .NOT. found)
         p2 = p2 - 1
         IF (p2 == 0) EXIT  !  .FALSE.
         IF (pattern(p2:p2) == '*' .OR. pattern(p2:p2) == '?') found = .TRUE.
       END DO
       s = s + 1

     IF (p2 > lenp2 .AND. s > lens) THEN
! end of both pattern2 and string
       match_wild = .TRUE.
       EXIT ! .TRUE.

     IF (s > lens .AND. p2 == lenp) THEN
       IF(pattern2(p2:p2) == "*") THEN
! "*" at end of pattern2 represents an empty string
         match_wild = .TRUE.

     IF (p2 > lenp2 .OR. s > lens) THEN
! end of either pattern2 or string
       EXIT ! .FALSE.

END FUNCTION match_wild
end module match_mod

program xmatch_wild
use match_mod, only: match_wild
implicit none
print*,match_wild("boy*",["boys","girl"]) ! T F
print*,match_wild("*man",["woman","women"]) ! T F
end program xmatch_wild
1 Like

I could tell you what the interface would likely look like.

function get_close_matches(word, possibilities, n, cuttoff) result(matches)
  character(len=*), intent(in) :: word
  character(len=*), intent(in) :: possibilities(:)
  integer, intent(in), optional :: n
  real, intent(in), optional :: cutoff
  character(len=:), allocatable :: matches(:)
end function

The algorithm for calculating the similarity score is probably the hardest part, but once you’ve got that (and you can probably translate it from the python pretty simply), the rest shouldn’t be too hard.

1 Like

Fuzzy string searches fall into several categories. Popular algorithms
that determine the minimum number of characters required to change one
string into another are:

  • Levenshtein distance - words; this can become very inefficient for
    long strings.
  • Needleman-Wunsch or Smith-Waterman - biometric sequences, but can be
    applied to phrases.

There are others that look for the most words in common, and/or combined
weights of the Levenshtein distance of the words, the number of matched
words, the similiarity in length, … A good place to start might be
“Fuzzy name match algorithms”.

Are you trying to find a description based on a few keywords in a manual,
trying to find names (ie. is “Bob” similar to “Robert?” do you need to
handle vernaculars and slang? (“I have a beef”, “have a cow”, … is
that about livestock or a grievance?), looking for similar chemical
composition or protein pairs? Exactly what kind of problem are
you solving?

Just matching a word or two, like finding the correct spelling of a word in a dictionary can be
handled by something like the Levenshtein algorithm; or looking up a famous quote related to a few words; things can get very complicated very quickly if the data you are trying to match is not categorized in some way. There is a big difference between a spelling checker that gives you a suggestion and a web search engine or trying to determine if someone talking about it “being the bomb” is a teenager thinking something is a great idea or a terrorist; or trying to determine the function of a gene sequence but fuzzy matches are used in all of that; so quite a range of possibilities to guess about.


If the python functionality is all you need, for just a word or two see:


Thanks for the all the feedback so far.

My specific problem isn’t that hard, I don’t think. I have a long array of chemical species:

species = ["H2O", "CO2,aq", "CH4,AQ", ...]

I have a function which, takes in a single species, and looks for a match in the list with findloc:

ind = findloc(species, "CO2", 1)

If the search fails (ind == 0), then I throw an error saying that the input species isn’t in the list. But I want to be more helpful. I want the error message to contain the “closest matches”. So in the above example, I would want the error message to say ““CO2” is not in the list of species. Closest matches are “CO2,aq”, etc…”


My guess would be to normalize the strings (ignore case, remove initial spaces, then change other alphanumerics to a space so “CO2(aq)”, “CO 2 (aq)”, “co2-aq”, “CO2,aq” would all be “co2,aq” ) and then calculate matched words in order and give those a heavy weight, and then do the edit distance using the Fortran links in the first two links (caveat emptor – did not try them); things like lower, substitute, split, the links above and weighting and then maybe requiring the first word to match or no word having a high edit distance might be where to end up, but just normalizing the string and doing the edit distance on the input string and the species trimming the dictionary to no more than one word longer than the input either starting at the beginning or at end of the first non-matching character (simpler than it sounds) would be good; if the species are all as simple as in the example or you can tell people to follow a particular syntax you could go exact match, glob match (like match routine above or using glob, then edit distance would be nice and simple. (glob, lower, split, substitute examples are all in M_strings if that is helpful).

If you use fpm(1) the dependency string is

M_strings      = { git = "" }

So if you already are doing the findloc and users have to follow a syntax like the compound is uppercase, comma delimited and lowercase after then you could use the wildcard/glob routine, and if no match give the three lowest edit distances; good start and you are already half there; then maybe the normalizing I mentioned, then play with weights between the measures of word match and edit distance. Probably getting too general, if your species are standardized …

1 Like

Ignoring case is no use for chemists: CO is carbon monoxide, Co is cobalt.

Ha! I had a lapse there! Was just thinking strings.

Started a skeleton, mostly to show the pros and cons of edit distance
and to try the linked code, and how globbing might be what is wanted,
and that it would only take a few lines and then of course, things went
south. For what it is worth …

It shows nicely why using edit distance by itself can
get odd results if you do not deal with string length or weight by
matching characters (H2O is as good a match as CO2,aq!).

glob matches are : CO2,aq
best matches are  H2O                  CO2,aq              
fpm: Leaving directory '/home/urbanjs/venus/V600/github/chem'
program main
use chem, only: distance
use M_strings, only : glob
implicit none
character(len=20),parameter :: species(*) = [character(len=20) :: "H2O", "CO2,aq", "CH4,AQ"  ]
character(len=20),allocatable :: matches(:)
character(len=:),allocatable :: mystring
integer :: ind,i,ismall
integer,allocatable :: distances(:)
FOUNDIT : block
  ind = findloc(species, "CO2", 1)
     write(*,'(*(g0))')'found match at ',species(ind)
     !exit FOUNDIT
     write(*,'(*(g0:,": "))')'glob matches are ',(trim(matches(i)),i=1,size(matches))
     !exit FOUNDIT
  ! you would want to heavily weight matching characters
  write(*,'(*(g0,1x))')'best matches are ',pack(species,distances.eq.ismall)
endblock FOUNDIT
end program main
module chem
  implicit none
  public :: distance
!> The Levenshtein distance function returns how many edits (deletions,
!! insertions, transposition) are required to turn one string into another.
integer function distance (a,b)
integer :: len_a, len_b, i, j, cost
character(len=*), intent(in) :: a, b
! matrix for calculating levenshtein distance
integer, dimension(0:len_trim(a), 0:len_trim(b)) :: leven_mat
integer, dimension(3) :: three_vals
   len_a = len_trim(a)
   len_b = len_trim(b)
   do i = 0,len_a
      leven_mat(i,0) = i
   do j = 0, len_b
      leven_mat(0,j) = j
   do i = 1, len_a
      do j = 1, len_b
         if (a(i:i) == b(j:j)) then
            cost = 0
            cost = 1
         three_vals(1) = leven_mat(i-1,j) + 1
         three_vals(2) = leven_mat(i, j-1) + 1
         three_vals(3) = leven_mat(i-1,j-1) + cost
         leven_mat(i,j) = minval(three_vals)
   distance = int(leven_mat(len_a,len_b))
end function distance
end module chem
1 Like

If the purpose is to show a list of candidate items that contain the word “CO2” exactly, then a “minimalist” approach may be like this…?

program main
    implicit none
    character(:), allocatable :: species(:), mol
    integer, allocatable :: locs(:)
    integer :: i

    mol = "CO2"
    ! mol = "H2O"

    species = [ character(10) :: "H2O", "CO2,aq", "CH4,AQ", "[CO2,gas]", "H2O,g" ]
    locs = pack( [(i, i=1,size(species))], index(species, mol) >= 1 )

    print *, "mol             = ", mol
    print *, "species(:)      = ", species(:)
    print *, "exact-match loc = ", findloc( species, mol )
    print *, "candidate list  = ", species( locs )
    print *, "candidate locs  = ", locs

The output for mol = “CO2” is:

 mol             = CO2
 species(:)      = H2O       CO2,aq    CH4,AQ    [CO2,gas] H2O,g     
 exact-match loc =            0
 candidate list  = CO2,aq    [CO2,gas] 
 candidate locs  =            2           4

and for mol = “H2O”:

 mol             = H2O
 species(:)      = H2O       CO2,aq    CH4,AQ    [CO2,gas] H2O,g     
 exact-match loc =            1
 candidate list  = H2O       H2O,g     
 candidate locs  =            1           5
1 Like

That may well be the case the OP wants to solve; the fancier things here allow the user to actually put in the globbing pattern themselves, so they could input ‘CO*aq*’ for anything
starting with “CO” followed by “aq”, and the edit distances are probably what the original question about a Fortran version of the python procedure uses, which allows for misspellings and other differences which are still interesting and useful variants, but that is a good combination just using intrinsics I use a lot. The other approach often used is allowing the user to use Regular Expressions; for others with similar problems.

1 Like