在大型集合中高效地查找汉明距离较小的二进制字符串

Question

问题：

给定一个包含大约100万个无符号32位整数的列表，一个无符号32位整数输入值和一个最大汉明距离，返回所有与输入值的汉明距离在指定范围内的列表成员。

数据结构用于保存列表的具体实现不限，性能要求为内存中的解决方案，构建数据结构的成本次要，查询数据结构的低成本至关重要。

示例：

For a maximum Hamming Distance of 1 (values typically will be quite small)

And input: 
00001000100000000000000001111101

The values:
01001000100000000000000001111101 
00001000100000000010000001111101 

should match because there is only 1 position in which the bits are different.

11001000100000000010000001111101

should not match because 3 bit positions are different.

我的思路：

对于汉明距离为0的极端情况，只需使用排序过的列表，并进行二分搜索以查找特定的输入值。

如果汉明距离仅可能为1，则可以翻转原始输入中的每个比特，并重复以上步骤32次。

如何高效地（不需要扫描整个列表）发现具有大于1的汉明距离的列表成员。

- Eric J.

---

如何通过期望的汉明距离来改变条件，可以使用递归函数来实现。下一步是获取这两个列表的并集？ - XecP277

这是关于该问题的最新论文：大规模汉明距离查询处理。 - hammar

@Eric，你说：“对于最大汉明距离为1（通常值会相当小）”。你能告诉我“相当小”是什么意思吗？ - Stefan Pochmann

@Eric 另外，这 ~1 亿个数字都是唯一的，还是有重复的？ - Stefan Pochmann

@StefanPochmann：没有重复项。最大的距离应该是4-5。 - Eric J.

Answer 1

问题：我们了解Hamming距离d(x, y)的哪些特点？

答案：

1. 它是非负的：d(x,y) ≥ 0
2. 仅在输入完全相同时才为零：d(x,y) = 0 ⇔ x = y
3. 它是对称的：d(x,y) = d(y,x)
4. 它遵守三角不等式，d(x,z) ≤ d(x,y) + d(y,z)

问题：我们为什么要关心它？

答案：因为这意味着Hamming距离是度量空间中的度量。有用于索引度量空间的算法。

• 度量树（维基百科）
• BK树（维基百科）
• M树（维基百科）
• VP树（维基百科）
• 覆盖树（维基百科）

您还可以查询关于“空间索引”的算法，掌握这个知识后可以应用于度量空间中，尽管该空间不是欧几里得空间。许多有关此主题的书籍涵盖了使用Hamming距离等度量进行字符串索引的算法。

注脚：如果您正在比较固定宽度字符串的Hamming距离，则可以通过使用汇编语言或处理器内置函数获得显着的性能提升。例如，在GCC（手册）中，您可以执行以下操作：

static inline int distance(unsigned x, unsigned y)
{
    return __builtin_popcount(x^y);
}

如果你告诉GCC编译针对支持SSE4a的计算机，那么我认为这只需要几个操作码。

编辑：根据许多来源，这有时/经常比通常的掩码/移位/加法代码慢。基准测试表明，在我的系统上，C版本比GCC的__builtin_popcount快大约160％。

附录：我对问题本身感到好奇，所以对三种实现进行了分析：线性搜索、BK树和VP树。请注意，VP树和BK树非常相似。 BK树中节点的子节点是包含每个距离树中心固定距离的点的“壳”树。 VP树中的节点有两个子节点，一个包含以节点中心为中心的球内所有点，另一个子节点包含所有点在外面。因此，您可以将VP节点视为具有两个非常厚的“壳”，而不是许多更细的BK节点。

结果是在我的3.2 GHz PC上捕获的，并且算法不尝试利用多个核（应该很容易）。 我选择了大小为100M的伪随机整数数据库。 结果是距离1..5的1000个查询的平均值，距离6..10和线性搜索的100个查询的平均值。

