algorithm - 查询给定子集是否存在于集合集合中的数据结构

Question

我正在尝试为文字游戏求解器构建数据结构。

我需要存储大约 150,000 组 {A, A, D, E, I, L, P, T, V, Y} 的形式。 (它们是规范化的英语单词，即排序的字符。注意这是一个多重集，可以包含相同的字母两次。)

需要高效地获得对以下类型查询的是/否答案:是否有任何集合包含给定的子集？例如，是否有任何已知单词包含集合 {D, E, I, L, L, P}？

要求:

• 查询必须很快
• 数据结构应适合合理的空间量(例如 <50 MB)
• 数据结构不需要实时构建；它是预先计算好的。

是否有任何数据结构可以很好地满足这种需求？这与 other 有点不同set matching StackOverflow 上的问题在于目标集实际上是多重集。

Answer 1

这让我想起了我曾经做过的一个变异的前缀树/trie。略有不同，但它可能会起作用。如果您的边界很大/没有边界，或者如果您无法将其转换为您的语言(我使用 C++ 编写代码)，它可能无法工作。

所以基本上，在 trie 中，您通常会存储与下一个字母对应的子项，但我所做的是存储与每个字母的频率对应的子项。

问题基本上(从我的角度来看)是，“是否有任何集合具有与子集中相同或更多的字母？”例如，如果子集是 { A,D,E,E } 那么您需要查找是否存在至少包含一个 A、一个 D 和两个 E 的集合。

所以，对于 trie，你有这样的东西

            Root
           / | \
          / /|\ \
         / / | \ \
        1 2  ... MAX <-- This represents the frequency of "A"
       /|\ ..... /|\
      1..MAX    1..MAX <-- Frequency of "B"
      ...............
      ...............
      ...............
     1 ... ... ... MAX <-- Frequency of "Y"
    /|\ .... .... / | \
   1..MAX ...... 1 .. MAX <-- Frequency of "Z"

基本上所有的 ... 都代表了很多需要很长时间才能显示的内容。/,|\代表父子关系，MAX代表一个字母出现的最大频率

那么你要做的是，你有一个结构(我用 c++ 编码)，比如:

struct NODE {
    NODE *child[MAX + 1]; // Pointers to other NODE's that represents
                          // the frequency of the next letter
};

创建节点时，需要将其所有子节点初始化为 NULL。您可以通过构造函数(在 C++ 中)或类似 makeNode() 的函数来执行此操作

NODE* makeNode() {
    NODE* n = new NODE;         // Create a NODE
    for(int i = 0;i <= MAX;i++) // For each child
        n->child[i] = NULL;     // Initialize to NULL
};

一开始，trie 树只是一个根

NODE* root = new NODE;

当你向 trie 添加一个集合时，你会得到每个字母的频率并遍历 trie。如果在某个特定节点，下一个字母对应的子节点为 NULL，则只需创建一个新节点即可。

当您搜索 trie 时，您会搜索每个节点的所有子节点，这些子节点对应于子集中或更大子集中字母的频率。例如，如果子集有 3 个 A，则您搜索所有 root->child[3]，然后是 root->child[4]，然后……然后是 root->child[MAX]。

它可能过于复杂和令人困惑，所以 1) 如果你认为我没有生气，那么请评论什么令人困惑，以及 2) 你可能/可能只想找到一个更简单的方法