4 ms·

Sublime Text Ctrl+P Like Fuzzy Matching In Few Lines of Python

69 points by cplat 13y ago

DrJosiah 13y ago
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.
- gngeal 13y ago
  The SLIME addon for Emacs has been using this for symbol completion for at least six or seven years. I'm not sure where they got it from.
- swah 13y ago
  Which editor is that?
  - DrJosiah 13y ago
    PyPE - https://sf.net/projects/pype https://sf.net/projects/pype It's sort-of abandoned in that I've had a user-submitted patch to fix a major bug since last October, but I haven't had the time to review and apply it yet. I wouldn't suggest anyone use it at this point (I only do because it is exactly what I want; no more, no less), and usually point people to use Eric4 or Eric5, depending on whether you are focused on Python 2.x or Python 3.x .
cjh_ 13y ago
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). 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. [1] https://github.com/kien/ctrlp.vim https://github.com/kien/ctrlp.vim
spencera 13y ago
A slightly more sophisticated implementation: https://code.google.com/p/google-diff-match-patch/ https://code.google.com/p/google-diff-match-patch/
crucialfelix 13y ago
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. AFAIK Sublime, Ctrl-P and friends all followed and improved from TextMate's version. 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. [1] http://www.obdev.at/products/launchbar/legacy.html http://www.obdev.at/products/launchbar/legacy.html
- sorbits 13y ago
  If you’re the same felix as the comment author of the following comment, then it seems you meant to suggest it, but never did: LaunchBar style file opening ! You are a god ! I was going to suggest this as a feature. You have saved us thousands of boring hours clicking on triangles. Source: http://blog.macromates.com/2005/elevating-the-standard/#comment-27 http://blog.macromates.com/2005/elevating-the-standard/#comm... The feature in LaunchBar was btw an evolution of the LaunchBar author having a dozen shell scripts (or aliases) a la “ps=open -a PhotoShop” that he called from a terminal to quickly open his various applications and then later realized it could be automated.
  - crucialfelix 13y ago
    He wrote command t and then when I tried it I suggested doing the multi word matching trick. To the best of my memory, could be misremembering. i had some back and forth with him about it and he revised it to its current state. 8 years ago, yikes.
- johncoltrane 13y ago
  I was talking with someone on #vim about the history of that feature a few days ago. I traced it back to either Launchbar or Quicksilver and I'm glad I wasn't that far off the mark. As a side note, it's somehow funny how a sentence like "Sublime Text Ctrl+P Like Fuzzy Matching" can tell quite a lot about the person who writes it. I'm not criticizing, of course, but well… I find it funny. That's all.
pjscott 13y ago
If you want to give more weight to matches of consecutive characters, or do other fancy things, a sequence alignment algorithm could be useful: http://en.wikipedia.org/wiki/Smith-Waterman_algorithm http://en.wikipedia.org/wiki/Smith-Waterman_algorithm
- omershapira 13y ago
  Seriously, this algorithm (along with Levenshtein distance) should be taught in high-school.
- Agathos 13y ago
  I don't think a local alignment is helpful for Sublime's ctrl-p. I would go with Needleman-Wunsch.
sorbits 13y ago
Source for TextMate’s ranker can be found here (GPLv3): https://github.com/textmate/textmate/blob/master/Frameworks/text/src/ranker.cc#L46-L192 https://github.com/textmate/textmate/blob/master/Frameworks/... And some tests here: https://github.com/textmate/textmate/blob/master/Frameworks/text/tests/t_ranker.cc https://github.com/textmate/textmate/blob/master/Frameworks/...
gondo 13y ago
call me old school, but Ctrl + P should do print
- melling 13y ago
  Old school is previous line. How often do you print? It's not worth wasting a keystroke.
- airtonix 13y ago
  pff you ain't even out of the school yard yet buddy.
- omershapira 13y ago
  I think I know who removed the Scroll Lock from our keyboards. Meet me by the service entrance to the 69th Regiment Armory, no questions asked. We'll trebuchet that little devil to Siam.
wting 13y ago
I had to do something similar for autojump (fuzzy matching search string vs directories list). I started hand rolling my own based on Damerau-Levenshtein, but it turns that Python already has a similar implementation in the difflib: http://docs.python.org/2/library/difflib.html#difflib.get_close_matches http://docs.python.org/2/library/difflib.html#difflib.get_cl...
dangoor 13y ago
For Brackets, I went with something that's not a regex because I wanted certain parts of the string to be "special": http://www.blueskyonmars.com/2013/03/26/brackets-quick-open-thats-no-regex/ http://www.blueskyonmars.com/2013/03/26/brackets-quick-open-... But, I'll definitely look up a couple of the links that people have posted here about some other algorithms (Smith-Waterman, for example).

