83

问题：

给定一个大型（约 1 亿）无符号 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 的列表成员。

4

7 回答 7

115

问题：我们对汉明距离 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)

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

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

通常，您还可以查找“空间索引”的算法，并知道您的空间不是欧几里得空间，而是度量空间。许多关于该主题的书籍都使用诸如汉明距离之类的度量来进行字符串索引。

脚注：如果您正在比较固定宽度字符串的汉明距离，则可以通过使用程序集或处理器内在函数来获得显着的性能改进。例如，使用 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 树 -- -- VP 树 -- -- 线性 --
分布结果 Speed Cov Speed Cov Speed Cov
1 0.90 3800 0.048% 4200 0.048%
2 11 300 0.68% 330 0.65%
3 130 56 3.8% 63 3.4%
4 970 18 12% 22 10%
5 5700 8.5 26% 10 22%
6 2.6e4 5.2 42% 6.0 37%
7 1.1e5 3.7 60% 4.1 54%
8 3.5e5 3.0 74% 3.2 70%
9 1.0e6 2.6 85% 2.7 82%
10 2.5e6 2.3 91% 2.4 90%
任何 2.2 100%

在您的评论中，您提到：

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

我认为这正是 VP 树的性能（略）优于 BK 树的原因。作为“更深”而不是“更浅”，它与更多点进行比较，而不是对更少点使用更细粒度的比较。我怀疑这种差异在更高维空间中更为极端。

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

于 2011-06-17T19:07:47.743 回答
14

我写了一个解决方案，我在一个 2 32位的位集中表示输入数字，所以我可以在 O(1) 中检查某个数字是否在输入中。然后对于查询的数字和最大距离，我递归地生成该距离内的所有数字，并根据位集检查它们。

例如，对于最大距离 5，这是 242825 个数字（sum d = 0 to 5 {32 choose d}）。作为比较，例如，Dietrich Epp 的 VP-tree 解决方案遍历了 1 亿个数字中的 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)

对于小距离，bitset 解决方案是迄今为止四个中最快的。问题作者 Eric 在下面评论说，最大的兴趣距离可能是 4-5。自然地，我的 bitset 解决方案对于更大的距离变得更慢，甚至比线性搜索更慢（对于距离 32，它将通过 2 32 个数字）。但是对于距离 9，它仍然很容易领先。

我还修改了 Dietrich 的测试。上述每个结果都是为了让算法在大约 15 秒内解决至少三个查询和尽可能多的查询（我对 1、2、4、8、16 等查询进行轮次，直到至少 10 秒共通过）。这相当稳定，我什至只用了 1 秒就得到了相似的数字。

我的 CPU 是 i7-6700。我的代码（基于迪特里希的）在这里（至少暂时忽略那里的文档，不知道该怎么做，但tree.c包含所有代码和我的test.bat显示我是如何编译和运行的（我使用了迪特里希的标志Makefile）） . 我的解决方案的捷径。

一个警告：我的查询结果只包含一次数字，因此如果输入列表包含重复的数字，则可能需要也可能不需要。在有问题的作者埃里克的案例中，没有重复（见下面的评论）。无论如何，此解决方案可能对输入中没有重复项或不希望或不需要查询结果中的重复项的人有好处（我认为纯查询结果很可能只是达到目的的一种手段，然后其他一些代码将数字转换为其他内容，例如将数字映射到哈希为该数字的文件列表的映射）。

于 2016-09-21T04:20:59.243 回答
4

一种常见的方法（至少对我来说是常见的）是将您的位串分成几个块，并在这些块上查询精确匹配作为预过滤步骤。如果您使用文件，您可以创建与块一样多的文件（例如，此处为 4 个），每个块在前面排列，然后对文件进行排序。您可以使用二分搜索，甚至可以在匹配块的上方和下方扩展搜索以获得奖励。

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

回顾一下：假设您在数据库或文件中有一堆 32 位字符串，并且您希望找到在 3 位汉明距离或更短的“查询”位字符串内的每个哈希：

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

  2. 在 qslice 1 到 4 中以相同的方式对查询位字符串进行切片。

  3. 查询此表，以便任何qslice1=islice1 or qslice2=islice2 or qslice3=islice3 or qslice4=islice4. 这将为您提供查询字符串 7 位 ( 8 - 1) 内的每个字符串。如果使用文件，请在四个排列的文件中的每一个中进行二进制搜索以获得相同的结果。

  4. 对于每个返回的位字符串，使用查询位字符串成对计算确切的汉明距离（从数据库或置换文件的四个切片中重建索引端位字符串）

步骤 4 中的操作数应该比整个表的完整成对汉明计算少得多，并且在实践中非常有效。此外，由于需要使用并行性来提高速度，因此很容易将文件分片为较小的文件。

当然，在您的情况下，您正在寻找一种自联接，即所有值都在彼此之间的一定距离内。恕我直言，相同的方法仍然有效，尽管您必须从一个起点向上和向下扩展以共享起始块的排列（使用文件或列表）并计算结果集群的汉明距离。

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

