最快的JavaScript頁面搜索

Question

我在寫一個Firefox擴展。我想在當前網頁搜索一組字詞，並計算每個字詞出現的次數。此活動僅在用戶提問時執行，但仍必須相當快地發生。

我目前使用的indexOf BODY標記的innerHTML元素，但我發現它太慢了以下方式重複運行：

function wordcount(doc, match) 
{ 
    var count = 0; 
    var pos = 0; 
    for(;;) 
    { 
    len=doc.indexOf(match, pos); 
    if(len == -1) 
    { 
     break; 
    } 
    pos = len + match.length; 
    count++; 
    } 
    return count; 
} 

var html = content.document.body.innerHTML.toLowerCase() 

for(var i=0; i<keywords.length; i++) 
{ 
    var kw = keywords[i]; 
    myDump(kw + ": " + wordcount(html, kw)); 
} 

有了100個關鍵字，這大約需要10〜20秒運行。有一些範圍可以減少關鍵字的數量，但它仍然需要運行得更快。

有沒有更明顯的方法來做到這一點？什麼是最有效的方法？我有一些想法，但我不願沒有表現的一些想法，我可以期待每個代碼了：

• 導航DOM，而不是使用 的innerHTML。這可能會更快或更慢， ？這將有 的好處，只有搜索文本 內容。
• 通過 單詞循環遍歷文檔單詞，同時累計每個單詞的出現次數 。 用這種方法，我不得不多做一些解析HTML的工作。

編輯：原來，最慢的部分是寫入錯誤控制檯的myDump函數。咄！儘管如此，還是提出了一些有趣的更有效的替代方案，我打算使用這些替代方案。

Answer 1

我不知道，如果它是最快的，但下面的工作很快我。

var words = document.body.innerHTML.replace(/<.*?>/g,'').split(/\s+/); 
var i = words.length; 
var keywordCounts = {'keyword': 0, 'javascript': 0, 'today': 0}; 
var keywords = []; 
var keywordMatcher = ''; 
var word; 
for (word in keywordCounts) { 
    keywords[keywords.length] = word ; 
    keywordMatcher = keywordMatcher + '(' + word + ')?'; 
} 
var regex = new RegExp(keywordMatcher); 
var j = keywords.length; 
var matched, keyword; 
if (i && j) { 
    do { 
     i = i - 1; 
     matched = words[i].match(regex); 
     if (!matched) continue; 
     j = keywords.length; 
     do { 
      j = j - 1; 
      if (matched[j + 1]) { 
       keyword = keywords[j]; 
       keywordCounts[keyword] = keywordCounts[keyword] + 1; 
      } 
     } while (j); 
    } while (i); 
} 

我一定會給予從一個大的（O）的看法，因爲作爲i和j得到它是不是最好的大它仍然需要n的平方的時間，但我已經找到了正則表達式的處理一般是相當快。

基本上我採取了tvanfosson的想法，並擴展它，而不是遍歷DOM我用正則表達式（第一行）去除標籤，然後將頁面分割成單獨的單詞。關鍵字'散列'在第三行上用初始計數定義（它們應該都明顯從零開始）。從那裏我一個新的正則表達式使用每個關鍵詞作爲所以當匹配它返回結果的一個陣列，其具有（在我的例子）[fullMatch，關鍵字匹配，javascriptMatch，todayMatch]的基團構成。我在循環中使用遞減操作，因爲它們已經在很多地方顯示爲JavaScript中最快的循環結構，並且因爲處理這些單詞的順序並不重要，循環速度實際上是唯一的考慮因素。

我希望這是有幫助的，如果不是這至少是一個有趣的練習。 :)

Answer 2

我會選擇文檔中的所有文本節點，遍歷它們（分割內容的空白），併爲遇到的每個單詞增加一個計數器。使用關鍵字/計數散列來加快關鍵字查找的增量。

var keywords = new Hash(); // from prototype or use your own 

function traverseNode(node) { 
    if (node.nodeName == '#text') { 
     indexNode(node); 
    } 
    else { 
     for (var i = 0, len node.ChildNodes.length; i < len; ++i) { 
      traverse(node.childNodes[i]); 
     } 
    } 
} 

function indexNode(node) { 
    var words = node.NodeValue.split(/\s/); 
    for (var i = 0, len = words.length; i < len; ++i) { 
     if (keywords.hasItem(words[i])) { 
      keywords.setItem(words[i], keywords.getItem(words[i]) + 1); 
     } 
     else { 
      keywords.setItem(words[i], 1); 
     } 
    } 
} 

traverseNode(document.body); 

Answer 3

手動遍歷DOM的替代方法是使用textContent代替innerHTML。缺點是你不能過濾掉你可能不想搜索的腳本或其他元素。

無論哪種方式，我會分裂成文本的話猶如@ tvanfosson的答案，雖然你可能需要取決於你如何定義一個字左右的東西拆除了剛纔空白。

Answer 4

我無法在原型中找到hasItem，setItem或getItem哈希像tvanfosson建議的那樣，但是使用了set並獲取並基於get寫了一個hasItem。但分析表明，與JavaScript本地對象相比，使用原型哈希的速度更慢。

如果你有一個關鍵字的數組，將其轉換爲以關鍵字爲核心和值0的哈希對象：

function prepareCount(words) { 
    var result = {}; 
    for (var i=0,len=words.length; i < len; i++) { 
     result[words[i]] = 0; 
    } 
    return result; 
} 

而是分割字符串，並通過它與for語句，你可以使用一個函數作爲參數來替換。在測試中，我做到了這一點，速度更快。在正則表達式中，我選擇匹配一切，但空白。您可能想要添加其他分隔符，如圓括號，逗號，點和短劃線等，或者如果您知道文本僅爲ASCII，則可以使用a-z代替。

function countKeywords(text,wordcount) { 
    text.replace(/[^\s]+/g,function(s) { 
    if (wordcount[s]!==undefined) { ++wordcount[s];} 
     return ""; 
    }); 
    return wordcount; 
} 

要使用它：

var wordcount = countKeywords(document.documentElement.textContent.toLowerCase(),prepareCount(["my","key","words"])); 

更新：

使用這個正則表達式來排除ASCII所有的分隔符，但下劃線（允許非ASCII字符）：

/[^\s\x00-\x2F\x3A-\x40\x5B-\x5E\x60\x7B-\x7F]+/g 

如果您知道您的關鍵字文字是ASCII只能使用： /[a-z] +

Answer 5

node.nodeType應該可以正常工作，因爲它是整數。值爲3的文本節點。