Карта<bitset, object>-подобная структура данных, которая может проверять подмножества наборов битов?

Question

У меня есть большая огромная хеш-таблица (такая большая, что я не могу проверить каждую строку) (в C++ с использованием boost::unordered_map), где ключи - это std::bitset, а значения - это некоторая структура, которая у меня есть.

Скажем, у меня есть это в таблице:

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

Если я запросить карту как map[01111101] Я хочу, чтобы это вернуло "Что угодно". Это хорошо, для чего нужна карта. НО, если я сделаю запрос map[00110101] Я хочу, чтобы он возвратил "Hello", ПОТОМУ ЧТО "00010101" (ключ для Hello) является подмножеством "00110101" моего запроса. Я представляю наборы с битами, я думаю, это говорит само за себя.

Если в таблице имеется более одной записи, такой, что ключ является подмножеством запроса, я хочу их всех.

Я понятия не имею, есть ли что-нибудь подобное. Я смотрю на Диаграммы Двоичных Решений, но я никогда не использовал их, и я не уверен, что они добьются цели.

Благодарю.

---

Изменить: установить представления. Скажем, у меня есть группа объектов A,B,C,D,E,F,G У меня есть два набора A, B, C и D,F. Я бы представлял их как 1110000 и 0001010 соответственно. Следовательно: 1110000 не является подмножеством 0001010 (или наоборот), но 1000100 является подмножеством 1010101.

Answer 1

Карта, основанная на хеш-таблице, является неправильной структурой данных.

Вы можете получить некоторую эффективность в обнаружении всех совпадений, храня битовые строки в дереве, где узлы дерева содержат соответствующие строки.

В отличие от попыток в примерах ссылки, у каждого узла в вашем случае будет 0, 1 или 2 дочерних элемента, помеченных 0 и / или 1.

Теперь поиск в вашем случае перемещается по заданному пути. Для каждого 1 в поисковом ключе вы будете искать как соответствующую 0, так и 1 ссылку в дереве. Для каждого 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;
}

Answer 2

Хорошо, давайте упростили вещи с map < int, string >, Теперь у меня есть это

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

Учитывая keyВы хотите, чтобы все подмножество было напечатано. Все, что вам нужно сделать, это пройти через все ключи и проверить, если key является подмножеством map key, Вы можете достичь этого с & бинарная операция (которая, как я знаю, может работать с битрейтом (да, в конце концов, это бинарная операция)). Давайте посмотрим после этого простого объяснения.

скажем, 13 в двоичном коде 00010101

Теперь у вас есть 00000001, который является подмножеством 00010101.

Чтобы называться подмножеством, необходимо содержать только ИСТИНА бит из фактического набора. С другой стороны, если это бит ИСТИНА в подмножестве, то он должен быть бит ИСТИНА в фактическом наборе. (Если третий бит равен 1 в подмножестве, значит, он должен быть 1 в фактическом наборе)

Вы можете проверить это используя &потому что после работы & и получить точно такое же значение, как ключ, вы знаете, что ключ является подмножеством из фактического набора.

1 и 13 равен 1 //00001, это подмножество 10101

4 и 13 4 /00100 является подмножеством 10101

А как насчет чего-то, не являющегося половиной подмножества из фактического набора?

2 и 13 равно 0 //00010 не является подмножеством 10101

3 и 13 равен 1 //00011 не является подмножеством 10101, потому что второй бит не ИСТИНА

Увидеть? результат от & должен быть таким же, как ключ. Сейчас время для программы

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