Sublime Text是很多碼農最喜歡的編程利器。蟲蟲也是是它的擁躉之一。它啟動快趁手好用，通過設置你打開的文件，下次還會繼續打開，在你電腦出現故障（比如藍屏）之後，再次打開還能回到你工作狀態，不怕丟失內容。還有很多很便捷實用的功能，比如utf8編碼轉換（去除bom）。當然還有一個我最喜歡的一個的功能，模糊搜索，這是本文今天的要說的主角。
用模糊匹配來過濾文件和函數的速度非常快。網上的有很多人都想知道如何工作的。但是還沒有一個令人滿意的答案。我決定對其探索研究一番。
Sublime的模糊匹配
Sublime有兩個超級方便的導航功能。一個用於查找文件，另一個用於查找字符（函數，類名等）。兩者工作方式都相同。我們不必完全正確地輸入文件名，只需鍵入文件名中包含的字母即可。文件模糊查詢模式的進入是通過快捷鍵Crtl+P（mac下是⌘+P）。進入模糊匹配模式然後輸入幾個字母，搜索會用字母做模糊匹配然後將匹配的文件列出了以供快速點擊進入，比如我們輸入js：
這是一個文件搜索。我進入搜索模式'js'。最上面的結果是'japanese-sjis.inc.php'。每個結果中的匹配字符都以粗體高亮顯示，這個結果如果熟悉正則的朋友應該知道好像就是模式匹配/j.*s/。
下面是另一個例子，我們在搜索框中先輸入@會進入當前文件的函數搜索模式。
比如我們輸入"add"會顯示以包含add所有函數和方法。同時文件中的相關文件就會高亮顯示，比如本例中的"AddAccessoryCommand"。點擊列表中的函數就會直接定位到函數的定義。
一點想法
好奇心促使我們相對其做一些探索，然後可能的話將其功能想辦法嫁接到其他項目使用。
功能探索
如果我們拿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
#include
#include
#include
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 != '\0' && *str != '\0') {
if (tolower(*pattern) == tolower(*str))
++pattern;
++str;
}
return *pattern == '\0' ? 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 == '\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 == '\0' ? 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 != '\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) + "" + str.charAt(idx) + "";
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;
};
this.cancel = function() {
if (resumeTimeout !== null)
clearTimeout(resumeTimeout);
};
this.start = function() {
step();
}
this.flush = function() {
max_ms_per_frame = Infinity;
step();
}
};
閱讀更多 蟲蟲安全 的文章
