Sort search results by relevance

[jtrees]

Prerequisites

• [x] I have searched open and closed issues for duplicates.

Feature

When performing a search in the applications menu, the results should be sorted by relevance.

Currently, when performing a search the results are displayed in categories that always appear in the same order (Applications, Actions, Settings). This means that for many items it's impossible to type the name of the item and press enter to execute it, even when a perfect match is made. Needless to say, this is poor a poor user experience.

Example (current state)

To get to the mouse settings I need to perform the following steps:

1. Press ⌘ + Space to open the menu
2. Type "mouse"
3. Press ↓
4. Press ↓
5. Press ↓
6. Press ↵

And this is the absolute best case quickest possible route (unless I uninstall Synergy and all programs with the word "mouse" in their .desktop file).

Solution

Text Match Quality Score

Each item receives a score, based on the quality of the text match. Search results are then sorted according to score. How this works should be quite intuitive.

Example

Search Term: "foo" Result Order

1. "foo" (exact match)
2. "food" (substring match)
3. "for honour" (fuzzy match)

.desktop Field Weights

Fields from .desktop should be weighted. E.g. a match of the search term in Name field should result in a high score and a match in the Comment field should result in a lower score (because it isn't even visible in the menu).

Dynamic Category Order

This one is a bit tricky because I see two possible approaches:

1. No longer group the results by category (Applications, Actions, Settings). The category could be indicated in a different way but that would require some additional design work.
2. Keep the grouping but sort the categories according to score. So if the result with the highest score is in the Settings category, this category comes first.

Final Notes

I realise the solution here is non-trivial since there are a number of factors to consider but I think this would dramatically improve elementary OS's user experience and make for a much more friendly keyboard-based workflow.

In the future I think this concept should be expanded to include the user's search history in the ranking but that is out-of-scope for now.