问题标签 [hamming-distance]

For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.

0 投票
1 回答
4669 浏览

heuristics - 8 谜题:汉明和马纳坦启发式考虑“空白空间”?

我有一个非常简单的问题。

我正在研究 8 个谜题(8 个数字(从 1 到 8)+ 空白(=0))

在计算汉明距离(错误位置的数字)和曼哈顿距离(开始和最终位置之间的水平+垂直距离)时,我应该考虑“空白”空间来计算结果吗?

例如..

有目标状态

什么是正确的?

  • 汉明距离 = 8(每个数字都没有到位)或 9(也 0 = 考虑空白)
  • 曼哈顿距离 (distance(7),distance(2),distance(4),...) = 3 (=1+2) + 1 (=1+0) + 2 (1+1) + 2 (2+ 0) + 0 (空白) + 3 (1+2) + 2 (2+0) + 3 (1+2) + 3 (2+1) --> 不考虑空白是 18 ,有空白 (+2)是20。什么是正确的?

谢谢

0 投票
1 回答
2691 浏览

ascii - 错误检测码和汉明距离

在此处输入图像描述

v 和 w 的汉明距离等于 2,但如果没有奇偶校验位,它只会是 1。为什么会这样?

0 投票
3 回答
3946 浏览

c++ - 二进制数组的快速 Popcount 指令或汉明距离?

我在 Visual Studio 2010 C++ 上实现

我有两个二进制数组。例如,

要计算和之间的汉明距离, 存储 和的结果。array1array2array3[100]xorarray1array2

然后我必须计算1. array3为此,我知道我可以使用该__popcnt指令。

现在,我正在做如下的事情:

它显示了一个很好的结果,但速度很慢。我怎样才能让它更快?

0 投票
3 回答
15624 浏览

math - 查找代码的汉明距离

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

答案是 2。这是如何工作的?我认为汉明距离仅在两个字符串之间?

0 投票
1 回答
1354 浏览

math - 如何计算数字滑块拼图的汉明距离

如何计算以下谜题的汉明距离:

在此处输入图像描述

据我了解,我需要比较以下两个序列:

还是没那么容易?

0 投票
1 回答
667 浏览

mysql - 在没有超级权限的mysql中创建汉明距离函数

我想在我的 MySQL 数据库中使用汉明距离(通过 phpMyAdmin 使用),但没有成功使用此处给出的代码创建函数

我指的是这段代码:

问题是我没有“超级特权”。我还尝试将这段代码放在两者之间DELIMITER //(它适用于 Levenshtein 距离函数,见下文),但也没有解决问题 - 我得到了一个超时:

/usr/share/phpmyadmin/libraries/import/sql.php第 132 行超过了 300 秒的最大执行时间

无论如何,我对 MySQL 还是很陌生,所以我想知道是否有人可以帮助我以其他方式在 MySQL 中创建汉明函数。

顺便说一句,我也在使用Levenshtein 距离函数,这个函数的创建工作得很好。然而,我发现应该使用 Levenshtein 距离来计算两个字符串之间的距离,而应该使用汉明距离来计算数值数据。

谢谢。

0 投票
2 回答
5876 浏览

mysql - MySQL 或 PostgreSQL 的汉明距离优化?

我试图改进在 MySQL 数据库中搜索相似图像 pHashed。现在我像这样比较 pHash 计数汉明距离:

选择结果(引擎 MyISAM)

  • 20000 行;查询时间 < 20ms
  • 100000 行;query time ~ 60ms # 这很好,直到达到 150000 行
  • 300000 行;查询时间 ~ 150ms

因此查询时间增加取决于表中的行数。


我还尝试了 在 SQL 中二进制字符串的 stackoverflow 汉明距离上找到的解决方案

行 300000 ; 查询时间 ~ 240ms


我将数据库引擎更改为 PostgreSQL。将此 MySQL 查询转换为 PyGreSQL 没有成功。行 300000 ; 查询时间~18s


有没有优化上述查询的解决方案? 我的意思是优化不取决于行数。

我有有限的方法(工具)来解决这个问题。到目前为止,MySQL 似乎是最简单的解决方案,但我可以在每个可以在专用机器上与 Ruby 一起使用的开源数据库引擎上部署代码。MsSQL https://stackoverflow.com/a/5930944/766217有一些现成的解决方案(未测试)。也许有人知道如何为 MySQL 或 PostgreSQL 翻译它。

请根据一些代码或观察发布答案。我们在 stackoverflow.com 上有很多关于汉明距离的理论问题

谢谢!

0 投票
1 回答
1159 浏览

matlab - 为什么MATLAB中的汉明距离聚类给出十进制质心?

我想测试如何使用汉明距离对二进制数据进行聚类所以在上面的代码中,我随机分配了 X 一个二进制值矩阵。然而,问题是我的质心是十进制值。就像我在下面展示的那样。

为什么答案中有 0.5?我希望质心也是二进制的。由于二进制数据,是否可以绘制没有重叠的集群?

0 投票
4 回答
3898 浏览

c - 寻找最快的汉明距离 C 实现

我想找出两个相等长度的字符串有多少个不同的字符。我发现异或算法被认为是最快的,但它们返回以位表示的距离。我想要用字符表示的结果。假设“pet”和“pit”以字符表示的距离为 1,但 'e' 和 'i' 可能有两个不同的位,因此 xoring 返回 2。

我写的函数是:

它可以变得更快吗?也许使用一些较低级别的命令或实现不同的算法?

系统:英特尔至强 X5650 上的 Gcc 4.7.2

谢谢

0 投票
0 回答
1206 浏览

c++ - 8-Puzzle Solver 意外行为

我正在研究一个 8-Puzzle Solver - 使用最佳优先搜索 + Hamming 距离(瓷砖不合适)启发式 - 这是我们作为项目所必需的。

我首先在一个单独的 cpp 文件中定义了一个Stat Struct,它在头文件中如下所示:

接下来是 main.cpp 文件:

现在,当我使用这样的示例输入运行程序时:

它解决了难题,一切都很好。但是在我尝试的所有其他输入中,开放集在达到目标之前就变空了,尽管这些难题有解决方案

编辑: 我试图查看进入开放集的统计数据,但没有,所以我使用下面的输入作为示例,我得到了什么:

打开的统计数据:

解决这个难题需要哪些步骤。

未在 Closed 中找到且未进入 Open 的统计信息:

因此,Open 集表示上述统计信息存在于 Open 中并拒绝输入它们,但 Open 中没有此类统计信息,并且这些状态的启发式值不同 On Open(4,4,5,5,5,5)其他(6,6,5,7)。

有人可以告诉我为什么 Open 拒绝输入这些统计数据,就好像它们已经存在一样。提前致谢。