相似度计算之汉明距离

2 sec read

汉明距离是以理查德·卫斯里·汉明的名字命名的,汉明在误差检测与校正码的基础性论文中首次引入这个概念这个所谓的距离,是指两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。

汉明距离有一个最为鲜明的特点就是它比较的两个字符串必须等长,否则距离不成立。它的核心原理就是如何通过字符替换(最初应用在通讯中实际上是二进制的0-1替换),能将一个字符串替换成另外一个字符串。维基百科给定了几个样例。(字符下标0为起始下标)

  • “karolin” 和 “kathrin” 的汉明距离为(字符2 3 4替换)
  • “karolin” 和 “kerstin” 的汉明距离为(字符1 3 4替换)
  • 1011101 和 1001001 的汉明距离为(字符2 4替换)
  • 2173896 和 2233796 的汉明距离为(字符1 2 4替换)

Python实现:

汉明距离主要应用在通信编码领域上,用于制定可纠错的编码体系。在机器学习领域中,汉明距离也常常被用于作为一种距离的度量方式。在LSH算法汉明距离也有重要的应用。

与汉明距离比较相近的是编辑距离,具体请查看:使用Python计算文本相似性之编辑距离

打赏作者
微信支付标点符 wechat qrcode
支付宝标点符 alipay qrcode

K-近邻算法KNN学习笔记

什么是K-近邻算法? K近邻法(k-nearest neighbor, k-NN)是1967年由Cover T
2 min read

使用Prophet进行时间序列预测

Prophet是Facebook开源的预测工具,相比ARIMA模型,Prophet真的是非常的简单。只要读入两
1 min read

采用时间序列预测股价变化

时间序列简介 在数学上,随机过程被定义为一族时间随机变量,即{x(t),t∈T},其中T表示时间t的变动范围。
5 min read

发表评论

电子邮件地址不会被公开。 必填项已用*标注