类似于 Map<bitset,object> 的数据结构，可以检查位集的子集？

Question

我有一个很大的散列table（大到我无法检查每一行）（在 C++ 中使用 boost::unordered_map），其中键是 std::bitset，值是我有一些结构。

假设我在 table:

中有这个

00010101 -> {"Hello"}
00100100 -> {"Good Bye"}
01111101 -> {"Whatever"}

如果我将地图查询为 map[01111101]，我希望它为 return "Whatever"。很好，这就是地图的用途。但是，如果我查询 map[00110101] 我希望它成为 return "Hello"，因为“00010101”（Hello 的键）是我查询的“00110101”的子集。我用位表示集合，我认为这是不言自明的。

如果 table 中有多个条目，使得键是查询的一个子集，我想要它们。

我不知道是否有这样的事情。我正在查看二元决策图，但我从未使用过它们，我不确定它们是否可以解决问题。

谢谢。

编辑：设置表示。假设我有一组对象 A、B、C、D、E、F、G 我有两组 A、B、C 和 D、F。我将分别表示为 1110000 和 0001010。因此：1110000 不是 0001010 的子集（反之亦然），但 1000100 是 1010101 的子集。

Answer 1

好的，让我们用 map < int, string > 简化一下。现在我有了这个

map < int,string > myMap;
myMap[13] = "Hello"; //13 is 00010101
myMap[36] = "Good Bye";

给定一个 key，您希望打印所有子集。您所要做的就是遍历所有密钥并检查 key 是否是 map key 的子集。您可以使用 & 二元运算来实现这一点（我知道它可以在 bitset 上工作（是的，毕竟它们是二元运算））。看完这个简单的解释再来看看吧

say 13 in binary is 00010101

Now you have 00000001 which is subset of 00010101.

要称为子集，一个必须仅包含来自实际集合的 TRUE 位。换句话说，如果它在子集上是 TRUE 位，那么它在实际集合上也必须是 TRUE 位。（如果第三位在子集上是1，那么在实际集合上也一定是1）

你可以用&来检查，因为你操作&得到和key完全一样的值后，你就知道key是实际集合的子集了。

1 & 13 is 1 //00001 is subset of 10101

4 & 13 is 4 //00100 is subset of 10101

还有一些不是实际集合的子集或一半的子集怎么样？

2 & 13 is 0 //00010 is not subset of 10101

3 & 13 is 1 //00011 is not subset of 10101 because the second bit is not TRUE

看到了吗？ & 的结果必须与密钥相同。现在是节目时间

int main(){
    map < int , string > myMap;
    myMap[13] = "Hello"; //00010101
    myMap[36] = "Good Bye"; //00100100
    int key;
    cin >> key;
    for(auto it = myMap.cbegin(); it != myMap.cend(); ++it){
        if((key & (*it).first) == key){ //Check if subset
            cout << (*it).second << endl; //print if subset
        }
    }
    
    return 0;
}

到此为止，希望对您有所帮助。

阅读来源cbegin, bitset operator

Answer 2

基于散列的映射 table 在这里是错误的数据结构。

您可以通过 storing the bit strings in a trie 提高发现所有匹配项的效率，其中 trie 节点包含相应的字符串。

与 link 示例中的尝试不同，您案例中的每个节点将有 0、1 或 2 个标记为 0 and/or 1.

的子节点

现在，您案例中的查找移动以自定义方式遍历 trie。对于搜索键中的每个 1，您将搜索 trie 中对应的 0 和 1 link。对于每个 0，只搜索 0 分支。您找到的节点将只是您想要的节点。

搜索时间将与搜索的键值的总位串长度成正比，在最坏的情况下是树中的所有元素。

添加代码

这里有一个玩具 C 实现供参考。

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// Simple bit vectors of arbitrary length.
typedef struct {
  unsigned n_bits;
  unsigned *bits;
} BIT_VECTOR;

void init_bit_vector(BIT_VECTOR *v) {
  v->n_bits = 0;
  v->bits = NULL;
}

void setup_bit_vector(BIT_VECTOR *v, unsigned n_bits) {
  v->n_bits = n_bits;
  v->bits = calloc((n_bits + WORD_BIT - 1) / WORD_BIT, sizeof(unsigned));
}

void clear_bit_vector(BIT_VECTOR *v) {
  free(v->bits);
  v->n_bits = 0;
}

void set_bit_vector(BIT_VECTOR *v, unsigned *bits, unsigned n_bits) {
  unsigned n_words = (n_bits + WORD_BIT - 1) / WORD_BIT;
  for (int i = 0; i < n_words; i++) v->bits[i] = bits[i];
  v->n_bits = n_bits;
}

unsigned get_bit(BIT_VECTOR *v, int i) {
  unsigned mask = 1u << (i % WORD_BIT);
  return !!(v->bits[i / WORD_BIT] & mask);
}

// A trie map from bit vectors to strings.
typedef struct trie_s {
  struct trie_s *b[2];
  char *val;
} TRIE;

TRIE *make_trie(void) {
  TRIE *trie = malloc(sizeof *trie);
  trie->b[0] = trie->b[1] = NULL;
  trie->val = NULL;
  return trie;
}

// Add a key/value entry to the given trie map.
void put(TRIE *trie, BIT_VECTOR *key, char *val) {
  TRIE *p = trie;
  for (int i = 0; i < key->n_bits; ++i) {
    unsigned bit = get_bit(key, i);
    if (!p->b[bit]) p->b[bit] = make_trie();
    p = p->b[bit];
  }
  p->val = val;
}

// Recursive search that implements the subset membership check.
static void search(TRIE *trie, BIT_VECTOR *key, int i, char **buf, unsigned *n) {
  if (!trie) return;
  if (i == key->n_bits) {
    if (trie->val) buf[(*n)++] = trie->val;
    return;
  }
  unsigned bit = get_bit(key, i);
  // A standard trie search does this.
  search(trie->b[bit], key, i + 1, buf, n);
  // But here, add a search of the 0 branch if the key bit is 1.
  if (bit) search(trie->b[0], key, i + 1, buf, n);
}

// Get all entries with keys a subset of the search key.
unsigned get_all(TRIE *trie, BIT_VECTOR *key, char **buf) {
  int n = 0;
  search(trie, key, 0, buf, &n);
  return n;
}

typedef struct {
  unsigned bits;
  char *val;
} EXAMPLE_DATA;

int main(void) {
  TRIE *trie = make_trie();
  #define N (sizeof data / sizeof data[0])
  EXAMPLE_DATA data[] = {
    { 0b00010101, "Hello" },
    { 0b00100100, "Goodbye" },
    { 0b00101101, "Farewell" },
    { 0b01111101, "Whatever"},
  };
  BIT_VECTOR key[1];
  init_bit_vector(key);
  setup_bit_vector(key, 8);
  for (int i = 0; i < N; i++) {
    set_bit_vector(key, &data[i].bits, 8);
    put(trie, key, data[i].val);
  }
  unsigned search_val = 0b00110101;
  set_bit_vector(key, &search_val, 8);
  char *buf[N];
  unsigned n = get_all(trie, key, buf);
  printf("Found:\n");
  for (int i = 0; i < n; i++) 
    printf(" %s", buf[i]);
  printf(".\n");
  clear_bit_vector(key);
  return 0;
}

类似于 Map<bitset,object> 的数据结构，可以检查位集的子集？

Map<bitset,object>-like data structure that can check subsets of bitsets?

algorithm

subset

data-structures

binary-decision-diagram