Fuzzy search still not on-par with FZF?

[alexozer]

:arrow_right: First read the guidelines! :arrow_left:

Version

Output of rofi -v Version: 1.5.1-dirty (tags/1.5.1)

Configuration

Output of rofi -help (in a gist) https://gist.github.com/8d000e38bca501289cda0a373cd1fefe

Launch Command

The commandline used to launch rofi

rofi -show drun

Steps to reproduce

Use this config:

rofi.matching: fuzzy
rofi.font: Ubuntu Mono derivative Powerline 16
rofi.modi: drun
rofi.hide-scrollbar: true
rofi.levenshtein-sort: true

Launch Rofi and type 'gpar' (unfortunately you'll need similar software installed as me, using with Xfce could work I think"

What behaviour you see

I believe the first four letters of the GParted entry should be selected, but the selection seems low quality.

See: https://i.imgur.com/dgBQftn.png

What behaviour you expect to see

fzf would definitely select the beginning of the GParted line, so I would expect that if rofi uses the fzf algorithm.

I tried fzf on the literal lines Rofi was showing and got this result, much better:

[DaveDavenport]

Somethings:

• Did you enable sort? rofi.sort: true or rofi -sort or hit the keybinding while running. (from your gist it looks like sorting is turned off)
• and you currently force it to use levenshtein sorting instead of fzf sorting. rofi.levenshtein-sort: false

Also rofi matches (in drun) more fields then are visible, this might throw off the algorithm.

The algorithm was pretty similar (but utf8 compatible.) so I expect similar results on the same input data.

I will cleanup the sorting flags for the next release, it is currently a mess.

edit: restructure.

[alexozer]

@DaveDavenport Thanks, wasn't aware of the sort option and how it mixes with the other options. Enabling sort and disabling levenshtein seems to produce great results.

[GordianDziwis]

I am still having this issue with the "right" options.

Version 1.5.1

-[no-]disable-history                Disable history in run/ssh
False (File)
-[no-]sort                           Use sorting
True (File)
-[no-]levenshtein-sort               Use levenshtein sorting also for fuzzy matching
False (File)
fuzzy (File)
-[no-]tokenize                       Tokenize input string

And with rofi -show drun and Input fi, rofi returns:

File Manager
Application Finder
...
...
...
Firefox

Is there any possibility to sort in a way, that matches, beginning with the search string, appear first?

[indeedwatson]

I'm having the same problem as @BonaBeavis describes. It basically renders rofi useless as a file finder.

[DaveDavenport]

For me it seems sane:

rofi -show drun -sorting-method fzf -sort (Git)

(duplicates are of testing on my side)

But if it is not working correctly, I will remove fzf. I did not implement it myself and have no time to dive into it.

[indeedwatson]

Okay, it's not as unusable as I thought, but take a look at this:

This is cat mpvbookmarks.txt | fzf https://paste.xinu.at/8Yc3A/

See how it matches letters together?

Now that same file, but through rofi https://paste.xinu.at/SqaftA/

See where the t and the m end up? I can't understand what's the logic in this.

Don't remove the fzf matching, but I think it's worth pointing out that it's not the same as fzf, in case someone else wants to work on this later.

---

The rofi script that I use to get stuff from that file, just in case:

#!/bin/bash
# use with https://gist.github.com/garoto/e0eb539b210ee077c980e01fb2daef4a
file="$HOME/.config/mpv/bookmarks-playlist"
if [ -f $file  ]
then
    mpv "$(rofi -theme-str "#window {width: 90%;}" -dmenu -markup-rows -i -p \
        "video" -matching fuzzy -sort -sorting-method fzf < $file \
        | grep -Po '\/home\/yama.*|http.*|ytdl:\/\/.*')"
fi

[DaveDavenport]

Wonder if the highlighting actually matches the algorithm. will take a look at that.

[JihongJu]

