Best practice for quick file searching

Question

So I want to start my question with an example:

In pretty well known extension for Visual Studio called Visual Assist there's a functionality for quick file searching. Which basically just creates the window where you can input some words to find the file you want to open, press enter and then file opens in a new tab. It looks basically like this:

I would like to point out that this functionality is already very useful as it is but the algorithm for searching which they use in my opinion is not perfect. Seemingly the current algorithm is:

1. Split input to single words by whitespaces
2. Show filenames which include all of the words, the arbitrary file is selected.

In my opinion this algorithm has at least two downsides:

1. When I have files like ColorfulWidget.cpp, AwesomeColorfulWidget.cpp, DivineColorfulWidget.cpp (like 15 or more files with pattern *ColorfulWidget.cpp) and I know that I want to have ColorfulWidget.cpp open, using this kind of dialog becomes counterproductive because no matter what words I will input it will show all those files in the list and even though they are sorted, the needed one may be even not visible (because of scroll bar)
2. If you made any kind of typo empty list is shown and you have to look through your input carefully character by character to find it.

So my question is, are there any better algorithms (still not very complex perhaps) that could be used in similar kind of dialog?

Answer 1

To give you a concrete example: have a look at Command-T which certainly solves the first of your problems and does use such a dialog (displaying a list of files). It targets developers working with rather large trees of code files, just like the Visual Studio plugin you mentioned.

Its core algorithm is based on subsequence matching which is pretty useful in practice. For example, imagine you have 5 files in a directory tree with similar names as in your question:

foo/FirstWidget.cpp
foo/SecondWidget.cpp
foo/ThirdWidget.cpp
foo/Widget.cpp
ba/ThirdWidget.cpp

Now, if you type in a search string, this list of paths gets sorted by a score determined by a match of the string (the needle) against each path (the haystack). The score is the sum of the scores from each character in the needle. So if the needle consists of 5 characters the score is based on 5 sub-scores.

As far as I can read from the code, a sub-score follows these rules (matching is case-insensitive):

1. A character that doesn't exist in the haystack makes the whole needle score 0.
2. Otherwise, a character that has the previously matched character right in front of it in the haystack scores highest.
3. The greater the distance between the previously matched character and the current one, the smaller the score.
4. However, the score is only diminished by a fixed factor (close to 1) if the character in the haystack in front of the current one is a slash, dash, lower-case letter whereas the current one is an upper-case letter, etc.

Also, the highest score per character is smaller if the haystack is shorter. Thus, matched substrings (consecutive subsequences) in shorter haystacks score higher than in longer haystacks disregarding the score of the first character.

• So if the needle is idget the highest-scoring haystack will be foo/Widget.cpp.
• And if the needle is Widget the top of the list would also be foo/Widget.cpp as additionally the W comes right after a slash (it is the first character of the file name).
• If the input is dw you get ba/ThirdWidget.cpp,
• you'd need odw for foo/ThirdWidget.cpp demonstrating the ability to match folders.

Of course, this method would also work with a list of only file names, not full paths.

Regarding your second problem, you could perhaps introduce negative sub-scores or something. Still, when using the Command-T plugin the sorted list is updated in real-time and the matched characters are highlighted making it easy to build the search string with this feedback.

The exact algorithm can be found within the Command-T github repository.