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

Question

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

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

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

要求:

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

有没有适合这种需求的数据结构？这与 StackOverflow上的其他 设置匹配问题略有不同,因为目标集实际上是多集的.

Answer 1

这让我想起了我曾经制作的一个变异的前缀树/特里树。略有不同，但可能有效。如果您有很大/没有界限或者无法将其转换为您的语言（我用 c++ 编码），它可能不起作用。

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

从我的角度来看，问题基本上是：“是否有任何集合具有与子集中相同或更多的字母？” 例如，如果子集是 { 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;

当您向特里树添加一组时，您会获得每个字母的频率并遍历特里树。如果在某个特定节点，下一个字母对应的子节点为 NULL，则只需创建一个新的 NODE。

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

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