GNOME Bugzilla – Bug 764417
Application search algorithm (g_desktop_app_info_search()) should use fuzzy matching
Last modified: 2018-05-24 18:45:45 UTC
Currently characters entered by a user must match the beginning of an application name.
Using fuzzy matching (a la Sublime Text) would make the search easier.
Created attachment 325090 [details] [review]
Adds a g_str_match_string_fuzzy function to glib
Based on https://github.com/forrestthewoods/lib_fts/blob/master/code/fts_fuzzy_match.h
Modified slightly to fit the coding style.
Created attachment 325091 [details] [review]
Use fuzzy matching in g_desktop_app_info_search
Use g_str_match_string_fuzzy to search applications that match characters entered by the user
Also see bug 753102.
Review of attachment 325090 [details] [review]:
There are coding style issues, like using // for comments; wrong indentation levels; and references to the original C++ code.
These need to be fixed before a proper review is possible.
@@ +305,3 @@
+gint g_str_match_string_fuzzy (const gchar *str,
+ const gchar *pattern);
The whitespace is all broken. Please, make sure you use spaces, not tabs.
Oh, sorry about the coding style issues, I should've double checked.
Created attachment 325095 [details] [review]
Adds a g_str_match_string_fuzzy function to glib v2
Fixed (hopefully) style issues
Created attachment 325097 [details] [review]
Use fuzzy matching in g_desktop_app_info_search v2
Style issues fixed
Before we go any further with this, please get Allison to chime in here wrt to plans for desktop file indexing that existed at some point
(In reply to Matthias Clasen from comment #8)
> Before we go any further with this, please get Allison to chime in here wrt
> to plans for desktop file indexing that existed at some point
In the meantime, would it make sense to discuss the addition of the g_str_match_string_fuzzy to glib?
I believe it's a useful addition to glib, regardless of the whether or not g_desktop_app_info_search uses it.
Also, is it worth asking feedback to gnome usability/design team to see if there's interest in having gnome-shell supporting fuzzy search for apps?
(In reply to Pierre-Eric Pelloux-Prayer from comment #9)
> In the meantime, would it make sense to discuss the addition of the
> g_str_match_string_fuzzy to glib?
I'd rather not add api, at least initially. It is really not clear what the use cases are, beyond the one we are discussing here.
(In reply to Matthias Clasen from comment #10)
> (In reply to Pierre-Eric Pelloux-Prayer from comment #9)
> > In the meantime, would it make sense to discuss the addition of the
> > g_str_match_string_fuzzy to glib?
> I'd rather not add api, at least initially. It is really not clear what the
> use cases are, beyond the one we are discussing here.
Other potential use cases: epiphany's address bar, gimp's action search dialog, Polari's tab completion, etc
I am slightly against this for the reasons that Matthias allude to -- our current approach to handling the search is very very dumb (because it was easy and it works "good enough" for the number of desktop files we have and the hardware we run on). If we ever want to optimise this in the future, we may regret having made this change...
In particular, the choice to match on prefixes only was made in order to allow binary search over the tokens in a sorted list.
Should this bug be marked as won't fix then?
*** Bug 786522 has been marked as a duplicate of this bug. ***
*** Bug 764570 has been marked as a duplicate of this bug. ***
I think there is definitely work to do here. We shouldn’t let performance concerns stand in the way of fixing search results which don’t match the users’ expectations.
Some more examples of suboptimal search results from bug #786522:
• Search for ‘power’, expect the ‘Power’ control panel to be listed first, but it’s ranked as equal with LibreOffice Impress.
• Search for ‘R’ (as in the statistics language), expect that app to be listed first, but actually the first result is ‘Sound Recorder’. R is listed fourth.
• Search for ‘Sound’, expect that the control panel is listed first, but it’s listed after ‘Sound Recorder’.
*** Bug 727341 has been marked as a duplicate of this bug. ***
Bug #727341 mentions the need for including punctuation in the search tokens: they want searching for ‘+’ to match ‘Google+’. That seems reasonable, given the search string is entirely punctuation.
-- GitLab Migration Automatic Message --
This bug has been migrated to GNOME's GitLab instance and has been closed from further activity.
You can subscribe and participate further through the new bug through this link to our GitLab instance: https://gitlab.gnome.org/GNOME/glib/issues/1152.