在論壇和聊天室這樣的場(chǎng)景里，為了保證用戶體驗(yàn)，我們經(jīng)常需要屏蔽很多不良詞語(yǔ)。對(duì)于單個(gè)關(guān)鍵詞查找，自然是indexOf、正則那樣的方式效率比較高。但對(duì)于關(guān)鍵詞較多的情況下，多次重復(fù)調(diào)用indexOf、正則的話去匹配全文的話，性能消耗非常大。由于目標(biāo)字符串通常來(lái)說(shuō)體積都比較大，所以必須要保證一次遍歷就得到結(jié)果。根據(jù)這樣的需求，很容易就想到對(duì)全文每個(gè)字符依次匹配的方式。比如對(duì)于這段文字：“Mike Jordan had said "Just do IT", so Mark has been a coder.”，假如我們的關(guān)鍵詞是“Mike”“Mark”，那么可以遍歷整句話，當(dāng)找到“M”就接著看能不能匹配到“i”或者“a”，能一直匹配到最后則成功找到一個(gè)關(guān)鍵詞，否則繼續(xù)遍歷。那么關(guān)鍵詞的結(jié)構(gòu)就應(yīng)該是這樣的： 

var keywords = {
 M: {
 i: {
  k: {
  e: {end: true}
  }
 },
 a: {
  r: {
  k: {end: true}
  }
 }
 }
}

由上文可以看出這個(gè)數(shù)據(jù)就是一個(gè)樹(shù)結(jié)構(gòu)，而根據(jù)關(guān)鍵詞組來(lái)創(chuàng)建樹(shù)結(jié)構(gòu)還是比較耗時(shí)的，而關(guān)鍵詞卻又是我們?cè)缫呀o定的，所以可以在匹配前預(yù)先創(chuàng)建這樣的數(shù)據(jù)結(jié)構(gòu)。代碼如下： 

function buildTree(keywords) {
 var tblCur = {},
 key, str_key, Length, j, i;
 var tblRoot = tblCur;

 for(j = keywords.length - 1; j >= 0; j -= 1) {
 str_key = keywords[j];
 Length = str_key.length;
 for(i = 0; i < Length; i += 1) {
  key = str_key.charAt(i);
  if(tblCur.hasOwnProperty(key)) {
  tblCur = tblCur[key];
  } else {
  tblCur = tblCur[key] = {};
  }
 }
 tblCur.end = true; //最后一個(gè)關(guān)鍵字
 tblCur = tblRoot;
 }
 return tblRoot;
}

 這段代碼中用了一個(gè)連等語(yǔ)句：tblCur = tblCur[key] = {}，這里要注意的是語(yǔ)句的執(zhí)行順序，由于[]的運(yùn)算級(jí)比=高，所以首先是在 tblCur對(duì)象中先創(chuàng)建一個(gè)key屬性。結(jié)合tblRoot = tblCur = {} 看，執(zhí)行順序就是： 

var tblRoot = tblCur = {};
tblRoot = tblCur;
tblCur['key'] = undefined; // now tblRoot = {key: undefined}
tblCur['key'] = {};
tblCur = tblCur['key'];

通過(guò)上面的代碼就構(gòu)建了好了所需的查詢數(shù)據(jù)，下面看看查詢接口的寫(xiě)法。 

對(duì)于目標(biāo)字符串的每一字，我們都從這個(gè)keywords頂部開(kāi)始匹配。首先是 keywords[a] ，若存在，則看 keyword[a][b]，若最后 keyword[a][b]…[x]=true 則說(shuō)明匹配成功，若 keyword[a][b]…[x]=undefined，則從下一個(gè)位置重新開(kāi)始匹配 keywords[a] 。 

function search(content) {
 var tblCur,
 p_star = 0,
 n = content.length,
 p_end,
 match, //是否找到匹配
 match_key,
 match_str,
 arrMatch = [], //存儲(chǔ)結(jié)果
 arrLength = 0; //arrMatch的長(zhǎng)度索引

 while(p_star < n) {
 tblCur = tblRoot; //回溯至根部
 p_end = p_star;
 match_str = "";
 match = false;
 do {
  match_key = content.charAt(p_end);
  if(!(tblCur = tblCur[match_key])) { //本次匹配結(jié)束
  p_star += 1;
  break;
  } else {
  match_str += match_key;
  }
  p_end += 1;
  if(tblCur.end) //是否匹配到尾部
  {
  match = true;
  }
 } while (true);

 if(match) { //最大匹配
  arrMatch[arrLength] = { 
  key: match_str,
  begin: p_star - 1,
  end: p_end
  };
  arrLength += 1;
  p_star = p_end;
 }
 }
 return arrMatch;
} 

