一.问题描述
B1[1 2 3
4 5 6
7 8 9]
B2[12 13 14
21 31 41
51 1 1
81 1 1]
两个十进制矩阵，行数不一样，分别是n1和n2，列数必须一致，为nwords，输出的矩阵Dh是[n1，n2]，这和求两句真的欧氏距离一样的。
输出[1 1] = 1和12海明+2和13海明 + 3和14海明，[1 2] = 1和21 + 2和31 + 3和41，也就是说[i j]是B1第i行和B2第j行的海明距离。
二.问题分析
1和12 21 51 81分别求海明距离，防御a（一个航向量）；2和13 31 1 1求海明距离，放于b；3和14 41 1 1 防御c；然后a+b+c就得到了，B1中第一行和B2中各行的海明距离。
为了加快运算，可以打表，两个nwords=8的数异或后还是0到255（bitxor异或得到的是10禁止数），所以吧0到255共256个数每个数包含几个1（就是海明距离）存在一个矩阵bit_in_char中。
三.实现
function Dh=hammingDist(B1, B2)
%
% Compute hamming distance between two sets of samples (B1, B2)
%
% Dh=hammingDist(B1, B2);
%
% Input
% B1, B2: compact bit vectors. Each datapoint is one row.
% size(B1) = [ndatapoints1, nwords]
% size(B2) = [ndatapoints2, nwords]
% It is faster if ndatapoints1 < ndatapoints2
%
% Output
% Dh = hamming distance.
% size(Dh) = [ndatapoints1, ndatapoints2]
% example query
% Dhamm = hammingDist(B2, B1);
% this will give the same result than:
% Dhamm = distMat(U2>0, U1>0).^2;
% the size of the distance matrix is:
% size(Dhamm) = [Ntest x Ntraining]
% loop-up table:
bit_in_char = uint16([...
0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 2 2 3 2 3 ...
3 4 2 3 3 4 3 4 4 5 1 2 2 3 2 3 3 4 2 3 3 4 ...
3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 1 2 ...
2 3 2 3 3 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 ...
3 4 4 5 4 5 5 6 2 3 3 4 3 4 4 5 3 4 4 5 4 5 ...
5 6 3 4 4 5 4 5 5 6 4 5 5 6 5 6 6 7 1 2 2 3 ...
2 3 3 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 ...
4 5 4 5 5 6 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6 ...
3 4 4 5 4 5 5 6 4 5 5 6 5 6 6 7 2 3 3 4 3 4 ...
4 5 3 4 4 5 4 5 5 6 3 4 4 5 4 5 5 6 4 5 5 6 ...
5 6 6 7 3 4 4 5 4 5 5 6 4 5 5 6 5 6 6 7 4 5 ...
5 6 5 6 6 7 5 6 6 7 6 7 7 8]);
n1 = size(B1,1);
[n2, nwords] = size(B2);
Dh = zeros([n1 n2], \'uint16\');
for j = 1:n1
for n=1:nwords
y = bitxor(B1(j,n),B2(:,n));
Dh(j,:) = Dh(j,:) + bit_in_char(y+1);
end
end
请发表评论