文档章节

汉明距离(hamming distance ) 的代码实现

Lennie002
 Lennie002
发布于 2015/03/02 23:16
字数 853
阅读 337
收藏 0
  1.  简介  详见维基百科

概念:

信息论中,两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说,它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。例如:

10111011001001之间的汉明距离是2。

21438962233796之间的汉明距离是3。

"toned"与"roses"之间的汉明距离是3。

汉明重量是字符串相对于同样长度的零字符串的汉明距离,也就是说,它是字符串中非零的元素个数:对于二进制字符串来说,就是1的个数,所以11101的汉明重量是4。

特性:

对于固定的长度n,汉明距离是该长度字符向量空间上的度量,很显然它满足非负、唯一及对称性,并且可以很容易地通过完全归纳法证明它满足三角不等式

两个字ab之间的汉明距离也可以看作是特定运算−的ab的汉明重量。

对于二进制字符串ab来说,它等于a 异或b以后所得二进制字符串中“1”的个数。另外二进制字符串的汉明距离也等于n超正方体两个顶点之间的曼哈顿距离,其中n是两个字串的长度。

   2.  实现:

/*
 *  =>实现自己的hamming distance计算代码
 *  =>面向图像特征描述子的计算要求
 *    1. feature长度128,256,..千万
 *    2. 实现在海量数据中快速匹配(笨的暴力匹配)
 */


#include <stdio.h>
#include <stdlib.h>

// 使用SSE
#include <nmmintrin.h>  

#define USE_SSE4 1

//定义特征描述子的长度,
#define FEATURE_LENGTH  128

typedef unsigned long long  uint64;
typedef unsigned int        uint32;



//c 实现的简单的hamming distance 计算,原理
int hamming_dis(unsigned x, unsigned y)
{
	int dist;
	unsigned val;

	dist = 0;
	val = x ^ y;  // X OR Y hammming Dis 是异或计算的值中“1”的个数
	
	while(val != 0) //统计val的二进制表示中“1”的个数
	{
	     dist++;
		 val &= val - 1;
	}
	return dist;
}
 
//https://tekpool.wordpress.com/2006/09/25/bit-count-parallel-counting-mit-hakmem/
//实现二进制数据并行统计
int BitCount(unsigned int u)
 {
         unsigned int uCount;

         uCount = u
                  - ((u >> 1) & 033333333333)
                  - ((u >> 2) & 011111111111);
         return
           ((uCount + (uCount >> 3))
            & 030707070707) % 63;
 }

// 计算uint64 长度的hamming distance
uint64 _m_hamming_distance_uint64(uint64 x, uint64 y)
{
    uint64 dist;
	uint64 val;

	dist = 0;
	val  =  x ^ y;

	while(val != 0)
	{
	    dist++;
		val &= val - 1;
	}
	return dist;
}



//计算空间长度更长的hamming distance,
int _m_hamming_dis(const unsigned char* x, const unsigned char *y)
{
#ifdef USE_SSE4
	uint64 dist;

	uint64  *xx = (uint64 *)x;
	uint64  *yy = (uint64 *)y;
	dist = 0;
	
	//此处可以尝试添加并行处理!
	for(unsigned i = 0; i <FEATURE_LENGTH /( sizeof(uint64) * 8 ); ++i)
	{
		//dist += _m_hamming_distance_uint64(xx[i],yy[i]);
		//printf("xx, yy, dist = %d, %d, %d\n",dist,xx[i],yy[i]);
		dist += _mm_popcnt_u64(xx[i] ^ yy[i]);
	}
	return (int)dist;
#else
	int dist;

	uint64  *xx = (uint64 *)x;
	uint64  *yy = (uint64 *)y;
	dist = 0;
	
	//此处可以尝试添加并行处理!
	for(unsigned i = 0; i <FEATURE_LENGTH /( sizeof(uint64) * 8 ); ++i)
	{
		//dist += _m_hamming_distance_uint64(xx[i],yy[i]);
		// 或者
		dist += BigCount(xx[i] ^ yy[i])
	}
	return dist;
#endif
}



