提到關鍵字搜索首先聯想到的無非就是使用一些indexOfreplace之類的字符函數最多加上一些正則表達式而已實現起來雖然很簡單但是這 背後的效率問題可曾仔細考慮過？例如論壇中的關鍵字過濾一般情況下需過濾的關鍵字數量及檢測的文本長度都不大所以這一瞬間的過程沒有太多值得關注的地 方但若關鍵字數量不在是屈指可數而是有成千上萬 並且待檢測的文本也是一長篇大論結果可不再是那麼樂觀了大家都知道每多一個關鍵字就要增加一次全文的檢索最終花費的時間將遠遠超出可接受的范圍 內
既然考慮的是那種極端的關鍵字搜索通常的逐個遍歷搜索顯然是行不通的如今用的是JavaScript若不使用Hash表實在是太對不起這門語言了有著對表特天獨厚的支持不妨就拿出少量的空間來換取大量的時間吧
先看個例子比如有如下的關鍵字: foofoobarbar既然要用空間換時間因此搜索之前先將他們預處理前面提到了JS靈活又高效的表顯而易見使用樹的結構是最 有優勢的即使不明白也沒關系最終實現結構正如如下的代碼熟悉JSON同樣很親切
復制代碼 代碼如下:
var Root =
{
f:
{
o:
{
o:
{
: true
: true
}
}
}
b:
{
a:
{
r:
{
: true
: true
}
}
}
};
這一層層的結構正如一棵樹每個字符便是樹的一個分枝到了最後一個字符便是樹葉不再有新的節點
此時你應該明白了只要對文章的每個字沿著這棵樹往下搜就是了能到達樹葉的就說明當前字符就是關鍵字的一個中途尋找不到對應枝干的當然就不是關鍵字
例如foo順著Root結構向下訪問最終到達Root[f][o][o][]即完成了一次匹配之後跳過foo的長度繼續往後檢索
因此整篇文章只需一次檢索即可找出每個關鍵字的位置
由於JS的hash表性能非常高所以所謂的尋找枝干也就非常的快了因為JS的靈活性實現此效果的代碼同樣很簡短
事實上可以發現關鍵字的數量與搜索的時間並沒太多的關系那僅僅影響了樹的寬度而已只有文章的長度才是決定搜索的時間
來一次極限測試
關鍵字 成語全集(條)
內容誅仙全集txt (字)
用時ms
(Chrome / i的CPU)
萬字的文章匹配萬個關鍵字還不到秒的時間可見充分利用JavaScript的靈活性仍能發揮很大的潛力
From:http://tw.wingwit.com/Article/program/Java/Javascript/201311/25502.html
