问题标签 [hamming-distance]

我有两个包含 1 和 0 的等长字符串。每个字符串都是 128 位长，我想计算它们之间的汉明距离。我能做的最好的方法是什么？

例如 a='1000001' 和 b='1110001' --> dist=Hamming(a,b);

对于我正在研究的问题，找到两个序列之间的距离以确定它们的相似性，序列顺序非常重要。但是，我拥有的序列的长度并不完全相同，因此我用空点填充任何有缺陷的字符串，以便两个序列的长度相同，以满足汉明距离要求。我这样做有什么大问题吗，因为我只关心换位的数量（而不是像 Levenshtein 那样的插入或删除）？

我发现汉明距离比 Levenshtein 快得多，作为更长长度序列的距离度量。什么时候应该使用 Levenshtein 距离（或 Levenshtein 距离的衍生物）而不是便宜得多的汉明距离？汉明距离可以被认为是两个序列之间可能的 Levenshtein 距离的上限，所以如果我比较两个序列的顺序偏差相似性度量，而不是匹配序列的绝对最小移动次数，则没有明显的我选择 Levenshtein 而不是 Hamming 作为指标的原因，有吗？

我的数据库中有一个表，我将 SHA256 哈希存储在 BINARY(32) 列中。我正在寻找一种方法来计算列中的条目到提供的值的汉明距离，例如：

（如果您想知道，字符串 A 和 B 的汉明距离定义为BIT_COUNT(A^B)，其中 ^ 是按位异或运算符，BIT_COUNT 返回二进制字符串中 1 的数量）。

现在，我知道 ^ 运算符和 BIT_COUNT 函数都只适用于 INTEGER，所以我想说可能唯一的方法是将二进制字符串分解为子字符串，将每个二进制子字符串转换为整数，计算汉明距离子串，然后添加它们。这样做的问题是它听起来非常复杂，效率不高，而且绝对不优雅。因此，我的问题是：您能提出更好的方法吗？（请注意，我在共享主机上，因此无法修改数据库服务器或加载库）

编辑（1）：显然在 PHP 中加载整个表并在那里进行计算是可能的，但我宁愿避免它，因为这个表可能会变得非常大。

编辑（2）：数据库服务器是 MySQL 5.1

编辑（3）：我下面的答案包含我刚才描述的代码。

编辑（4）：我刚刚发现使用 4 个 BIGINT 来存储哈希而不是 BINARY（32）会产生巨大的速度提升（快 100 倍以上）。请参阅下面对我的答案的评论。

我有 N < 2^n 随机生成的 n 位数字存储在一个文件中，其查找成本很高。给定一个数字 Y，我必须在文件中搜索一个最多为 k hamming dist 的数字。来自 Y。现在这需要 C(n 1) + C(n 2) + C(n 3)...+C(n,k) 最坏情况查找，这在我的情况下是不可行的。我尝试在内存中的每个位位置存储 1 和 0 的分布，并优先考虑我的查找。因此，我存储了位 i 为 0/1 的概率：

但这并没有太大帮助，因为 N 太大并且在每个位位置几乎相等的 1/0 分布。有没有办法可以更有效地完成这件事。现在，您可以假设 n=32，N = 2^24。

作为我硕士论文的一部分，我得到了一个带有 2 个有效位（第 2 位和第 4 位）的数字（例如 5 位）。这意味着例如x1x0x，其中$x \in {0,1}$(x 可以是 0 或 1) 并且1,0是具有固定值的位。

我的第一个任务是计算上述给定数字的所有组合2^3 = 8。这称为S_1组。

然后我需要计算 'S_2' 组，这是两个数字的所有组合x0x0x和x1x1x（这意味着有效位中有一个不匹配），这应该给我们$\bin{2}{1} * 2^3 = 2 * 2^3 = 16。

编辑 每个数字x1x1x和与原始数字x0x0x不同，在一个有效位上。x1x0x

最后一组，S_3当然是两个有效位的不匹配，这意味着，所有通过形式的数字x0x1x，8 种可能性。

计算可以递归地或独立地计算，这不是问题。

如果有人可以为这些计算提供一个起点，我会很高兴，因为我所拥有的并不是那么有效。

