美文网首页
几种距离的基础研究下——汉明距离

几种距离的基础研究下——汉明距离

作者: 如烟花非花 | 来源:发表于2016-12-15 11:06 被阅读433次

二、汉明距离

简介

汉明距离是以理查德·卫斯里·汉明的名字命名的,汉明在误差检测与校正码的基础性论文中首次引入这个概念

这个所谓的距离,是指两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。

维基百科

中文维基:快戳我

英文维基:英文不好别戳我

基本原理

汉明距离有一个最为鲜明的特点就是它比较的两个字符串必须等长,否则距离不成立。

它的核心原理就是如何通过字符替换(最初应用在通讯中实际上是二进制的0-1替换),能将一个字符串替换成另外一个字符串。

维基百科给定了几个样例。(字符下标0为起始下标)

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

Python实现

python3中已经内置汉明距离函数了,几点说明:

  • zip函数接收两个字符串,并返回一个元组列表。假如str1 = ’abc‘, str2 = ’123‘,则返回[('a', '1'), ('b', '2'), ('c', '3')]。
  • 这只是python内置的函数实现,如果觉得zip效率太低,则可以考虑自己实现。
#!/user/bin/env python  
# -*- coding: utf-8 -*-  
  
def hammingDistance(s1, s2):
    """Return the Hamming distance between equal-length sequences"""
    if len(s1) != len(s2):
        raise ValueError("Undefined for sequences of unequal length")
    return sum(el1 != el2 for el1, el2 in zip(s1, s2))

相关文章

  • 几种距离的基础研究下——汉明距离

    二、汉明距离 简介 汉明距离是以理查德·卫斯里·汉明的名字命名的,汉明在误差检测与校正码的基础性论文中首次引入这个...

  • 几种距离的基础研究上——编辑距离

    一、编辑距离(Levenshtein距离) 简介 这个距离是1965年一个战斗名族叫Levenshtein的一个发...

  • LeetCode 461.汉明距离

    ?博客原文 :《LeetCode 461.汉明距离 - JavaScript》 汉明距离定义:两个整数之间的汉明距...

  • 汉明距离

  • 汉明距离

    两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。 给出两个整数 x 和 y,计算它们之间的汉明...

  • 汉明距离

    指的是两个(相同长度)字符串,你变成我,我变成你,需要换掉多少个字符的总和,即Max(Sum1,Sum2),比如...

  • 汉明距离

    题目来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/hamm...

  • 汉明距离

    https://zhuanlan.zhihu.com/p/94081111pHash简单来说,是通过感知哈希算法对...

  • 汉明距离

    题目: 题目的理解: 将整数转化为二进制,然后再转化为字符串,进行字符串比较,得到不同的位数。 python实现 ...

  • 汉明距离

    两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。 给出两个整数 x 和 y,计算它们之间的汉明...

网友评论

      本文标题:几种距离的基础研究下——汉明距离

      本文链接:https://www.haomeiwen.com/subject/zznwmttx.html