以上就是整個(gè)關(guān)鍵詞匹配系統(tǒng)的核心。這里很好的用到了js的語(yǔ)言特性，效率非常高。我用一篇50萬(wàn)字的《搜神記》來(lái)做測(cè)試，從中查找給定的300個(gè)成語(yǔ)，匹配的效果是1秒左右。重要的是，由于目標(biāo)文本是一次遍歷的，所以目標(biāo)文本的長(zhǎng)短對(duì)查詢時(shí)間的影響幾乎不計(jì)。對(duì)查詢時(shí)間影響較大的是關(guān)鍵詞的數(shù)量，目標(biāo)文本的每個(gè)字都遍歷一遍關(guān)鍵詞，所以對(duì)查詢有一定影響。

簡(jiǎn)單分析

看到上文估計(jì)你也納悶，對(duì)每個(gè)字都遍歷一遍所有關(guān)鍵詞，就算有些關(guān)鍵詞有部分相同，但是完全遍歷也是挺耗時(shí)的呀。但js中對(duì)象的屬性是使用哈希表來(lái)進(jìn)行構(gòu)建的，這種結(jié)構(gòu)的數(shù)據(jù)跟單純的數(shù)組遍歷是有很大不同的，效率要比基于順序的數(shù)組遍歷高得多?？赡苡行┩瑢W(xué)對(duì)數(shù)據(jù)結(jié)構(gòu)不太熟悉，這里我簡(jiǎn)單說(shuō)一下哈希表的相關(guān)內(nèi)容。 

首先看看數(shù)據(jù)的存儲(chǔ)。

數(shù)據(jù)在內(nèi)存的存儲(chǔ)由兩部分組成，一部分是值，另一部分是地址。把內(nèi)存想象成一本新華字典，那字的解釋就是值，而目錄就是地址。字典里面是按拼音排序的，比如相同發(fā)音的“ni”就排在同一塊，也就是說(shuō)數(shù)組整齊排列在一塊內(nèi)存區(qū)域里面，這樣的結(jié)構(gòu)就是數(shù)組，你可以指定“ni” 1號(hào)，10號(hào)來(lái)訪問(wèn)。結(jié)構(gòu)圖如下：

數(shù)組的優(yōu)勢(shì)是遍歷簡(jiǎn)單，通過(guò)下標(biāo)就能直接訪問(wèn)相應(yīng)的數(shù)據(jù)了。但是它要增刪某一項(xiàng)就非常困難。比如你要把第6項(xiàng)刪掉，那第5項(xiàng)之后的數(shù)據(jù)都要向前移一個(gè)位置。如果你要?jiǎng)h除第一位，整個(gè)數(shù)組都要移動(dòng)，消耗非常大。

為了解決數(shù)組增刪的問(wèn)題，鏈表就出現(xiàn)了。如果我們將值分成兩部分，一部分用來(lái)儲(chǔ)存原來(lái)的值，另一部分用來(lái)儲(chǔ)存一個(gè)地址，這個(gè)地址指向另外一個(gè)同樣的結(jié)構(gòu)，以此類推就構(gòu)成了一個(gè)鏈表。結(jié)構(gòu)如下：

從上圖可以明顯看出，對(duì)鏈表進(jìn)行增刪非常簡(jiǎn)單，只要把目標(biāo)項(xiàng)和前一項(xiàng)的next改寫(xiě)就完成了。但是要查詢某個(gè)項(xiàng)的值就非常困難了，你必須依次遍歷才可以訪問(wèn)到目標(biāo)位置。

 為了整合這兩種結(jié)構(gòu)的優(yōu)勢(shì)，聰明如你一定想到了下面這種結(jié)構(gòu)。

