问题标签 [hamming-distance]

如何计算相同点的两个数据集之间的汉明距离？两个数据集看起来完全一样。
http://postimg.org/image/u11qnsolh/

有两个相同点数的数据集。
总点数-19

第一个数据集有 3 个集群。
集群 A 有 4 个点
集群 B 有 2 个点
集群 C 有 4 个点

其余点在集群之外

第二个数据集有 3 个集群。
集群 A 有 8 个点
集群 B 有 5 个点
集群 C 有 6 个点

我正在尝试计算 n 个节点图中每个节点之间的汉明距离。此图中的每个节点都有一个相同长度 (k) 的标签，用于标签的字母表是 {0, 1, *}。'*' 用作无关符号。例如，标签 101*01 和 1001*1 之间的汉明距离等于 1（我们说它们仅在第 3 个索引处不同）。

我需要做的是找到每个节点的所有 1 汉明距离邻居，并准确报告这两个标签在哪个索引处不同。

我正在逐个字符地将每个节点标签与所有其他节点标签进行比较，如下所示：

我可能有几百万个节点。k 通常在 50 左右。我使用的是 JAVA，这种比较需要 n*n*k 时间并且运行缓慢。我考虑使用尝试和 VP 树，但无法弄清楚哪种数据结构适用于这种情况。我还研究了 Simmetrics 库，但什么都没有出现在我的脑海中。我真的很感激任何建议。

我正在尝试生成一个带有 6 个 UNIQUE 条码的随机条码列表，这些条码的汉明距离为 3。问题是程序正在生成一个带有重复的条码列表，而不是正确的汉明距离。下面是代码。

我认为我的问题在于最后一个 while 循环：我想compare_barcodes不断生成符合条件的条形码（不是重复的，并且不在已经生成的任何条形码的汉明距离内）。

我正在尝试编写一个程序来尽可能地打乱 dna 序列以破坏序列中的顺序。我写了matlab代码，但是太慢了。此外，我正在研究汉明距离测量或列文斯坦测量，以及如何结合这些测量以确保正确的洗牌。我在洗牌时遵循的规则

• 规则 1：第 i 个残差不应靠近 i-1,i-2,i-3,i+1,i+2,i+3
• 规则2：在接下来的安排中，我的新位置和旧位置必须相差20位。即，如果 A 在 shuffled 字符串中的字符串中排名第 1，则它必须大于等于第 21 位。

我在这里读过：

搜索引擎如何合并倒排索引的结果？

“查询执行算法实际上相当愚蠢”

并且有许多使用汉明距离的复杂算法应该在搜索引擎中使用。

这些算法可以在论文中找到：

MapReduce 上基于汉明距离的相似性搜索查询的有效处理。HmSearch：一种高效的汉明距离查询处理算法。多索引散列：在汉明空间中快速精确最近邻搜索的数据结构。

有人知道汉明空间中的算法是否真的有用吗？

我不明白如何根据这篇文章计算 levenshtein 矩阵中的值。我确实知道我们如何达到 3 的编辑距离。有人可以用外行的方式解释我们如何达到每个单元格中的每个值吗？

我在 mysql 中存储了一些哈希值，我将通过汉明距离进行比较来获取这些哈希值。

存储的哈希是这些：

我通常会像这样获取：

但是在 mysql 中，汉明距离是按位运算符，如果字符串只是数字，我可以这样做：

它仅适用于整数（数字），但我的要求是使用数字和字母，例如：

从我的小研究中，我知道首先我必须将字段转换为binary，然后bitcount通过使用CAST或CONVERT类似来使用：

或者

可以将数据转换为binary和使用bitcount. 现在出现的问题是，varbinary存储的字符/散列mysql已经是字母数字，如果我将字段转换为varbinary然后bitcount它将不起作用，因为存储的散列不是二进制字符串。

我应该怎么办？

我指的是 php hamming 距离匹配示例：

但是我不明白如何与mysql匹配并获取，因为我无法在mysql中实现它。

我在这个网站上发现了一个有趣的算法来计算汉明距离：

关键是该算法仅适用于位字符串，我正在尝试比较两个二进制字符串，但它们是字符串格式，例如

我怎样才能让他们使用这个算法？

我想从汉明距离为（比如说）1的单词列表中构建一个图表，或者换句话说，如果两个单词仅与一个字母不同（lo l -> lo t），则它们是连接的。

所以给定

words = [ lol, lot, bot ]

该图将是

简单的方法是将列表中的每个单词相互比较并计算不同的字符；可悲的是，这是一种O(N^2)算法。

我可以使用哪种算法/ds/策略来获得更好的性能？

另外，让我们假设只有拉丁字符，并且所有单词的长度都相同。

我想知道如何按 group计算不匹配的情况。

让我们想象这是我的数据：

数据看起来像这样

为了得到类似的东西

stringdist使用库来计算它会很有趣。

就像是

但它不起作用。

有任何想法吗 ？

快速更新：您将如何解决权重问题？例如，在设置两个字符之间的不匹配时，我如何传递一个参数 - 一个值 (1,2,3, ...)。就像b 和 c之间的不匹配花费2，而a 和 c之间的不匹配花费1等等。