11

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

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

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

要求：

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

是否有任何数据结构可以很好地满足这种需求？这与 StackOverflow 上的其他 集合匹配问题略有不同，因为目标集合实际上是多集合。

4

3 回答 3

3

这让我想起了我曾经做过的一个变异的前缀树/树。略有不同，但它可能会起作用。如果您的界限很大/没有界限，或者您无法将其转换为您的语言（我用 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）你可能/可能只想找到一个更简单的方法

于 2011-03-05T01:46:57.527 回答
2

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

一个相关的探索主题是多维范围搜索/查询。

警告：我自己没有使用过这些，但我希望您可以通过阅读有关上述主题的一些文献找到有用的东西。

希望有帮助。

于 2011-03-05T01:42:01.323 回答
0

您可能可以使用 trie 并将每个集合插入到 trie 中，使用目标子集迭代遍历 trie 以确定是否有匹配的子集。至少我认为我会这样做。

'trie' 实际上是为 reTRIEvable 数据结构设计的，非常像普通树，但具有不同排列的节点，例如：

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

在上面的示例中，您可以看到这可能对您的情况有用，因为可以像集合一样检索 ANN 和 ANNA。您可能希望使用一些置换代码以及这种类型的 ADT（抽象数据类型）。

在这里找到更多

于 2011-03-05T01:32:17.230 回答