8

我的数据由映射到值的键组成，如下所示：

---------------------
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 算法可以用来回答任何查询。但问题是这棵树随着密钥的每个新部分呈指数增长。

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

4

3 回答 3

6

数组。对真的！您将没有空间开销，没有“指针追逐”开销，计算索引只需要一点点数学，处理器真的很擅长。

假设你得到一个作为 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部分看起来很有趣，这是它的工作原理。

（|按位或）使所有非通配符为 1。这确保增量继续通过非通配符的位。添加之后，应该“固定”的位被破坏（如果进位通过它们，则为 0，否则为 1），因此必须将它们屏蔽掉（the & ~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 n -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 位宽，这是在这种情况下它们可以是最窄的）。它仅在通配符的位置具有那些“偏移量”。

偏移关键部分，以便它们的最高允许值映射到“全1”，确保进位通过它们传播。但是，这意味着它们通常处于无效状态（除非它接收到进位并变为零）。那么烦人的部分就来了：偏移量必须仅针对未回绕为零的关键部分撤消。

所以fix进来了。它计算一个不为零的关键部分的掩码。如果关键部分更宽，那就更烦人了，如果它们的关键部分大小不一样，那就太糟糕了。

然后最后一部分，key = temp - fix | bits撤消偏移并将非通配符放回。那个减法永远不会破坏任何东西，因为只有 1 仅从至少为 1 的 2 位组中减去，因此进位永远不会留下键-部分。

当然，这种索引方式确实会浪费一些空间，这与二次幂的情况不同，因为数组中存在永远无法索引的“洞”。

于 2013-09-01T08:50:43.870 回答
2

如果键的每个部分都存在一个最大值（ ）值，则可以通过将键解释为以基数（或混合基数）M编写的数字来创建单个键控树M

  • 我假设通配符只出现在一个索引中，并且所有进一步都是通配符，这种方式(x,*,*,*)将是一个查询(x*M^3,(x+1)*M^3-1)

对于字符串：

  • 您可以使用分隔符和标记粘贴键（使用|：

('ax','bc','a','x') -> 'ax|bc|a|x'

分隔符不应出现在输入字符串中（它可能会出现，但在这种情况下它可能会干扰访问询问的结果）

但是......如果你的情况是difficult你可以使用对象keys，在java中我会class为键创建一个，并在它们之间定义一个比较操作符

例如我会引用： 如何通过多个字段比较对象

于 2013-09-01T08:18:41.970 回答
1

将每个关系编码为一行文本，然后使用正则表达式 where '.' 可以匹配键中该位置的任何单个字符。

这将消除对不关心的位置的任何限制。

这是一些Python：

>>> import re
>>> 
>>> map = '''
... 0000 a
... 0001 b
... 0101 c
... 0110 d
... '''
>>> 
>>> def search(query='0001'):
...     matches = re.findall(query + r' .', map)
...     return [match.split()[-1] for match in matches]
... 
>>> search('0001')
['b']
>>> search('0...')
['a', 'b', 'c', 'd']
>>> search('01..')
['c', 'd']
>>>
于 2013-09-02T16:56:52.047 回答