Kho?ng cach Hamming
Trong
ly thuy?t thong tin
,
Kho?ng cach Hamming
(
ti?ng Anh
: Hamming distance
) gi?a hai
xau
(
strings
) co
chi?u dai
b?ng nhau la s? cac ky hi?u ? v? tri t??ng đ??ng co gia tr? khac nhau. Noi m?t cach khac, kho?ng cach Hamming đo s? l??ng
thay th?
c?n ph?i co đ? đ?i gia tr? c?a m?t day ky t? sang m?t day ky t? khac, hay s? l??ng
l?i
x?y ra bi?n đ?i m?t day ky t? sang m?t day ky t? khac.
L?y vi d?:
- Kho?ng cach Hamming gi?a
10
1
1
1
01
va
10
0
1
0
01
la 2.
- Kho?ng cach Hamming gi?a
2
14
3
8
96
va
2
23
3
7
96
la 3.
- Kho?ng cach Hamming gi?a "
t
o
n
e
d
" va "
r
o
s
e
s
" la 3.
Tr?ng s? Hamming
(
Hamming weight
) c?a m?t day ky t? la kho?ng cach Hamming t? m?t day ky t? toan s? khong co cung
chi?u dai
. Co ngh?a la s? ph?n t? trong day ky t? khong co gia tr? khong (0): đ?i v?i m?t
day ky t? nh? phan
(
binary string
), no ch? la s? cac ky t? co gia tr? m?t (1), l?y vi d? tr?ng s? Hamming c?a day ky t?
11101
la 4.
đ?i v?i m?t
chi?u dai
c? đ?nh "n", kho?ng cach Hamming la
đ? đo
tren khong gian vect? c?a cac t? co
chi?u dai
đo, vi no th?a man yeu c?u v? tinh ch?t s? khong am (
non-negativity
) (
s? tuy?t đ?i
), hi?n than c?a
tinh b?t kh? phan đ?nh
(
indiscernibles
) va
tinh đ?i x?ng
(
symmetry
), va no co th? đ??c ch?ng minh m?t cach d? dang b?ng
phep quy n?p toan ph?n
(
complete induction
) r?ng no con th?a man
b?t đ?ng th?c tam giac
(
triangle inequality
).
Kho?ng cach Hamming gi?a hai t?
a
va
b
con đ??c g?i la
tr?ng s? Hamming
(
Hamming weight
) c?a phep toan
a
?
b
, dung m?t
toan t?
thich h?p thay th? cho
toan t?
"?".
đ?i v?i hai
day ky t? nh? phan
(
binary strings
)
a
va
b
, phep toan nay t??ng đ??ng v?i phep toan
a
XOR
b
. Kho?ng cach Hamming c?a cac day ky t? nh? phan con t??ng đ??ng v?i
kho?ng cach Manhattan
(
Manhattan distance
) gi?a hai giao đi?m c?a m?t hinh
sieu l?p ph??ng n-chi?u
(
n-dimensional hypercube
), trong đo
n
la
chi?u dai
c?a cac t?.
Kho?ng cach Hamming la cai ten đ??c đ?t theo ten c?a
Richard Hamming
, ng??i gi?i thi?u ly thuy?t nay trong tai li?u co tinh c? s? c?a ong v?
ma phat hi?n l?i va s?a l?i
(
error-detecting and error-correcting codes
). No đ??c s? d?ng trong k? thu?t
vi?n thong
đ? tinh s? l??ng cac bit trong m?t t? nh? phan (
binary word
) b? đ?i ng??c, nh? m?t hinh th?c đ? ??c tinh s? l?i x?y ra trong qua trinh truy?n thong, va vi th?, đoi khi, no con đ??c g?i la
kho?ng cach tin hi?u
(
signal distance
). Vi?c phan tich tr?ng s? Hamming c?a cac bit con đ??c s? d?ng trong m?t s? nganh, bao g?m
ly thuy?t tin h?c
,
ly thuy?t ma hoa
, va
m?t ma h?c
. Tuy v?y, khi so sanh cac day ky t? co
chi?u dai
khac nhau, hay cac day ky t? co xu h??ng khong ch? b? thay th? khong thoi, ma con b? ?nh h??ng b?i d? li?u b? l?ng them vao, ho?c b? xoa đi, ph??ng phap đo l??ng ph?c t?p h?n, nh?
kho?ng cach Levenshtein
(
Levenshtein distance
) la m?t ph??ng phap co tac d?ng va thich h?p h?n.
Ph?ng theo m?t ph?n t?
Federal Standard 1037C
.
Richard W. Hamming
. Error-detecting and
error-correcting codes
, Bell System Technical Journal 29(2):147-160,
1950
.