时间戳

首页 > 解决方案 > 字符串/（字符串向量）匹配的快速算法

c++ - 字符串/（字符串向量）匹配的快速算法

问题描述

所以我有一个正好有 5 个字符串的向量 V1。

我有一组向量（称为过滤器）（每个都有 5 个字符串）。

我需要一个快速算法，以便我可以查看给定向量是否与集合中的任何向量匹配。

向量V1对集合中的一个向量（例如filter1）进行数学运算，如果

V1[i] = filter1[i] OR filter[i] = ""（空字符串）

例子：

过滤器：

过滤器1： “abc”“bcd”“bb”“”“”

过滤器2： “abc”“bcd”“bb”“ee”“ff”

过滤器3： “abc”“ddd”“bb”“j”“”

搜索向量：

V1：“abc”、“bcd”、“bb”、“ee”、“ff”

V1匹配过滤器中的两个向量：filter1和filter2。

所以我正在考虑将过滤器存储在 unordered_set 中。但我不知道如何制作散列函数，所以它可以找到一个匹配项（它会为不同的向量提供不同的散列值（即使它们可以匹配）。我的另一个想法是构造一个正则表达式。但再次搜索将是 O(n)。任何提示如何检查O(log(n))或O(1)的匹配（其中 n 是过滤器向量的大小）？

标签： c++algorithmdata-structureshashmapunordered-set

解决方案

目前还不完全清楚您想要的所有行为和约束是什么。例如，按照您列出的示例过滤器从左到右的顺序，过滤器是否可以包含“”（您的匹配所有“通配符”），然后是另一个非“”字符串？

无论如何，假设您不允许过滤器有一个""通配符后跟一个非""术语，您可以使用类型创建过滤器的索引...

std::unordered_map<std::string,
  std::variant<filter*,
    std::unordered_map<std::string,
      std::variant<filter*,
        std::unordered_map<std::string,
          std::variant<filter*,
            std::unordered_map<std::string,
              std::variant<filter*,
                std::unordered_map<std::string, filter*>
> > > > > > > > index;

这有效地描述了一个树，其中每个级别可能具有精确的字符串匹配或""通配符过滤器匹配，filter*如果匹配的过滤器是过滤器中的最后一个非""术语，则产生 a 或索引的下一个级别。

给定您的筛选候选对象v1，并假设您已经完成了填充索引的明显工作，您可以像这样进行搜索：

std::vector<filter*>
match(const std::array<string, 5>& v,
      const auto& index) {
    std::vector<filter*> matches;

    auto it0 = index.find("");
    if (it0 != index.end())
         matches.push_back(std::get<filter*>(*it0)); // match-everything filter
    if ((it0 = index.find(v[0])) == index.end())
        return matches; // no non-wildcard match

    const auto& i1 = std::get<1>(*it0); // next level in index
    auto it1 = i1.find("");
    ...same kind of logic, working your way through the 5 levels...

这涉及最多 10 个哈希表查找，因此 O(1) 与过滤器集的大小有关。

这并不一定意味着它对于任何给定数据来说都是性能方面的最佳选择：字符串的典型长度，其中的模式，例如可能以相同的字符开头并且仅在最后几个字符中有所不同，过滤器集的长度 - 了解这些知识可能会建议一种实际上更快的方法。

哈希表的工作情况还取决于所使用的哈希函数。对于较长的字符串，GCC 的字符串哈希函数 - MURMUR32 - 比 Visual C++ 的质量要高得多（为了提高速度，它只包含沿字符串间隔的 10 个字符），并且 GCC 使用质数桶计数，这比 Visual C++ 的功能更不容易发生冲突 - of-2 选择。对数据的了解可能会建议其他优化，例如，如果您知道字符串始终小于 8 个字符，您可以选择将它们放入填充的 uint64_t 并进行直接相等比较，并使用开放寻址/封闭哈希哈希表实现以减少 CPU 缓存未命中并提高速度。

推荐阅读