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

Dane O'Connor
  • 75,180
  • 37
  • 119
  • 173
  • 2
    Care to explain what exactly those tools do? – Michael Petrotta Sep 11 '10 at 05: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. – Jorge Israel Peña Sep 11 '10 at 05:36
  • 1
    http://stackoverflow.com/questions/2891514/algoritms-for-fuzzy-matching-strings – ergosys Sep 11 '10 at 06: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. – David May 18 '11 at 02:14

5 Answers5

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.

monksy
  • 14,156
  • 17
  • 75
  • 124
2

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

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

nickf
  • 537,072
  • 198
  • 649
  • 721
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).

Rebecca Scott
  • 2,421
  • 2
  • 25
  • 39
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.

Luka Rahne
  • 10,336
  • 3
  • 34
  • 56
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…)

sqwk
  • 1,506
  • 2
  • 12
  • 13