Here's an example string ranking algorithm: https://sourcegraph.com/github.com/quicksilver/Quicksilver@a239587a6e890056c83bf7c120967bfba63cc917/-/blob/Quicksilver/Code-QuickStepCore/QSense.m
Note that it's very sensitive to order, since it's usually used to search in filesystems, not in history entries:
You can try a derivate of it here: https://fwextensions.github.io/quick-score-demo/, and compare it to other popular string ranking libraries, or even the original Quicksilver algorithm.
Here's the json to try the examples @Gamma posted in Gamma:
[
{"title": "github.com/borgbase/vorta: Desktop backup client for Borg backup", "url": "github.com/borgbase/vorta"},
{"title": "github.com/httpie/httpie: whatever", "url": "github.com/httpie/httpie"},
{"title": "tabby.sh: A terminal for a more modern age", "url": "tabby.sh"},
{"title": "borgbackup.org: Deduplicating with compression and authenticated encryption", "url": "borgbackup.org"},
{"title": "github.com/grafana/k6: A modern load testing tool", "url": "github.com/grafana/k6"}
]
Note I have concatenated the title to the URL to be able to match across both, but it doesn't work for modern GitHub
as the search term because of the aforementioned order sensitivity. There might be string ranking algorithms that are much more suited to this, or even ranking algorithms that can rank across multiple fields (you'll notice the example pages ranks url and title separately, then order by max score of either, that doesn't work for search strings that match partly in the url and partly in the title).
This approach to ranking generally scales quite well as you can compute score for all candidates in parallel, and you can easily build the results up incrementally since new candidates do not modify the score of existing candidates, so are you find new hits you can easily insert them in the partial results that you're already displaying.
Again note that the Quicksilver scoring algorithm specifically might not work well in practice for bookmarks / history, but I wanted to describe the concept of score ranking in general and it's is a very popular one.