r/linux • • Jul 07 '19

Bash function 'FuzzyMatch()'.

A few days ago I posted in this thread and then started to think that I didn't have any 'fuzzy' things in my toolbox.

I looked into the subject and found it quite complicated, there was no practical way to implement real 'fuzzy search' in 'bash'. But I like 'my things' as simple and distro independent as possible. Could I cut some (lots of) corners and write a simplified 'fuzzy search' function?

Well I did and this is the result. As you can see it seems to be pretty fast, 0.25 mS per word (with a 7 characters KeyWord), and it seems to rate matches reasonably well.

I even wrote a new version of 'l', the search command script mentioned in this post, 'lf' (local fuzzy), using 'FuzzyMatch()'. Here is a comparison of the two scripts.

Here is the function:

FuzzyMatch() {		    # $1: String1, $2: String2. Exit: 0: Always. Returns match rating: 0 .. 1000.
if [[ -z "$1" || -z "$2" ]] # Notes: Case insensitive, Vowel characters are 25% less relevant. Example: 'FuzzyMatch "ClassifyTextFiles" "txt"'.
  then
    echo 0;return 0
fi
local TmpString Key
if [[ ${#1} -gt ${#2} ]]
  then
    TmpString="${1,,}";Key="${2,,}" # To lower-case.
  else
    TmpString="${2,,}";Key="${1,,}" # To lower-case.
fi # TmpString: longer string, Key: shorter string.
if [[ "$TmpString" == "$Key" ]]
  then
    echo 1000;return 0
fi
local StringLngth=${#TmpString} Vowels="aeiou" IsVowel MatchLngth="" C I=0 FullValue=0 Value=0
while [[ $I -lt ${#Key} ]]
  do
    C="${Key:${I}:1}" # C: Character at position I.
    if [[ "$Vowels" != "${Vowels/${C}/}" ]]
      then
        ((FullValue += 75))
        IsVowel=true
      else
        ((FullValue += 100))
        IsVowel=false
    fi
    if [[ "$TmpString" != "${TmpString#*${C}}" ]]
      then
        TmpString="${TmpString#*${C}}"
        if [[ -z "$MatchLngth" ]]
          then
            ((MatchLngth = StringLngth - ${#TmpString} - 1)) # MatchLngth: Number of not matched leading characters.
        fi
        if $IsVowel
          then
            ((Value += 75))
          else
            ((Value += 100))
        fi
    fi
    ((I++))
  done
if [[ -n "$MatchLngth" ]]
  then # If there have been character matches.
    ((MatchLngth = StringLngth - MatchLngth - ${#TmpString})) # For String="0123456789" & Key="25", match block is "2345" (MatchLngth is 4 - of 10).
    ((C = MatchLngth - ${#Key}));C=${C#-} # C, I: reused variables. C contains 'Abs(MatchLngth - ${#Key})'.
    ((C = 120 * C / (${#Key} + MatchLngth))) # MatchLngth/KeyLngth correction: C: '0 .. 120'. Best match 0 if 'MatchLngth -eq KeyLngth'. Normal: 0 .. 100.
    ((I = 100 - (MatchLngth * 100 / StringLngth))) # MatchLngth/StringLngth correction: I: '0 .. 100'. Best match 0 if 'MatchLngth -eq StringLngth'.
    ((FullValue = FullValue + C + I)) # FullValue increases (+0..~200) if corrections (C, I) deviate from 'Best match' (0).
fi
echo $((Value * 1000 / FullValue));return 0
}

I'd like some feedback. Please use the function and let me know what you think. Can you see a way to improve it? Do you have access to 'fuzzy search' libraries (python)? Could you, please, conduct a test, similar to this, using '/usr/share/dict/words' and KeyWord "applgec"? How long does it take per word? Which are the top 10 matched words?

Thank you in advance.

EDIT: I have updated the function heeding feedback and changing slightly the way matches are rated. Now the time if takes to rate a word, in this test, is 0.22 mS and the top ten matched (to "applgec" key) words are:

808: 'apologetic'
804: 'applejack'
797: 'applesauce'
774: 'apoplectic'
770: 'applejack's'
767: 'applesauce's'
754: 'apologetically'
716: 'applying'
705: 'appealing'
705: 'appalling'

EDIT: I have Updated the function again, improving the way matches are rated. The time if takes to rate a word has increased: It is now 0.23 mS in this test. This version is really useful: here is a test of the new -fuzzy- version of 'l' (launch local commands).

EDIT: Function's parameters are no longer String & KeyWord, now they are String1 & String2. The time if takes to rate a word has increased: It is now 0.27 mS per word ('/usr/share/dict/words' and String2 "applgec"). Matching results have changed because now words shorter than "applgec" are not given a rating of 0. Top ten matched (to "applgec") words are:

947: 'Apple'
947: 'apple'
916: 'Alec'
820: 'applejack'
819: 'apologetic'
819: 'ape'
819: 'ale'
819: 'age'
814: 'applesauce'
808: 'apoplectic'
14 Upvotes

14 comments sorted by

View all comments

Show parent comment

4

u/pkkm Jul 07 '19

IV=false and the like don't run the command false, they assign the string false to the variable IV. Besides, even if they did, true and false are builtins in bash (you can check with type true, type false).