- 数据库：100M伪随机整数 - 测试次数：距离1..5的1000次，距离6..10和线性搜索100次 - 结果：平均查询命中率（非常近似） - 速度：每秒查询数量 - 覆盖范围：每个查询检查的平均数据库百分比

在您的评论中，您提到：

我认为通过生成具有不同根节点的一堆BK树并将它们分散开来可以改进BK树。

我认为这正是VP树比BK树表现略好的原因。 比“更浅”而不是“更深”，它会与更多点进行比较，而不是针对少量点使用细粒度比较。 我怀疑在更高维度的空间中差异更为极端。

最后一个提示：树中的叶节点应该只是整数的平面数组，用于线性扫描。对于小集合（可能是1000个或更少的点），这将更快且更节省内存。

- Dietrich Epp

---

好极了！我的声望达到了10k分；-) - Dietrich Epp

如果将整数看作位串，则固定大小的整数的汉明距离与L1范数相同。否则，两个字符串之间的“标准”L1范数是元素之间正距离的总和。 - Mokosha

@DietrichEpp 这是我在SO上找到的最棒的答案之一。我正要问建立索引需要多长时间，但是我看到你发布了代码。答案：在3.5Ghz i7-3770K上，1M项BK树建立时间为0.034秒，100M项BK树建立时间为13秒。VP树需要大约4倍的时间来构建，并使我的风扇开始大声旋转。 - Mark E. Haase

@StefanPochmann：你好像把“添加另一个答案”按钮和“添加评论”按钮搞混了。看一下页面底部，你会在那里找到“添加另一个答案”按钮。 - Dietrich Epp

@StefanPochmann：这不是真正的“改进”，而是完全不同的答案，与此处的答案毫无关系。将另一个解决方案与比较基准相结合需要相当大的时间。虽然可能很有趣，但至少需要几个小时，如果你那么感兴趣，为什么不自己做呢？至于你的答案被埋没——根据我的个人经验，如果你回答一个得到高票答案的问题，并在几年后发布更好的答案，新答案将被投票排名第一。 - Dietrich Epp

Answer 2

我写了一个解决方案，其中将输入数字表示为2³²位的位集(bitset)，因此可以以O(1)的时间复杂度检查某个数字是否在输入中。然后对于一个查询数和最大距离，我递归生成该距离内的所有数字，并将它们与bitset进行比较。

例如，对于最大距离5，共有242825个数字（sum_{d = 0 to 5} {32 choose d}）这比Dietrich Epp的VP-tree解决方案要快22%，例如它通过了100百万个数字的22%即2200万个数字。

我使用Dietrich的代码/解决方案作为基础来添加我的解决方案并与他的进行比较。以下是最大距离高达10时每秒查询次数的速度:

Dist     BK Tree     VP Tree         Bitset   Linear

   1   10,133.83   15,773.69   1,905,202.76   4.73
   2      677.78    1,006.95     218,624.08   4.70
   3      113.14      173.15      27,022.32   4.76
   4       34.06       54.13       4,239.28   4.75
   5       15.21       23.81         932.18   4.79
   6        8.96       13.23         236.09   4.78
   7        6.52        8.37          69.18   4.77
   8        5.11        6.15          23.76   4.68
   9        4.39        4.83           9.01   4.47
  10        3.69        3.94           2.82   4.13

Prepare     4.1s       21.0s          1.52s  0.13s
times (for building the data structure before the queries)

对于较短的距离，位集解决方案是四种方案中最快的。提问者Eric在下面评论说感兴趣的最大距离可能是4-5。自然地，我的位集解决方案对于更大的距离变得更慢，甚至比线性搜索还要慢（对于距离32，它需要遍历2³²个数字）。但对于距离为9，它仍然表现出色。

我还修改了Dietrich的测试方式。上述每个结果都是让算法至少解决三个查询，并尽可能多地处理约15秒内的所有查询的结果（我进行1、2、4、8、16等轮次的查询，直到总计经过至少10秒为止）。这相当稳定，我甚至在只有1秒时也获得了类似的数字。

