问题标签 [hamming-distance]

我有一个 MySQL 数据库，其中包含大量 2048 位二进制字符串（例如 '0111001...0101'）。我需要的一个计算是这些字符串与一些外部生成的位串相比的汉明距离（异或结果中 1 的总数）。为了了解如何编写此查询，我尝试为较小的位串编写它。这是一个例子：

计算 XOR 的内部部分工作正常，但 BIT_COUNT 返回奇怪的结果。此示例返回 14，它比字符串本身长。

所以我有几个问题：

首先，为什么 BIT_COUNT 返回如此奇怪的结果。它是在一个字符串上操作，而不是我希望它操作的二进制字符串吗？如果是这样，我该如何处理？

其次，请注意我通过在前面加上 b 将字符串转换为二进制（这是正确的词吗？）。我将如何使用列名和变量来执行此操作？显然，我不能简单地将 ab 添加到变量名之前，也不能在两者之间插入空格。有任何想法吗？

谢谢，

编辑：所以这是第一个问题的解决方案：

将其用于较大的字符串（2048 位）时似乎存在问题。我试过了：

它给了我类似 28 的结果，而实际的位数应该在 1024 左右。如果我删除 b，那么它似乎在 64 处达到最大值。关于如何解决这个问题的任何想法？

我不太确定如何表达这个问题，所以这里有详细信息。我正在使用一种技巧来计算两个位串之间的汉明距离。这是查询：

本质上，它计算两个字符串之间的异或，删除所有 0，然后返回长度。这在功能上等同于两个位串之间的汉明距离。不幸的是，这只返回汉明距离，没有别的。在 codeTable 表中，还有一个名为 person_id 的列。我希望能够返回最小汉明距离和与之相关的 id。返回最小汉明距离很简单，只需在“长度”部分周围添加一个 min() 即可。

这很好，但是，它只返回汉明距离，而不是 person_id。我不知道我需要做什么才能返回与该汉明距离相关的 person_id。

有人知道如何做到这一点吗？

问题：

我有 N (~100k-1m) 个字符串，每个 D（例如 2000）个字符长并且字母低（例如 3 个可能的字符）。我想对这些字符串进行排序，以使相邻字符串之间的变化尽可能少（例如汉明距离低）。解决方案不一定是最好的，但越接近越好。

例子

关于问题的想法

我有一种不好的感觉，这是一个不小的问题。如果我们将每个字符串视为一个节点，将与其他字符串的距离视为一条边，那么我们正在研究一个旅行商问题。大量字符串意味着事先计算所有成对距离可能是不可行的，我认为将问题变成更像加拿大旅行者问题的问题。

目前我的解决方案是使用VP树来找到一个贪婪的最近邻类型的解决方案来解决这个问题

但初步结果似乎很差。散列字符串以使更多相似的字符串更接近可能是另一种选择，但我对这将提供一个多么好的解决方案或它将如何扩展到这种大小的数据知之甚少。

我有一个 MongoDB，里面有大约 100 万个文档。这些文档都有一个字符串，表示 1 和 0 的 256 位二进制文​​件，例如：

0110101010101010110101010101

理想情况下，我想查询接近二元匹配。这意味着，如果两个文档具有以下编号。是的，这就是汉明距离。

Mongo 目前不支持此功能。所以，我被迫在应用层做这件事。

因此，鉴于此，我试图找到一种方法来避免在文档之间进行单独的汉明距离比较。这使得做这件事的时间基本上是不可能的。

我有很多内存。而且，在 ruby​​ 中，似乎有一个很棒的宝石（算法）可以创建许多树，但我似乎都无法完成（但）这会减少我需要进行的查询数量。

理想情况下，我想进行 100 万次查询，找到几乎重复的字符串，并能够更新它们以反映这一点。

任何人的想法将不胜感激。

我有一组字符串[S1 S2 S3 ... Sn]，我要计算所有这样的目标字符串T，以便每个字符串S1 S2... Sn都可以T在总共K编辑中转换。
所有字符串都是固定长度L的，这里的编辑是汉明距离。

我所拥有的只是一种蛮力方法。所以，如果我的字母大小是 4，我有 O(4^L) 的样本空间，并且需要 O(L) 时间来检查它们中的每一个。我似乎无法将复杂性从指数降低到某种多边形或伪多边形！有没有办法修剪样本空间以做得更好？

我试图将其可视化为 L 维向量空间。我已经获得了 N 个点，并且必须计算与给定 N 个点的距离之和小于或等于 K 的所有点。
i.e. d1 + d2 + d3 +...+ dN <= K
是否有任何已知的几何算法可以更复杂地解决这个或类似问题？请指出我正确的方向或任何提示表示赞赏。
谢谢

我的工作是遗传学，我正在使用汉明距离（在 Matlab 中）来计算病毒基因型之间的遗传距离。

例如：1型的结构是01234，2型的结构是21304等。显然存在许多基因型。因为基因型的长度相同，所以我认为使用汉明距离就可以了。

我的问题是：如何根据汉明距离对基因型进行排序。另一种说法：如何根据它们之间的汉明距离将基因型分类成簇？

谢谢

我想在 Matlab 中使用 kmeans 聚类中的汉明距离，但我收到一条错误消息，说我的数据必须是二进制的。

有没有办法解决？我使用的数据矩阵不能是二进制的（它具有必须允许值 0、1、2、3 的物理解释），但我使用汉明距离很重要。

我有一个过程，类似于生成感知散列的 tineye，这些是 32 位整数。

我打算将来将这些存储在 sql 数据库（可能是 nosql db）中

但是，我对如何根据哈希的相似性检索记录感到困惑。

有任何想法吗？

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

我想编写一个程序来比较两个数字时获得 1 的位数。如果我比较任何两个数字之间的位，以找出二进制数在 1 和 0 中的不同之处。换句话说，异或（XOR）关系。

就像 if 22 （它有 10110 二进制）并将它与 15 （它有 01111 二进制）进行比较

第一个 10110

第二个 01111

结果 11001

答案是 25，但我想得到的是 3，其中有三个不同的 1 和 0。

我有数十万个长度为 32 位的稀疏位串。

我想对它们进行最近邻搜索，查找性能至关重要。我一直在阅读各种算法，但它们似乎针对的是文本字符串而不是二进制字符串。我认为本地敏感散列或频谱散列似乎是不错的候选者，或者我可以研究压缩。这些中的任何一个都可以很好地解决我的位串问题吗？任何方向或指导将不胜感激。