Implement fuzzy text search

[raphj]

Describe the bug

The search box for musical items will not be very forgiving if you make mistakes. For instance, it won't show results if you type "crechendo" instead of "crescendo". This does not make MuseScore unusable, but fuzzy search may make the live of dyslexic (and related conditions) people easier, and more generally, musical items can have somewhat complicated spelling and providing relevant items even if there is a mistake might help save people's focus / flow when they are using MuseScore.

To Reproduce
Steps to reproduce the behavior:

1. Input "crechendo" in the search field
2. notice that crescendo is not suggested

Expected behavior

Crescendo could be suggested.

Additional context

This issue is:

• related to Show results for synonyms during text searches #11411 (comment)
• opened as suggested by @shoogle in the following comment Show results for synonyms during text searches #11411 (comment) - I'm not myself too much concerned by this issue, but I like the idea nonetheless

[wizofaus]

ChatGPT integration anybody?

[shoogle]

As suggested by @ecstrema, the rapidfuzz-cpp library could be useful here.

It can compute a similarity ratio between strings, where a ratio score of 100% means an exact match:

// score is 96.55171966552734
double score = rapidfuzz::fuzz::ratio("this is a test", "this is a test!");

This can be used to filter a list of strings to return the ones that match the search term above a certain cutoff ratio.

ChatGPT integration anybody?

An AI assistant would be useful for many things in MuseScore, but it would be overkill for this.

[raphj]

Yep, and MuseScore not relying on an external service which is also proprietary is a good thing.

[shoogle]

If somebody wants to tackle this, PR #25281 introduced an algorithm to compute the Levenshtein distance between two strings. That's the minimum number of single-character insertions, deletions, and substitutions needed to turn one string into the other.

Let's say the user is searching for an element in the Palettes, or an instrument in the New Score dialog. The input search string would be compared to all palette elements / instrument names, and anything with a Levenshtein distance or 4 (the "fixed cutoff") or smaller could be considered a "fuzzy match" and included in the results.

This means the user can make up to 4 "typos" before the string is no longer considered a match.

However, we want to start showing results before the user has finished typing, so the "actual cutoff" would have to be something like 4 plus the difference in length of the two strings being compared (perhaps only if the search string is shorter).

Also, longer strings are likely to contain more typos, so the "fixed" part wouldn't really be fixed, but start at 0 and increase by 1 for every 3 characters typed, or something like that.

These numbers would have to be tweaked experimentally until we feel like we're getting the right results. We could also try sorting the results by Levenshtein distance (minus the difference in string length) to put more relevant results first.

---

Another option would be to implement the Damerau–Levenshtein distance, which also considers transposition (i.e. swapping) of two adjacent characters to be a single operation, which could help to catch a common typo. We would use it in exactly the same way as the Levenshtein distance, possibly with a reduced cutoff (e.g. 1 typo allowed per 5 characters typed instead of per 3 characters typed).

[maxthemusicnerd]

Me and my friends can take on this issue, I'll get them to comment here too.

[scottvan2008]

I'm maxthemusicnerd's friend, we are gonna take this.

[avvvvve]

This may very well already be on your minds @maxthemusicnerd & @scottvan2008, but just want to document this idea as an expected part of this feature since it's related:

Currently, search fields seemingly not only need an exact spelling match, but also an exact match of word order. For example, in Preferences > Shortcuts, these four new shortcuts are being added (in this PR):

• Add/remove system lock
• Lock/unlock all systems
• Lock/unlock selected system(s)
• Create system from selection*

All have to do with locking systems, but if I type 'lock system' in the shortcut search, NONE of the shortcuts come up because there is no direct match, even though 3/4 of them contain the words 'lock' and 'system'. Instead, search should surface results that contain any of the words in any order (and perhaps put exact matches first).

*'Create system from selection' ideally would also show up when you search 'lock system', but that will require that we add a hidden search term to that shortcut since 'lock' isn't actually in the shortcut name. Not expecting this project to address that.