漢明距離

在資訊理論中，兩個等長字符串之間的漢明距離（英語：Hamming distance）是兩個字符串對應位置的不同字符的個數。換句話說，它就是將一個字符串變換成另外一個字符串所需要替換的字符個數。

漢明重量是字符串相對於同樣長度的零字符串的漢明距離，也就是說，它是字符串中非零的元素個數：對於二進制字符串來說，就是1的個數，所以11101的漢明重量是4。

範例

例如：

• 1011101與1001001之間的漢明距離是2。
• 2143896與2233796之間的漢明距離是3。
• "toned"與"roses"之間的漢明距離是3。

特性

對於固定的長度n，漢明距離是該長度字符向量空間上的度量，很顯然它滿足非負、唯一及對稱性，並且可以很容易地通過完全歸納法證明它滿足三角不等式。

兩個字a與b之間的漢明距離也可以看作是特定運算−的a−b的漢明重量。

對於二進制字符串a與b來說，它等於a 異或b以後所得二進制字符串中「1」的個數。另外二進制字符串的漢明距離也等於n維超正方體兩個頂點之間的曼哈頓距離，其中n是兩個字串的長度。

歷史及應用

漢明距離是以理察·衛斯里·漢明的名字命名的，漢明在誤差檢測與校正碼的基礎性論文中首次引入這個概念。在通信中累計定長二進制字中發生翻轉的錯誤數據位，所以它也被稱為信號距離。漢明重量分析在包括資訊理論、編碼理論、密碼學等領域都有應用。但是，如果要比較兩個不同長度的字符串，不僅要進行替換，而且要進行插入與刪除的運算，在這種場合下，通常使用更加複雜的編輯距離等算法。

參考文獻

部分摘自Federal Standard 1037C.

理察·衛斯里·漢明，誤差檢測與糾錯碼（Error-detecting and error-correcting codes）, Bell System Technical Journal 29 (2):147-160, 1950.

參見

• 漢明重量
• 傑卡德指數
• 編輯距離，一般化的漢明距離
• 相似
• 數值分類學中的相似空間