Fuzzy string matching for History and Favourites

Suggestions and feature requests.
Posts: 4
Joined: 16.03.2009, 03:27

Fuzzy string matching for History and Favourites

#1 Post by tomlu » 16.03.2009, 03:50

I would like to see fuzzy string matching for your history and favourite locations, and possibly the quick search. This allows _very_ efficient navigation through these menus.

Currently, you are forced to either reach for the mouse or hit arrow down a fair few times to get to where you want to. Instead, pop up the menu with a focused textbox on top that can accept a text pattern, and filter the history (eg.) list according to a fuzzy algorithm. This way, if you still wish to use the mouse or the arrow keys, you still can.

A fuzzy matching algorithm that has proven to work well for file names is: Each character in the source pattern must exist in the file name in the order of the source pattern. Eg.

Code: Select all

pattern: stucomtxt
file:    some_stuffCommand.txt
match:   *****stu**com*****txt
To sort the results, each "jump" in the match is given a negative score unless there is a space in the pattern at this point.

If this is of interest and you would like more exact details (or code) feel free to contact me.

Posts: 3166
Joined: 10.04.2006, 09:48
Location: Germany

#2 Post by Marek » 16.03.2009, 22:17

Hi tomlu,

you can send me more details and if you have Delphi code...

Posts: 4
Joined: 16.03.2009, 03:27

#3 Post by tomlu » 17.03.2009, 11:37


I decided to reply here in case someone else is interested.

Unfortunately, I don't know Delphi. The closest is that I've implemented this algorithm in is perhaps C#. I've included the scoring code.

Essentially, each character from the pattern must be in the file name or the score is -1 (no match). Each gap except the first incurs a penalty of (gapPenalty + gap length) unless there is a space character in the input pattern at this point. (The first gap incurs a penalty of (gap length) number of points). The best score is 0.

What you do, is:
1. Take each file name and assign a score to it.
2. Remove any files with score -1 (non matching).
3. Sort the rest according to the score, lowest first.
4. Present this list to the user

The best scoring file is preselected, but the user can select any other score with the up or down arrow keys (or use the mouse). Return commits the current selection.

For some things (like history) it makes sense to reverse the file path that you use for scoring, i.e. make "C:\Folder\Temp" into "Temp\Folder\C:". (You don't necessarily need to display the same path to the user that you use for scoring.)

For demonstration videos, check out screencasts of emacs users that use the plugin "ido.el" which uses a similar algorithm. It really makes you fly through a file system at amazing speeds, and is really good for selecting things from the history.

Code: Select all

private static int score(string fileName, string pattern)
            fileName = fileName.ToLower();
            pattern = pattern.ToLower();

            int i = -1;
            int expectedIndex = -1;
            int score = 0;
            const int gapPenalty = 20;
            foreach(char c in pattern)
                if (c == ' ')
                    i = i + 1;
                    expectedIndex = -1;

                int index = fileName.IndexOf(c, i+1);
                if (index == -1) return -1;

                if (i == -1)
                    score = index;
                else if (expectedIndex != -1 && index != expectedIndex)
                    score += gapPenalty + (index - expectedIndex);
                i = index;
                expectedIndex = index + 1;
            return score;
I am happy to provide more information, or a port to Delphi if need be. I really like this feature and would really love for it to be in FreeCommander.

Posts: 9
Joined: 20.12.2007, 12:00

#4 Post by FCMCA » 17.03.2009, 14:54

Hi, tomlu:

You're suggesting something like Everything (http://www.voidtools.com) is already able to do, but that's sure a welcome feature for FreeCommander. Marek, by the way, could go a bit further while he eventually tries to implement this, adding an alias feature (abbreviation shortcut commands, like Firefox keywords or Opera nicks for opening URLs in tabs) to open tabs on both panels - imagine the user, wanting to open two tabs, one on each panel, just having to type in a special tiny prompt, say, "win" for the Windows folder and "wins" for the Windows32 system folder, for copying, moving files etc. Opus Directory is able to do this; however I just couldn't figure out a way of doing this on DOpus by creating a user command - I can only manage to open tabs or groups of tabs on a SINGLE panel, not on both at the same time.



Who is online

Users browsing this forum: No registered users and 7 guests