TextMate的“转到文件”模糊搜索算法是什么？

Question

Textmate的“跳转到文件”模糊搜索功能真的很棒。

Wincent的Command-T插件也能完成类似的功能，而且效果很好。

有人可以解释一下它们是如何工作的吗？这种方法有一个通用术语吗？

编辑：关于这些工具的更多细节

这些工具让你在输入时缩小选项列表(在本例中是文件路径)。

例如，如果我有以下文件：

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

我可以输入以下任意一种方式，缩小列表以获取/app/models/people.rb：

amp
peo
mp
modelsp

它非常灵活，当我使用的应用程序没有这个功能时，我会感到缺失。我想了解更多关于它的知识，以便在必要时可以实现我的自己的插件。希望我能更好地解释它，但这就是我在这里的原因 :)

要看它的实际效果，请查看wincent的Command-T演示视频

- Dane O'Connor

---

能否解释一下这些工具具体是做什么的？ - Michael Petrotta

它就像 Firefox 的 Awesomebar，但是针对当前打开项目中的文件。随着您的输入，它会“缩小范围”，以便找到您想要的文件。我发现这个功能非常棒，但我从未多想过它。 - Jorge Israel Peña

https://dev59.com/jHE85IYBdhLWcg3wNgrk - ergosys

ReSharper for Visual Studio允许您使用大小写来缩小文件中的CamelCasing范围...非常酷。您还可以混合使用通配符。 - David

Answer 1

似乎是在每个字母之间进行通配符搜索。

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

如果它只匹配到选项列表中的一个项目，那么它会将其作为预期选项返回。

- monksy

---

我相信它也更加重视靠近dirsep的字母。 - kniteli

Answer 2

看起来Command-T使用match.c中的recursive_match函数给出一个double分数进行排序，以执行模糊搜索。尽管Command-T的源代码受版权保护，但可以通过在文本编辑器中打开vimball（在此页面底部下载）找到该源代码，并且可能可用作更通用的模糊搜索算法的灵感来源（至少对于比我更擅长阅读C语言的人而言）。请注意保留HTML标签。

- Rebecca Scott

Answer 3

看起来这就是你所谈论的确切代码：

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

- nickf

Answer 4

虽然我不知道这是怎么工作的，但是如果你想要快速查找，你可以生成类似于http://en.wikipedia.org/wiki/Directed_acyclic_word_graph的东西，并且具有O（L）复杂度，其中L是搜索模式的长度。

- Luka Rahne

Answer 5

顺便提一下：看看Apache Solr以及它生成索引的方式。当我尝试在Web上实现类似Textmate的Command-T时，我发现自己经常使用它。

具体来说，请查看EdgeNGramFilterFactory。我相信可能会有一些源代码可用。（不过是Java…）

- sqwk