Khoảng cách Hamming (Hamming distance)

Định nghĩa

Cho hai chuỗi $s_1$ và $s_2$ có cùng độ dài $n$. Khoảng cách Hamming giữa $s_1$ và $s_2$, ký hiệu là $d(s_1, s_2)$, được tính bằng số vị trí $i$ (với $1 \le i \le n$) sao cho $s_1[i] \ne s_2[i]$. Nói cách khác, khoảng cách Hamming chính là số lượng ký tự khác nhau giữa hai chuỗi.

Ví dụ

Xét hai chuỗi:

• $s_1 = \text{“karolin”}$
• $s_2 = \text{“kathrin”}$

Độ dài của cả hai chuỗi là $n = 7$. Các ký tự khác nhau ở vị trí thứ 4 và thứ 5. Vậy khoảng cách Hamming giữa $s_1$ và $s_2$ là $d(s_1, s_2) = 2$.

Một số ví dụ khác:

• $d(\text{“000”}, \text{“111”}) = 3$
• $d(\text{“2173896”}, \text{“2235796”}) = 2$
• $d(\text{“toned”}, \text{“roses”}) = 3$

Tính chất

Khoảng cách Hamming thỏa mãn các tính chất của một metric (độ đo khoảng cách):

• Không âm: $d(s_1, s_2) \ge 0$ với mọi $s_1$ và $s_2$.
• Đẳng thức: $d(s_1, s_2) = 0$ nếu và chỉ nếu $s_1 = s_2$.
• Đối xứng: $d(s_1, s_2) = d(s_2, s_1)$ với mọi $s_1$ và $s_2$.
• Bất đẳng thức tam giác: $d(s_1, s_3) \le d(s_1, s_2) + d(s_2, s_3)$ với mọi $s_1$, $s_2$ và $s_3$.

Ứng dụng

Khoảng cách Hamming có nhiều ứng dụng trong khoa học máy tính và các lĩnh vực khác:

• Lý thuyết mã hóa: Khoảng cách Hamming được sử dụng để phát hiện và sửa lỗi trong truyền dữ liệu. Mã có khoảng cách Hamming lớn hơn có khả năng phát hiện và sửa lỗi tốt hơn.
• Xử lý tín hiệu số: Đo lường sự tương đồng giữa các tín hiệu.
• Tin sinh học: So sánh các chuỗi DNA hoặc protein.
• Tìm kiếm thông tin: Tìm kiếm các chuỗi gần giống với một chuỗi cho trước.
• Mật mã học: Phân tích độ mạnh của các hàm băm.

Cách tính toán

Việc tính toán khoảng cách Hamming khá đơn giản. Chỉ cần duyệt qua hai chuỗi và đếm số vị trí mà các ký tự tương ứng khác nhau.

Ví dụ code Python:

def hamming_distance(s1, s2):
  if len(s1) != len(s2):
    raise ValueError("Chuỗi phải có cùng độ dài")
  distance = 0
  for i in range(len(s1)):
    if s1[i] != s2[i]:
      distance += 1
  return distance

print(hamming_distance("karolin", "kathrin")) # Output: 2

Khoảng cách Hamming trong không gian Boolean

Khái niệm khoảng cách Hamming có thể được mở rộng cho các vector trong không gian Boolean $n$ chiều. Trong trường hợp này, mỗi vector có $n$ thành phần, mỗi thành phần nhận giá trị 0 hoặc 1. Khoảng cách Hamming giữa hai vector $x = (x_1, x_2, …, x_n)$ và $y = (y_1, y_2, …, y_n)$ được định nghĩa là số thành phần khác nhau giữa chúng.

$d(x, y) = \sum_{i=1}^{n} |x_i – y_i|$

Ví dụ: Khoảng cách Hamming giữa $x = (1, 0, 1, 0)$ và $y = (0, 1, 1, 0)$ là $d(x, y) = |1-0| + |0-1| + |1-1| + |0-0| = 2$.

Mối liên hệ với các khái niệm khác

