我试图在MySQL数据库中改进搜索类似图像的pHashed.现在我比较pHash计算汉明距离像这样:
SELECT * FROM images WHERE BIT_COUNT(hash ^ 2028359052535108275) <= 4
选择结果(引擎MyISAM)
因此查询时间增加取决于表中的行数.
我还尝试在SQL上的二进制字符串上的stackoverflow 汉明距离上找到解决方案
SELECT * FROM images WHERE
BIT_COUNT(h1 ^ 11110011) +
BIT_COUNT(h2 ^ 10110100) +
BIT_COUNT(h3 ^ 11001001) +
BIT_COUNT(h4 ^ 11010001) +
BIT_COUNT(h5 ^ 00100011) +
BIT_COUNT(h6 ^ 00010100) +
BIT_COUNT(h7 ^ 00011111) +
BIT_COUNT(h8 ^ 00001111) <= 4
行300000; 查询时间~240ms
我将数据库引擎更改为PostgreSQL.将此MySQL查询转换为PyGreSQL但 没有成功.行300000; 查询时间〜18s
有优化上述查询的解决方案吗？ 我的意思是优化不依赖于行数.
我有限的方法(工具)来解决这个问题.MySQL到目前为止似乎是最简单的解决方案,但我可以在每个开源数据库引擎上部署代码,该引擎将在专用机器上使用Ruby.有一些针对MsSQL的现成解决方案/sf/answers/415166111/(未经测试).也许有人知道如何为MySQL或PostgreSQL翻译它.
请根据一些代码或观察结果发布答案.我们在stackoverflow.com上有很多关于汉明距离的理论问题
谢谢!
我有一个奇怪的通信通道,我需要检测错误并消除通道中的某些序列.
每条消息长12位,分成3个半字节(每个4位).我需要提取至少450个不同的代码,所以我的汉明距离可以达到3.
但是,我不能将两个半字节序列相同,因此以下序列无效:
0xf 0xf 0xf - Three of the same nibbles in sequence
0x8 0x8 0x0 - Two of the same nibbles in sequence
0xf 0x3 0x3 - Two of the same nibbles in sequence
此外,消息可以相互跟随而不会中断,因此一个序列的开头不能与最后一个序列的末尾具有相同的第一个半字节:
0x327 0x743 - Even though they are not in the same message, two sequential nibbles are the same in the message stream
但是以下序列很好:
0x1 0x2 0x1 - Two nibbles same, but separated by another nibble
0x0 0x1 0x2 - All nibbles different
0xf …我正在寻找一种快速的方法来生成小于2 ^ 64的k个非负整数,其中,在基数2中,任意两个数之间的最小汉明距离尽可能高.
例如,如果我正在寻找k = 4的数字并且它们应该小于2 ^ 4它们可以是:
0000
0011
1100
1111
并且最小汉明距离将是2.
是否有快速算法为给定的k生成这些数字？我将得到大约10 ^ 4的k.
或者,产生一组数字的算法也可以正常工作,所述数字具有成对的汉明距离大于给定值.
我正在使用一些递归神经网络结构进行多标签分类。我的问题是关于损失函数的：我的输出将是true / false（1/0）值的向量，以指示每个标签的类。许多资源表示，汉明损失是适当的目标。但是，汉明损耗在梯度计算中存在问题： H =平均值（y_true XOR y_pred），XOR无法得出损耗的梯度。那么，还有其他损失函数可用于训练多标签分类吗？我已经尝试过使用单独的S型输入进行MSE和二进制交叉熵。
machine-learning neural-network hamming-distance gradient-descent multilabel-classification
假设你有N(~100k-1m)个整数/位串,每个K(例如256)位长.该算法应返回具有最低成对汉明距离的k对.
N = 4
K = 8
i1 = 00010011
i2 = 01010101
i3 = 11000000
i4 = 11000011
HammingDistance(i1,i2) = 3
HammingDistance(i1,i3) = 5
HammingDistance(i1,i4) = 3
HammingDistance(i2,i3) = 4
HammingDistance(i2,i4) = 4
HammingDistance(i3,i4) = 2
对于k = 1,它应该返回pairlist {(i3,i4)}.对于k = 3,它应该返回{(i1,i2),(i1,i4),(i3,i4)}.等等.
天真的实现计算所有成对距离,对对进行排序并返回具有最小距离的k:O(N ^ 2).有没有更好的数据结构或算法？由于没有单个查询整数,因此无法使用Efficiently中找到大集合中具有低汉明距离的二进制字符串的想法.
我想将二进制向量（数百万个）聚类成 k 个簇。我使用汉明距离来查找初始簇的最近邻居（这也很慢）。我认为 K 均值聚类并不适合这里。问题在于计算某个初始聚类中心的最近邻（二元向量）的平均值，以更新质心。
第二种选择是使用 K-medoids，其中新的聚类中心是从最近邻居之一（最接近特定聚类中心的所有邻居的中心）中选择的。但发现这是另一个问题，因为最近邻居的数量也相当大。
有人可以指导我吗？
我写了一个比较2个两位无符号整数的新程序.比较汉明距离.但我的算法并不完美.你能告诉我这段代码有什么问题:(感谢很多!!
这是我的计算方法;
int countHammDist(unsigned int n, unsigned int m)
{
int i=0;
unsigned int count = 0 ;
for(i=0; i<8; i++){
if( n&1 != m&1 ) {
count++;
}
n >>= 1;
m >>= 1;
}
return count;
}
a和b 8位二进制文件.
PrintInBinary(a);
PrintInBinary(b);
printf("\n %d", countHammDist(a,b));
让我告诉你输出;
Enter two unsigned integers (0-99): 55 64
Your choices are 55 and 64
Number A: 00110111
Number B: 01000000
Hamming distance is ; 5
Python初学者在这里。所以我在尝试仅使用 numpy 库来计算输入矩阵的行之间的结果二进制成对汉明顿距离矩阵时遇到了麻烦。我应该避免循环并使用矢量化。例如，如果我有类似的东西：
[ 1, 0, 0, 1, 1, 0]
[ 1, 0, 0, 0, 0, 0]
[ 1, 1, 1, 1, 0, 0]
矩阵应该是这样的：
[ 0, 2, 3]
[ 2, 0, 3]
[ 3, 3, 0]
即如果原始矩阵是 A 并且汉明距离矩阵是 B。B[0,1] = 汉明距离（A[0] 和 A[1]）。在这种情况下，答案是 2，因为它们只有两个不同的元素。
所以对于我的代码是这样的
def compute_HammingDistance(X):
hammingDistanceMatrix = np.zeros(shape = (len(X), len(X)))
hammingDistanceMatrix = np.count_nonzero ((X[:,:,None] != X[:,:,None].T))
return hammingDistanceMatrix
然而，它似乎只是返回一个标量值而不是预期的矩阵。我知道我可能在数组/矢量广播方面做错了什么，但我不知道如何解决它。我试过使用 np.sum 而不是 np.count_nonzero 但它们几乎都给了我类似的东西。
如何有效存储二进制代码？对于某些固定大小,例如32位,可以使用原始类型.但是如果我的二进制代码要长得多呢？
计算两个二进制代码之间汉明距离的最快方法是什么？
我有两个数据框，df1包含参考数据和df2新数据。对于 中的每一行，我需要根据汉明距离df2找到最佳（和第二最佳）匹配行。df1
我使用e1071包来计算汉明距离。两个向量之间的汉明距离x可以y计算如下：
x <- c(356739, 324074, 904133, 1025460, 433677, 110525, 576942, 526518, 299386,
92497, 977385, 27563, 429551, 307757, 267970, 181157, 3796, 679012, 711274,
24197, 610187, 402471, 157122, 866381, 582868, 878)
y <- c(356739, 324042, 904133, 959893, 433677, 110269, 576942, 2230, 267130,
92496, 960747, 28587, 429551, 438825, 267970, 181157, 36564, 677220,
711274, 24485, 610187, 404519, 157122, 866413, 718036, 876)
xm <- sapply(x, intToBits)
ym <- sapply(y, intToBits) …