我的CPU是i7-6700。我的代码（基于Dietrich的）在这里（暂时忽略那里的文档，不确定该怎么处理，但tree.c包含所有代码，而我的test.bat显示了我编译和运行的方法（我使用了Dietrich的Makefile中的标志）。我的解决方案的快捷方式。

一个注意事项：我的查询结果只包含数字一次，因此如果输入列表中包含重复数字，则可能是期望的也可能不是期望的。在提问者Eric的情况下，没有重复项（请参阅下面的评论）。无论如何，这个解决方案适用于要么输入中没有重复项的人，要么不希望或不需要查询结果中有重复项的人（我认为纯查询结果只是达到目的的手段，然后其他代码会将数字转换为其他东西，例如将数字映射到哈希值为该数字的文件列表）。

- Stefan Pochmann

---

最大的距离可能是4-5，所以这个解决方案非常有趣。在启发问题的实际域中没有重复项。 - Eric J.

Answer 3

一种常见的方法（至少对我而言）是将您的比特串分成几个块，并在这些块上查询完全匹配作为预过滤步骤。如果您使用文件，您将创建与块数相同的文件（例如这里的4个），每个块都排列在前面，然后对文件进行排序。您可以使用二进制搜索，甚至可以扩展您的搜索以获取匹配块的上下文奖励。

然后，您可以对返回结果执行按位海明距离计算，这应该只是您整个数据集的较小子集。这可以使用数据文件或SQL表完成。

因此，总结一下：假设您在DB或文件中有一堆32位字符串，并且您想要找到每个哈希值，这些哈希值与您的“查询”比特串的3位海明距离或更少相同。

1. 创建一个包含四列的表：每个列都将包含32位哈希的8位（作为字符串或整数）切片，分别为islice 1到4。如果使用文件，则创建四个文件，每个文件都是具有每行前面一个“islice”的切片排列。

2. 以与前面相同的方式在qslice 1到4中切分查询位字符串。

3. 查询此表，使得任何一个qslice1=islice1 or qslice2=islice2 or qslice3=islice3 or qslice4=islice4。这将给出与查询字符串相差不超过7位（8-1）的所有字符串。如果使用文件，请在四个排列文件中进行二进制搜索以获得相同的结果。

4. 对于每个返回的位字符串，使用您的查询位字符串计算精确的汉明距离对（从DB或排列文件中从四个切片重建索引侧位字符串）。

第四步的操作次数应该比对整个表进行完全的逐对汉明计算要少得多，并且在实践中非常高效。此外，可以很容易地使用并行性将文件分成更小的文件以获得更快的速度。

当然，在您的情况下，您正在寻找一种自我连接的方式，即所有在某些距离内的值。同样的方法在我看来仍然有效，尽管您将不得不从起始点扩展排列（使用文件或列表），这些排列共享起始块，并计算所得到的集群的汉明距离。

如果在内存中运行而不是在文件中，您的100M 32位字符串数据集将在4GB范围内。因此，四个排列列表可能需要约16GB+的RAM。虽然我使用内存映射文件获得了出色的结果，而且对于类似大小的数据集需要更少的RAM。

有开源实现可用。在这个领域最好的是我认为为Simhash by Moz制作的C++版本，但它设计用于64位字符串而不是32位。

这种有界的距离方法最早由Moses Charikar在其“simhash”经典论文和相应的Google专利中描述。

5. 在哈明空间中进行近似最近邻搜索

[...]

给定由d位组成的比特向量，我们选择 N = O(n 1/(1+ ) ) 个随机置换来对这些向量进行处理。对于每个随机置换σ，我们按照由σ排列的比特的字典序维护比特向量的排序顺序Oσ。对于查询比特向量q，我们通过以下步骤找到近似最近邻：

