标签: hamming-distance

一个问题问:找到以下代码的汉明距离:

11111  
10101  
01010  
11100  
00011  
11001

答案是2.这是如何工作的？我觉得汉明距离只在两根琴弦之间？

是否有算法通过给定数量的可以变化的最大允许位置(最大不匹配,最大汉明距离)生成字符串(DNA序列)的所有可能的字符串组合？

字母表是{A,C,T,G}.

字符串示例AGCC和最大不匹配数2:

Hamming distance is 0
  {AGCC}
Hamming distance is 1
  {CGCC, TGCC, GGCC, AACC, ACCC, ATCC, AGAC, AGTC, ..., AGCG}
Hamming distance is 2
  {?}

一种可能的方法是生成一个包含给定String的所有排列的集合,迭代它们并删除具有更大汉明距离的所有字符串.

通过给定的20个字符的字符串和最大汉明距离5,这种方法非常耗费资源.

那还有另一个更有效的approcahes/implementation吗？

我的任务是计算两组中1D二进制数组之间的汉明距离 - 一组3000个数组和一组10000个数组,每个数组长100个项目(位).这就是在100位长的物体上进行3000x10000高清计算.所有这些都必须在最多十几分钟内完成

这是我提出的最好的

#X - 3000 by 100 bool np.array 
#Y - 10000 by 100 bool np.array
hd = []
i=1
for x in X:
    print("object nr " + str(i) + "/" + str(len(X)))
    arr = np.array([x] * len(Y)) 
    C = Y^arr # just xor this array by all the arrays in the other group simultainously
    hd.append([sum(c) for c in C]) #add up all the bits to get the hamming distance
    i+=1

return np.array(hd)

它还需要1-1.5小时才能完成.我该如何更快地完成这项工作？

我有一个过程,类似于生成感知哈希的tineye,这些是32位整数.

我打算将来存储在一个sql数据库(也许是一个nosql db)中

但是,我很难理解如何根据哈希的相似性检索记录.

有任何想法吗？

可能重复:
计算32位整数中设置位数的最佳算法？

我想编写一个程序来比较两个数字得到1位数.如果我比较任意两个数字之间的位,找到二进制数在1和0中的不同位置.换句话说,异或(XOR)关系.

比如22(有10110二进制)并将它与15(有01111二进制)进行比较

第一个10110

第二个01111

结果11001

答案是25,但我想要的是3,其中有3个1和0是不同的.

我想做一件相对简单的事情：

• 给定一个查询号码Q，查询距离d，以及一组数字S，确定是否不S包含任何与汉明距离数小于或等于d。

最简单的解决方案是制作S一个列表并对其进行迭代，计算距离。如果计算出的距离小于或等于 d，则退出 return TRUE。

但是考虑到我想要做的就是检查是否存在，比线性时间解决方案更快的东西应该是可能的。

