文档章节

用C语言实现计算两个字符串的汉明距离

z
 zhongdecai
发布于 2014/04/16 21:13
字数 481
阅读 1227
收藏 2


发表时间: 2013年1月17日 | 作者: 陈杰斌 | 所属分类: C语言 | 评论: 0 | 浏览: 1376

在庞果网上看到计算两个字符串的汉明距离问题,要求用java实现。自己不熟悉java,就想着用c尝试下。汉明距离就是两个等长字符串对应位置的不同字符的个数。例如:

  • “toned”和”roses”的汉明距离是3。

  • 1011101和1001001的汉明距离是2。

  • 2173896和2233796的汉明距离是3。

c语言的实现代码:

1 int hamdist(char *a, char *b)
2 {
3     int dist = 0;
4
5     while (*a && *b) {
6         dist += (*a != *b) ? 1 : 0;
7         *a++;
8         *b++;
9     }
10
11     return dist;
12 }

这里没有考虑两个字符串长度不一致的情况,如果长度不一致则涉及到编辑距离,关于编辑距离维基百科上有相关说明,这里就不介绍了。该方法的执行时间由字符串长度决定,时间复杂度是O(n)。用两个字符串来测试一下:

1 #include <stdio.h>
2
3 int main()
4 {
5     char *a, *b;
6     a = "00001001000001110000000000100001";
7     b = "00101000000101110000010000100001";
8
9     int dist = hamdist(a, b);
10     //输出4
11     printf("%d\n", dist);
12
13     return 0;
14 }

另外如果要计算两个整数的二进制的汉明距离,可以使用如下方法,效率更高。

查看源代码打印帮助

1 int hamdist(int a, int b)
2 {
3     int dist = 0, val = a ^ b;
4     printf("%d\n", val);
5     while (val) {
6         ++dist;
7         val &= val - 1;
8     }
9
10     return dist;
11 }

这边while循环的次数其实就是汉明距离。

小结

汉明距离是以理查德·卫斯里·汉明的名字命名的,有兴趣的朋友可以了解下这位先辈。除了汉明距离,还有汉明重量、汉明码等理论在信息论、编码理论、密码学等领域都有应用。


本文转载自:

z
粉丝 1
博文 14
码字总数 2137
作品 0
广州
私信 提问
机器学习中的度量——字符串距离

机器学习是时下流行AI技术中一个很重要的方向,无论是有监督学习还是无监督学习都使用各种“度量”来得到不同样本数据的差异度或者不同样本数据的相似度。良好的“度量”可以显著提高算法的分...

Kalafinaian
06/08
0
0
文本相似度十大方法简要说明

1、余弦相似性 余弦(余弦函数),三角函数的一种。在Rt△ABC(直角三角形)中,∠C=90°,角A的余弦是它的邻边比三角形的斜边,即cosA=b/c,也可写为cosA=AC/AB。余弦函数:f(x)=cosx(x...

u012654154
2017/04/21
0
0
机器学习——几种距离度量方法比较

欧氏距离(Euclidean Distance) 欧氏距离是最容易直观理解的距离度量方法,我们小学、初中和高中接触到的两个点在空间中的距离一般都是指欧氏距离。 二维平面上点a(x1,y1)与b(x2,y2)间的欧氏距...

牧师-Panda
2016/11/14
29.2K
2
利用word分词来计算文本相似度

word分词提供了多种文本相似度计算方式: 方式一:余弦相似度,通过计算两个向量的夹角余弦值来评估他们的相似度 实现类:org.apdplat.word.analysis.CosineTextSimilarity 用法如下: Stri...

杨尚川
2015/05/20
7.1K
29
LeetCode算法题-Hamming Distance(Java实现)

这是悦乐书的第237次更新,第250篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第104题(顺位题号是461)。两个整数之间的汉明距离是相应位不同的位置数。给定两个整数x和y,...

小川94
01/21
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周六乱弹 —— 早上儿子问我他是怎么来的

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @凉小生 :#今日歌曲推荐# 少点戾气,愿你和这个世界温柔以待。中岛美嘉的单曲《僕が死のうと思ったのは (曾经我也想过一了百了)》 《僕が死の...

小小编辑
今天
1K
14
Excption与Error包结构,OOM 你遇到过哪些情况,SOF 你遇到过哪些情况

Throwable 是 Java 中所有错误与异常的超类,Throwable 包含两个子类,Error 与 Exception 。用于指示发生了异常情况。 Java 抛出的 Throwable 可以分成三种类型。 被检查异常(checked Exc...

Garphy
今天
38
0
计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
昨天
40
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
昨天
61
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
昨天
20
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部