在// Sublime (Ctrl+p或Cmd+p)中，使用哪种算法来实现文件搜索？

Question

我非常印象深刻的强大的搜索功能的崇高，我们后来发现在Visual代码和谷歌Chrome开发者。

一个非常基本的搜索算法可能会使用Trie，我想，但是这种对崇高文件等的搜索似乎是一种多方向的Trie (如果有这样的东西！)也就是说，如果您有一个文件名，如：

"I-am-a-very-big-beautifully-created-file-and-something-else.js“

搜索“已创建的文件”、“创建的文件”、“漂亮的东西”、“其他大的”、“大的其他”或该文件名称中的任何其他字符串组合，崇高和Visual代码将很快找到它和其他具有类似名称的文件。(版本并不是很强大，但这并不是重点。)

因此，我研究了一下Visual的源代码，但仍然不知道搜索是如何实现的，以及使用了哪种算法。我不是在找它的密码。只是需要了解一个高层次的理论，这个强大的特性是如何实现的，它为我们的开发人员节省了很多时间。

Answer 1

可以通过查看调用此函数时发生的情况来跟踪您正在寻找的VS代码功能：

https://github.com/microsoft/vscode/blob/master/src/vs/workbench/contrib/search/browser/anythingQuickAccess.ts#L365

这里有一个有趣的部分(只对第一个项进行筛选，然后对整个过滤器进行筛选)：

https://github.com/microsoft/vscode/blob/d1220da07267242e9b58193da0ded43bbe7f2aa5/src/vs/workbench/contrib/search/browser/anythingQuickAccess.ts#L570

如果您在那里进行挖掘，您会发现大部分有用的内容都重新组合在这个文件中：

https://github.com/microsoft/vscode/blob/master/src/vs/base/common/fuzzyScorer.ts

一些注意事项：

模糊搜索是相当严格的，如果没有找到单个字母或没有找到正确的顺序，则筛选器将不匹配。一个关键的优点是，您可以在结果中突出显示匹配的部分，它可以非常清楚地说明您的用户正在发生什么。

模糊记分器基于匹配的标签/描述/path对结果进行评分。

Answer 2

这看起来像DevTools在命令菜单中用于模糊搜索的代码。

open/CommandMenu.js?l=174

基本的diff算法是：

结束/diff/Diff.js?q=Diff.Diff&dr=CSs&l=4

Answer 3

我想这个名字是“模糊搜索”lol。这里有一个不错的github回购程序，其中一些善良的人发布了一个开源的JS版本，它比VS代码版本容易得多，因为它在npm上，而且只是一个文件：

https://github.com/farzher/fuzzysort