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

我正在尝试为文字游戏解算器构建数据结构。用于查询给定子集是否存在于一组集合中的数据结构

我需要存储大约150,000集的形式的{A，A，d，E，I，L，P，T，V，Y}。（他们是标准化的英语单词，分类即字符注，这是一个多集其中包含相同字母两次。）

需要有效地得到一个是/否回答以下类型的查询：有什么设置给定的子集？例如，任何已知的单词是否包含集合{D，E，I，L，L，P}？

要求：

查询一定要快
的数据结构应该适合在空间合理数量（例如< 50 MB）
的数据结构不必是在实际建时间;它是预先计算的。

是否有任何数据结构，在那里会适合这种需要呢？这与有关StackOverflow的other set matching问题有点不同，因为目标集实际上是多个集合。

来源

2011-03-05 PBJ

听起来像是你需要查找anagram软件的例子。 – Orbling 2011-03-05 01:27:55

有趣的是你应该提到这一点;这是一种变形图;但是，我需要找到“近似anagrams”或部分anagrams。即我需要通过重新排列和添加给定池中的字母来找到字形。 – PBJ 2011-03-05 11:23:38

这让我想起了我做过一次的变异前缀树/ trie。稍有不同，但它可能工作。如果你有很大/没有界限，或者如果你不能把它转换成你的语言（我用C++编写），它可能无法工作。

因此，基本上，在特里，你通常存储对应于下一个字母的孩子，但我所做的就是对应于每个字母的频率，我存储的孩子。

什么问题，主要是（从我的角度来看）是，“是否存在有信的相同或更多的比任何子集？“例如，如果子集是{A，D，E，E}，那么你需要找到是否有至少有一个A，一个D和两个E的集合

因此，像这样

  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代表一个字母的最大频率

所以你做什么，你有一个类似的结构（I代码在C++中）：

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

当您创建节点时，您需要将其所有子节点初始化为NULL。您可以通过（在C++）构造函数或类似

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 
};

，在启动时makeNode（）函数做到这一点，线索仅仅是一个根

NODE* root = new NODE;

当您添加一组到特里，你得到每个字母的频率，并通过特里。如果在特定的节点上，与下一个字母对应的子项为NULL，则只需创建一个新的NODE。

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

它可能过于复杂和混乱，从而1）如果你觉得我是不是疯了，那么请在什么混乱发表评论，2）你可能/可能想随便找一个更简单的方法

来源

2011-03-05 01:46:57 quasiverse

我刚刚实现了这一点，它的构建速度非常快，而且体积空间效率很高（对于180k字大约6MB）。它也适用于许多查询。然而，不幸的是，有些退化的查询只需要遍历许多分支。也许最优化是按照最大数量顺序重新排列树的级别，从而最大限度地减少所需的回溯数量。 – PBJ 2011-03-05 11:21:54

你也许可以用一个线索，并插入各设置成线索，反复穿越线索使用你的目标的子集，以找出是否你有一个匹配的子集。至少我认为我会这样做。

的“线索”实际上被设想为一个检索的数据结构，是非常像一个正常的树，但有不同的排列节点，例如：

 A 
    /\ 
    AT AN 
    /| \ 
    | | AND 
    ANN ANY 
    | 
    ANNA

在上面的例子中，你可以看到这可能对你的情况有用，因为ANN和ANNA可以像一组一样检索。您可能需要使用一些置换代码，以及此类型的ADT（抽象数据类型）。

寻找更多here

来源

2011-03-05 01:32:17 atx

我认为是一个trie，但这种直接的方法并不真正有效。考虑一下，只有一个“单词”，“AANN”。然后，我们查找“ANN”，看看它是否在树中，而不是。我早些时候尝试过使用类似DAWG（定向非循环字图）之类的技术，为每个有效集添加多个路由，但大小非常巨大。主要困难在于，对于长度为m的子集，您有O（m！）种方式来实现 - 以不同顺序添加字符。 – PBJ 2011-03-05 04:17:50

这就是为什么我建议排列代码。 – atx 2011-03-05 07:14:48

看起来你可以尝试使用KD-Trees或变体。

要探索的相关主题是多维范围搜索/查询。警告：我没有用过这些，但我希望你能通过阅读关于上述主题的一些文献来找到有用的东西。

希望有所帮助。

来源

2011-03-05 01:42:01

如果我正确理解了这个建议，这个想法是把每个字母集合当作26个元素的向量。子集查询对应于正交范围查询。 – mhum 2011-03-05 02:11:39

做了一些搜索，它听起来像一个26-D范围树正是我所需要的，但它实现起来非常复杂！ – PBJ 2011-03-05 11:19:21

@大卫：我猜测那里必须有现成的解决方案。当然，我还没有尝试过自己寻找它们。 – 2011-03-05 14:19:19

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

回答

相关问题