• Trọng số Hamming (Hamming weight): Trọng số Hamming của một chuỗi là số ký tự khác không trong chuỗi đó. Đối với vector nhị phân, trọng số Hamming chính là số thành phần bằng 1. Khoảng cách Hamming giữa hai vector $x$ và $y$ có thể được tính bằng trọng số Hamming của hiệu của chúng (phép XOR): $d(x, y) = w(x \oplus y)$, trong đó $\oplus$ là phép XOR bitwise.
• Mã khối tuyến tính (Linear block codes): Trong lý thuyết mã hóa, khoảng cách Hamming nhỏ nhất của một mã khối tuyến tính là khoảng cách Hamming nhỏ nhất giữa bất kỳ hai từ mã khác nhau nào. Khoảng cách Hamming nhỏ nhất xác định khả năng phát hiện và sửa lỗi của mã.

Khó khăn và hạn chế

• Khoảng cách Hamming chỉ hữu ích khi so sánh các chuỗi có cùng độ dài. Đối với các chuỗi có độ dài khác nhau, cần sử dụng các phương pháp khác như khoảng cách Levenshtein.
• Khoảng cách Hamming không tính đến ý nghĩa ngữ nghĩa của các ký tự. Ví dụ, trong xử lý ngôn ngữ tự nhiên, việc thay thế một ký tự bằng một ký tự khác có thể có tác động khác nhau đến ý nghĩa của từ.

Phát triển và biến thể

Có nhiều biến thể và mở rộng của khoảng cách Hamming, ví dụ như khoảng cách Hamming có trọng số, khoảng cách Lee, và khoảng cách Manhattan. Các biến thể này được sử dụng trong các ứng dụng cụ thể để giải quyết các hạn chế của khoảng cách Hamming cơ bản.

• MacKay, David J. C. Information Theory, Inference, and Learning Algorithms. Cambridge University Press, 2003.
• Roth, Ron M. Introduction to Coding Theory. Cambridge University Press, 2006.
• Roman, Steven. Coding and Information Theory. Springer-Verlag, 1992.
• Cover, Thomas M., and Joy A. Thomas. Elements of Information Theory. Wiley, 2006.

Câu hỏi và Giải đáp

Làm thế nào để tính khoảng cách Hamming giữa hai chuỗi có độ dài khác nhau?

Trả lời: Khoảng cách Hamming theo định nghĩa chỉ áp dụng cho các chuỗi có cùng độ dài. Đối với chuỗi có độ dài khác nhau, cần sử dụng các thước đo khác như khoảng cách Levenshtein, đo số thao tác chèn, xóa và thay thế cần thiết để biến đổi một chuỗi thành chuỗi kia.

Ngoài lý thuyết mã hóa và tin sinh học, khoảng cách Hamming còn được ứng dụng trong lĩnh vực nào khác?

Trả lời: Khoảng cách Hamming còn được sử dụng trong xử lý tín hiệu số (đo sự tương đồng giữa các tín hiệu), tìm kiếm thông tin (tìm kiếm gần đúng), mật mã học (phân tích độ mạnh của hàm băm), nhận dạng mẫu, và học máy.

Khoảng cách Hamming có liên quan gì đến khái niệm “hình cầu” trong không gian vector?

Trả lời: Trong không gian Boolean $n$ chiều, tập hợp tất cả các vector có khoảng cách Hamming $r$ so với một vector trung tâm $x$ được gọi là hình cầu Hamming bán kính $r$ tâm $x$. Hình cầu này bao gồm tất cả các vector có thể nhận được từ $x$ bằng cách thay đổi tối đa $r$ bit.

Giả sử ta có một mã khối với khoảng cách Hamming nhỏ nhất là $d$. Mã này có thể phát hiện và sửa được bao nhiêu lỗi?

Trả lời: Mã này có thể phát hiện được tối đa $d-1$ lỗi và sửa được tối đa $lfloor \frac{d-1}{2} rfloor$ lỗi. Ví dụ, một mã có $d=3$ có thể phát hiện 2 lỗi và sửa 1 lỗi.

Có những hạn chế nào khi sử dụng khoảng cách Hamming?

Trả lời: Một hạn chế chính của khoảng cách Hamming là nó chỉ xem xét số lượng ký tự khác nhau mà không quan tâm đến vị trí hay ý nghĩa của sự khác biệt đó. Trong một số trường hợp, việc thay đổi một ký tự ở vị trí quan trọng có thể ảnh hưởng lớn hơn so với việc thay đổi nhiều ký tự ở vị trí ít quan trọng hơn. Hơn nữa, như đã đề cập, khoảng cách Hamming chỉ áp dụng cho các chuỗi có cùng độ dài.