匹配包含"不关心"的二进制模式

Question

我有一组位模式,并希望找到集合中与给定输入匹配的元素的索引.位模式包含"不关心"位,即x-es,它匹配0和1.

示例 位模式集是

index abcd
   0  00x1
   1  01xx
   2  100x
   3  1010
   4  1x11

然后,尝试匹配0110应返回索引1和1011应返回索引4.

如何通过元素线性搜索更快地解决这个问题？我想可以制作一种二叉树,但是,创建这样一棵树的智能方法是什么？是否存在针对此类问题的其他有效数据结构/算法,主要是在查询效率和存储要求方面.

• 位模式将是64位(或更多)
• 集合中的元素数量将为10 ^ 5 - 10 ^ 7
• 并非所有比特组合都在集合中表示,例如在示例中未表示0000
• 数据集中将有大量的x-es
• 位串只匹配集合中的一个元素

我有两种不同的情况需要解决这个问题

• 案例1:我有可能进行大量的预计算
• 案例2:新元素将动态添加到集合中

更新 x-es更有可能出现在某些位位置,也就是说,某些位位置将由x-es支配,而其他位将主要为零/ 1.

Answer 1

我认为，模式容器的解决方案将是一个特定的有序树。

• 树的节点会说：
  • 它的位置是什么（node.position）
  • 这个位置 (0,1,x) 是什么位 (node.value)
• 只有叶节点可以将 x 作为值。
• 子级的位置应始终大于父级的位置 - 以排除重复的分支。
• 如果一个节点有很多子节点，它们的顺序如下：
  • 首先按位置
  • 两个具有相同位置的孩子中，第一个孩子的值为 0。
• 这种树的根节点是空的。
• 树的读法如下：
  • 从根开始，获取到叶子的路径，取 1 和 0 并将它们放在适当的位置。
  • 当我们到达 x 时，用 x-es 填充所有空闲位置。
  • 如果我们没有到达 x，则叶子的值为 1/0，并且模式被填充。如果没有填写，就会发生错误。

该节点中的匹配不应通过叶子完成，而应通过级别完成。一个级别将是一个父级的一组子级。

Take first level of the children as current level
Take the first child on the level for current
  read currentnode.position
  check the appropriate position in the matched string against child value. 
  If it fits, go higher up the tree.
  If it doesn't fit, go to next child.
  If we are out of children on the level, go down the tree.

这里模式添加和二进制字符串匹配的复杂度都是log(n)。如果有 a% 的 x'es，则时间大约会缩短 a%，这与@Qiang Jin 的解决方案相反。搜索多分支树比仅搜索三分支树更快。

我将该树实现为列表的层次结构。