// 测试函数
int main()
{

	//printf("ham_dis = %d",hamming_dis(4,8));
	
	unsigned  *a = (unsigned *)malloc(256); //256  bit
	unsigned  *b = (unsigned *)malloc(256); //256

	for(unsigned i = 0; i < 256 /(sizeof(unsigned)*8); ++i)
	{
	    a[i] = i + 1;
		b[i] = i + 2;
		printf("a,b = %d,%d\n",a[i],b[i]);
	}

	uint64 *aa = (uint64 *)a;
	uint64 *bb = (uint64 *)b;

	for(unsigned i = 0; i < 256/(sizeof(uint64)*8); ++i)
	{
	    printf("aa,bb = %d, %d\n",aa[i],bb[i]);
	}


	//测试计算长数据hamming dis结果正确
	printf("ham_dis = %d\n",_m_hamming_dis((const unsigned char *)a,(const unsigned char *)b));
	
	system("pause");
	return 0;
}


© 著作权归作者所有

Lennie002
粉丝 8
博文 121
码字总数 64832
作品 0
大连
私信 提问
Hamming Distance (汉明距离)

原文链接:https://blog.csdn.net/chouisbo/article/details/54906909 Hamming Distance (汉明距离) 1. 汉明距离的定义 在信息理论中,Hamming Distance 表示两个等长字符串在对应位置上不同...

ersaijun
08/31
0
0
有那个大神会求小数的汉明距离吗

想问一下汉明距离怎么求小数之间的呢?下面的代码是求整数之间的汉明距离的,怎么改成小数之间的呢? def hammingDistance(x, y): """ :type x: int :type y: int :rtype: int """ hammingdi......

风署
昨天
20
0
总的海明距离 Total Hamming Distance

问题: The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Now your job is to find the total Hamming distance bet......

叶枫啦啦
2018/01/06
10
0
LeetCode笔记:461. Hamming Distance

问题(Easy): TheHamming distancebetween two integers is the number of positions at which the corresponding bits are different. Given two integersand, calculate the Hamming dis......

Cloudox_
2017/12/22
0
0
【7%】100小时机器学习——K近邻法

K近邻法(K-NN,k-NearestNeighbor) 前言 什么是KNN K-NN是一种简单且最常用的分类算法,可以应用于回归计算。K-NN是无参数学习,这意味它不会对底层数据的分布做出任何假设,它是基于实例并...

JustMe23
2018/11/03
0
0

没有更多内容

加载失败,请刷新页面

加载更多

最简单的获取相机拍照的图片

  import android.content.Intent;import android.graphics.Bitmap;import android.os.Bundle;import android.os.Environment;import android.provider.MediaStore;import andr......

MrLins
29分钟前
4
0
说好不哭!数据可视化深度干货,前端开发下一个涨薪点在这里~

随着互联网在各行各业的影响不断深入,数据规模越来越大,各企业也越来越重视数据的价值。作为一家专业的数据智能公司,个推从消息推送服务起家,经过多年的持续耕耘,积累沉淀了海量数据,在...

个推
30分钟前
7
0
第三方支付-返回与回调注意事项

不管是支付宝,微信,还是其它第三方支付,第四方支付,支付机构服务商只要涉及到钱的交易都要进行如下校验,全部成功了才视为成功订单 1.http请求是否成功 2.校验商户号 3.校验订单号及状态...

Shingfi
33分钟前
4
0
简述Java内存分配和回收策略以及Minor GC 和 Major GC(Full GC)

内存分配: 1. 栈区:栈可分为Java虚拟机和本地方法栈 2. 堆区:堆被所有线程共享,在虚拟机启动时创建,是唯一的目的是存放对象实例,是gc的主要区域。通常可分为两个区块年轻代和年老代。更...

DustinChan
39分钟前
6
0
Excel插入批注:可在批注插入文字、形状、图片

1.批注一直显示:审阅选项卡-------->勾选显示批注选项: 2.插入批注快捷键:Shift+F2 组合键 3.在批注中插入图片:鼠标右键点击批注框的小圆点【重点不可以在批注文本框内点击】----->调出批...

东方墨天
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部