해밍 거리

해밍 거리
4-bit binary tesseract 4-bit binary tesseract for finding Hamming distance.	섬네일을 만드는 중 오류 발생: Two example distances: 0100→1001 has distance 3; 0110→1110 has distance 1
분류	문자열 유사성
자료 구조	문자열
최악 시간복잡도	O(n)
최선 시간복잡도	O(1)
평균 시간복잡도	O(n)
공간복잡도	O(n)

블록 부호 이론에서, 해밍 거리(Hamming距離, 영어: Hamming distance)는 곱집합 위에 정의되는 거리 함수이다. 대략, 같은 길이의 두 문자열에서, 같은 위치에서 서로 다른 기호들이 몇 개인지를 센다.

정의

다음이 주어졌다고 하자.

그렇다면, 곱집합 $S^{n}$ 위에 다음과 같은 거리 함수를 줄 수 있다.

d_{H} (s, t) = | {i \in {0, 1, \dots, n - 1} : s_{i} \neq t_{i}} | \in {0, 1, \dots, n}

이 거리 함수를 $S^{n}$ 위의 해밍 거리라고 한다.

만약 $(S, +, 0)$ 가 아벨 군(예를 들어, 유한체)이라고 할 때, $s \in S^{n}$ 의 해밍 무게(영어: Hamming weight)는 영벡터와의 해밍 거리이다.

d_{H} (\vec{0}, s) = | {i \in {0, 1, \dots, n - 1} : s_{i} \neq 0} | \in {0, 1, \dots, n}

리처드 해밍이 1950년에 해밍 부호와 함께 도입하였다.^[1]

↑ Hamming, Richard W. (1950년 4월). “Error detecting and error correcting codes” (영어). 《Bell Labs Technical Journal》 29 (2): 147–160. doi:10.1002/j.1538-7305.1950.tb00463.x. ISSN 1089-7089.

모듈:Authority_control 159번째 줄에서 Lua 오류: attempt to index field 'wikibase' (a nil value).

v t e 문자열
스트링 메트릭	해밍 거리 리 거리
문자열 검색 알고리즘	보어-무어 문자열 검색 알고리즘 커누스-모리스-프랫 알고리즘 라빈-카프 알고리즘
다중 문자열 검색	아호 코라식 코멘츠-월터 알고리즘
정규 표현식	정규 문법 비결정론적 유한 상태 기계
서열 정렬	스미스-워터맨 알고리즘
자료 구조	접미사 배열 접미사 트리 로프 트라이
기타	구문 분석 패턴 매칭 압축 패턴 매칭 최장 공통 부분 수열 최장 공통 부분 문자열