ハッシュ テーブルに基づくマップは、ここでは間違ったデータ構造です。
ビット文字列を trie に格納することで、すべての一致を効率的に検出できます。ここで、trie ノードには対応する文字列が含まれています。
リンクの例の試行とは異なり、ケースの各ノードには、0 および/または 1 というラベルの付いた 0、1、または 2 つの子があります。
あなたの場合のルックアップは、カスタマイズされた方法でトライをトラバースします。検索キーの 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;
}