漢明距離
来自维基百科，自由的百科全书
在資訊理論中，兩個等長字符串之間的漢明距離（英語：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.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
