15

Textmate's 'go to file' fuzzy search is really awesome.

Wincent's Command-T plugin for vim does something similar and it rocks too.

Can someone explain how these work? Is there a general term for the method they use?

Edit: I little more detail about what those tools do

The tools let you narrow a list of options (in this case file paths) as you type.

For example if I had the following files:

/app/models/people.rb
/app/models/address.rb
/app/person.rb
/person.rb

to get to narrow the list to /app/models/people.rb I could type any of the following: 

amp
peo
mp
modelsp

it's very flexible and I find my self missing this 'list narrowing' when the app I'm using doesn't have it. I'd like to learn more about it so that I may implement my own plugins if I ever felt the need. Wish I could explain it better, but that's why I'm here :)

To see it in action take a look at wincent's demo of command-t

Improve this question
4
  • 2
    Care to explain what exactly those tools do? Commented Sep 11, 2010 at 5:25
  • It's like the firefox awesomebar but for the files in your currently open project. It 'narrows down' what file you want as you type. I do find this feature to be great but I never thought much of it. Commented Sep 11, 2010 at 5:36
  • 1
    stackoverflow.com/questions/2891514/… Commented Sep 11, 2010 at 6:35
  • ReSharper for Visual Studio lets you use case to narrow down the CamelCasing in files.. really cool. You can mix in wildcards as well. Commented May 18, 2011 at 2:14

5 Answers 5

Reset to default
3

It appears to be doing a wildcard search between every letter.

amp -> *a*m*p*
peo -> *p*e*o*
mp  -> *m*p*
modelsp -> ...

If it matches only one item in the list of options, then it would return that as the intended option.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

I believe it also weights the letters near a dirsep more heavily.
2

It looks like Command-T does a sort based on a double score given by the recursive_match function in match.c to do the fuzzy search. Command-T's source is copyrighted by the author but the source can be found by opening the vimball in a text editor (download at the bottom of this page), and could probably be used as inspiration for a more general fuzzy search algorithm (by somebody who reads C better than me at least).

Improve this answer

Comments

2

Looks like this is the exact code you're talking about:

https://github.com/textmate/textmate/blob/master/Frameworks/text/src/ranker.cc

Improve this answer

Comments

0

Have no idea how this works, but for fast lookups you can generate something similar to http://en.wikipedia.org/wiki/Directed_acyclic_word_graph and have O(L) complexity, where L is length of search pattern.

Improve this answer

Comments

0

As a sidenote: Take a look at (Apache Solr) and the way it generates indexes. I find myself using it quite a bit when I am trying to implement something similar to Textmate's Command-T on the web.

Specifically check out the EdgeNGramFilterFactory. I believe there might even be some sourcecode somewhere. (It's in Java though…)

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.