Как удалить все слова из списка из фиксированного списка кандидатов?
Я работаю над кодом, который включает в себя всеобъемлющую предварительную обработку текста, в том числе удаление стоп-слов, прохождение, удаление / замену стандартной информации (URL-адреса, электронные письма, номер, денежные суммы, теги и т. Д.), Создание инвертированного индекса, LCA и т. Д. Не совсем удивительно — удаление стоп-слов является узким местом, самой дорогой частью процедуры.
То, что у меня сейчас, довольно просто:
У меня есть около 500 стоп-терминов, хранящихся в статическом массиве static const std::wstring stopwords [],
Тогда для каждого документа (std::vector<wstring>):
for each ( auto term in stopwords)
{
doc.erase( std::remove( doc.begin(), doc.end(), term), doc.end() );
}
Любое предложение, как улучшить производительность этого кода?
Решение
Ваш алгоритм n * m, несколько раз отправляющий документ. Вместо этого вы должны перебирать слова в документе, проверяя, является ли каждое из них стоп-словом, и ваши стоп-слова должны быть в хеш-таблице (не на карте), чтобы вы могли выполнить проверку O (1), является ли данное слово стоп-словом. Это сократит ваше время до O (n), где n — размер документа.
Пример: C ++ 11 предоставляет контейнер неупорядоченных множеств, который вы можете использовать для своей хеш-таблицы.
std::unordered_set<std::wstring> stopwords; // keep your stop words in here.
Если у вас есть это, тривиальное решение становится:
doc.erase(std::remove_if(
doc.begin(),
doc.end(),
[](const std::wstring& s){ return stopwords.find(s) != stopwords.end(); }),
doc.end());
Проверка чувствительности к регистру не выдерживает (что не было учтено в вашем исходном образце, поэтому мы тоже здесь не участвовали), это выполнит существенно лучше, чем у вас раньше, при условии, что ваши слова имеют разумное распределение хешей.
Другие решения