c++ - 如何从固定的候选列表中删除列表中的所有单词？

Question

我正在编写包含综合文本预处理的代码，包括停用词删除、词干提取、样板信息删除/替换(网址、电子邮件、数字、金额、标签等...)、构建倒排索引、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() );
}

有什么建议可以提高这段代码的性能吗？

Answer 1

您的算法是 n*m，多次搜索文档。相反，您应该遍历 doc 中的单词，检查每个单词是否是停用词，并且您的停用词应该在哈希表(而不是映射)中，这样您就可以进行 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());

不区分大小写检查，(您的原始样本没有考虑，所以我们也没有在这里)，这将比您之前的表现显着更好，假设您的单词有合理的哈希分布。