ublime Text是很多码农最喜欢的编程利器。虫虫也是是它的拥趸之一。它启动快趁手好用，通过设置你打开的文件，下次还会继续打开，在你电脑出现故障（比如蓝屏）之后，再次打开还能回到你工作状态，不怕丢失内容。还有很多很便捷实用的功能，比如utf8编码转换（去除bom）。当然还有一个我最喜欢的一个的功能，模糊搜索，这是本文今天的要说的主角。

用模糊匹配来过滤文件和函数的速度非常快。网上的有很多人都想知道如何工作的。但是还没有一个令人满意的答案。我决定对其探索研究一番。

Sublime的模糊匹配

Sublime有两个超级方便的导航功能。一个用于查找文件，另一个用于查找字符（函数，类名等）。两者工作方式都相同。我们不必完全正确地输入文件名，只需键入文件名中包含的字母即可。文件模糊查询模式的进入是通过快捷键Crtl+P（mac下是?+P）。进入模糊匹配模式然后输入几个字母，搜索会用字母做模糊匹配然后将匹配的文件列出了以供快速点击进入，比如我们输入js：

这是一个文件搜索。我进入搜索模式'js'。最上面的结果是'japanese-sjis.inc.php'。每个结果中的匹配字符都以粗体高亮显示，这个结果如果熟悉正则的朋友应该知道好像就是模式匹配/j.*s/。

下面是另一个例子，我们在搜索框中先输入@会进入当前文件的函数搜索模式。

比如我们输入"add"会显示以包含add所有函数和方法。同时文件中的相关文件就会高亮显示，比如本例中的"AddAccessoryCommand"。点击列表中的函数就会直接定位到函数的定义。

一点想法

sublime模糊匹配非常好用，非常强大。但是其他的地方都没有这样的功能，包括其他的编辑器、IDE等。

好奇心促使我们相对其做一些探索，然后可能的话将其功能想办法嫁接到其他项目使用。

功能探索

如果我们拿Sublime Text做实验，我们会观察到两件事情：

模糊匹配会按顺序匹配每个字符。

有一个隐藏的匹配打分，其中有一些匹配的字符比其他字符的分值多。

我们可以轻松实现第一部分。我们自己实现下吧吧！

瞧！目前，我们可以很容易实现了C++和JavaScript的简单版本。我这样做是出于一个非常具体的原因。它可以用来取代简单的子串匹配。

匹配打分

有趣的部分打分。打分时候考虑到什么因素得？这新因素都会给打多少分？首先，下面是可能设计的打分点：

匹配的字母

未匹配的字母

连续匹配的字母

接近开始

分隔符后的字母（空格符包括空格，下划线）

写字母后面的大写字母（又名CamelCase，驼峰命名法）

这部分很简单。匹配的字母加分。不匹配字母减分。匹配接近开始加分。匹配短语中间的第一个字母加分。在驼峰命名案例中匹配大写字母加分。

当然具体怎么加分，加多少分？目前我还不知道正确的答案。权重取决于你的预期数据集。文件路径与文件名不同。文件扩展名则可以忽略的。单个单词关心连续的匹配，但不包括分隔符或骆驼大小写。

目前我们定义了一个各项指标的权衡。它对很多不同的数据集都有很好的效果。

分数从0开始

匹配的字母：+0分

不匹配的字母：-1点

连续匹配加分：+5分

分隔符匹配加分：+10分

驼峰匹配加分：+10分

不匹配的大写字母：-3分（最大-9）

需要指出的是打分值没有啥实在的意义，只作为一个相对比较的参考。得分范围也没有限定到0-100不。它大概是-50-50之间是]。由于不匹配的字母减分，较长的单词具有可能会得到比较低的最低分值。由于匹配加分，更长的搜索模式可能更可能得到最高分。

分隔符和驼峰加分比较大。连续的匹配加分比较有意义。

如果你不匹配前三个字母，会减分。如果在开始附近匹配会加分。中间和结束之间的匹配没有区别。

完全匹配没有明确的加分机制。不匹配的字母有会减分。所以更短的字符串和更近的匹配会得分更大。

大概的加分情况就是这样。对于单个搜索模式，结果可以按分数排序。

搜索性能

Grep很快。真的很快。它高度优化，不需要测试每个字母。它可以跳过开头。

模糊匹配速度不如grep快。它需要测试搜索字符串中的每个字母。虽然我写了我认为干净的代码，但它并没有经过大量的优化。作为演示目的，在可读性上做了一定的考虑。

我电脑的CPU是Intel i5-4670 Haswell @ 3.4Ghz。将模式与Unreal Engine 4中找到的13,164个文件名匹配，在单个线程上花费约5毫秒。使用355,000个字对英文单词列表进行测试需要大约50毫秒。 JavaScript没有C++快。实际的测试红总，它大概慢25倍。可能有一些明显的改进空间。提供了异步帮助程序，因此脚本不会在慢速搜索中阻止。

