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

  1 var keywords = {
  2   M: {
  3     i: {
  4       k: {
  5         e: {end: true}
  6       }
  7     },
  8     a: {
  9       r: {
 10         k: {end: true}
 11       }
 12     }
 13   }
 14 }

由上文可以看出這個數據就是一個樹結構,而根據關鍵詞組來創建樹結構還是比較耗時的,而關鍵詞卻又是我們早已給定的,所以可以在匹配前預先創建這樣的數據結構。代碼如下:

  1 function buildTree(keywords) {
  2   var tblCur = {},
  3     key, str_key, Length, j, i;
  4   var tblRoot = tblCur;
  5 
  6   for(j = keywords.length - 1; j >= 0; j -= 1) {
  7     str_key = keywords
[j]; 8 Length = str_key.length; 9 for(i = 0; i < Length; i += 1) { 10 key = str_key.charAt(i); 11 if(tblCur.hasOwnProperty(key)) { 12 tblCur = tblCur[key]; 13 } else { 14 tblCur = tblCur[key] = {}; 15 } 16 } 17 tblCur.end = true; //最后一個關鍵字 18 tblCur = tblRoot; 19 } 20 return tblRoot; 21 }

這段代碼中用了一個連等語句:tblCur = tblCur[key] = {},這里要注意的是語句的執行順序,由于[]的運算級比=高,所以首先是在 tblCur對象中先創建一個key屬性。結合tblRoot = tblCur = {} 看,執行順序就是:

  1 var tblRoot = tblCur = {};
  2 tblRoot = tblCur;
  3 tblCur['key'] = undefined;  // now tblRoot = {key: undefined}
  4 tblCur['key'] = {};
  5 tblCur = tblCur['key'];
通過上面的代碼就構建了好了所需的查詢數據,下面看看查詢接口的寫法。

對于目標字符串的每一字,我們都從這個keywords頂部開始匹配。首先是 keywords[a] ,若存在,則看 keyword[a][b],若最后 keyword[a][b]…[x]=true 則說明匹配成功,若 keyword[a][b]…[x]=undefined,則從下一個位置重新開始匹配 keywords[a] 。

  1 function search(content) {
  2   var tblCur,
  3     p_star = 0,
  4     n = content.length,
  5     p_end,
  6     match, //是否找到匹配
  7     match_key,
  8     match_str,
  9     arrMatch = [], //存儲結果
 10     arrLength = 0; //arrMatch的長度索引
 11 
 12   while(p_star < n) {
 13     tblCur = tblRoot; //回溯至根部
 14     p_end = p_star;
 15     match_str = "";
 16     match = false;
 17     do {
 18       match_key = content.charAt(p_end);
 19       if(!(tblCur = tblCur[match_key])) { //本次匹配結束
 20         p_star += 1;
 21         break;
 22       } else {
 23         match_str += match_key;
 24       }
 25       p_end += 1;
 26       if(tblCur.end) //是否匹配到尾部
 27       {
 28         match = true;
 29       }
 30     } while (true);
 31 
 32     if(match) { //最大匹配
 33       arrMatch[arrLength] = { 
 34         key: match_str,
 35         begin: p_star - 1,
 36         end: p_end
 37       };
 38       arrLength += 1;
 39       p_star = p_end;
 40     }
 41   }
 42   return arrMatch;
 43 }
 44

以上就是整個關鍵詞匹配系統的核心。這里很好的用到了js的語言特性,效率非常高。我用一篇50萬字的《搜神記》來做測試,從中查找給定的300個成語,匹配的效果是1秒左右。重要的是,由于目標文本是一次遍歷的,所以目標文本的長短對查詢時間的影響幾乎不計。對查詢時間影響較大的是關鍵詞的數量,目標文本的每個字都遍歷一遍關鍵詞,所以對查詢有一定影響。

簡單分析

看到上文估計你也納悶,對每個字都遍歷一遍所有關鍵詞,就算有些關鍵詞有部分相同,但是完全遍歷也是挺耗時的呀。但js中對象的屬性是使用哈希表來進行構建的,這種結構的數據跟單純的數組遍歷是有很大不同的,效率要比基于順序的數組遍歷高得多??赡苡行┩瑢W對數據結構不太熟悉,這里我簡單說一下哈希表的相關內容。

 

首先看看數據的存儲。

數據在內存的存儲由兩部分組成,一部分是值,另一部分是地址。把內存想象成一本新華字典,那字的解釋就是值,而目錄就是地址。字典里面是按拼音排序的,比如相同發音的“ni”就排在同一塊,也就是說數組整齊排列在一塊內存區域里面,這樣的結構就是數組,你可以指定“ni” 1號,10號來訪問。結構圖如下:
array01

數組的優勢是遍歷簡單,通過下標就能直接訪問相應的數據了。但是它要增刪某一項就非常困難。比如你要把第6項刪掉,那第5項之后的數據都要向前移一個位置。如果你要刪除第一位,整個數組都要移動,消耗非常大。

array02

 

為了解決數組增刪的問題,鏈表就出現了。如果我們將值分成兩部分,一部分用來儲存原來的值,另一部分用來儲存一個地址,這個地址指向另外一個同樣的結構,以此類推就構成了一個鏈表。結構如下:

link01

從上圖可以明顯看出,對鏈表進行增刪非常簡單,只要把目標項和前一項的next改寫就完成了。但是要查詢某個項的值就非常困難了,你必須依次遍歷才可以訪問到目標位置。

link02

 

為了整合這兩種結構的優勢,聰明如你一定想到了下面這種結構。

hash

 

這種數據結構就是哈希表結構。數組里面存儲鏈表的頭地址,就可以形成一個二維數據表。至于數據如何分布,這個就是哈希算法,正規的翻譯應該是散列算法。算法雖然有很多種,原理上都是通過一個函數對key進行求解,再根據求解得到的結果安放數據。也就是說key和實際地址之間形成了一個映射,所以這個時候我們不再以數組下標或者單純的遍歷來訪問數組,而是以散列函數的反函數來定位數據。js中的對象就是一個哈希結構,比如我們定義一個obj,obj.name通過散列,他在內存中的位置可能是上圖中的90,那我們想要操作obj.name的時候,底層就會自動幫我們通過哈希算法定位到90的位置,也就是說直接從數組的12項開始查找鏈表,而不是從0開始遍歷整個內存塊。

js中定義一個對象obj{key: value},key是被轉換成字符串然后經過哈希處理得到一個內存地址,然后將值放入其中。這就可以理解為什么我們可以隨意增刪屬性,也能理解為什么在js中還能為數組賦屬性,而且數組也沒有所謂的越界了。

在數據量較大的場合,哈希表具有非常明顯的優勢,因為它通過哈希算法減少了很多不必要的計算。所謂性能優化,其實就是讓計算機少運算;最大的優化,就是不計算!

算法的優化

現在理解算法底層實現,回過頭來就可以考慮對算法進行優化了。不過在優化前還是要強調一句:不要盲目追求性能!比如本案例中,我們最多就是5000字的匹配,那現有算法足矣,所有優化都是不必要的。之所以還來說說優化,就是為了提高自己對算法對程序的理解,而不是真的要去做那1ms的優化。

我們發現我們的關鍵詞都沒有一個字的,那我們按照一個字的單位進行關鍵詞遍歷顯然就是一個浪費了。這里的優化就是預先統計關鍵詞的最大最小長度,每次以最小長度為單位進行查找。比如說我測試用例的關鍵詞是成語,最短都是4個字,那么我每次匹配都是4個字一起匹配,如果命中就繼續深入查找到最大長度。也就是說我們最開始構造樹的時候首先是以最小長度構建的,然后再逐字增加。

youhua01

 

簡單計算一下,按照我們的測試用例,300個成語,我們匹配一個詞只需一次對比,而單字查詢的話我們需要對比4次,而每次對比我們都要訪問我們的樹結構,這就是可避免的性能消耗。更重要的是,這里的對比并不是字符串對比,這里我們的關鍵字都是作為key存在的,效果就是 和key in obj一樣的,都是對key進行哈希變換然后訪問相應的地址!所以千萬不要糾結對比一個字和對比4個字的差異,我們沒對比字符串!

 

關于多關鍵詞的匹配就說到這里了,優化版代碼我就不貼了,因為一般也用不到。碼字不易,隨手點贊哈!

更多關于前端開發的信息,請關注WeX5微信公眾號!

894160860174831184

原創文章,轉載請注明出處!本文鏈接:http://www.1400584.live/openway_wordsmatch/