69 points by cplat 13y ago

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.

gngeal 13y ago
The SLIME addon for Emacs has been using this for symbol completion for at least six or seven years. I'm not sure where they got it from.
swah 13y ago
Which editor is that?
- DrJosiah 13y ago
  PyPE - https://sf.net/projects/pype https://sf.net/projects/pype It's sort-of abandoned in that I've had a user-submitted patch to fix a major bug since last October, but I haven't had the time to review and apply it yet. I wouldn't suggest anyone use it at this point (I only do because it is exactly what I want; no more, no less), and usually point people to use Eric4 or Eric5, depending on whether you are focused on Python 2.x or Python 3.x .

cjh_ 13y ago

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). 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. [1] https://github.com/kien/ctrlp.vim https://github.com/kien/ctrlp.vim

spencera 13y ago

A slightly more sophisticated implementation: https://code.google.com/p/google-diff-match-patch/ https://code.google.com/p/google-diff-match-patch/

crucialfelix 13y ago

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. AFAIK Sublime, Ctrl-P and friends all followed and improved from TextMate's version. 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. [1] http://www.obdev.at/products/launchbar/legacy.html http://www.obdev.at/products/launchbar/legacy.html

sorbits 13y ago
If you’re the same felix as the comment author of the following comment, then it seems you meant to suggest it, but never did: LaunchBar style file opening ! You are a god ! I was going to suggest this as a feature. You have saved us thousands of boring hours clicking on triangles. Source: http://blog.macromates.com/2005/elevating-the-standard/#comment-27 http://blog.macromates.com/2005/elevating-the-standard/#comm... The feature in LaunchBar was btw an evolution of the LaunchBar author having a dozen shell scripts (or aliases) a la “ps=open -a PhotoShop” that he called from a terminal to quickly open his various applications and then later realized it could be automated.
- crucialfelix 13y ago
  He wrote command t and then when I tried it I suggested doing the multi word matching trick. To the best of my memory, could be misremembering. i had some back and forth with him about it and he revised it to its current state. 8 years ago, yikes.
johncoltrane 13y ago
I was talking with someone on #vim about the history of that feature a few days ago. I traced it back to either Launchbar or Quicksilver and I'm glad I wasn't that far off the mark. As a side note, it's somehow funny how a sentence like "Sublime Text Ctrl+P Like Fuzzy Matching" can tell quite a lot about the person who writes it. I'm not criticizing, of course, but well… I find it funny. That's all.

pjscott 13y ago

If you want to give more weight to matches of consecutive characters, or do other fancy things, a sequence alignment algorithm could be useful: http://en.wikipedia.org/wiki/Smith-Waterman_algorithm http://en.wikipedia.org/wiki/Smith-Waterman_algorithm

omershapira 13y ago
Seriously, this algorithm (along with Levenshtein distance) should be taught in high-school.
Agathos 13y ago
I don't think a local alignment is helpful for Sublime's ctrl-p. I would go with Needleman-Wunsch.

sorbits 13y ago

Source for TextMate’s ranker can be found here (GPLv3): https://github.com/textmate/textmate/blob/master/Frameworks/text/src/ranker.cc#L46-L192 https://github.com/textmate/textmate/blob/master/Frameworks/... And some tests here: https://github.com/textmate/textmate/blob/master/Frameworks/text/tests/t_ranker.cc https://github.com/textmate/textmate/blob/master/Frameworks/...

gondo 13y ago

call me old school, but Ctrl + P should do print

melling 13y ago
Old school is previous line. How often do you print? It's not worth wasting a keystroke.
airtonix 13y ago
pff you ain't even out of the school yard yet buddy.
omershapira 13y ago
I think I know who removed the Scroll Lock from our keyboards. Meet me by the service entrance to the 69th Regiment Armory, no questions asked. We'll trebuchet that little devil to Siam.

wting 13y ago

I had to do something similar for autojump (fuzzy matching search string vs directories list). I started hand rolling my own based on Damerau-Levenshtein, but it turns that Python already has a similar implementation in the difflib: http://docs.python.org/2/library/difflib.html#difflib.get_close_matches http://docs.python.org/2/library/difflib.html#difflib.get_cl...

dangoor 13y ago

For Brackets, I went with something that's not a regex because I wanted certain parts of the string to be "special": http://www.blueskyonmars.com/2013/03/26/brackets-quick-open-thats-no-regex/ http://www.blueskyonmars.com/2013/03/26/brackets-quick-open-... But, I'll definitely look up a couple of the links that people have posted here about some other algorithms (Smith-Waterman, for example).