对于每个置换σ，我们在Oσ上执行二分查找以定位最接近q的两个比特向量（按照由σ排列的比特的字典序）。现在，我们在每个排序顺序Oσ中从上下文位置开始检查元素，以匹配q的最长前缀长度为顺序。

Monika Henziger在她的论文"Finding near-duplicate web pages: a large-scale evaluation of algorithms"中对此进行了详细阐述:

3.3 算法C的结果

我们将每个页面的位串划分为12个不重叠的4字节片段，创建20B片段，并计算所有具有至少一个公共片段的页面的C相似度。这种方法保证可以找到差异最多为11的所有页面对，即C相似度373，但可能会错过一些更大差异的页面对。

这也在Gurmeet Singh Manku、Arvind Jain和Anish Das Sarma的论文Detecting Near-Duplicates for Web Crawling中进行了解释。

3. 海明距离问题

定义：给定一个由 f 位指纹组成的集合和一个查询指纹 F，确定是否存在一种现有指纹与 F 最多在 k 位上不同。（在上述问题的批处理版本中，我们有一组查询指纹而不是单个查询指纹）

[...]

直觉：考虑一个排序的 2^d 个 f 位真随机指纹的表格。只关注表格中最重要的 d 位。这些 d 位数字的列表相当于“几乎是计数器”，因为 (a) 存在相当多的 2^d 位组合，且 (b) 很少有 d 位组合重复。另一方面，最不重要的 f-d 位是“几乎随机”的。

现在选择 d，使得 |d-d| 是一个小整数。由于表格已经排序，一个探针就足以识别所有在 d 个最重要的位位置上与 F 匹配的指纹。由于 |d-d| 很小，这样匹配的数量也应该很小。对于每个匹配的指纹，我们可以轻松地找出它是否与 F 在最多 k 个位位置上不同（这些差异自然限制在最不重要的 f-d 位位置上）。

上述过程帮助我们定位一个现有的指纹，它与 F 在 k 个位位置上不同，这些位置都限制在 F 的最不重要的 f-d 位之间。这解决了相当多的情况。为了涵盖所有情况，在下一节中正式概述了构建少量附加排序表的方法。

注意：我在相关的仅限数据库问题上发布了类似的答案。

- Philippe Ombredanne

Answer 4

您可以预先计算原始列表在指定汉明距离内的所有可能变化，并将其存储在布隆过滤器中。这样可以快速得出“NO”，但不一定能清楚地回答“YES”。

对于“YES”，请存储与布隆过滤器中每个位置相关联的所有原始值的列表，并逐个检查它们。优化布隆过滤器的大小以进行速度/内存平衡。

如果您有运行时RAM可用并愿意花费很长时间进行预计算，那么这似乎是一个不错的方法。

- Leopd

---

这不会很不可能吗？只有2%的条目存在。 - Neil G

Answer 5

将列表排序，然后在排序后的列表中对汉明距离内的不同可能值进行二分搜索，这个想法怎么样？

- borrible

---

对于汉明距离为1，这是合理的，因为原始输入有32个排列（将原始输入中的每个位翻转一次）。对于汉明距离为2，需要搜索更多的排列输入值。 - Eric J.

1024+32+1次搜索并不是非常多的二进制搜索。即使是32^3次搜索也不算太多。 - τεκ

@EricJ - 然而，有1亿条数据。鉴于发布者声明“构建数据结构的成本是次要的”，对于合理的海明距离来说仍然是合理的。 - borrible

请参阅 bit-string-nearest-neighbour-searching，该方法使用各种排序，然后进行二分查找。 - denis

Answer 6

一个解决这个问题的可能方法是使用不相交集合数据结构。其思想是将汉明距离小于等于k的列表成员合并到同一个集合中。以下是算法的概要：

