Самый быстрый поиск по JavaScript

Question

Я пишу расширение Firefox. Я хотел бы найти на текущей веб-странице набор слов и посчитать, сколько раз каждое из них встречается. Это действие выполняется только по запросу пользователя, но все равно должно происходить достаточно быстро.

В настоящее время я использую indexOf для элемента innerHTML тега BODY, но считаю, что он слишком медленный для повторного запуска следующим образом:

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 в консоль ошибок. Duh! Тем не менее, были представлены некоторые более интересные альтернативы, которые я собираюсь использовать.

Answer 1

Я не смог найти hasItem, setItem или getItem в прототипах Hash, как предложил tvanfosson, но использовал set и get и написал hasItem на основе get. Но профилирование показало, что прототипы Hash медленнее по сравнению с нативным объектом javascripts.

Если у вас есть массив с ключевыми словами, преобразуйте его в хеш-объект с ключевыми словами в качестве ключа и значением 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 2

Я не уверен, что он самый быстрый, но следующее сработало довольно быстро для меня.

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);
}

Я определенно признаю, что с точки зрения Big (O) это не самое лучшее, потому что, когда i и j становятся большими, это все равно требует времени n в квадрате, но я обнаружил, что обработка регулярных выражений обычно довольно быстрая. 1004 *

По сути, я беру идею tvanfosson и расширяю ее, но вместо того, чтобы обходить DOM, я удаляю теги с помощью регулярного выражения (первая строка), а затем разделяю страницу на отдельные слова. Ключевое слово 'hash' определено в третьей строке с начальными значениями (очевидно, все они должны начинаться с нуля). Оттуда я создаю новое регулярное выражение, используя каждое ключевое слово как группу, поэтому при сопоставлении оно возвращает массив результатов, которые имеют (в моем примере) [fullMatch, keywordMatch, javascriptMatch, todayMatch]. Я использую декрементные циклы do while, потому что они были показаны во многих местах как самая быстрая структура циклов в JavaScript, и поскольку не имеет значения, в каком порядке обрабатываются слова, скорость цикла на самом деле является единственным соображением.

Надеюсь, это полезно, если не было, по крайней мере, забавным упражнением. :)

Answer 3

Я бы выделил все текстовые узлы в документе, перебрал их (разделив содержимое на пробелы) и увеличил счетчик для каждого встреченного слова. Используйте хэш ключевого слова / count, чтобы ускорить поиск ключевых слов для приращения.

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 4

Альтернативой обходу DOM вручную является использование textContent вместо innerHTML. Недостатком является то, что вы не можете отфильтровать скрипт или другие элементы, которые вы, возможно, не хотите искать.

В любом случае, я бы разбил текст на слова наподобие ответа @ tvanfosson, хотя вам может потребоваться разбить что-то, кроме пробела, в зависимости от того, как вы определяете слово.

Answer 5

node.nodeType также должен работать и, возможно, немного быстрее, поскольку он является целым числом Значение 3 для текстовых узлов.