编辑 也许我错误地选择了我的话，使用了显着位。我的意思是，一个五位数字中的特定位置是固定的。我定义为特定位的那些地方。

编辑 我已经看到了 2 个答案，看来我应该更清楚。我更感兴趣的是找到数字，x0x0x这只是一个简单的例子。实际上，组（在此示例中）将由至少 12 位长的数字构成，并且可能包含 11 个有效位。然后我会有12组...x1x1xx0x1xS_1x1x0x

如果仍有不清楚的地方，请询问；）

问题：

给定一个大型（约 1 亿）无符号 32 位整数列表、一个无符号 32 位整数输入值和最大汉明距离，返回输入值的指定汉明距离内的所有列表成员。

保存列表的实际数据结构是开放的，性能要求决定了内存解决方案，构建数据结构的成本是次要的，查询数据结构的低成本是关键。

例子：

到目前为止我的想法：

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

如果汉明距离只有 1，我可以翻转原始输入中的每一位并重复上述 32 次。

如何有效地（不扫描整个列表）发现汉明距离 > 1 的列表成员。

在 ruby​​ 中，计算两个无符号整数之间的位差（例如汉明距离）的最有效方法是什么？

例如，我有整数 a = 2323409845 和 b = 178264714​​4。

它们的二进制表示是：

a & b 之间的位差是 17..

我可以对它们进行逻辑异或，但这会给我一个不同的整数！= 17，然后我必须遍历结果的二进制表示并计算 1 的数量。

计算位差的最有效方法是什么？

现在，计算许多整数序列的位差的答案会改变吗？例如，给定 2 个无符号整数序列：

计算两个序列之间的位差的最有效方法是什么？

您会遍历序列，还是有更快的方法来一次计算整个序列的差异？

此处定义的二进制字符串是固定大小的位“数组”。我称它们为字符串，因为它们没有顺序（将它们排序/索引为数字没有意义），每一位都独立于其他位。每个这样的字符串都有 N 位长，其中 N 为数百。

我需要存储这些字符串，并使用汉明距离作为距离度量，为最近的邻居提供一个新的二进制字符串查询。
基于度量的搜索（VP-trees、cover-trees、M-trees）有专门的数据结构（metric-trees），但我需要使用常规数据库（在我的例子中是 MongoDB）。

是否有一些索引功能可以应用于二进制字符串，可以帮助数据库在执行一对一的汉明距离匹配之前只访问记录的子集？或者，如何在标准数据库上实现这种基于汉明的搜索？

问题

假设您有 N (~100k-1m) 个整数/位串，每个 K（例如 256）位长。该算法应返回具有最低成对汉明距离的 k 对。

例子

对于 k=1，它应该返回对列表 {(i3,i4)}。对于 k=3，它应该返回 {(i1,i2), (i1,i4), (i3,i4)}。等等。

算法

朴素的实现计算所有成对的距离，对成对进行排序并返回距离最小的 k：O(N^2)。有没有更好的数据结构或算法？由于没有单个查询整数，因此无法使用有效地在大集合中找到具有低汉明距离的二进制字符串的想法。

这是一个家庭作业问题，我在理解它时遇到了一些困难。家庭作业问题是

我在一本书中读到，最初我必须将所有这些都视为集群，然后开始合并最接近的集群。将形成一个新的集群。现在，我必须通过计算这个新集群和其他集群之间的距离来找到最接近这个新形成的集群的集群，方法是平均两个集群中每个元素之间的距离，如问题中所述。

我的解决方案：我会找到所有对之间的汉明距离，并选择至少有一个是 C3 和 C5 的一对（汉明距离为 2）。现在可以将其合并到一个新的集群中。

我关心的是在这里合并到底是什么意思？我该怎么做？或者只是我将它们保持原样并将其命名为新集群？

以及如何找到新集群的每个元素与其他集群的平均距离？

还要计算平均值，给出的公式表示除以 |C1| 和 |C2|。那么，这是否意味着我必须在此处除以元素的数量（每组 8 乘以它合并到的集群？）

任何帮助是极大的赞赏。谢谢你。