DIV CSS 佈局教程網

用 JavaScript 實現上萬關鍵字的瞬間匹配
編輯:JavaScript綜合知識     

逐個比對的做法撐不住

談到關鍵字搜尋,多數人第一時間想到的就是 indexOf、replace,最多再補上正規表達式。實作起來確實簡單,但你有沒有算過背後的效能帳?

論壇的關鍵字過濾之所以感覺很快,是因為關鍵字屈指可數、待測文本也不長,那一瞬間的開銷不值得計較。可一旦關鍵字從幾十個暴增到成千上萬,檢測對象又是一篇長文,結論就完全不同了。每多一個關鍵字,就多一遍全文掃描,總耗時會遠遠超出可接受範圍。

用空間換時間:把關鍵字建成一棵樹

既然要處理的是極端場景,逐一遍歷顯然行不通。既然手上拿的是 JavaScript,不用 Hash 表實在太可惜——這門語言對「表」結構有著得天獨厚的支援,正好拿少量空間去換大量時間。

以 foo1、foo2、bar1、bar2 為例。預先處理後的結構長這樣,熟悉 JSON 的人會覺得很親切:

var Root = {
  f: { o: { o: { 1: true } } },
  b: { a: { r: { 1: true, 2: true } } }
};

這層層嵌套正如一棵樹:每個字元是一個分支,走到最後一個字元就成了樹葉,不再往下延伸。

匹配過程

於是只要拿文章裡的每個字沿著這棵樹往下走即可。能走到樹葉的,說明當前位置就是一個關鍵字;中途找不到對應分支的,自然不是。

例如 foo1,沿著 Root 一路拜訪到 Root['f']['o']['o']['1'],就完成了一次匹配,接著跳過 foo1 的長度繼續往後掃。整篇文章只需一次走訪,就能找出所有關鍵字的位置。由於 JS 的 Hash 表效能極高,所謂「找分支」也快得驚人。

值得注意的一點:關鍵字數量幾乎不影響搜尋時間,它只決定了樹有多寬;真正決定耗時的是文章長度。

極限測試

關鍵字:成語全集(19830 條)
內容:誅仙全集.txt(1659219 字)
耗時:935ms
環境:Chrome 26 / i3-2312 CPU

160 萬字的長文、近 2 萬個關鍵字,不到一秒完成。可見把 JavaScript 的靈活性用到位,還有相當可觀的潛力可挖。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved