해밍 거리 문서 원본 보기

{{위키데이터 속성 추적}}
{{Infobox algorithm
|name           = 해밍 거리
|class          = [[스트링 메트릭|문자열 유사성]]
|image          = {{image array
| perrow = 2
| width = 150
| image1 = Hamming distance 4 bit binary.svg
| alt1 = 4-bit binary tesseract
| caption1 = 4-bit binary [[tesseract]] for finding Hamming distance.
| image2 =Hamming distance 4 bit binary example.svg
| alt2 = 4-bit binary tesseract Hamming distance examples
| caption2 = Two example distances: {{font color|red|0100→1001}} has distance 3; {{font color|blue|0110→1110}} has distance 1
}}
|caption        =
|data           = [[문자열]]
|time           = <math>O(n)</math>
|best-time      = <math>O(1)</math>
|average-time   = <math>O(n)</math>
|space          = <math>O(n)</math>
}}
[[블록 부호]] 이론에서, '''해밍 거리'''(Hamming距離, {{llang|en|Hamming distance}})는 곱집합 위에 정의되는 [[거리 함수]]이다. 대략, 같은 길이의 두 문자열에서, 같은 위치에서 서로 다른 기호들이 몇 개인지를 센다.

== 정의 ==
다음이 주어졌다고 하자.
* [[집합]] <math>S</math>
* [[자연수]] <math>n</math>
그렇다면, [[곱집합]] <math>S^n</math> 위에 다음과 같은 [[거리 함수]]를 줄 수 있다.
:<math>\operatorname{d_H}(s,t)=|\{i\in\{0,1,\dotsc,n-1\}\colon s_i\neq t_i\}|\in\{0,1,\dotsc,n\}</math>
이 [[거리 함수]]를 <math>S^n</math> 위의 '''해밍 거리'''라고 한다.

만약 <math>(S,+,0)</math>가 [[아벨 군]](예를 들어, [[유한체]])이라고 할 때, <math>s\in S^n</math>의 '''해밍 무게'''({{llang|en|Hamming weight}})는 영벡터와의 해밍 거리이다.
:<math>\operatorname{d_H}(\vec 0,s)=|\{i\in\{0,1,\dotsc,n-1\}\colon s_i\ne0\}|\in\{0,1,\dotsc,n\}</math>

== 예 ==
* '1011101'과 '1001001'사이의 해밍 거리는 2이다. (1011101, 10<span style="color:red;">0</span>1<span style="color:red;">0</span>01''')
* '2143896'과 '2233796'사이의 해밍 거리는 3이다. (2143896, 2<span style="color:red;">2</span><span style="color:red;">3</span>3<span style="color:red;">7</span>96)
* "toned"와 "roses"사이의 해밍 거리는 3이다. (toned, <span style="color:red;">r</span>o<span style="color:red;">s</span>e<span style="color:red;">s</span>)

== 역사 ==
[[리처드 해밍]]이 1950년에 [[해밍 부호]]와 함께 도입하였다.<ref>{{저널 인용|제목=Error detecting and error correcting codes|이름=Richard W.|성=Hamming|저자링크=리처드 해밍|doi=10.1002/j.1538-7305.1950.tb00463.x|날짜=1950-04|저널=Bell Labs Technical Journal|권=29|호=2|쪽=147–160|issn=1089-7089|언어=en}}</ref>

== 각주 ==
{{각주}}

== 같이 보기 ==
* [[그레이 부호]]
* [[유클리드 거리]]

== 외부 링크 ==
* {{eom|title=Hamming distance}}
* {{매스월드|id=HammingDistance|title=Hamming distance}}
* {{웹 인용|url=http://www.ktword.co.kr/abbr_view.php?m_temp1=3937|제목=해밍중, 해밍 무게, 해밍 최소 무게, 최소 해밍 무게, 해밍 거리, 해밍 최소 거리, 최소 해밍 거리|웹사이트=정보통신기술용어해설|저자=차재복|날짜=2016-10-17|언어=ko}}

{{문자열}}
{{전거 통제}}

[[분류:계량기하학]]
[[분류:부호 이론]]
[[분류:정육면체]]
[[분류:문자열 유사도]]