快捷導(dǎo)航

JavaScript 上萬(wàn)關(guān)鍵字瞬間匹配實(shí)現(xiàn)代碼

更新時(shí)間：2013年07月07日 23:36:21 作者：

發(fā)一篇之前寫的文章，平時(shí)還是經(jīng)常用到的，尤其是河蟹詞特別多的聊天系統(tǒng)里

提到關(guān)鍵字搜索，首先聯(lián)想到的無(wú)非就是使用一些indexOf，replace之類的字符函數(shù)，最多加上一些正則表達(dá)式而已.實(shí)現(xiàn)起來(lái)雖然很簡(jiǎn)單，但是這背后的效率問題可曾仔細(xì)考慮過(guò)？例如論壇中的關(guān)鍵字過(guò)濾，一般情況下需過(guò)濾的關(guān)鍵字?jǐn)?shù)量及檢測(cè)的文本長(zhǎng)度都不大，所以這一瞬間的過(guò)程沒有太多值得關(guān)注的地方。但若關(guān)鍵字?jǐn)?shù)量不在是屈指可數(shù)，而是有成千上萬(wàn)，并且待檢測(cè)的文本也是一長(zhǎng)篇大論，結(jié)果可不再是那么樂觀了。大家都知道，每多一個(gè)關(guān)鍵字，就要增加一次全文的檢索，最終花費(fèi)的時(shí)間將遠(yuǎn)遠(yuǎn)超出可接受的范圍內(nèi)。
　　
　　既然考慮的是那種極端的關(guān)鍵字搜索，通常的逐個(gè)遍歷搜索顯然是行不通的。如今用的是JavaScript，若不使用Hash表實(shí)在是太對(duì)不起這門語(yǔ)言了。有著對(duì)表特天獨(dú)厚的支持，不妨就拿出少量的空間來(lái)?yè)Q取大量的時(shí)間吧。
　　
　　先看個(gè)例子，比如有如下的關(guān)鍵字: foo1，foo2，bar1，bar2，既然要用空間換時(shí)間，因此搜索之前先將他們預(yù)處理。前面提到了JS靈活又高效的表，顯而易見，使用樹的結(jié)構(gòu)是最有優(yōu)勢(shì)的。即使不明白，也沒關(guān)系，最終實(shí)現(xiàn)結(jié)構(gòu)正如如下的代碼，熟悉JSON同樣很親切：

復(fù)制代碼代碼如下:

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

這一層層的結(jié)構(gòu)正如一棵樹，每個(gè)字符便是樹的一個(gè)分枝，到了最后一個(gè)字符便是樹葉，不再有新的節(jié)點(diǎn)。
　　此時(shí)你應(yīng)該明白了，只要對(duì)文章的每個(gè)字沿著這棵樹往下搜就是了。能到達(dá)樹葉的，就說(shuō)明當(dāng)前字符就是關(guān)鍵字的一個(gè)；中途尋找不到對(duì)應(yīng)枝干的，當(dāng)然就不是關(guān)鍵字。

　　例如foo1，順著Root結(jié)構(gòu)向下訪問，最終到達(dá)Root['f']['o']['o']['1']，即完成了一次匹配。之后跳過(guò)foo1的長(zhǎng)度，繼續(xù)往后檢索。

　　因此，整篇文章只需一次檢索，即可找出每個(gè)關(guān)鍵字的位置。
　　由于JS的hash表性能非常高，所以所謂的尋找枝干也就非常的快了。因?yàn)镴S的靈活性，實(shí)現(xiàn)此效果的代碼同樣很簡(jiǎn)短。
　　
　　事實(shí)上可以發(fā)現(xiàn)，關(guān)鍵字的數(shù)量與搜索的時(shí)間并沒太多的關(guān)系，那僅僅影響了樹的寬度而已，只有文章的長(zhǎng)度才是決定搜索的時(shí)間。
　　
　　來(lái)一次極限測(cè)試：
　　關(guān)鍵字：成語(yǔ)全集(19830條)
　　內(nèi)容：誅仙全集.txt (1659219字)
　　用時(shí)：935ms
　　(Chrome26 / i3-2312的CPU)
160萬(wàn)字的文章，匹配2萬(wàn)個(gè)關(guān)鍵字，還不到1秒的時(shí)間?？梢姡浞掷肑avaScript的靈活性，仍能發(fā)揮很大的潛力。