ublime Text是很多碼農(nóng)最喜歡的編程利器。蟲蟲也是是它的擁躉之一。它啟動快趁手好用，通過設置你打開的文件，下次還會繼續(xù)打開，在你電腦出現(xiàn)故障（比如藍屏）之后，再次打開還能回到你工作狀態(tài)，不怕丟失內(nèi)容。還有很多很便捷實用的功能，比如utf8編碼轉(zhuǎn)換（去除bom）。當然還有一個我最喜歡的一個的功能，模糊搜索，這是本文今天的要說的主角。

用模糊匹配來過濾文件和函數(shù)的速度非常快。網(wǎng)上的有很多人都想知道如何工作的。但是還沒有一個令人滿意的答案。我決定對其探索研究一番。

Sublime的模糊匹配

Sublime有兩個超級方便的導航功能。一個用于查找文件，另一個用于查找字符（函數(shù)，類名等）。兩者工作方式都相同。我們不必完全正確地輸入文件名，只需鍵入文件名中包含的字母即可。文件模糊查詢模式的進入是通過快捷鍵Crtl+P（mac下是?+P）。進入模糊匹配模式然后輸入幾個字母，搜索會用字母做模糊匹配然后將匹配的文件列出了以供快速點擊進入，比如我們輸入js：

這是一個文件搜索。我進入搜索模式'js'。最上面的結(jié)果是'japanese-sjis.inc.php'。每個結(jié)果中的匹配字符都以粗體高亮顯示，這個結(jié)果如果熟悉正則的朋友應該知道好像就是模式匹配/j.*s/。

下面是另一個例子，我們在搜索框中先輸入@會進入當前文件的函數(shù)搜索模式。

比如我們輸入"add"會顯示以包含add所有函數(shù)和方法。同時文件中的相關文件就會高亮顯示，比如本例中的"AddAccessoryCommand"。點擊列表中的函數(shù)就會直接定位到函數(shù)的定義。

一點想法

sublime模糊匹配非常好用，非常強大。但是其他的地方都沒有這樣的功能，包括其他的編輯器、IDE等。

好奇心促使我們相對其做一些探索，然后可能的話將其功能想辦法嫁接到其他項目使用。

功能探索

如果我們拿Sublime Text做實驗，我們會觀察到兩件事情：

模糊匹配會按順序匹配每個字符。

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

我們可以輕松實現(xiàn)第一部分。我們自己實現(xiàn)下吧吧！

瞧！目前，我們可以很容易實現(xiàn)了C++和JavaScript的簡單版本。我這樣做是出于一個非常具體的原因。它可以用來取代簡單的子串匹配。

匹配打分

有趣的部分打分。打分時候考慮到什么因素得？這新因素都會給打多少分？首先，下面是可能設計的打分點：

匹配的字母

未匹配的字母

連續(xù)匹配的字母

接近開始

分隔符后的字母（空格符包括空格，下劃線）

寫字母后面的大寫字母（又名CamelCase，駝峰命名法）

這部分很簡單。匹配的字母加分。不匹配字母減分。匹配接近開始加分。匹配短語中間的第一個字母加分。在駝峰命名案例中匹配大寫字母加分。

當然具體怎么加分，加多少分？目前我還不知道正確的答案。權重取決于你的預期數(shù)據(jù)集。文件路徑與文件名不同。文件擴展名則可以忽略的。單個單詞關心連續(xù)的匹配，但不包括分隔符或駱駝大小寫。

目前我們定義了一個各項指標的權衡。它對很多不同的數(shù)據(jù)集都有很好的效果。

分數(shù)從0開始

匹配的字母：+0分

不匹配的字母：-1點

連續(xù)匹配加分：+5分

分隔符匹配加分：+10分

駝峰匹配加分：+10分

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

需要指出的是打分值沒有啥實在的意義，只作為一個相對比較的參考。得分范圍也沒有限定到0-100不。它大概是-50-50之間是]。由于不匹配的字母減分，較長的單詞具有可能會得到比較低的最低分值。由于匹配加分，更長的搜索模式可能更可能得到最高分。

分隔符和駝峰加分比較大。連續(xù)的匹配加分比較有意義。

如果你不匹配前三個字母，會減分。如果在開始附近匹配會加分。中間和結(jié)束之間的匹配沒有區(qū)別。

完全匹配沒有明確的加分機制。不匹配的字母有會減分。所以更短的字符串和更近的匹配會得分更大。

大概的加分情況就是這樣。對于單個搜索模式，結(jié)果可以按分數(shù)排序。

搜索性能

Grep很快。真的很快。它高度優(yōu)化，不需要測試每個字母。它可以跳過開頭。

模糊匹配速度不如grep快。它需要測試搜索字符串中的每個字母。雖然我寫了我認為干凈的代碼，但它并沒有經(jīng)過大量的優(yōu)化。作為演示目的，在可讀性上做了一定的考慮。

我電腦的CPU是Intel i5-4670 Haswell @ 3.4Ghz。將模式與Unreal Engine 4中找到的13,164個文件名匹配，在單個線程上花費約5毫秒。使用355,000個字對英文單詞列表進行測試需要大約50毫秒。 JavaScript沒有C++快。實際的測試紅總，它大概慢25倍。可能有一些明顯的改進空間。提供了異步幫助程序，因此腳本不會在慢速搜索中阻止。

總結(jié)

我喜歡Sublime Text以及他的模糊匹配算法。我的目標模仿他實現(xiàn)相同同能的代碼。我認為我實現(xiàn)了這個目標，最后附上兩種語言的實現(xiàn)源碼，有興趣的同學可以參考學習。

源代碼一 C實現(xiàn)：

#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代碼實現(xiàn)：

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;

};