Blog Archives

R的极客理想系列文章，涵盖了R的思想，使用，工具，创新等的一系列要点，以我个人的学习和体验去诠释R的强大。

R语言作为统计学一门语言，一直在小众领域闪耀着光芒。直到大数据的爆发，R语言变成了一门炙手可热的数据分析的利器。随着越来越多的工程背景的人的加入，R语言的社区在迅速扩大成长。现在已不仅仅是统计领域，教育，银行，电商，互联网….都在使用R语言。

要成为有理想的极客，我们不能停留在语法上，要掌握牢固的数学，概率，统计知识，同时还要有创新精神，把R语言发挥到各个领域。让我们一起动起来吧，开始R的极客理想。

关于作者：

• 张丹，分析师/程序员/Quant: R,Java,Nodejs
• blog: http://blog.fens.me
• email: bsspirit@gmail.com

转载请注明出处：
http://blog.fens.me/r-hamming-distance/

前言

在文字处理时，经常会用到编码方式，把文字和数字进行编码转换，从而计算文本的相似性。比如英文，差一个字母，字母的顺序写反了。要实现对文字的模糊匹配，就可以用到汉明距离的思路，计算将一个字符串变换成另外一个字符串所需要替换的字符个数。

目录

1. 汉明距离介绍
2. 算法原理
3. R语言代码实现

1. 汉明距离介绍 Hamming Distance

Hamming Distance汉明距离，是以理查德·卫斯里·汉明的名字命名的。在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。汉明距离的计算思路与莱文斯坦距离算法有类似之处，参考文章R语言莱文斯坦距离算法Levenshtein Distance

汉明距离计算，例如：

• 二进制 1011101 与 1001001 之间的汉明距离是 2。
• 字符串 2143896 与 2233796 之间的汉明距离是 3。
• 字符串 toned 与 roses 之间的汉明距离是 3。

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

2. 算法原理

我们以d（x,y）表示两个数字x,y之间的汉明距离。

• 对于两个等长字符串，可直接进行两个字符串对应位置的不同字符的个数。
• 对于两个数字，可先转为二进制，然后进行异或运算，并统计结果为1的个数。

两个二进制组(00)与(01)的距离是1，(110)和(101)的距离是2。在一个码组集合中，任意两个编码之间汉明距离的最小值称为这个码组的最小汉明距离。最小汉明距离越大，码组越具有抗干扰能力。

例如，2个数字93和73，93的二进制为10001001，73的二进制为10110001，然后进行xor异或运算，结果为10100，对结果统计1的个数，即得到汉明距离为2。

3. R语言实现

3.1 字符串类型

针对字符串的建立汉明距离算法，计算汉明距离。

> haming_string<-function(txt1,txt2){
+   len1<-nchar(txt1)
+   len2<-nchar(txt2)
+   
+   if(len1!=len2){
+     stop(paste("length is not equal"))
+   }
+   
+   n<-0
+   for(i in 1:len1){
+     t1<-substring(txt1,i,i)
+     t2<-substring(txt2,i,i)
+     if(t1!=t2){
+       n<-n+1
+     }
+   }
+   return(n)
+ }

汉明距离测试。

> haming_string("1011101","1101001")
[1] 3
> haming_string("2143896","2233796")
[1] 3
> haming_string("toned","roses")
[1] 3

3.2 数字类型
针对数字的建立汉明距离算法，先转换为二进制，再进行异或计算，计算汉明距离。

> haming_int<-function(num1,num2){
+   b1<-intToBits(num1)
+   b2<-intToBits(num2)
+   x<-xor(b1,b2);x
+   length(which(x==1))
+ }

汉明距离测试。

> haming_int(93,73)
[1] 2
> haming_int(137,177)
[1] 3

本文我们了解汉明距离的原理和实现，后面我们就可以利用汉明距离的特性，对字符串和数字进行相似度的距离计算，从而实现文本的模糊匹配。本文代码：https://github.com/bsspirit/r-string-match/blob/main/hanmming.r

转载请注明出处：
http://blog.fens.me/r-hamming-distance/