部分多键映射的数据结构？

Question

我有数据由映射到值的键组成,如下所示:

---------------------
Key          | Value
---------------------
(0, 0, 0, 0) | a
(0, 0, 0, 1) | b
(0, 1, 0, 1) | c
(0, 1, 1, 0) | d
....

我正在寻找一种数据结构,可以通过密钥有效地执行搜索查询,其中查询可以是完整的或部分地指定密钥.例如:

(0, 0, 0, 1) -> a
(0, *, *, *) -> [a, b, c, d]
(0, 1, *, *) -> [c, d]

我现在的想法是使用常规树来实现它,类似于: 叶节点表示值,非叶节点是键的一部分(即,w,x,y和z节点分别是键的第一,第二,第三和第四部分).可以使用简单的BFS算法来回答任何查询.但问题是这棵树随着密钥的每个新部分呈指数级增长.

什么数据结构/算法更适合解决这个问题？请注意,关键部分可以是数字或字符串.

Answer 1

数组.对真的!你将没有空间开销,没有"指针追逐"开销,计算索引只需要一点点,处理器真的相当擅长.

假设你得到一个部分密钥作为a mask,bits其中mask0为通配符的位和1在其他位置,并且bits通配符为0,非通配符为0.

收集具有与该模式匹配的键的所有项的算法是:

int key = bits;
do {
    yield items[key];
    key = (key | mask) + 1 & ~mask | bits;
} while (key != bits);

那key = (key | mask) + 1 & ~mask | bits部分看起来很有趣,这是它的工作原理.

将|(按位OR)使所有的非通配符1.这可确保增量不断通过未通配符位携带.在添加之后,应该被"修复"的位被破坏(如果进位通过它们则为0,否则为1),因此必须将它们屏蔽掉(& ~mask),然后将其设置回正确的值(| bits).运算符的优先级使得它可以在没有括号的情况下编写.你也可以把它写成

key = (((key | mask) + 1) & (~mask)) | bits;

这适用于任何类型的模式.如果您只需要"最后x位是可变的",您可以优化一位:

int wildcards = 0;
int invmask = ~mask;
do {
    yield items[wildcards++ | bits];
} while (wildcards & invmask);

这只是从0到2 ^{个通配符运行},然后放入顶部的固定位.

非二进制密钥

在最简单的非二进制情况下,密钥的部分仍然是一些整数位,即它们的范围从0到2 ⁿ -1.在这种情况下,您可以使用完全相同的代码,但掩码的解释是不同的:对于通配符而言不是单个0位,对于非通配符而是单个1位,它将具有一些其他位数(对应于关键部分的位宽度).

对于非二次幂,需要更多的诡计.问题是必须尽快生成进位以便满足关键部分小于某个值的约束.

例如,如果所有关键部分都可以是0,1或2(但不是3),则可以执行(未测试):

int key = bits;
int increment = (0x55555555 & ~mask) + 1;
do {
    yield items[key];
    int temp = (key | mask) + increment & ~mask;
    int fix = (temp | (temp >> 1)) & 0x55555555;
    key = temp - fix | bits;
} while (key != bits);

额外的increment是1加上"最近2的幂与键部分的最大值之差"的掩码,在这种情况下每个键部分为1,所以每个"槽"中都有1个(槽是2位宽,在这种情况下它们可以是最窄的).它只有那些是通配符位置的"偏移量".

偏移关键部件,使其最高允许值映射到"全部",确保进位传播通过它们.但是,这意味着它们通常处于无效状态(除非它接收到进位并且变为零).然后是令人烦恼的部分:只有未封装为零的关键部分才能撤消偏移.

因此,它fix进来了.它计算了非零的关键部分的掩模.如果关键部件更宽,则会变得更加烦人,如果关键部件的尺寸不同,则会变得非常糟糕.

然后最后一部分,key = temp - fix | bits撤消偏移并将非通配符重新放入.该减法永远不会破坏任何东西,因为只从1位的组中减去1只至少1,所以进位永远不会留下密钥 -部分.

这种索引方式确实浪费了一些空间,不像两个幂的情况,因为数组中有"漏洞",你永远无法索引.