问题标签 [hamming-distance]

对于数据结构项目，我必须找到两个单词（如"cat"和"dog"）之间的最短路径，一次只更改一个字母。我们得到了一个拼字游戏单词列表，用于寻找我们的路径。例如：

我已经使用广度优先搜索解决了这个问题，但正在寻找更好的东西（我用特里树表示字典）。

请给我一些想法，以获得更有效的方法（在速度和内存方面）。一些荒谬和/或具有挑战性的东西是首选。

我问了我的一个朋友（他是一名大三学生），他说这个问题没有有效的解决方案。他说我会在学习算法课程时了解原因。对此有何评论？

我们必须逐字逐句。我们不能去cat -> dat -> dag -> dog。我们还必须打印出遍历。

我读过关于 kd-trees 的文章，但是当空间的维度很高时它们效率低下。我有一个值数据库，我想找到查询的某个汉明距离内的值。例如，数据库是一个 32 位数字的列表，我想找到与查询值相差小于 3 位的所有数字。

我在某处听说过 MultiVariate Partition 树，但找不到好的参考。我知道 min-Hash 给出了一个很好的近似值，更好，但我想要一个准确的答案。

上面的结果应该是8。

如何实施？

如何找到某个CRC生成的代码的汉明距离？

假设我有一个生成多项式，例如 4 位和 11 位数据。

如何仅根据这些信息计算 HD？

有一个包含 N 个固定长度字符串的数据库。有一个相同长度的查询字符串。问题是从数据库中获取与 q 具有最小汉明距离的前 k 个字符串。

N很小（约400），字符串很长，长度固定。数据库不会改变，所以我们可以预先计算索引。查询差异很大，缓存和/或预计算不是一种选择。每秒有很多。我们总是需要 k 个结果，即使 k-1 个结果匹配 0（按汉明距离排序并取第一个 k，因此局部敏感散列和类似方法不会这样做）。kd-tree 和类似的空间分区可能会比线性搜索执行得更差（字符串可能很长）。BK-tree 目前是最好的选择，但它仍然比它需要的慢和复杂。

感觉就像有一个算法，它将建立一个索引，它将在很少的步骤中丢弃大部分条目，留下 k <= t << N 个条目来计算真正的汉明距离。

人们建议基于 Levenstein 距离进行模糊字符串匹配 - 谢谢，但问题要简单得多。基于广义距离度量的方法（如 BK 树）是好的，但也许有一些利用上述事实的东西（小 DB/长固定大小的字符串，简单的汉明距离）

链接、关键词、论文、想法？=)

有人写这个函数

我问，为什么你把 * 放在 p++ 之前？

回答：因为“都是一样的”，所以我更正了代码，然后生气了一会儿，因为两者的工作原理是一样的……

所以我想和stackoverflow分享这个，例如：

字符 s[6]="你好";

它会做什么？

这将评估 ++ 预增量（在指针上），然后是取消引用运算符 *，因此它将让一个 char 值 'e'（“hello”的第二个字母）（在这种情况下不使用并且可以生成编译警告）并且指针将指向“e”（位置 1）

它会做什么？

这有点奇怪，因为它会首先评估取消引用运算符 *，所以它会让一个 char 值 'h' （在这种情况下都没有使用），然后是 ++ 后增量（到指针），所以（再次）指针将从“e”（位置 1）指向

它会做什么？

最后它不会有 char 的左值，但如果不使用它不会产生任何警告，并且指针也会从 'e'（位置 1）指向。

从指针地址的角度来看，这三种形式的作用相同。

恕我直言，这是某些计算机语言（几乎所有人）中最糟糕的事情。

“任何代码和任何错误之间的汉明距离都很差”

我们在编程时没有冗余，如果你拿一本法律书，在里面写随机字符，它是可读的，但是如果你在编程时输入随机，你会得到一个错误，100% 准确

假设我希望有可能检测 4 位错误并恢复 2 位错误。那么汉明距离应该是多少？

我想知道应该是 d = Max{2r+1, r+1} 还是 d = s + r，其中 s 是 4，r 是 2？

提前感谢您的回复！

干杯

我想为要分类的 k 个不同输入生成 n 位代码。该代码的主要要求是纠错标准：不同输入的任意两个编码之间的最小成对距离最大化。我不需要它是精确的——近似就可以了，易用性和计算实现的速度也是一个优先事项。

一般来说，n 将在数百个中，k 在数十个中。

此外，k 个不同的 n 位二进制编码之间的最小汉明距离是否有合理的严格限制？

输入：图 G 输出：几个独立的集合，这样一个节点对所有独立集合的成员资格是唯一的。因此，一个节点与它自己集合中的任何节点都没有连接。这是一个示例路径。

由于这里需要进行澄清，因此需要重新改写：

将给定的图划分为集合，使得

1. 我可以通过集合中的成员身份将节点与所有其他节点区分开来，例如，如果节点 i 仅存在于集合 A 中，则其他节点不应仅存在于集合 A 中

   如果节点 j 存在于集合 A 和 B 中，则其他节点不应仅存在于集合 A 和 B 中。如果节点的成员资格由位模式编码，那么这些位模式的汉明距离至少为 1

2. 如果两个节点在图中相邻，它们不应该出现在同一个集合中，因此是一个独立的集合

示例：B 没有相邻节点 D=>A, A=>D

解决方案：

1. 乙/
2. / BD

A 的位模式为 10，并且在其集合中没有相邻节点。B 具有位模式 11 且没有相邻节点，D 具有 01 因此所有节点的汉明距离至少为 1 且没有相邻节点 => 正确

错了，因为 D 和 A 是相连的：

1. 亚行
2. / D B

A 在其集合中有位模式 10 和 D，它们是相邻的。B 有 11 位模式且没有相邻节点，D 有 11 和 B 一样，所以这个解决方案有两个错误，因此它不被接受。

当然，随着图中节点数量的增加，这应该扩展到更多的集合，因为您至少需要log(n)集合。

我已经写了一个到 MAX-SAT 的转换，为此使用 sat-solver。但是子句的数量太大了。更直接的方法会很好。到目前为止，我有一个近似值，但我想要一个精确的解决方案或至少一个更好的近似值。

我尝试了一种方法，我使用粒子群将任意解决方案优化为更好的解决方案。然而，运行时间非常糟糕，结果远非很好。我正在寻找动态算法或其他东西，但是我无法理解如何分而治之。

在学习计算机网络课程时，教授谈到了示例代码中两个有效代码字之间的汉明距离。我已经阅读了有关汉明距离的信息，从告诉 2 个字符串之间的差异距离的角度来看，这是有道理的。例如：

发送方发送代码字 1，引入了一个错误，接收方收到 10100。所以您看到第 4 位已损坏。这将导致汉明距离为 1，因为：

2 个字符串的 XOR 得到一个 1，因此汉明距离为 1。我理解到这一点。但随后教授问：

• 标准 CRC-16 位协议的汉明距离是多少？
• 标准 CRC-32 位协议的汉明距离是多少？

我有点困惑，想知道是否有人可以提供帮助。谢谢。