二颓哮、漢明距離
簡介
漢明距離是以理查德·衛(wèi)斯里·漢明的名字命名的愿吹,漢明在誤差檢測與校正碼的基礎(chǔ)性論文中首次引入這個概念
這個所謂的距離,是指兩個等長字符串之間的漢明距離是兩個字符串對應(yīng)位置的不同字符的個數(shù)。
維基百科
基本原理
漢明距離有一個最為鮮明的特點就是它比較的兩個字符串必須等長炫加,否則距離不成立瑰煎。
它的核心原理就是如何通過字符替換(最初應(yīng)用在通訊中實際上是二進制的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實現(xiàn)
python3中已經(jīng)內(nèi)置漢明距離函數(shù)了,幾點說明:
- zip函數(shù)接收兩個字符串赋铝,并返回一個元組列表插勤。假如str1 = ’abc‘, str2 = ’123‘革骨,則返回[('a', '1'), ('b', '2'), ('c', '3')]饮六。
- 這只是python內(nèi)置的函數(shù)實現(xiàn),如果覺得zip效率太低苛蒲,則可以考慮自己實現(xiàn)卤橄。
#!/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))