我尝试过的一件事是M-tree. 参考有关 stackoverflow、维基百科文章 ( https://en.wikipedia.org/wiki/M-tree ) 和两个预先存在的实现的一些其他问题，我昨天花了几个小时来实现自定义解决方案。这个问题的一个好处是，通过两个数字的异或（使用 SSE 指令）计算 popcount 实际上比存储允许避免计算度量的数字更便宜，因此解决方案的几个方面可以简化和优化速度。

结果非常令人失望。事实证明，与最小汉明距离相比，我正在处理的公制半径很小。例如，在 12 位数字的空间中，最大汉明距离是 12。如果我要寻找的最小值是 4，那么就没有太多机会进行良好的非重叠分区。事实上，我只是尝试过，通过蛮力创建一组最小汉明距离为 4 的 12 位数字，然后（通过蛮力）找到最佳二叉树分区，以便搜索算法可以访问最少数量的节点。如果我想数查询的 d 内的集合元素的数量，我不能将节点访问次数减少到总数的 30% 以下，并且当我发现第一个访问了大约 4% 时停止。这意味着我或多或少做了一个线性时间解决方案，其中精心设计的树搜索算法的开销与不必检查尽可能多的集合成员所节省的开销大致相同。

但是我想做的很有限。我什至不想用 query distance 计算 set 成员的数量<= d，更不用说枚举它们了。我只是想检查是否存在。这让我想到了布隆过滤器和哈希之类的东西。

我还考虑过尝试构建一个图结构，其中集合成员通过带权重的边连接。使用汉明距离尊重三角不等式这一事实，在我看来，必须有某种方法来搜索此图，使得边遍历导致与查询的距离可能更小，但我什至不知道从哪里开始这里。

有没有人对这里的解决方案有任何其他建议，可以轻松击败简单迭代数组的性能？

编辑和动机：

最终这来自一个编码理论问题。对于给定的偶数d和字长N，我可以将多少个具有最小汉明距离 d 的代码放入一个 N 位数字中？这允许创建可以检测d/2位错误的代码，纠正多达d/2-1位的错误。我们知道像 LDPC 这样的香农极限码，但这是针对具有模糊最小汉明距离的长码，它们需要很长时间才能解码。还有像 OLSC …

我试图找出如何计算任意 CRC 多项式的错误检测能力。

我知道有各种错误检测功能可能（或可能不）适用于任意多项式：

1. 检测单个位错误：所有 CRC 都可以执行此操作，因为这仅需要 CRC 宽度 >= 1。

2. 突发错误检测：所有 CRC 都可以检测大小等于其宽度的突发错误。

3. 检测奇数位错误：CRC 与多项式的偶数项（这意味着完整二进制多项式中 1 位的偶数）可以做到这一点。

4. 检测随机位错误（取决于帧大小）：我有一个现成的 C 算法，可以计算给定 HD 和多项式的最大帧大小。我没有完全理解它，但它有效。

让我们假设一个 16 位 CRC 多项式 x¹?+x¹²+x?+1 = 0x11021。该多项式可以：

• 检测所有单位错误（与数据大小无关）。
• 检测所有高达 16 位宽度的突发错误（与数据大小无关）。
• 检测所有奇数个误码（因为它有 4 个多项式；与数据大小无关）。
• 检测高达 32571 位数据大小的 3 位错误 (HD4)。

以上正确吗？

是否有额外的 CRC 错误检测功能？如果是，我如何检查（没有深入的数学知识）任意 CRC 多项式是否支持它们？

我们正在将 MySQL 5.7 数据库迁移到 PostgreSQL 9.6。

一个真正的问题是bit_countPostgreSQL缺乏功能。此功能在即将发布的版本 10 中也不可用。

当前 MySQL 代码片段（简化）：

-- mysql specific, tested with 5.7.19
select code,phash,bit_count(phash ^ -9187530158960050433) as hd 
from documents 
where phash is not null and bit_count(phash ^ -9187530158960050433) < 7
order by hd;

我们尝试了一个简单的解决方案（将 BIGINT 转换为字符串并计算“1”），但与 MySQL 相比，它的表现非常糟糕。

Java使用了 Hacker's Delight 的一个技巧，但 AFAIK 这在 PostgreSQL 中是不可能的，因为该>>>运算符（也）不可用。

问题：是否有与 MySQL 性能相当的解决方案/解决方法？

更新 1

我能找到的最佳解决方案是基于这个 SO 答案：

首先创建bit_count函数：

CREATE OR REPLACE FUNCTION bit_count(value …

我正在尝试计算输入散列和数据库存储的散列之间的汉明距离。这些是感知散列，因此它们之间的汉明距离对我很重要，并告诉我两个不同图像的相似程度（参见http://en.wikipedia.org/wiki/Perceptual_hashing，http://jenssegers.com/61/感知图像哈希，http://stackoverflow.com/questions/21037578/）。哈希是 16 个十六进制字符长，如下所示：

b1d0c44a4eb5b5a9
1f69f25228ed4a31
751a0b19f0c2783f

我的数据库看起来像这样：

CREATE TABLE `hashes` (
  `id` int(11) NOT NULL,
  `hash` binary(8) NOT NULL
) ENGINE=InnoDB AUTO_INCREMENT=4 DEFAULT CHARSET=latin1;

INSERT INTO `hashes` (`id`, `hash`) VALUES
    (1, 0xb1d0c44a4eb5b5a9),
    (2, 0x1f69f25228ed4a31),
    (3, 0x751a0b19f0c2783f);

现在，我知道我可以像这样查询汉明距离：

SELECT BIT_COUNT(0xb1d0c44a4eb5b5a9 ^ 0x751a0b19f0c2783f)

正如预期的那样，它将输出 38。但是，我似乎无法为此比较引用列名。以下不按预期工作。

SELECT BIT_COUNT(hash ^ 0x751a0b19f0c2783f) FROM hashes

有谁知道如何SELECT使用我的数据库中的列像上面的第一个查询一样计算汉明距离？我试着使用的场景无数hex()，unhex()，conv()，并cast()以不同的方式。这是在 MySQL 中。

更新我上面的查询在 MySQL v8 中运行时似乎按预期工作（感谢@LukStorms 指出这一点）。您可以使用我下面的小提琴并更改左上角的版本。我现在的问题是：如何确保该行为适用于所有版本的 MySQL？

小提琴：https : //www.db-fiddle.com/f/mpqsUpZ1sv2kmvRwJrK5xL/0

找到 12 个 32 位数字，其中每对至少在 17 个位置上有位不同。

我正在努力寻找解决这个问题的最佳算法。更一般的问题是：找到“n”个 32 位数字，使得它们中的每对至少在“m”个位置上有位不同。

我的第一个方法是随机选择一个数字，或者从 6 (00000110) 开始，然后再次选择其他随机数字。然后进行异或运算并计算异或结果的二进制表示形式中有多少个 1，这将表明数字有多少个位置不同。如果条件被接受，我们可以存储这两个数字并执行相同的过程，直到达到所需的数字数量。然而，这种算法似乎不是最佳的，因为我们选择随机数，因此它可以“永远”持续下去。

*更新 我准备了这样的代码，对于 m = 16 它实际上返回 12 个结果，但是对于 17 （我需要的）它停止在 9 个结果并且代码永远不会完成。我想知道在[0, 2^32]范围内是否有可能没有这十二个数字，但如何证明呢？

import random

def hamming_distance(x, y):
    dist = 0

    # The ^ operator sets to 1 only the bits that are different
    val = x ^ y
    while val > 0:
        # We then count the bit set to 1 using the Peter Wegner way
        val = val & (val - 1) …