总结

我喜欢Sublime Text以及他的模糊匹配算法。我的目标模仿他实现相同同能的代码。我认为我实现了这个目标，最后附上两种语言的实现源码，有兴趣的同学可以参考学习。

源代码一 C实现：

#ifndef FTS_FUZZY_MATCH_H

#define FTS_FUZZY_MATCH_H

#include <cstdint>

#include <ctype.h>

#include <cstring>

#include <cstdio>

namespace fts {

static bool fuzzy_match_simple(char const * pattern, char const * str);

static bool fuzzy_match(char const * pattern, char const * str, int & outScore);

static bool fuzzy_match(char const * pattern, char const * str, int & outScore, uint8_t * matches, int maxMatches);

}

#ifdef FTS_FUZZY_MATCH_IMPLEMENTATION

namespace fts {

namespace fuzzy_internal {

static bool fuzzy_match_recursive(const char * pattern, const char * str, int & outScore, const char * strBegin,

uint8_t const * srcMatches, uint8_t * newMatches, int maxMatches, int nextMatch,

int & recursionCount, int recursionLimit);

}

static bool fuzzy_match_simple(char const * pattern, char const * str) {

while (*pattern !='>while (*pattern !='>while (*pattern !='\0' && *str !='\0') {<' && *str !='>while (*pattern !='\0' && *str !='\0') {<') {<' && *str !='>while (*pattern !='\0' && *str !='\0') {<') {

if (tolower(*pattern)==tolower(*str))

++pattern;

++str;

}

return *pattern=='>return *pattern=='\0' ? true : false;<' ? true : false;

}

static bool fuzzy_match(char const * pattern, char const * str, int & outScore) {

uint8_t matches[256];

return fuzzy_match(pattern, str, outScore, matches, sizeof(matches));

}

static bool fuzzy_match(char const * pattern, char const * str, int & outScore, uint8_t * matches, int maxMatches) {

int recursionCount=0;

int recursionLimit=10;

return fuzzy_internal::fuzzy_match_recursive(pattern, str, outScore, str, nullptr, matches, maxMatches, 0, recursionCount, recursionLimit);

}

static bool fuzzy_internal::fuzzy_match_recursive(const char * pattern, const char * str, int & outScore,

const char * strBegin, uint8_t const * srcMatches, uint8_t * matches, int maxMatches,

int nextMatch, int & recursionCount, int recursionLimit)

{

++recursionCount;

if (recursionCount >=recursionLimit)

return false;

if (*pattern=='>if (*pattern=='\0' || *str=='\0')<' || *str=='>if (*pattern=='\0' || *str=='\0')<')

return false;

bool recursiveMatch=false;

uint8_t bestRecursiveMatches[256];

int bestRecursiveScore=0;

bool first_match=true;

while (*pattern !='\0' && *str !='\0') {

if (tolower(*pattern)==tolower(*str)) {

if (nextMatch >=maxMatches)

return false;

if (first_match && srcMatches) {

memcpy(matches, srcMatches, nextMatch);

first_match=false;

}

uint8_t recursiveMatches[256];

int recursiveScore;

if (fuzzy_match_recursive(pattern, str + 1, recursiveScore, strBegin, matches, recursiveMatches, sizeof(recursiveMatches), nextMatch, recursionCount, recursionLimit)) {

if (!recursiveMatch || recursiveScore > bestRecursiveScore) {

memcpy(bestRecursiveMatches, recursiveMatches, 256);

bestRecursiveScore=recursiveScore;

}

recursiveMatch=true;

}

matches[nextMatch++]=(uint8_t)(str - strBegin);

++pattern;

}

++str;

}

bool matched=*pattern=='>bool matched=*pattern=='\0' ? true : false;<' ? true : false;

if (matched) {

const int sequential_bonus=15;

const int separator_bonus=30;

const int camel_bonus=30;

const int first_letter_bonus=15;

const int leading_letter_penalty=-5;

const int max_leading_letter_penalty=-15;

const int unmatched_letter_penalty=-1;

while (*str !='>while (*str !='\0')<')

++str;

outScore=100;

int penalty=leading_letter_penalty * matches[0];

if (penalty < max_leading_letter_penalty)

penalty=max_leading_letter_penalty;

outScore +=penalty;

int unmatched=(int)(str - strBegin) - nextMatch;

outScore +=unmatched_letter_penalty * unmatched;

for (int i=0; i < nextMatch; ++i) {

uint8_t currIdx=matches[i];

if (i > 0) {

uint8_t prevIdx=matches[i - 1];

if (currIdx==(prevIdx + 1))

outScore +=sequential_bonus;

}

if (currIdx > 0) {

char neighbor=strBegin[currIdx - 1];

char curr=strBegin[currIdx];

if (::islower(neighbor) && ::isupper(curr))

outScore +=camel_bonus;

bool neighborSeparator=neighbor=='_' || neighbor==' ';

if (neighborSeparator)

outScore +=separator_bonus;

}

else {

outScore +=first_letter_bonus;

}

}

}

if (recursiveMatch && (!matched || bestRecursiveScore > outScore)) {

memcpy(matches, bestRecursiveMatches, maxMatches);

outScore=bestRecursiveScore;

return true;

}

else if (matched) {

return true;

}

else {

return false;

}

}

}

#endif // FTS_FUZZY_MATCH_IMPLEMENTATION

#endif // FTS_FUZZY_MATCH_H

源代码二 JS代码实现：

function fuzzy_match_simple(pattern, str) {

var patternIdx=0;

var strIdx=0;

var patternLength=pattern.length;

var strLength=str.length;

while (patternIdx !=patternLength && strIdx !=strLength) {

var patternChar=pattern.charAt(patternIdx).toLowerCase();

var strChar=str.charAt(strIdx).toLowerCase();

if (patternChar==strChar)

++patternIdx;

++strIdx;

}

return patternLength !=0 && strLength !=0 && patternIdx==patternLength ? true : false;

}

function fuzzy_match(pattern, str) {

var adjacency_bonus=5;

var separator_bonus=10;

var camel_bonus=10;

var leading_letter_penalty=-3;

var max_leading_letter_penalty=-9;

var unmatched_letter_penalty=-1;

var score=0;

var patternIdx=0;

var patternLength=pattern.length;

var strIdx=0;

var strLength=str.length;

var prevMatched=false;

var prevLower=false;

var prevSeparator=true;

var bestLetter=null;

var bestLower=null;

var bestLetterIdx=null;

var bestLetterScore=0;

var matchedIndices=[];

while (strIdx !=strLength) {

var patternChar=patternIdx !=patternLength ? pattern.charAt(patternIdx) : null;

var strChar=str.charAt(strIdx);

var patternLower=patternChar !=null ? patternChar.toLowerCase() : null;

var strLower=strChar.toLowerCase();

var strUpper=strChar.toUpperCase();

var nextMatch=patternChar && patternLower==strLower;

var rematch=bestLetter && bestLower==strLower;

var advanced=nextMatch && bestLetter;

var patternRepeat=bestLetter && patternChar && bestLower==patternLower;

if (advanced || patternRepeat) {

score +=bestLetterScore;

matchedIndices.push(bestLetterIdx);

bestLetter=null;

bestLower=null;

bestLetterIdx=null;

bestLetterScore=0;

}

if (nextMatch || rematch) {

var newScore=0;

if (patternIdx==0) {

var penalty=Math.max(strIdx * leading_letter_penalty, max_leading_letter_penalty);

score +=penalty;

}

if (prevMatched)

newScore +=adjacency_bonus;

if (prevSeparator)

newScore +=separator_bonus;

if (prevLower && strChar==strUpper && strLower !=strUpper)

newScore +=camel_bonus;

if (nextMatch)

++patternIdx;

if (newScore >=bestLetterScore) {

if (bestLetter !=null)

score +=unmatched_letter_penalty;

bestLetter=strChar;

bestLower=bestLetter.toLowerCase();

bestLetterIdx=strIdx;

bestLetterScore=newScore;

}

prevMatched=true;

}

else {

formattedStr +=strChar;

score +=unmatched_letter_penalty;

prevMatched=false;

}

prevLower=strChar==strLower && strLower !=strUpper;

prevSeparator=strChar=='_' || strChar==' ';

++strIdx;

}

if (bestLetter) {

score +=bestLetterScore;

matchedIndices.push(bestLetterIdx);

}

var formattedStr="";

var lastIdx=0;

for (var i=0; i < matchedIndices.length; ++i) {

var idx=matchedIndices[i];

formattedStr +=str.substr(lastIdx, idx - lastIdx) + "<b>" + str.charAt(idx) + "</b>";

lastIdx=idx + 1;

}

formattedStr +=str.substr(lastIdx, str.length - lastIdx);

var matched=patternIdx==patternLength;

return [matched, score, formattedStr];

}

function fts_fuzzy_match_async(matchFn, pattern, dataSet, onComplete) {

var ITEMS_PER_CHECK=1000;

var max_ms_per_frame=1000.0/30.0; /

var dataIndex=0;

var results=[];

var resumeTimeout=null;

function step() {

clearTimeout(resumeTimeout);

resumeTimeout=null;

var stopTime=performance.now() + max_ms_per_frame;

for (; dataIndex < dataSet.length; ++dataIndex) {

if ((dataIndex % ITEMS_PER_CHECK)==0) {

if (performance.now() > stopTime) {

resumeTimeout=setTimeout(step, 1);

return;

}

}

var str=dataSet[dataIndex];

var result=matchFn(pattern, str);

if (matchFn==fuzzy_match_simple && result==true)

results.push(str);

else if (matchFn==fuzzy_match && result[0]==true)

results.push(result);

}

onComplete(results);

return null;

};