It was actually me that suggested to the TextMate guy to do the fuzzy lookup in this way: matching significant characters in side the search term.<p>AFAIK Sublime, Ctrl-P and friends all followed and improved from TextMate's version.<p>It was originally a feature in LaunchBar which was on NextStep and was ported to OS X [1] QuickSilver and Spotlight were also influenced by LaunchBar.<p>[1] <a href="http://www.obdev.at/products/launchbar/legacy.html" rel="nofollow">http://www.obdev.at/products/launchbar/legacy.html</a>
Source for TextMate’s ranker can be found here (GPLv3): <a href="https://github.com/textmate/textmate/blob/master/Frameworks/text/src/ranker.cc#L46-L192" rel="nofollow">https://github.com/textmate/textmate/blob/master/Frameworks/...</a><p>And some tests here: <a href="https://github.com/textmate/textmate/blob/master/Frameworks/text/tests/t_ranker.cc" rel="nofollow">https://github.com/textmate/textmate/blob/master/Frameworks/...</a>
If you want to give more weight to matches of consecutive characters, or do other fancy things, a sequence alignment algorithm could be useful:<p><a href="http://en.wikipedia.org/wiki/Smith-Waterman_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Smith-Waterman_algorithm</a>
A slightly more sophisticated implementation: <a href="https://code.google.com/p/google-diff-match-patch/" rel="nofollow">https://code.google.com/p/google-diff-match-patch/</a>
I implemented something very similar in perl a few weeks back for my user interfaces project; I wrote a desktop search client that would take a query from the user and score results based on how many and how well it matches a series of different interpretations of the query (fuzzy was one of them).<p>I too am really amazed this isn't more prevalent as it is so easy to do, after discovering the vim ctrl-p [1] plugin I rarely go a day without using it.<p>[1] <a href="https://github.com/kien/ctrlp.vim" rel="nofollow">https://github.com/kien/ctrlp.vim</a>
For Brackets, I went with something that's not a regex because I wanted certain parts of the string to be "special":<p><a href="http://www.blueskyonmars.com/2013/03/26/brackets-quick-open-thats-no-regex/" rel="nofollow">http://www.blueskyonmars.com/2013/03/26/brackets-quick-open-...</a><p>But, I'll definitely look up a couple of the links that people have posted here about some other algorithms (Smith-Waterman, for example).
I had to do something similar for autojump (fuzzy matching search string vs directories list).<p>I started hand rolling my own based on Damerau-Levenshtein, but it turns that Python already has a similar implementation in the difflib:<p><a href="http://docs.python.org/2/library/difflib.html#difflib.get_close_matches" rel="nofollow">http://docs.python.org/2/library/difflib.html#difflib.get_cl...</a>
I added similar functionality to my editor about 5 years ago after seeing a coworker use Sublime Text. I'm amazed that all editors don't have it already.