Fuzzy searching

[PMunch]

I got asked if xlunch supports or was planned to support fuzzy searching. I think it would be cool but might require a certain rewrite of the internal data structure of entries.

Here is an algorithm (in C#, but should be pretty easy to port):
https://www.codeproject.com/Articles/36869/Fuzzy-Search

The problem is that currently the entries are sorted in a linked list. Using fuzzy search like it's normally used would mean having to sort this list based on their edit distance (Levenshtein distance). Another option would of course be to have a cut-of in "similarity" and keep the entries in their original order, but that's a bit of a hack and not "proper" fuzzy searching.

[Tomas-M]

I think it is not worth. The code added will be harder to maintain and the benefit is near zero.

[renkam]

@Tomas-M I think this is totally worth it. Lack of fuzzy search is a stopper for me. 99% of work I am doing from console. I use launcher program rarely. When I use it I often barely remember the program name I want to launch. Fuzzy search is a must have for me.
Maybe it would be good idea to add a generic possibility to filter results with an external third party cmd application? Regarding too much code, take a look on @PMunch proposition. It's barely 100loc.

[PMunch]

Well, the problem is not the comparison algorithm in itself, as you say that's only about 100loc. The problem is that the system in place today is a linked list of entries. when a character is typed the list is iterated over and those with no substring match in either program name or command name are marked as hidden. The drawing function then iterates over them and draws all the non-hidden elements. To implement other search heuristics we would need to implement sorting of the list of entries, something which isn't trivial and would likely mean that the data structure for storing entries would have to change (at least for an efficient implementation).

[PMunch]

I created a proposal for fuzzy searching in PR #47, @renkam could you try it out and see if it works like you would expect? It's not the most sophisticated algorithm but it should be fairly easy to change if need be.

[PMunch]

@Tomas-M would you mind if I merged this into master? The PR is growing further and further away from the master. It works fine and I would say it's pretty easy to use and maintain, with little to no overhead if it is turned off.

[Tomas-M]

I never tried it. Is it working fine with UTF-8?
I have basically nothing against it, since it is turned off by default.
So feel free to merge. Just I am not sure if -z option is still free, so you may use -Z.
By the way, in some commit I sorted the arguments alphabetically, so we can easily see what letters are unused yet, so please keep it sorted if you add more. Not sure if you noticed :)

[byaka]

is this feature included in 3.2.12?

[PMunch]

No, this never got merged so fuzzy searching is not in this version of xlunch. It's probably easier to redo this PR though at this point if we want to add it.