The problem is the "fuzzy" matching. Instead of matching the characters as close as possible, rofi's fuzzy matching tries to match the character as far as possible.

For example, ffxwb will match Firefox Web Browser (Web Browser) whereas I would expect: Firefox Web Browser (Web Browser)

[indeedwatson]

It took so long for someone to be able to explain this. Thank you so much @JihongJu

[DaveDavenport]

The problem is the "fuzzy" matching. Instead of matching the characters as close as possible, rofi's fuzzy matching tries to match the character as far as possible.

For example, ffxwb will match Firefox Web Browser (Web Browser) whereas I would expect: Firefox Web Browser (Web Browser)

I am pretty sure this is highlighting issue and not how it matches! https://github.com/davatorium/rofi/blob/next/source/helper.c#L886

@MaskRay can probably comment on this.

[fiskhest]

@DaveDavenport I could just be misunderstanding entirely, but after looking for a solution to my problem and finally seeing this reply, I'm not certain that I can agree with your assertion.

Running rofi and inputing the string super + shift + h rofi -no-config -show fb -modi fb:hkhelper.py -sorting-method fzf -sort -matching fuzzy

produces:

whilst hkhelper.py | fzf gives me a more sane result:

[DaveDavenport]

I did not write the fzf sorter, so I cannot judge exactly what is happening, I do not use it myself.. if it is not working right and it is not going to be fixed I will remove the fzf sorting.

Highlighting for fuzzy is not 100% matching reality, this is something that needs to be fixed. Sorting is a separate story and not linked to matching/highlighting!!. The FZF scoring for sorting I linked above. I might be wrong, but please check the actual implementation, instead of comparing screenshots where you cannot see what actually happens in the algorithms.

[MaskRay]

@fiskhest Can you provide textual form of the collection?

-matching fuzzy indeed uses a dynamic programming based fuzzy matching algorithm. The problem is that highlighting does not take into account how the individual characters are matched.

[DaveDavenport]

If you look here: https://github.com/davatorium/rofi/blob/next/source/view.c#L635

mode_token_match() does that matching,

then on line 647 and down it creates the 'score' for sorting.

(state->distance[] is used to sort the results using qsort).

