string - 将算法的大 O 表示法从 O(n^2) 改进为更好的东西

Question

我正在寻求改进我目前拥有的算法，虽然它可以工作，但目前的复杂度为 O(n^2)。我希望尽可能降低这种复杂性，或者改进/更改算法本身以改进运行时间。

我有一个字符串列表，每个字符串都包含多个单词，最终目标是找到这些字符串之间的“匹配项”，并根据“相似度”百分比进行排序。

假设我有以下字符串:

《世界末日》
《旅程的开始》
《时间的尽头》
“我们今天离开这个世界的时间”

我的算法执行以下步骤:

• 遍历每个字符串，将每个字符串分解成它的组成词并按字母顺序重新排列这些词(在整个算法中不区分大小写)。(即“世界末日”变成“世界末日”。“我们今天离开这个世界的时间”变成“今天我们离开这个世界的时间”等)
• 出于商业原因，某些词从处理过的字符串中删除。这通常是代词和其他类似的词 - 即 a、等等，所以“世界末日”变成了“世界末日”。
• 我们现在有一个字符串列表，根据组成单词的字母顺序分解和重新组合，并删除了特定的非必要单词。
• 首先，我可以简单地查看列表中是否有完全相同的副本。这很简单，让我能够识别出 100% 有效匹配的字符串。
• 然而，现在是算法中最难和最慢的部分。我必须遍历字符串列表，将每个字符串与列表中的每个其他字符串进行比较(即嵌套循环)，以确定每个字符串在被比较的两个字符串中共有多少个单词。即当比较“End Of World”和“End Of Time”时，有 66.6% 的共性，因为这两个字符串在三个词中有两个是相同的。当比较“End Of World”和“Left This Time Today We World”时，我们发现两个字符串之间只有一个相同的词(因为每个字符串中的词数不同，这种情况下的实际百分比是根据两者之间的平均水平 - 所以大约有 22% 的共同性)。

最终，我得到了字符串对(起始列表中所有字符串的所有可能配对)和它们之间匹配的百分比值。然后我可以丢弃所有低于某个阈值的匹配项，只处理高于阈值的匹配项。阈值是用户定义的，整个算法用作“过滤”非常大的数据集的一种方式，让人类的眼球只关注那些最初看起来非常匹配的数据。

正如您可以从算法的嵌套循环(即 O(n^2))部分想象的那样，这是非常慢的，并且随着输入大小的增加会变得相当慢。

是否有任何方法可以改进该算法的 Big O，或者是否可以对生成相同输出的算法进行任何更改以提高运行时复杂度？

Answer 1

如果你在所有计算中都拉动字符串，就会有额外的复杂性，这使得最后一个操作不是 O(M^2) 而是 O(M^2 * sizeof(sentence) * AvgLength(word))

让我们看看(概念代码)

std::vector<std::set<int>> sSets;
sentenceSets.reserve(sentences.size());

for(auto& sentence : sentences) { // O(m)
  std::vector<const char *> words = SplitWord(sentence); // O(n) needs to go through all letters.
  sSet.emplace_back();
  for(auto& word: words) {
    int wordNo = LookUp(word); // table of all words, with entries of 0 for unwanted words. O(log AllWords)
    if (wordNo)
      sSet.back().insert(wordNo); // also removes duplicates. O(Log(#diff words in sentence))
  }
} 

总 O(m Log(AllWords) avgWordLen) 或 O(m collisionFactor avgWordLen) 如果您认为所有可能单词的哈希表工作完美。

LookUp 为所有以后的比较保存一个因子 O(单词中的字母)。

for(const auto& theSet : sSet) { // O(sSet.size()
  for(const auto& cmpSet : sSet) { // O(sSet.size()
    std::vector<int> intersect;
    std::set_intersection(theSet.begin(), theSet.end(),
                          cmpSet.begin(), cmpSet.end(),
                          std::back_insert<std::vector<int>>(intersect)); // O(set.size())
    StoreRes(theSet, cmpSet, intersect);
  }
}

这里总共是 O(sSet.size()^2*O(set.size())。可以优化为仅运行 O(sSet.size()*sSet.size()/2)，因为表是对称的。

使用 LookUp 在这里节省了一个因子 O(字长)。

std::set 可能会被一些 flat_set 取代，以实现更快的现实世界操作。