해밍 거리

4-bit binary tesseract for finding Hamming distance. Two example distances: 0100→1001 has distance 3; 0110→1110 has distance 1
分類	文字列 類似性
資料 構造	文字列
最惡 時間複雜度	${\displaystyle O(n)}$
最善 時間複雜度	${\displaystyle O(1)}$
平均 時間複雜度	${\displaystyle O(n)}$
空間複雜度	${\displaystyle O(n)}$

블록 富豪 理論에서, 해밍 거리 (Hamming距離, 英語 : Hamming distance )는 곱集合 위에 定義되는 거리 函數 이다. 大略, 같은 길이의 두 文字列에서, 같은 位置에서 서로 다른 記號들이 몇 個인지를 센다.

正義 [ 編輯 ]

다음이 주어졌다고 하자.

• 集合 ${\displaystyle S}$
• 自然數 ${\displaystyle n}$

그렇다면, 곱集合 ${\displaystyle S^{n}}$ 위에 다음과 같은 거리 函數 를 줄 수 있다.

${\displaystyle \operatorname {d_{H}} (s,t)=|\{i\in \{0,1,\dotsc ,n-1\}\colon s_{i}\neq t_{i}\}|\in \{0,1,\dotsc ,n\}}$

이 거리 函數 를 ${\displaystyle S^{n}}$ 위의 해밍 거리 라고 한다.

萬若 ${\displaystyle (S,+,0)}$가 아벨 軍 (例를 들어, 柔한체 )이라고 할 때, ${\displaystyle s\in S^{n}}$의 해밍 무게 ( 英語 : Hamming weight )는 영벡터와의 해밍 距離이다.

${\displaystyle \operatorname {d_{H}} ({\vec {0}},s)=|\{i\in \{0,1,\dotsc ,n-1\}\colon s_{i}\neq 0\}|\in \{0,1,\dotsc ,n\}}$

예 [ 編輯 ]

• '1011101'과 '1001001'사이의 해밍 거리는 2이다. (1011101, 10 0 1 0 01 )
• '2143896'과 '2233796'사이의 해밍 거리는 3이다. (2143896, 2 2 3 3 7 96)
• "toned"와 "roses"사이의 해밍 거리는 3이다. (toned, r o s e s )

歷史 [ 編輯 ]

리처드 해밍 이 1950年에 해밍 富豪 와 함께 導入하였다. ^[1]

各州 [ 編輯 ]

같이 보기 [ 編輯 ]

• 그레이 富豪
• 유클리드 거리

外部 링크 [ 編輯 ]

• “Hamming distance” . 《Encyclopedia of Mathematics》 (英語). Springer-Verlag. 2001. ISBN   978-1-55608-010-4 .  
• Weisstein, Eric Wolfgang. “Hamming distance” . 《 Wolfram MathWorld 》 (英語). Wolfram Research.  
• 차재복 (2016年 10月 17日). “해밍中, 해밍 무게, 해밍 最小 무게, 最小 해밍 무게, 해밍 거리, 해밍 最小 距離, 最小 해밍 거리” . 《情報通信技術用語解說》.