跳至內容

漢明距離

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

信息論中,兩個等長字符串之間的漢明距離(英語:Hamming distance)是兩個字符串對應位置的不同字符的個數。換句話說,它就是將一個字符串變換成另外一個字符串所需要替換的字符個數。

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

範例

例如:

  • 10111011001001之間的漢明距離是2。
  • 21438962233796之間的漢明距離是3。
  • "toned"與"roses"之間的漢明距離是3。

特性

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

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

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

歷史及應用

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

參考文獻

部分摘自Federal Standard 1037C.

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

參見