[Bug] Partial name search results don't match search string well

[TheophileMot]

(Related: #901)

Is it possible to refine the string matching algorithm? When I type "vscode", for example, hoping to get Visual Studio Code, the first hit is instead MuseScore, and another hit is XCode:

I find this counterintuitive because the string "MuseScore" doesn't have a v or a d; it seems like a poor match for "vscode". I tried playing with the fuzzyness parameter, but if I make it either fuzzier or stricter, then Visual Studio Code isn't listed as a hit at all!

I'm guessing that the app is using some metric like the Levenshtein distance? If so, I wonder what would happen if there were less penalty for deleting letters from the app name? It could be a low (or zero) penalty for deleting lowercase letters, so that the important characters are the uppercase letters; this would let you type "vsc" to get Visual Studio Code. Currently:

In contrast, the search is extremely forgiving of typos:

In short, I would love to see a search bar where the score is reversed, i.e., unforgiving of typos, but tolerant of missing characters.

[oliverschwendener]

Ueli is using the fuse.js library to do the search. I don't know what we could do here apart from suggesting to play around with the fuzziness option 🤔 What could help here is that ueli has an "algorithm" that adds priority to items that are executed frequently. So in theory, Visual Studio Code should get higher priority over time, the more you open it. Maybe this helps.

[TheophileMot]

Ah, I see; thanks for the explanation. Indeed, it turns out that fuse.js essentially uses Levenshtein distance. There are times when this metric is useful, but I feel that in this case their algorithm doesn't really correspond to human reality (e.g., you can test on their online demo using their default parameters that a search like o=4 ~1q4s 3wa>f produces the hit "Old Man's War", which is pretty wacky).

It looks like there are reasonable (i.e., small, fast, simple) alternatives out there like fuzzysort. If you have time, it could be interesting to compare the results against fuse.js and potentially switch libraries.

[tkohlmeier]

I tried fuzzysort and compared the search results for some inputs. Here are my results (only listing those with interesting differences):

• Input "co":

  • Fuse:
    1: Discord
    2: Visual Studio Code
  • fuzzysort:
    1: Visual Studio Code
    2: Discord

  Here I think the result of fuzzysort is better because I executed Code more often.

• Input "pr":

  • Fuse:
    1: Programme und Features
    2: Process Hacker 2
  • fuzzysort:
    1: Process Hacker 2
    2: Programme und Features

  Here I think the result of Fuse is better because I executed Programme und Features a lot more often (about 3 times).

• Input "vs":

  • Fuse:
    1: VS2015 x64 Native Tools-Eingabeaufforderung
    2: VS2015 x86 Native Tools-Eingabeaufforderung
  • fuzzysort:
    1: Visual Studio Code
    2: Visual Studio 2022

  Here I think the result of fuzzysort is much better because I think i never executed those CLIs. Fuse just does not work for this kind of searches.

• Input "forefox":

  • Fuse:
    1: Firefox
    2: Firefox Privater Modus
  • fuzzysort:
    No results

  Here we see an advantage of Fuse as it forgives typos which fuzzysort does not at all.

Another disadvantage of fuzzysort is that it does not allow searching by an array property (e. g. our searchable string array). I combined the searchable strings to one long string to make it work. Also there is no parameter for fuzzyness (despite the name).

No clear winner here in my opinion but I slightly tend to fuzzysort.

[oliverschwendener]

The latest ueli v9 beta release supports multiple filtering algorithms (currently Fuse.js and fuzzysort). Feel free to try it out via downloading it from the release page here: https://github.com/oliverschwendener/ueli/releases/tag/v9.0.0-beta.3

I consider this bug to be solved.