有可用的开源实现。该领域最好的是恕我直言，Moz 为 Simhash设计的 C++，但设计用于 64 位字符串而不是 32 位。

Moses Charikar在其“simhash”开创性论文和相应的谷歌专利中首次描述了这种有界的重叠距离方法：

  1. 汉明空间中的近似最近邻搜索

[...]

给定每个由 d 位组成的位向量，我们选择 N = O(n 1/(1+ ) ) 个位的随机排列。对于每个随机排列 σ，我们维护位向量的排序顺序 O σ，按照由 σ 排列的位的字典顺序。给定一个查询位向量 q，我们通过执行以下操作找到近似最近邻：

对于每个置换 σ，我们对 O σ 执行二分搜索以定位最接近 q 的两个位向量（按照由 σ 置换的位获得的字典顺序）。我们现在按照与 q 匹配的最长前缀的长度的顺序在每个排序顺序 O σ 中搜索由二分搜索返回的位置上方和下方的元素。

Monika Henziger在她的论文“寻找近乎重复的网页：算法的大规模评估”中对此进行了扩展：

3.3 算法 C 的结果

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

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

  1. 汉明距离问题

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

[...]

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

现在选择 d 使得 |d − d| 是一个小整数。由于该表已排序，因此单个探针足以识别在 d 个最高有效位位置中与 F 匹配的所有指纹。由于|d - d| 小，这样的比赛的数量预计也很少。对于每个匹配的指纹，我们可以很容易地确定它是否与 F 最多 k 位位置不同（这些差异自然会限制在 f - d 个最低有效位位置）。

上面描述的过程帮助我们在 k 位位置上找到与 F 不同的现有指纹，所有这些都被限制在 F 的最低有效 f - d 位之间。这处理了相当多的情况。为了涵盖所有情况，只需构建少量额外的排序表就足够了，如下一节中正式概述的那样。

注意：我对相关的仅限 DB 问题发布了类似的答案

于 2017-11-27T19:42:29.730 回答
2

您可以在指定的汉明距离内预先计算原始列表的所有可能变化，并将其存储在布隆过滤器中。这会给你一个快速的“不”，但不一定是关于“是”的明确答案。

如果是，则在布隆过滤器中存储与每个位置关联的所有原始值的列表，并一次遍历它们。优化布隆过滤器的大小以在速度/内存之间进行权衡。

不确定这一切是否完全正常，但如果您有运行时 RAM 需要刻录并且愿意在预计算上花费很长时间，这似乎是一个好方法。

于 2011-06-17T18:52:51.580 回答
1

如何对列表进行排序，然后在该排序列表中对汉明距离内的不同可能值进行二进制搜索？

于 2011-06-17T18:39:58.853 回答
1

解决此问题的一种可能方法是使用不相交集数据结构。这个想法是在同一集合中合并具有汉明距离 <= k 的列表成员。下面是算法的概要：

  • 对于每个列表成员，计算汉明距离 <= k 的每个可能值。对于 k=1，有 32 个值（对于 32 位值）。对于 k=2, 32 + 32*31/2 值。

    • 对于每个计算值，测试它是否在原始输入中。您可以使用大小为 2^32 的数组或哈希映射来执行此检查。

    • 如果该值在原始输入中，则对列表成员执行“联合”操作。

    • 将执行的联合操作的数量保存在一个变量中。

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

于 2015-04-06T15:25:33.833 回答
1

这是一个简单的想法：对 100m 输入整数进行逐字节基数排序，首先是最重要的字节，在某些外部结构中跟踪前三个级别的存储桶边界。

要查询，从距离预算d和您的输入单词开始w。对于顶层的每个带有字节值的桶，计算其与 的高字节之间b的汉明距离。以 为 的预算递归搜索该存储桶：也就是说，对于每个字节值，令为与 的第二个字节之间的汉明距离。递归搜索到预算为 的第三层，依此类推。d_0bwd - d_0b'd_1b'wd - d_0 - d_1

请注意，桶形成一棵树。每当您的预算变为负数时，请停止搜索该子树。如果您在不超出距离预算的情况下递归地下降到一片叶子，那么该叶子值应该是输出的一部分。

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

内存预算为 100m * 每个字 4 字节 = 400 MB 用于输入，2**24 * 4 字节每个地址 = 64 MiB 用于索引结构，或者总共不到半个 gig。索引结构是原始数据的 6.25% 开销。当然，一旦你构建了索引结构，你只需要存储每个输入字的最低字节，因为其他三个隐含在索引结构的索引中，总共 ~(64 + 50) MB。

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

我尝试了一些实验，结果和线性搜索差不多，有时甚至更糟。这么多这个奇特的想法。哦，好吧，至少它的内存效率很高。

于 2020-05-21T12:59:16.747 回答