(highlighting is done here: https://github.com/davatorium/rofi/blob/next/source/helper.c#L381. one of the differences is that the matching algorithm is not used on separate tokens, but the whole string. (this is why it does not always match correctly)).

[fiskhest]

@fiskhest Can you provide textual form of the collection?

-matching fuzzy indeed uses a dynamic programming based fuzzy matching algorithm. The problem is that highlighting does not take into account how the individual characters are matched.

You mean something like this?

Unhide window in stack                            super + shift + u                                 toggle show
Move or swap node to the left (desktop/leaf)      super + shift + h                                 if ! bspc node -s west.local; then bspc node -d prev -f ; fi

Those two lines and searching for super + shift + h is enough to reproduce for me, please clarify if you're asking for something else.

[DaveDavenport]

I can clearly reproduce what you describe. thanks.

[kantord]

I noticed that the fuzzy scorer works particularly bad for very long strings. I assume this is due to the scorer returning minimal score for anything longer than 256 characters.

I think some of the descriptions in rofimoji might exceed that: https://github.com/fdw/rofimoji. (Also splatmoji https://github.com/cspeterson/splatmoji) With splatmoji in particular I found that the matches seem to be more or less random. I think the long emoji descriptions in splatmoji show that for fuzzy matching, it might be particularly useful to have very long options with a nice searching algorithm, so that there are multiple ways you could find what you are looking for.

Would it be reasonable to increase the maximum character length, or to perhaps punish long strings less severely? For example, instead of returning minimal score for 256, only halving the score. At 512, dividing by 4, at 1024 dividing the score by 8 etc. etc.

Or perhaps somehow make the scoring mixed: give a Levenshtein score to anything that exceeds the length?

[DaveDavenport]

(not knowing fzf matching, just thinking):

Is it because it matches 's' in the first part of the string.. and uper later.

Then the 2nd entry has a lot more 'gap' between the 's' and 'super' and that counts heavy.

so like:

[MaskRay]

https://github.com/MaskRay/ccls/blob/master/src/fuzzy_match.cc has a simple fuzzy searching implementation (100+ lines of code) and it works pretty well in practice.

I thought about contributing it but rofi grabs mouse/keyboard so it is really difficult to debug.

cgdb --args Debug/rofi -dmenu -sort -sorting-method fzf -input /tmp/p/ctags/tags
r
# My mouse/keyboard is locked. I have to switch to a virtual console to kill gdb.

(not knowing fzf matching, just thinking):

Is it because it matches 's' in the first part of the string.. and uper later.

Then the 2nd entry has a lot more 'gap' between the 's' and 'super' and that counts heavy.

It works well for me.

% cat /tmp/c/a.txt
Unhide window in stack                           super + shift + u
Move or swap node to the left (desktop/leaf)     super + shift + h
% Debug/rofi -dmenu -sort -matching fuzzy -input /tmp/c/a.txt
# Type `super + shift + h` => `super + shift + h` is the first item.

[MaskRay]

OK, I just realized that -matching fuzzy (I used for a long time) no longer enables the fuzzy matching algorithm. -sorting-method fzf needs to be used instead. IMHO this really causes confusion. Moreover, fzf is a misnomer because the algorithm has nothing to do with fzf. fzf is not invoked as an external process.

Created #1173 to fix the issue and created #1174 to improve --sorting-method fuzzy performance a bit.

[DaveDavenport]

I think it was originally called fzf as it implemented scoring as implemented in fzf (at that point in time).

[OJFord]

It's not just a highlighting issue, fzf prioritises longer matching strings, so that abcd sorts for abcd ahead of abc...d.

On the input echo -e 'abcccccd\nabcd\nabcccd' | /usr/bin/dmenu (dmenu symlinked to rofi), rofi doesn't change the order at all when searching 'abcd', output is the same three input lines in the same order.

fzf given the same query reorders to show abcd, abcccd, abcccccd.

Aside from whether you want to improve this or not, I agree that it would be better named 'fuzzy' than 'fzf', which although generic on the face of it ('fuzzy find') is widely understood to refer to a specific tool, which isn't being used here.

[DaveDavenport]

This works for me: echo -e 'abcccccd\nabcd\nabcccd' | rofi -dmenu -matching fuzzy -sort-method fzf -sort

@OJFord did you enable sorting?

[OJFord]

Ah, I was missing -sort... :facepalm:

If the default is sort: false, sorting-method: normal, perhaps sorting-method: none instead could avoid this, so that sort isn't needed and setting it to anything implies sorting? Perhaps I'm missing a use case for having a sorting method defined without it being enabled.

[DaveDavenport]

Sort enable/disable can be triggered at run-time using a keybinding. its why it is separated.

[OJFord]

Ah, ok. :+1: Apologies for noise.

[DaveDavenport]

no problem.

[MaskRay]

Ah, I was missing -sort...

If the default is sort: false, sorting-method: normal, perhaps sorting-method: none instead could avoid this, so that sort isn't needed and setting it to anything implies sorting? Perhaps I'm missing a use case for having a sorting method defined without it being enabled.

I think this is an issue about an inconvenient default. Currently 3 options are needed to enable fuzzy finding: -matching fuzzy -sort-method fzf -sort

[DaveDavenport]

It is what it is, I had -sort/-sort-method merged (kind off) before and this caused more confusion.

[MaskRay]

Maybe have a master option of fuzzy sorting related features? The current way things are organized, fuzzy finding has poor discoverability and people just keep coming to comment on this issue.

[github-actions[bot]]

This issue has been automatically locked since there has not been any recent activity after it was closed. Please open a new issue for related bugs.