寻求优于O(n³)的多词逐行频率统计文本搜索优化方案

我正在优化多词文本搜索功能，需要统计每行中目标关键词的出现频率。由于要基于同一数据多次执行多关键词搜索，我已经尽可能优化了现有实现，但仍希望找到比O(n³)更高效的解决方案。当前方案在408MB数据集、6个关键词的场景下，搜索耗时为410ms。

演示源码如下：

#include <iostream>
#include <fstream>
#include <cstring>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
#include <chrono>

using namespace std;

unsigned int addWord(std::map<std::string, unsigned int>& wordLookup, std::string word)
{
    std::transform(word.begin(), word.end(), word.begin(), ::tolower);

    auto it = wordLookup.find(word);
    unsigned int id;
    if (it == wordLookup.end())
    {
        id = wordLookup.size(); //assign consecutive numbers using size()
        wordLookup[word] = id;
    }
    else
    {
        id = it->second;
    }
    return id;
}

void tokenizeWords(std::map<std::string, unsigned int>& wordLookup, std::vector<unsigned int>& wordList, std::string& line)
{
    static const char newsDelimiters[] =  ".,!?\"()'\n\r\t<>/\\";
    char str[line.size()];
    strncpy(str, line.c_str(), line.size());

    // Getting the first token
    char *token = strtok(str, newsDelimiters);
    while (token != NULL)
    {
        //finding a word:
        unsigned int id = addWord(wordLookup, token);
        wordList.push_back(id);

        // Getting the next token
        // If there are no tokens left, NULL is returned
        token = strtok(NULL, newsDelimiters);
    }
}


int main()
{
    std::vector<std::vector<unsigned int>> textAsNumbers;
    std::map<std::string, unsigned int> wordLookup;
    std::vector<std::string> searchWords = {"this", "blog", "political", "debate", "climate", "iphone"};
    unsigned int searchLength = searchWords.size();
    unsigned int searchWordIds[searchLength];

    //convert searchWords
    unsigned int i = 0;
    for(const std::string& word : searchWords)
    {
        searchWordIds[i] = addWord(wordLookup, word);
        ++i;
    }


    //#### This part is not time critical ####
    //reading file and convert words to numbers
    fstream newsFile;
    newsFile.open("news.txt",ios::in);
    if (newsFile.is_open())
    {
        string line;
        while(getline(newsFile, line))
        {
            textAsNumbers.push_back(std::vector<unsigned int>());
            std::vector<unsigned int>& wordList = *textAsNumbers.rbegin();
            tokenizeWords(wordLookup, wordList, line);
        }
        newsFile.close();
    }

    //#### This part should be fast ####
    auto start = std::chrono::system_clock::now();
    std::vector<unsigned int> counts; //end result
    counts.reserve(textAsNumbers.size());
    for(std::vector<unsigned int>& line : textAsNumbers)
    {
        unsigned int count = 0;
        for(unsigned int word : line)
        {
            for(unsigned int s = 0; s < searchLength; ++s)
            {
                unsigned int searchWord = searchWordIds[s];
                if(word == searchWord)
                {
                    ++count;
                }
            }
        }
        counts.push_back(count);
    }
    auto end = std::chrono::system_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    cout << elapsed.count() << "ms" << endl;

    //#### Print for checking result, time insensitive :)
    int n = 0;
    for(unsigned int count : counts)
    {
        cout << "Count[" << n << "]: " << count << endl;
        ++n;
        if(n > 100)
        {
            break;
        }
    }
}

我尝试了多种优化方案，性能数据如下：

相关结果已提交至代码仓库，可自行查看。

使用哈希表加速搜索确实能缩短耗时，但仍涉及字符串操作，速度受限。A M提出的有序编码词方案因避免了字符串操作，性能最优。我也曾尝试结合哈希表与编码词方案，但性能仍不及A M的方案。感谢各位的建议！

内容的提问来源于stack exchange，提问作者kcid42