- 对于每个列表成员，计算汉明距离小于等于k的所有可能值。对于k=1，有32个值（对于32位值）。对于k=2，有32 + 32*31/2个值。 - 对于每个计算出的值，测试它是否在原始输入中。您可以使用大小为2^32的数组或哈希映射来进行此检查。 - 如果该值在原始输入中，则执行“union”操作与列表成员一起。 - 记录执行的联合操作数的数量。

你开始算法时有N个不相交的集合（其中N是输入元素的数量）。每次执行联合操作时，不相交集合的数量减少1。当算法终止时，不相交集数据结构将把所有Hamming距离<= k的值分组到不相交集中。这种不相交集数据结构可以在几乎线性时间内计算出来。

- Marcio Fonseca

---

我不明白。如果您的输入集是{11000000，0110000，00110000，00011000，00001100，00000110，00000011}，并且k = 2，我认为您的算法将统一每个元素与其下一个邻居（它们的汉明距离为2），从而统一所有元素。但是11000000和00000011的汉明距离不是2，它们的汉明距离是4。使用不相交集合森林（并查集）的根本问题在于近似性不是等价关系。 - Jonas Kölker

好观点！但是你必须考虑到每个元素都是按顺序处理的，一旦找到匹配项，匹配的元素就会从列表中删除。因此，在你的例子中，在11000000和01100000之间进行联合操作后，后者将不可用于与00110000进行联合。你最终会得到5个集合，并且只需要将输入与每个集合的一个代表元素进行比较。 - Marcio Fonseca

我不明白你的建议。也许你可以为某个小值n编写代码？这里有一个测试: 如果你有四个列表成员x、y、z、w，每个成员与下一个成员的汉明距离为3，并且你的查询汉明距离为5，那么x和y是否属于同一等价类(即并查集树)?y和z呢?z和w呢?你如何使用等价类来决定输出什么?据我所知，如果你在任何地方使用并查集，你都是在使用它来去重你的输出，而我认为哈希集合也可以做到同样的效果。但我不确定我是否理解了？ - Jonas Kölker

Answer 7

这里有一个简单的想法：对100m个输入整数进行按字节排序，从最高有效字节开始，同时在某些外部结构中跟踪前三个级别的桶边界。

查询时，从一个距离预算d和您的输入单词w开始。对于顶层具有字节值b的每个桶，计算b与w的高字节之间的汉明距离d0。以d-d0的预算递归搜索该桶：也就是说，对于每个字节值b'，让d1成为b'和w的第二个字节之间的汉明距离。用d-d0-d1的预算递归搜索到第三层等等。

请注意，桶形成一棵树。当您的预算变为负数时，请停止搜索该子树。如果您递归进入叶子而没有超出您的距离预算，则该叶子值应该是输出的一部分。

这里有一种表示外部桶边界结构的方法：使用长度为16_777_216的数组（=(2**8)**3=2**24），其中索引i处的元素是包含范围在[256*i, 256*i+255]内的值的桶的起始索引。要找到该桶结束后的下一个索引，查找索引+1（或使用i+1=2**24的数组结尾）。

内存预算为100m *每个字4个字节=400 MB用于输入，以及2**24 *每个地址4个字节=64 MiB用于索引结构，总计接近半GB。索引结构对原始数据的开销为6.25%。当然，一旦构建了索引结构，您只需要存储每个输入单词的最低字节，因为其他三个字节隐含在索引结构中的索引中，总计约为（64 + 50）MB。

如果您的输入不均匀分布，可以使用（单个、普遍共享的）置换排列输入单词的位，使所有熵都集中在树的顶部。这样，修剪的第一层将消除搜索空间的更大部分。

我尝试了一些实验，这个算法的性能和线性搜索差不多，有时甚至更差。所以这个想法就此告终了。嗯，至少它很节省内存。

- Jonas Kölker

---

感谢分享这个替代方案。在我的环境中，“内存便宜”，但是一个内存高效的解决方案可能会使其他人受益。 - Eric J.