data-structures - 用于搜索和插入位串的数据结构，其中只有 "1"是重要的

Question

很难用纯粹的语言来解释这个问题，所以这里有一个我需要解决的抽象问题的例子:

• 在此示例中，已将键为“1111”、“1010”、“1011”、“1000”、“0001”的条目插入到数据结构中
• 我使用查询“1001”进行搜索
• 查询应该返回数据结构中的所有条目，其中查询对条目键中的所有“1”都有匹配的“1”，但查询可能比比较的条目有更多的 1。对于此示例，应该返回键“1000”和“0001”，因为查询匹配这些键的 1。您可以说数据结构中的条目“不关心”查询中的其他位，具有“1000”键的条目只关心查询的第一位是 1，而只关心“0001”键关心他们的最后一位是 1。

一些辅助信息/约束:

• 这是针对实时应用程序的优化，分析表明欢迎在此领域进行改进。
• 条目的数量将是“小的”(很可能 <500)。这意味着我不一定在寻找最佳的“大 O”性能，而是在当代 PC 和移动 CPU 和内存上的实用性能。尽可能小的内存占用是一个巨大的好处，但我强烈怀疑这将与性能良好的解决方案齐头并进。
• 很少插入数据结构。大多数在应用程序启动时，因此不必针对它优化结构。但是搜索会很频繁。
• 我的具体问题中的条目(键/值对)的值将是指针数组。
• 数字中的位数是任意的，但结构和查询中的所有键都具有相同的长度。我只是提到这一点，以防存在依赖 CPU 硬件指令高效运行的算法，这可能只适用于 32 位/64 位类型。我的 key 会更长，但不会很大(~128-256 位)。
• 我想再次特别指出的是，这是针对比特串的，没有别的。
• 查询也可以没有结果。例如，在我的应用程序中，“0000”永远不会返回结果，因为没有要关心的“1”。
• 使用的编程语言是C++，编译器是“各种编译器”，因为它会在多个平台和操作系统上运行

我怎样才能有效地解决这个问题？另外，是否有实际的实现方式可供引用？

Answer 1

首先，我假设您已经优化了查询/键比较代码。您应该能够通过对键和查询的每个单词进行按位加比较来有效地做到这一点。如果您使用的是带有 SIMD 指令的架构，那么这些指令可以并行完成。

您还没有说明位的含义或您希望它们如何在键和查询之间分配。

如果您希望查询频繁重复，您可以做的一件非常简单的事情就是简单地使用线性搜索，并缓存 n 个最常用的查询。

如果键的大多数位不会出现在大多数键中，那么您可以对键中的位重新排序，使最不频繁出现的位具有最低的值索引(即位 0 具有最少数量的键设置该位后，位 1 次之，依此类推)。然后创建一个由位索引索引的数组，其条目包含包含该位的键列表。解析查询时，选择查询中最低的设置位(有一些技巧可以有效地做到这一点)，查找相应的匹配列表并线性搜索。只要 key 没有过于密集的位模式，这应该会提供显着的加速。