這種數(shù)據(jù)結(jié)構(gòu)就是哈希表結(jié)構(gòu)。數(shù)組里面存儲(chǔ)鏈表的頭地址，就可以形成一個(gè)二維數(shù)據(jù)表。至于數(shù)據(jù)如何分布，這個(gè)就是哈希算法，正規(guī)的翻譯應(yīng)該是散列算法。算法雖然有很多種，原理上都是通過(guò)一個(gè)函數(shù)對(duì)key進(jìn)行求解，再根據(jù)求解得到的結(jié)果安放數(shù)據(jù)。也就是說(shuō)key和實(shí)際地址之間形成了一個(gè)映射，所以這個(gè)時(shí)候我們不再以數(shù)組下標(biāo)或者單純的遍歷來(lái)訪問(wèn)數(shù)組，而是以散列函數(shù)的反函數(shù)來(lái)定位數(shù)據(jù)。js中的對(duì)象就是一個(gè)哈希結(jié)構(gòu)，比如我們定義一個(gè)obj，obj.name通過(guò)散列，他在內(nèi)存中的位置可能是上圖中的90，那我們想要操作obj.name的時(shí)候，底層就會(huì)自動(dòng)幫我們通過(guò)哈希算法定位到90的位置，也就是說(shuō)直接從數(shù)組的12項(xiàng)開(kāi)始查找鏈表，而不是從0開(kāi)始遍歷整個(gè)內(nèi)存塊。

js中定義一個(gè)對(duì)象obj{key: value}，key是被轉(zhuǎn)換成字符串然后經(jīng)過(guò)哈希處理得到一個(gè)內(nèi)存地址，然后將值放入其中。這就可以理解為什么我們可以隨意增刪屬性，也能理解為什么在js中還能為數(shù)組賦屬性，而且數(shù)組也沒(méi)有所謂的越界了。

在數(shù)據(jù)量較大的場(chǎng)合，哈希表具有非常明顯的優(yōu)勢(shì)，因?yàn)樗ㄟ^(guò)哈希算法減少了很多不必要的計(jì)算。所謂性能優(yōu)化，其實(shí)就是讓計(jì)算機(jī)少運(yùn)算；最大的優(yōu)化，就是不計(jì)算！

算法的優(yōu)化

現(xiàn)在理解算法底層實(shí)現(xiàn)，回過(guò)頭來(lái)就可以考慮對(duì)算法進(jìn)行優(yōu)化了。不過(guò)在優(yōu)化前還是要強(qiáng)調(diào)一句：不要盲目追求性能！比如本案例中，我們最多就是5000字的匹配，那現(xiàn)有算法足矣，所有優(yōu)化都是不必要的。之所以還來(lái)說(shuō)說(shuō)優(yōu)化，就是為了提高自己對(duì)算法對(duì)程序的理解，而不是真的要去做那1ms的優(yōu)化。

我們發(fā)現(xiàn)我們的關(guān)鍵詞都沒(méi)有一個(gè)字的，那我們按照一個(gè)字的單位進(jìn)行關(guān)鍵詞遍歷顯然就是一個(gè)浪費(fèi)了。這里的優(yōu)化就是預(yù)先統(tǒng)計(jì)關(guān)鍵詞的最大最小長(zhǎng)度，每次以最小長(zhǎng)度為單位進(jìn)行查找。比如說(shuō)我測(cè)試用例的關(guān)鍵詞是成語(yǔ)，最短都是4個(gè)字，那么我每次匹配都是4個(gè)字一起匹配，如果命中就繼續(xù)深入查找到最大長(zhǎng)度。也就是說(shuō)我們最開(kāi)始構(gòu)造樹(shù)的時(shí)候首先是以最小長(zhǎng)度構(gòu)建的，然后再逐字增加。

 簡(jiǎn)單計(jì)算一下，按照我們的測(cè)試用例，300個(gè)成語(yǔ)，我們匹配一個(gè)詞只需一次對(duì)比，而單字查詢的話我們需要對(duì)比4次，而每次對(duì)比我們都要訪問(wèn)我們的樹(shù)結(jié)構(gòu)，這就是可避免的性能消耗。更重要的是，這里的對(duì)比并不是字符串對(duì)比，這里我們的關(guān)鍵字都是作為key存在的，效果就是 和key in obj一樣的，都是對(duì)key進(jìn)行哈希變換然后訪問(wèn)相應(yīng)的地址！所以千萬(wàn)不要糾結(jié)對(duì)比一個(gè)字和對(duì)比4個(gè)字的差異，我們沒(méi)對(duì)比字符串！

 關(guān)于多關(guān)鍵詞的匹配就說(shuō)到這里了，優(yōu)化版代碼我就不貼了，因?yàn)橐话阋灿貌坏健?/p>

最新評(píng)論